赛时ADFJ，补BE

F

题意

给定n，每次先给n减去a，再减去b，你可以提前减少一次n，但不能全减，请问最少减去多少使得n是在减去b时被减光
如果无解输出"Sayonara"

思路

n<=a无解
考虑最后一轮所剩 $r=n\%(a+b)$ ,如果 $0<r<=a$ ，减去r，否则减去0就行

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n,a,b;
        cin >> n >> a >> b;
        if(n<=a) cout << "Sayonara" << endl;
        else {
            cout << (n%(a+b)>a||n%(a+b)==0?0:n%(a+b)) <<endl;
        }
    }
    return 0;
}

D

题意

给定长为n的01串，你可以将a个1翻转为0，或者将a+1个0翻转成1
请问最终最多有多少个1

思路

只要可以进行一次翻转，就可以全部翻转成1，扫描一遍串看最长的0段和1段即可
如果不够就是初始的1的个数

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n,a;
        priority_queue<int,vector<int>,less<int>> q1,q0;
        cin >> n >> a ;
        string s;
        cin >> s;
        int cnt0=0,cnt1=0,cntt=0;
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                if(cnt1!=0){
                    q1.push(cnt1);
                    cnt1=0;
                }
                cnt0++;
            }else{
                cntt++;
                if(cnt0!=0){
                    q0.push(cnt0);
                    cnt0=0;
                }
                cnt1++;                
            }
        }
        q0.push(cnt0);
        q1.push(cnt1);
        if((!q0.empty()&&q0.top()>=a+1)||(!q1.empty()&&q1.top()>=a))
            cout << n << endl;
        else
            cout << cntt << endl;
    }    
    return 0;
}

J

题意

两个人玩游戏，分别有x个筹码和y个筹码
筹码少的人获胜
输的人要给赢的人赢的人所具有的筹码

思路

神仙队友直接瞪眼秒了
观察所得：两个数加和除以gcd，剩下的数取log2,如果是整数就是答案，否则无解

代码

void solve(){
    int x,y;
    cin >> x >> y;
    int all=(x+y)/__gcd(x,y);
    bool ok=true;
    int cnt=0;
    while(all>1){
        if(all%2) ok=false;
        all/=2;
        cnt++;
    }
    cout << (ok?cnt:-1) << endl;
}

A

PS：由于队伍里没有构学长所以构造不了一点

题意

给定一个长度为n的序列，其中 $1<=a_i<=i$ 构造n阶矩阵，使得第i行和第i列满足 $mex(A_{ik})=mex(A_{ki})\,(1<=k<=n)$

思路

只考虑上三角矩阵
对角线放1如果冲突就变成0
第i行放i+1这样行永远不会冲突
检查每一列，不满足mex就置0

代码

#include<bits/stdc++.h>
using namespace std;
int a[2020];
int maze[2020][2020];
void solve(){
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i] ;
    }
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            if(j==i)maze[i][j]=(a[j]==1?0:1);
            else{
                maze[i][j]=(a[j]!=i+2?i+2:0);
                maze[j][i]=(a[j]!=i+2?i+2:0);                
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout << maze[i][j] << ' ';
        }
        cout << endl;
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

E

题意

给定一个长度为n的正整数序列，你可以做以下两种操作任意次
1. 选择任意两个数，将它们两个都除以某一个公因子
2. 选择任意两个数，将它们乘上一个数
判断最终能否使得序列中所有数相等

思路

赛时差一点，没想到如何判断质因子是否出现了偶数次
分类讨论
- n=1，显然直接可以
- n=2，除非相等，否则不可以
- n>=3，对于每一个质因子p考虑，将 $a_i$ 中p的次数记为 $b_i$
  - $n\%2=0\,\,\sum(b_i)\%2=1$ 要求最终 $a_i$ 相同，则所有 $b_i$ 相等，则 $n*b_i$ 一定是偶数，与sum奇偶性不同，无解
  - $n\%2=0\,\,\sum(b_i)\%2=0$ 对于给定的操作，每次可以使sum-=2||sum+=2，最终使sum变为0
  - $n\%2=1\,\,\sum(b_i)\%2=1$ 先通过若干次+2使得每个 $b_i>=1$ ，记 $c_i=b_i-1$ ，则 $\sum(c_i)=\sum(b_i)-n$ ，最终 $\sum(c_i)$ 是一个偶数，可以将 $\sum(c_i)$ 变为0，那么所有 $b_i==1$
  - $n\%2=1\,\,\sum(b_i)\%2=0$ 无所谓，只要sum(b_i)是偶数，就可以变为全0
