Codeforces Round #796 (Div. 2) vp报告A-D

E题vp后看了眼应该很好做，马上就补

谨记交互题让我痛失ccpc生涯。
Codeforces Round #796 (Div. 2)

vp体验糟糕，40min突然腹痛难忍解决之后回来都60min了（没准正好差出了E的时间）

A
题意：给个正整数x找另一个最小的正整数y来满足 x&y>0且x^y>0

思路：二进制水题，特判1，统计x二进制最低位的1代表的数值，如果最低位就是最高位则要在此基础上加1

#include 

using namespace std;
#define int long long
int bit[70];
signed main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        if(n==1)
        {
            cout<<3<<endl;
            continue;
        }
        int cnt=0;
        while(n)
        {
            if(n&1)
            bit[++cnt]=1;
            else
            bit[++cnt]=0;
            n>>=1;
        }
        int pos=0;
        for(int i=1;i<=cnt;i++)
        {
            if(bit[i]==1)
            {
                pos=i;
                break;
            }
        }
        if(pos==cnt)
        {
            cout<<(1<<(pos-1))+1<<endl;
        }
        else
        {
            cout<<(1<<(pos-1))<<endl;
        }
        memset(bit,0,sizeof(bit));
    }
    return 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

B

给定一个数组，每次可以选择一个偶数除二或者选择两个数变为两数之和，问多少次之后数组整体都变成奇数

思路：思维题好题，先把一个数变成奇数然后用这个数累加所有偶数就可以了。

#include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;
int a[N];
int cnt[N];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            while(a[i]%2==0)
            {
                cnt[i]++;
                a[i]/=2;
            }
        }
        sort(cnt+1,cnt+n+1);
        sum=cnt[1];
        for(int i=2;i<=n;i++)
        {
            if(cnt[i])
            {
                sum++;
            }
        }
        cout<<sum<<endl;
        for(int i=1;i<=n;i++)
            cnt[i]=0;
    }
    return 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

C

求一个未知的初始字母ch。

给定2*n个字符串代表着曾经是从这里写字符串里选一个作为“被替换串”，然后再选一个作为“替换串”，来用，每个字符串都被选一次且仅被选一次。

在给定一个字符串s，代表ch经过了这些字符串变换之后的模样

思路：思维题好题，初始的是一个字母作为突破点，细数情况易知，在给出的2*n+1个字符串中，初始字母出现的次数必然是奇数次，其他字母出现的次数必然是偶数次。

PS：这题我想了很多：AC自动机，可持久化KMP，SAM之类的，但是没有一种算法能够在要求的复杂度内实现对一堆未知顺序的字符串操作后的答案。这样我才确定这题应该是个思维题，所以才能想到正解。

#include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;
int cnt[30];
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        string s;
        for(int i=1;i<=n*2+1;i++)
        {
            cin>>s;
            for(int i=0;i<s.length();i++)
            {
                cnt[s[i]-'a']++;
            }
        }
        for(int i=0;i<=25;i++)
        {
            if(cnt[i]&1)
            {
                cout<<(char)('a'+i)<<'\n';
            }
        }
        memset(cnt,0,sizeof(cnt));
    }
    return 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

D

给定一个数组，你初始可以从任意位置开始，每一次操作（向距离为1的位置走去或者停留在原地）之后你会获得所在位置的数值，然后整个数组的所有位置都会加一。

思路：

数据过大非DP可解，思维+贪心结论+公式。

对于k 自增，只要我们是保持移动，获取的自增数值肯定都是最优，推算发现是一个k*(k+1)/2
然后选择一段和最大的区间即可（利用前缀和枚举长度为k的最大子段和）

对于k>=n

自增，无论我们怎么走动，只要每个位置都走过一遍，无法拿走的数值必然是一样的。

所有位置自增的总和是nk（n个位置经过k次操作后的总自增值）
我们在第一个位置坚挺到第n-k次后开始向右走，走到最后发现从第一个位置到最后一个位置我们无法拿走的自增数值是: n n-1 n-2 n-3 … 3 2 1，就是(nn+n)/2

所以用总的减去不能拿走的就好了nk-(nn+n)/2

然后答案在加上整个数组初值的和就可以了。

#include 

using namespace std;
#define int long long
#define endl '\n'
const int N = 2e5+100;
int a[N];
int sum[N];
void init(int n)
{
    for(int i=0;i<=n;i++)
        sum[i]=a[i]=0;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int maxx=-1;
        if(k<n)
        {
            for(int i=1;i+k-1<=n;i++)
            {
                maxx=max(sum[i+k-1]-sum[i-1],maxx);
            }
            k--;
            int add=(k+k*k)/2;
            cout<<maxx+add<<endl;
        }
        else
        {
            int add=n*k;
            add-=n*(n+1)>>1;
            cout<<add+sum[n]<<endl;
        }
    }
    return 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

E题梭哈交互，立马搞