CF969

A

方法

直接每一次选择一个两个奇数和偶数即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int l,r;    cin>>l>>r;
    int num=0;
    for (int i = l; i < r+1; ++i)
    {
        if(i&1) num++;
    }
    cout<<(num)/2<<"\n";
}    
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

B

方法

如果是增加，那么最大数肯定还是原来的那一个。如果是减少，肯定是会比其他没有减少的数大，所以只需要对最大数进行操作即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    int m;  cin>>m;
    std::vector<int> v(n,0);
    for (int i = 0; i < n; ++i)
    {
        cin>>v[i];
    }
    int maxn=0;
    for (int i = 0; i < n; ++i)
    {
        maxn=max(maxn,v[i]);
    }
    for (int i = 0; i < m; ++i)
    {
        char opt;   cin>>opt;
        int l,r;    cin>>l>>r;
        if(l<=maxn && maxn<=r)
        {
            if(opt=='+')    maxn++;
            else    maxn--;
        }
        cout<<maxn<<" \n"[i==n-1];
    }
}    
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

C

方法

a和b可以由他们两者的最大公约数构成。可以通过多次操作使得一个数相对于其他数增加了gcd(a,b)，那么对每个数%gcd(a,b)，然后进行维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    ll a,b; cin>>a>>b;
    ll div=gcd(a,b);
    std::vector<ll> v(n,0);
    for (int i = 0; i < n; ++i)
    {
        cin>>v[i];
    }
    if(div==1)
    {
        cout<<"0\n";
        return;
    }
    set<ll> s;
    for (int i = 0; i < n; ++i)
    {
        s.insert(v[i]%div);
    }
    int m=s.size();
    ll ans=(*s.rbegin())-(*s.begin());
    for (int i = 0; i < m; ++i)
    {
        int cur=*s.begin();
        s.insert(*s.begin()+div);
        s.erase(cur);
        ans=min(ans,(*s.rbegin())-(*s.begin()));
    }
    cout<<ans<<"\n";
}    
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

D

补题，一开始以为是树形dp，不知道怎么搞，看了其他人的方法，惊觉这是一道奇妙的好题。

思路

以最简单的权重为1的“10”串为例，惊奇地发现无论以何种方式在串内部添加0，1，均不会改变该串的权重。

比如：

添加0构成“100000...0”，显然，由于并未创造“01”，故权重不变；

添加1构成“111111...0”，由于所有与0不相邻的1均不参与“10”串的构成，故权重不变；

添加0和1任意排列的字符串构成“1...0101...1110...0”，发现每出现一个“01”串，其中的1必然会与后续0组成“10”，0必然与前序1组成“10”，故权重不变。

得出结论：路径权重仅与根节点、叶子节点有关。从而直接弱化了本题图论的部分。

那么我们就可以统计叶子中0、1和?的个数，然后根据根节点进行分类讨论。

• 根节点为1，那么答案就是ans=cnt0+(cntq+1)/2;，其中cntq为叶子中?的个数。

• 根节点为0，那么答案就是ans=cnt1+(cntq+1)/2。

• 根节点为?，那么肯定就是取max(cnt0,cnt1)+cnt/2，注意这里发生了一次交换先后手顺序，所以是cnt/2。

  另外特殊情况：如果cnt0==cnt1，并且cnt为奇数（cnt为非叶子中?的个数），那么我们可以强行进行一次交换先后手顺序。此时答案就是：

  ans=cnt0+(cntq+1)/2;。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;  
void solve()
{
    int n;  cin>>n;
    std::vector<std::vector<int>> e(n);
    for (int i = 0; i < n-1; ++i)
    {
        int u,v;    cin>>u>>v;
        --u,--v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    string s;   cin>>s;
    int cnt1=0,cnt0=0,cntq=0,cnt=0;
    bool flag=(s[0]!='?');
    for (int i = 1; i < n; ++i)
    {
        if(e[i].size()==1)
        {
            if(s[i]=='1')   cnt1++;
            else if(s[i]=='0')  cnt0++;
            else    cntq++;
        }
        else
        {
            if(s[i]=='?')   cnt++;
        }
    }
    int ans=0;
    if(flag)
    {
        if(s[0]=='0')
        {
            ans=cnt1+(cntq+1)/2;
        }
        else if(s[0]=='1')
        {
            ans=cnt0+(cntq+1)/2;
        }
    }
    else
    {
        ans=max(cnt0,cnt1)+cntq/2;
        if(cnt0==cnt1 && cnt%2)
        {
            ans=cnt0+(cntq+1)/2;
        }
    }
    cout<<ans<<"\n";
}
int main()
{
    int t;  cin>>t;
    for (int i = 1; i <= t ; ++i)
    {
        //cout<<"case "<<i<<": "<<"\n";
        solve();
    }
    return 0;
}

题外话

不知道为什么单向建图不行？看了官方题解说好像都是从小到大连接的。