CF276 - LeAf146

1
signed main(){
2
    int n,k;cin>>n>>k;
3
    int maxx=-0x7fffffff;
4
    for(int i=0;i<n;i++){
5
        int f,t;cin>>f>>t;
6
        if(t>k)maxx=max(maxx,f-(t-k));
7
        else maxx=max(maxx,f);
8
    }
9
    cout<<maxx<<endl;
10
    return 0;
11
}

B. Little Girl and Game #

由于每次行动前都可以重新排列，所以一开始的输入顺序没有意义，只需要计算各个字母的个数。

对于初始输入即可构成回文串，即最多有一个字母的个数为奇数，则 First 胜利。若有多于一个字母的个数为奇数，则可以得到最终状态：只有一个字母的个数为奇数。

先考虑有偶数个的字母，对这样的字母操作没有意义：若 A 操作后，B 可以通过再次操作该字母还原为 A 操作之前的状态。则初始状态等价于长度为 $k$ 的字符串，且字符串中的每个字母仅出现一次，这些字母都是原本有奇数个的字母。此时，双方只能轮流删除一个字母，直到最终结束，即 k%2==1 时 First 胜利，反之 Second 胜利。

1
signed main(){
2
    string s;cin>>s;
3
    vector<int> cnt(26);
4
    for(int i=0;i<s.size();i++){
5
        cnt[s[i]-'a']++;
6
    }
7
    int odd=0;
8
    for(int i=0;i<26;i++){
9
        if(cnt[i]%2)odd++;
10
    }
11
    if(odd%2||odd==0)cout<<"First\n";
12
    else cout<<"Second\n";
13
    return 0;
14
}

C. Little Girl and Maximum Sum #

更改数组排列，使得多次区间和的和结果最大。

考虑不同位置的贡献，将最大的数放到贡献最多的位置。

每次求区间和对整个的贡献为 $1$ ，使用差分可以将每次操作的花费从 $O(length)$ 降低到 $O(1)$ ，总花费从 $O(\sum(length))$ 变为 $O(n)$ ，这在操作长度之和大于数组长度和时是更优的。

由于仅输出结果，所以只需要记录所有位置贡献的次数而不需要记录具体位置，将贡献次数排序和原数组排序后相乘求和即得答案。

1
signed main(){
2
    int n,q;cin>>n>>q;
3
    vector<int> a(n);for(int i=0;i<n;i++)cin>>a[i];
4
    vector<int> diff(n);
5
    for(int i=0;i<q;i++){
6
        int l,r;cin>>l>>r;
7
        l--,r--;
8
        diff[l]++;
9
        if(r<n-1)diff[r+1]--;
10
    }
11
    vector<int> b(n);
12
    b[0]=diff[0];
13
    for(int i=1;i<n;i++)b[i]=b[i-1]+diff[i];
14
    sort(b.rbegin(),b.rend());
15
    sort(a.rbegin(),a.rend());
16
    int ans=0;
17
    for(int i=0;i<n;i++){
18
        ans+=a[i]*b[i];
19
    }
20
    cout<<ans<<endl;
21
    return 0;
22
}

D. Little Girl and Maximum XOR #

考虑二进制。

先找到 r 的最高位，这也是答案的最高位。之后从这一位开始向后检查，在二进制情况下，当 l 的位数少于 r 时，在 l 的前面加前导 0，和 r 的位数补齐。若 r 和 l 的前 k 位均相等，则前 k 位异或结果一定是零，直到第一个不相同的位置开始，后面都可以通过异或取 1，最终得到答案。

1
signed main(){
2
    int l,r;cin>>l>>r;
3
    int bit=63;
4
    if(l==r){cout<<0<<endl;return 0;}
5
    while((r>>bit)==0)bit--;
6
    while((r>>bit)==(l>>bit))bit--;
7
    cout<<((2LL<<bit)-1)<<endl;
8
    return 0;
9
}