2022“杭电杯”中国大学生算法设计超级联赛（2）

C++ to Python

给出一行C++代码，输出对应的Python代码。

思路：省略字母，冒号，"_"输出即可。

AC Code：

#include 
 
int t;
std::string s; 
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>s;
        int len=s.length();
        for(int i=0;i
            if(s[i]=='s') std::cout<<'(';
            if(s[i]>='0'&&s[i]<='9') std::cout<
            if(s[i]==','||s[i]==')'||s[i]=='-') std::cout<
        }
        std::cout<<'\n';
    }
    return 0;
}

Snatch Groceries

前面一大段没啥用，，看最后一段即可。给出若干区间，计算有多少不重叠的区间，注意，一旦遇到重叠的区间就不再计算了。

思路：扫一遍讨论即可。

AC Code：

#include 
 
const int N=1e5+5;
int t,n,l,r;
 
struct node{
    int l,r;
} e[N];
 
bool cmp(node a,node b){
    if(a.lreturn true;
    else if(a.l==b.l&&a.rreturn true;
    else return false;
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n;
        for(int i=1;i<=n;i++){
            std::cin>>l>>r;
            e[i].l=l,e[i].r=r;
        }
        int cnt=0;
        std::sort(e+1,e+1+n,cmp);
        r=e[1].r;
        for(int i=2;i<=n;i++){
            if(r>=e[i].l) break;
            else cnt++,r=e[i].r;
        }
        if(r==e[n].r) cnt++;
        std::cout<'\n';
    }
    return 0;
}

 os：很简单的题给队里贡献了两发WA，我是fw

Luxury cruise ship

给出一个long long范围内的数，判断是否可以用7,31,365组成，若能则输出最少组成所需要的个数，若不能输出-1。

思路： 在n较小的范围内，可以直接暴力预处理得到答案，我们队取的这个范围是365*2，这个范围可以再大一些；较大时，先把n减去若干个365使其到我们预处理的范围，再判断。

AC Code：

#include 
 
typedef long long ll;
const int N=365;
int t;
ll n;
std::vectora(N<<1+5,-1);
 
void init(){
    a[0]=0;
    for(int i=1;i<=(N<<1);i++){
        for(int j=0;j<=i/31;j++){
            int tmp=i-31*j;
            if(tmp%7==0) a[i]=j+tmp/7;
        }
    }
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    init();
    std::cin>>t;
    while(t--){
        std::cin>>n;
        ll ans=n/365;
        ll res=n%365;
        if(a[res]==-1){
            if(ans==0) ans=-1;
            else ans=ans-1+a[res+365];
        }
        else ans+=a[res];
        std::cout<'\n';
    }
    return 0;
}

ShuanQ

给出一些关系，如第二三四段那样，给出P,Q,ed，求满足条件的rd，若没有输出“shuanQ”。

思路：由题目所说，可以得出P*Q-1=0 MOD M，即M是P*Q-1的质因子，处理一下质因数，挨个带入第三四段等式即可，注意限制条件，P,Q,ed

AC Code：

#include 
 
typedef long long ll;
const int N=2e6+5;
int t,cnt;
ll p,q,e;
ll prime[N];
 
void pr(ll x){
    cnt=0;
    memset(prime,0,sizeof(prime));
    ll temp=x;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            prime[++cnt]=i;
            while(temp%i==0)
            temp/=i;
        }
        if(temp==1) break;
    }
    if(temp!=1)
    prime[++cnt]=temp;
}
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>p>>q>>e;
        memset(prime,0,sizeof(prime));
        pr(p*q-1);
        ll ans=-1;
        for(int i=1;i<=cnt;i++){
            if(prime[i]<=e||prime[i]<=p||prime[i]<=q) continue;
            ll r=e*q%prime[i];
            ll E=r*p%prime[i];
            if(e==E){
                ans=r;
                break;
            }
        }
        if(ans==-1){
            std::cout<<"shuanQ"<<'\n';
            continue;
        }
        std::cout<'\n';
    }
    return 0;
}

os：这个题真的栓Q了，一开始队友推出来是二元一次方程，结果解了半天一直WA，没想到暴力就可以，乐了

Copy

给出一个序列，每次操作可以将某一段复制后放在该段后面，也可以询问某一位的数字，求最后所有被询问过的数字的异或和是多少。

思路： （1）暴力：没想到这个题暴力就可以过，但是由于我对STL实在不熟练，学习一下别的大佬的代码；

（2）正解：首先容易知道修改对后面的查询的影响，如果x<=r则无影响，否则相当于查询x-(r-l+1)，因此可以离线，倒着修改每次操作，每个修改操作之后，对于x>r的，令x-=r-l+1。因为我们只需要答案的异或和，所以对于两次相同的查询可以抵消，因此同一位置最多只会查询一次，我们使用bitset表示每一位的信息。令f第i位为1表示答案需要对a[i]异或。倒着遍历所有操作，如果是查询操作，f[x]^=1，否则就令r+1....n这些位右移r-l+1，即：

low=f&(~std::bitset(0)>>(N-r-1));
high=f&(~std::bitset(0)<<(r+1));
f=low^(high>>(r+1-l));

low表示[1,r]部分，high表示[r+1,n]部分，每次操作将后面一部分向前移动r-l+1个单位，最后累加答案即可。

AC Code：

（1）暴力：

#include 
 
int t,n,q;
 
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>q;
        std::vector<int>a(n+1);
        for(int i=1;i<=n;i++){
            std::cin>>a[i];
        }
        int ans=0;
        for(int i=1;i<=q;i++){
            int op;
            std::cin>>op;
            if(op==1){
                int l,r;
                std::cin>>l>>r;
                auto p=a.begin()+r+1;
                auto L=a.begin()+l;
                auto R=a.begin()+r+1;
                auto del=a.begin()+n+1;
                if(del!=a.end()) a.erase(del,a.end());
                std::vector<int>vec(L,R);
                a.insert(p,vec.begin(),vec.end());
            }
            else{
                int pos;
                std::cin>>pos;
                ans^=a[pos];
            }
        }
        std::cout<'\n';
    }
    return 0;
}

（2）标解：

#include 
 
#define int long long
const int N=1e5+5;
int t,n,m;
int a[N],v[N][3];
std::bitsetf,low,high;
 
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>m;
        for(int i=1;i<=n;i++){
            std::cin>>a[i];
        }
        for(int i=1;i<=m;i++){
            std::cin>>v[i][0];
            if(v[i][0]==1) std::cin>>v[i][1]>>v[i][2];
            else std::cin>>v[i][1];
        }
        f.reset();
        for(int i=m;i>=1;i--){
            if(v[i][0]==1){
                int l=v[i][1],r=v[i][2];
                low=f&(~std::bitset(0)>>(N-r-1));
                high=f&(~std::bitset(0)<<(r+1));
                f=low^(high>>(r+1-l));
            }
            else{
                int x=v[i][1];
                f[x]=!f[x];
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(f[i]) ans^=a[i];
        }
        std::cout<'\n';
    }
    return 0;
}

剩下的基本都触及知识盲区了，，好多线段树啊，不会啊呜呜呜