杂题

发表于 | 分类于 |

以前在cf做的一些题目

1628A-Meximum Array

给定长度为n的数列A，设Mex[l,r]为除去a[l]~a[r]的最小自然数，如{1,2,3}mex为0，{2,3,0,1}mex为4，先在选定k，将Mex[1,k]存到b数列的末尾后，截去A的前k项直至A为空，现求字典序最大的b数列（n≤1e5)

错解：暴力模拟，求每位数字的mex，后选定mex最大、最靠前的数字（易知mex递增），将mex存入b，再次求每位数字的mex，直至a为空，复杂度为n的三次方

正解：首先录入数列时，记录每种数字出现的次数，之后遍历A数列求最大、最靠前的mex，假设当前mex为x，则后续数组中不存在x+1时，mex最大。如何保证最前？在更新x的位置停下，即当前位置：能否更新—更新到最大值，检查能否继续更新，不能就停下得到k，—不能更新，继续。综上，如何保证将来得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
using ll = long long;
ll T;
ll n;
ll a[200005];
bool vis[200005];
ll cnt[200005];
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> n;
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    for(ll i=1;i<=n;i++)
    {
      cin >> a[i];
      cnt[a[i]]++;
    }
    ll tmp = -1;
    ll ans = 0;
    vector<ll> b;
    for(ll i=1;i<=n;i++)
    {
      vis[a[i]] = 1;
      cnt[a[i]]--;//a[i]不干预后续是否能更新
      while(vis[tmp+1])
      {
        tmp++;
      }
      if(!cnt[tmp+1])
      {
        b.push_back(tmp+1);
        ans++;
        memset(vis, 0, sizeof(vis));
        tmp = -1;
      }
    }
    cout << ans << '\n';
    for(auto i:b)
    {
      cout << i << ' ';
    }
    cout << '\n';
  }  
}

1629B-GCD Arrays

题面：给定[l,r]之间的数列（如[1,4]={1,2,3,4}),对其进行操作如下：选定两个数，将两个数从数列中抹去，将其乘积加入数列，求最少几次操作能使数列公共gcd>1（l,r<1e9)

正解：思考，将数字用质数的乘积表示，则公共gcd表示所有的数都有共同的质数，而每一次操作本质上是消除1个没有共同质数的数，故最小次数k=数列总数n-所含质数相同的子数列m（m为最大），问题—如何找到一个质数使m最大？—结论：区间连续，则质数2分布最广

注意：找偶数个数时不要用遍历，1e9会超时，直接用首位数字算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
using ll = long long;
ll T;
ll n;
ll k;
ll l;
ll r;
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> l >> r >> k;
    ll tmp = 0;
    if (l % 2)
    {
      tmp = (r - l) / 2 + (r + 1) % 2;
    }else
    {
      tmp = (r - l) / 2+1;
    }
    if (r - l + 1 - tmp <= k || (l == r && l > 1))
    {
      cout << "YES\n";
    }
    else
    {
      cout << "NO\n";
    }
  }
}

1622C-Set or Decrease题面：给定长度为n的数列，给定k，求最少对数列进行多少次操作可使数列总和小于等于k，操作有两种：1.选定1个数使其减1 2.选定两个数，使后者大小与前者相同

正解：易知，若操作数最小，则必是先让最小数-1x次，再从大到小施加2操作（1只能减少1，2能减少大于等于1，且先减效果更好）

锁定最小数，如何算出x？算出x后，如何算出y？易知，x大了，y会小，x小了，y会大，而我们要求的是x+y的最小值。

可以列出关于x与y的不等式，之后列举范围较小的1个数，得到x+y的许多结果，取最小值—将问题转化为简单的数学式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
#include<functional>
using namespace std;
using ll = long long;
ll T;
ll n;
ll k;
ll a[200005];
ll sum[200005];
ll x;
ll tmp;
ll ans;
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> n >> k;
    ans = 0x7fffffff;
    for (ll i = 1; i <= n; i++)
    {
      cin >> a[i];
    }
    sort(a+1, a + n+1);
    sum[0] = 0;
    for(ll i=1;i<=n;i++)
    {
      sum[i] = sum[i - 1] + a[i];
    }
    if(sum[n]<=k)
    {
      cout << 0 << '\n';
    }else
    {
      for(ll y=0;y<=n-1;y++)
      {
        x =  (1.0*sum[n - y] - a[1] - k) / (y + 1)+0.9999+ a[1];//0.9999用来向上取整(PS:最好用y替代），注意转成double运算
        x = max((ll)0, x);//当x为负数时，即不需要-1操作，取x为0
        ans = min(x + y, ans);
      }
      cout << ans << '\n';
    }
    
  }
}
//(a[1]-x)*(y+1)+sum[n-y]-a[1]<=k

1624C-Division by two and permutation

题面：给定数列，对其任意的数进行操作，求若干次操作后，能否将该数列变为排列

正解:将数列从小到大排列，依次div，并标记used[得到的数]=1,若div到0都得不到used[当前的数]=0,则撞车，不可能形成全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
using ll = long long;
ll T;
ll n;
ll k;
bool flag;
ll a[55];
bool used[55];
int main()
{
  cin >> T;
  while (T--)
  {
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
      used[i] = 0;
      cin >> a[i];
    }
    bool flag = 1;
    sort(a + 1, a + 1 + n);
    for (ll i = 1; i <= n; i++)
    {
      while(a[i]>n||(a[i]>0&&used[a[i]]==1))
      {
        a[i] /= 2;
      }
      if(a[i]>0)
      {
        used[a[i]] = 1;
      }else
      {
        flag = 0;
        break;
      }
    }
    if (flag)
    {
      cout << "YES\n";
    }
    else
    {
      cout << "NO\n";
    }
    
  }
  return 0;
}

但为什么小的数一定比大的数有优先选择权？—若1个数不能div（如1），先将其放入，然后考虑能div的数（如2、3），此时也只能为本身，故放入，依次类推，要从小到大排

1606A-AB Balance

题面：给定只含a、b的字符串，可将a变b，将b变a，求最少需要多少步操作能使字符串中”ab”子串数与”ba”子串数相同

结论：若s1==sn，则子串个数相同，若s1≠sn，则子串个数不相同，且只需1不就能使其相同

论证：当s所含字母都相同时，显然成立，若s所含字母不相同，首位字母相同、中间字母也相同（如abbba）时，显然成立。

若首尾字母相同，但中间字母不同（如abbabba），显然能找到至少1个字母与首位字母都相同，该字母将字符串分割成两个子串，且子串的首尾字母相同（1个子串的尾是另一个子串的首，不影响ab、ba个数）故不断递归可至中间字母相同的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
using ll = long long;
ll T;
ll n;
ll k;
string s;
int main()
{
  cin >> T;
  while (T--)
  {
    s.clear();
    cin >> s;
    if (*(s.begin()) == *(s.rbegin()))
    {
      cout << s << '\n';
    }
    else
    {
      *(s.begin()) = *(s.rbegin());
      cout << s << '\n';
    }
  }
  return 0;
}

1606B-Update Files

题面：较简单，不提了，注意最后是算两个大整数的商并向上取整（a/b向上取整—a+b-1/b)