赛时ABFIL，补D

B

题意

长度为n的数组，操作一次会删掉其中的两个，并添加他们的异或和，请问一次操作后会不会减小 $\sum_{i=1}^{n}2^{a_{i}}$

思路

就是判断任意两个的异或的最高位会不会小于等于这两个数中大的的最高位
如果两个数异或变得更小就一定不行，最多有63位，所以如果超过63个数一定会有两个数最高位相同，异或变小，不行
小于63个数的时候 $O(n^2)$ 暴力枚举就行
另一种思路是，先排序，从小到大判断，每次将两个数异或后的最高位加入p，如果某一次加入的数和p异或消除了p的某一位，就说明会变小

代码

#include<bits/stdc++.h>
using ll=long long;
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+10);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    if(n>=64) cout << "NO" << endl;
    else{
        int flg=0;//换成for(i,0,n-1&&flg)就不用特判60位，暴力也过
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if((a[i]^a[j])<max(a[i],a[j])){
                    flg=1;
                }
            }
        }
        cout << (flg?"NO":"YES") << endl;
    }
    return ;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

F

题意

一个由01构成的环形数组，每个1在每个单位时间会向两边扩散，你可以在某一个1旁边放置一个1阻止这个1向放置方向扩散，求最终最多剩多少个0

思路

遍历两遍这个环，用两个dis数组记录每一个0距离左or右侧最近的1的距离，距离最大的就是最长的0段，在这个地方放1，然后向另一侧更新dis为极大值，最终遍历环，如果两个dis都大于给定ddl就不会被烧毁

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> dis1(2e5);
vector<int> dis2(2e5);
signed main(){
    int t;
    cin >> t;
    while(t--){
        dis1.clear();
        dis2.clear();
        int n,ddl;
        cin >> n >> ddl;
        int cnt=0;
        string s;
        cin >> s;
        int mx=0,mxid=0;
        for(int i=0;i<2*n;i++){
            if(s[i%n]=='0'){
                cnt++;
            }else{
                cnt=0;
            }
            dis1[i%n]=cnt;
            if(dis1[i%n]>mx){
                mxid=i%n;
                mx=dis1[i%n];
            }
        }
        cnt=0;
        s[mxid]='1';
        for(int i=2*n-1;i>=0;i--){
            if(s[i%n]=='0'){
                cnt++;
            }else{
                cnt=0;
            }
            dis2[i%n]=cnt;
        }
        // cout << mxid << endl;
        for(int i=2*n-1;i>=0;i--){
            if(i%n==mxid){
                i--;
                while(s[i%n]!='1'&&i>=0){
                    dis2[i%n]=0x7f7f7f7f;
                    i--;
                }
            }
        }        
        int ans=0;
        // for(int i=0;i<n;i++){cout << dis1[i] << ' ';}
        // cout << endl;
        // for(int i=0;i<n;i++){cout << dis2[i] << ' ';}
        // cout << endl;
        for(int i=0;i<n;i++){
            if(dis1[i]>ddl&&dis2[i]>ddl) ans++;
        }
        cout << ans<< endl;
    }
    return 0;
}

I

题意

对于不相等的x，y，求解k使得 $({x}mod{k})+({k}mod{x})=({y}mod{k})+({k}mod{y})$
如果不存在就输出-1

思路

签到题，有1就不行，没1输出1
dirt：cout输出记得加括号

代码

#include<bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int a,b;
        cin >> a >> b;
        cout << (a==1||b==1?-1:1) << endl;
    }
    return 0;
}

A

题意

长度为n由0，1，-1构成的数组，-1可被替换为0或1
最终求和每个方案中连续1的数量

思路

线性dp
每次从0变成1后答案就要增加，增加的量是到当前的总方案数
维护两个dp数组，一个记录到当前的和，一个记录到当前的方案数
永远继承上一步状态，如果不可能就清零

代码

#include<bits/stdc++.h>

using namespace std;

const int p=998244353;

int a[505050];
int day[505050][2],cnt[505050][2];
/**
 * 当前位是0,对方案数和天数都不会影响
 * 当前位是1,上一位是0的时候天数增加总方案数，上一位是1天数不变
 * 总方案数不变
 * 当前位是-1,天数和方案数是前两种情况加和
 */
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n ;
        for(int i=1;i<=n;i++){
            cin >> a[i];
        }
        if(a[1]==1){
            day[1][1]=1;day[1][0]=0;
            cnt[1][1]=1;cnt[1][0]=0;
        }else if(a[1]==0){
            day[1][1]=0;day[1][0]=0;
            cnt[1][1]=0;cnt[1][0]=1;            
        }else{
            day[1][1]=1;day[1][0]=0;
            cnt[1][1]=1;cnt[1][0]=1;   
        }
        for(int i=2;i<=n;i++){
            if(a[i]==1){
                day[i][1]=(day[i-1][0]+cnt[i-1][0]+day[i-1][1])%p;
                day[i][0]=0;
                cnt[i][1]=(cnt[i-1][0]+cnt[i-1][1])%p;
                cnt[i][0]=0;
            }else if(a[i]==0){
                day[i][0]=(day[i-1][0]+day[i-1][1])%p;
                day[i][1]=0;
                cnt[i][0]=(cnt[i-1][0]+cnt[i-1][1])%p;
                cnt[i][1]=0;
            }else{
                day[i][1]=(day[i-1][0]+cnt[i-1][0]+day[i-1][1])%p;
                day[i][0]=(day[i-1][0]+day[i-1][1])%p;
                cnt[i][1]=(cnt[i-1][0]+cnt[i-1][1])%p;
                cnt[i][0]=(cnt[i-1][0]+cnt[i-1][1])%p;
            }
        }
        cout << ((day[n][1]+day[n][0])%p) << endl;
    }
    return 0;
}