综上
- n为奇数直接YES
- n为偶数，判断每一个质因子出现的次数和，如果和是偶数就YES，奇数就NO
对于判断质因子出现次数
- 先做一遍筛法，得知每个数的最小质因子，然后开一个cnt，记录每个质因子出现的次数，cnt[v[a[i]]]++;a[i]/=v[a[i]];直到a[i]==i
- 这样复杂度是O(Nlog(max(a_i)))
- 最终看cnt奇偶不用遍历，开一个变量cnt_odd，当一个数从偶数变成奇数就给cnt_odd++，否则就cnt_odd--，最终检查是不是0即可
- 另一个方法异或哈希，把所有质数映射到随机值，筛法的同时按积性函数的方法维护每一个数对应的哈希值
- 最终做一个 $\oplus_{i=1}^n hash[a_i]$ 检查是不是0即可

代码

#pragma gcc optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

std::mt19937_64 rng;
long long rand(long long l,long long r){//long long随机数生成
    std::uniform_int_distribution<long long> distribution(l,r);
    return(distribution(rng));
}

int prime[1010110],v[5010101];
long long h[5010101];
int cnt=0;
void seive(int x){
    for(int i=2;i<=x;i++){
        if(v[i]==0){
            prime[++cnt]=i;
            v[i]=i;
            h[i]=rand(1ll,(1ll<<62));
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>x||prime[j]>v[i])break;
            v[i*prime[j]]=prime[j];
            h[i*prime[j]]=h[i]^h[prime[j]];
        }
    }
}
void solve(){
    int n;
    cin >> n;
    vector<int> a(n+10);
    vector<long long> f(n+10);
    for(int i=0;i<n;i++){
        cin >> a[i] ;
    }
    if(n%2) cout << "YES" << endl;
    else if(n==2) cout << (a[0]==a[1]?"YES":"NO") << endl;
    else{
        long long sum=0;
        for(int i=0;i<n;i++){
            sum^=h[a[i]];
        }
        cout << (sum==0?"YES":"NO") << endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    seive(5000010);
    // cout << cnt <<endl; //348513个
    while(T--){
        solve();
    }
    return 0;
}

B

题意

给定a，b，c，你可以做以下四种操作
1. 将a左移一位
2. 将b右移一位
3. a^=b
4. b^=a
判断能否在64次操作内，使得a=b=c，如果可以输出操作方案

思路

特别的，如果a=0,b=0，需要特判，如果c=0直接可以，如果c!=0则一定不可以
首先，可以用最多1次操作使得a和b最高位相同
然后比较a和c的最高位
- 如果a的位数更高，用b一位位修改a，a和c有不同就异或，这样最多2*(a的位数)次操作就能使得a和c完全相同，同时b为0，最后使用1次操作使得b和a相等
- 如果c的位数更高，不断将a提高，同时用b修改a的对应位，直到a和c位数相等，然后再将b向右移动，一位位修改a，最终使得a和c相等，然后使用1次操作使得b和a相等

代码

#include<bits/stdc++.h>
using namespace std;

int geth(int x){
    if(x==0) return -1;
    int cnt=0;
    while(x){
        cnt++;
        x>>=1;
    }
    return cnt;
}
int a,b,c;
vector<int> path;
void op1(){ path.push_back(1); a<<=1; }
void op2(){ path.push_back(2); b>>=1; }
void op3(){ path.push_back(3); a^=b; }
void op4(){ path.push_back(4); b^=a; }

void solve(){
    path.clear();
    cin >> a >> b >> c;
    int ha=geth(a),hc=geth(c),hb=geth(b);
    if(a==b&&a==0){
        if(c==0){ cout << 0 << endl; return ;}
        else{ cout << -1 << endl; return ;}
    }
    //总保证a和b最高位相同
    if(ha>hb){op4();hb=ha;}
    if(hb>ha){op3();ha=hb;}
    
    if(ha>=hc){
        for(int i=ha-1;i>=0;i--){
            if(((a>>i)&1)!=((c>>i)&1)){
                op3();
            }
            op2();
        }
        op4();
    }else{
        int cnt=1;
        while(ha<hc){
            if(((a>>(ha-cnt))&1)!=((c>>(hc-cnt))&1)){
                op3();
            }
            cnt++;
            ha++;
            op1();
        }
        while(hb){
            if(((a>>(hb-1))&1)!=((c>>(hb-1))&1)){
                op3();
            }
            hb--;
            op2();
        }
        op4();
    }
    cout << path.size() << endl;
    for(auto x:path){
        cout << x << ' ';
    }
    cout << endl;
}
int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

牛客多校03

F

题意

思路

代码

D

题意

思路

代码

J

题意

思路

代码

A

题意

思路

代码

E

题意

思路

代码

B

题意

思路

代码