L

题意

一个长度为n的排列，其中n为偶数，有多少种形成 $\frac{n-2}{n}$ 个数对的方式，使得数对中出现了1~n中的n-2个不同元素，且对数对<x,y>，满足p[x]=y或p[y]=x

思路

由排列知道一定会成若干个环
如果要满足条件必定是0个奇环或者两个奇环，不然总有奇环无法配对
分类讨论，如果没有奇环，则没删点的偶环每个可以提供两种方案，删掉点的偶环每个可以提供 $\frac{siz^2}{4}$ 种方案(每个点都可删，删掉一个点后必须删掉一个间隔为偶数的点，共 $\frac {n}{2}$ 个)；如果奇环为两个，则每个偶环提供两种方案，每个奇环提供cnt种方案

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int p=998244353;

int fa[505050];
long long qpow(long long a,long long b){
    a%=p;
    long long res=1;
    while(b){
      if(b&1) res=res*a%p;
      a=a*a%p;
      b>>=1;
    }
    return res;
}

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int a,int b){
    fa[find(a)]=find(b);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i=1;i<=n;i++){ fa[i]=i; }
        for(int i=1;i<=n;i++){
            int tmp;
            cin >> tmp;
            merge(i,tmp);
        }
        unordered_map<long long,long long> mp;
        for(int i=1;i<=n;i++){
            mp[find(i)]++;
        }
        // cout << ">>" << mp.size() << endl;
        int odd=0,dou=0;
        for(auto [x,y]:mp){
            if(y%2) odd++;
            if(y==2) dou++; 
        }
        // cout << odd << ' ' << dou << endl;
        if(odd!=0&&odd!=2) cout << 0 << endl;
        else if(odd==0){
            //全是偶环，被删的环提供n^2/4，剩下的超过2的环每个提供两种
            long long ans=0;
            for(auto [x,y]:mp){
                ans+=((y*y/4)%p*qpow(2,mp.size()-1-dou+(y==2)))%p;
                ans%=p;
            }
            cout << ans << endl;
        }else {
            //两个奇环删点：奇环每个点可删，删后提供一种方案
            long long ans=1;
            for(auto [x,y]:mp){
                if(y%2)
                    ans=(ans*(y%p))%p;
            }
            ans=(ans*qpow(2,mp.size()-odd-dou))%p;
            cout << ans << endl;
        }
    }
}

D

题意

n个物品，有 $(s_i,h_i,d_1)$ 三种性质
求在 $\sum s_i < V$ 的情况下， $\sum h_i - (V-\sum s_i)(\sum d_i)$
n~1e5,V<=500

思路

枚举填满的体积，这样每个物品的价值就固定，变成背包问题
背包复杂度 $O(nV^2)$ 会超时，考虑占据空间为S时，如果选择空间s的物品，最多选价值最大的S/s个，可以使用nth_element函数快速得到
复杂度就可以通过
nth_element(起始迭代器,第n大迭代器,末尾迭代器,比较函数)

代码

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
/**
 * 总价值=sum(h_i)-(V-sum(s_i))*sum(d_i)
 * 可以视作一个装满V-U的体积，每个物品价值为(h_i-U*d_i)的01背包
 * 枚举U
 * 
 */

ll h[101010],s[101010],d[101010];
vector<ll> chip[600];
ll dp[600];
void solve(){
    ll ans=0;
    int n,V;
    cin >> n >> V;
    for(int i=1;i<=n;i++){
        cin >> h[i] >> s[i] >> d[i];
    }
    for(int v_now=1;v_now<=V;v_now++){//枚举当前体积
        int u=V-v_now;
        for(int i=0;i<=v_now;i++){
            chip[i].clear();
            dp[i]=-1e18;
        }
        for(int i=1;i<=n;i++){//计算当前体积下的价值
            chip[s[i]].push_back(h[i]-u*d[i]);
        }
        dp[0]=0;
        for(int i=1;i<=v_now;i++){//枚举每个体积的物品
            //算每个体积的物品能取多少件
            int cnt=min(v_now/i,(int)chip[i].size());
            nth_element(chip[i].begin(),chip[i].begin()+cnt-1,chip[i].end(),greater<ll>());
            for(int j=0;j<cnt;j++){
                for(int k=v_now;k>=i;k--){
                    dp[k]=max(dp[k],dp[k-i]+chip[i][j]);
                }
            }
        }
        ans=max(ans,dp[v_now]);
    }
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        solve();
    }    
}

牛客多校02

B

题意

思路

代码

F

题意

思路

代码

I

题意

思路

代码

A

题意

思路

代码

L

题意

思路

代码

D

题意

思路

代码