2022杭电多校联赛第二场 题解

比赛传送门
作者： fn

• 签到题
• • 1002题 C++ to Python / C++到Python
  • 1007题 Snatch Groceries / 抢菜
• 基本题
• • 1012题 Luxury cruise ship / 豪华游轮
  • 1009题 ShuanQ / “栓Q”
• 进阶题
• • 1003题 Copy / 复制

题目大意
把 std::make_tuple(1,2) 变成 (1,2) 的形式。

考察内容
签到

分析
把 “std::make_tuple” 中的字符忽略即可。

#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
const int N=1e6+10;
ll n,m,a[N];
string s;
string s0="std::make_tuple";
map mp;

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll len2=s0.size();
	for(int i=0;i
		mp[s0[i]]=1;
	}
	
	int t; cin>>t;
	while(t--){
		cin>>s; ll len=s.size();
		
		for(int i=0;i
			if(mp[s[i]]!=1){
				cout< 
 
1007题 Snatch Groceries / 抢菜 
题目大意
 给定 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个区间，按时间顺序，求区间重叠前有几个区间。端点重合也算重叠。
 
考察内容
 排序
 
分析
 按照区间左端点排序，然后暴力枚举即可。
 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
const int N=1e6+10;
ll n,m;

struct node{
	ll l,r;
}a[N];

bool cmp(node x,node y){
	if(x.l!=y.l)return x.ly.r;
}

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i].l>>a[i].r;
		}
		sort(a+1,a+n+1,cmp);
		
		ll maxr=a[1].r;
		ll ans=0;
		
		for(int i=2;i<=n;i++){
			if(a[i].l<=maxr){
				break;
			}
			else{ // a[i].l>maxr
				maxr=max(maxr,a[i].r);
				ans++;
			}
		}
		
		if(ans==n-1){
			ans++;
		}
		cout< 
 
基本题 
1012题 Luxury cruise ship / 豪华游轮 
题目大意
 用体积为7、31或365的物品装填容量为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的背包，求把背包装满最少需要多少个物品。不能装满输出-1。
 
考察内容
 dp，贪心
 
分析
 7，31，365的最小公倍数为79205，所以 
    
     
      
       
        n
       
      
      
       n
      
     
    n 中大于79205的部分使用体积为365的物品填充是最优的。剩下的79205以内的部分直接用一维dp解决。
 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
ll n;
ll f[79210];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	for(int i=0;i<=79205;i++){
		f[i]=1e18+10;
	}
	
	f[0]=0;
	for(int i=365;i<79205;i+=365){
		f[i]=f[i-365]+1;
	}
	for(int i=31;i<79205;i++){
		f[i]=min(f[i],f[i-31]+1);
	}
	for(int i=7;i<79205;i++){
		f[i]=min(f[i],f[i-7]+1);
	}
	
	int t; cin>>t;
	while(t--){
		cin>>n;
		if(n%79205==0){ // 每一份
			cout<1e17){
			cout<<-1<
			cout< 
 
1009题 ShuanQ / “栓Q” 
题目大意
 rsa加密算法中，给定私钥 
    
     
      
       
        p
       
      
      
       p
      
     
    p ，公钥 
    
     
      
       
        q
       
      
      
       q
      
     
    q ，密文 
    
     
      
       
        x
       
      
      
       x
      
     
    x，求解明文 
    
     
      
       
        a
       
       
        n
       
       
        s
       
      
      
       ans
      
     
    ans。若无法求解则输出 “ShuanQ” 。
 
其中 
    
     
      
       
        p
       
       
        ,
       
       
        q
       
       
        ,
       
       
        x
       
       
        ,
       
       
        a
       
       
        n
       
       
        s
       
      
      
       p,q,x,ans
      
     
    p,q,x,ans 满足：
 
    
     
      
       
        p
       
       
        ×
       
       
        q
       
       
        ≡
       
       
        1
       
       
       
       
        
         m
        
        
         o
        
        
         d
        
         
       
        M
       
      
      
       p×q≡1 mod M
      
     
    p×q≡1modM ，其中 
    
     
      
       
        M
       
      
      
       M
      
     
    M 为质数且 
    
     
      
       
        M
       
       
        >
       
       
        p
       
       
        ,
       
       
        M
       
       
        >
       
       
        q
       
       
        ,
       
       
        M
       
       
        >
       
       
        x
       
      
      
       M>p, M>q, M>x
      
     
    M>p,M>q,M>x 。
 
    
     
      
       
        a
       
       
        n
       
       
        s
       
       
        =
       
       
        x
       
       
        ×
       
       
        q
       
       
       
       
        
         m
        
        
         o
        
        
         d
        
         
       
        M
       
      
      
       ans=x×q mod M
      
     
    ans=x×qmodM
 
考察内容
 质数，数学知识
 
分析
 思路：先找出M，然后可以通过 
    
     
      
       
        a
       
       
        n
       
       
        s
       
       
        =
       
       
        x
       
       
        ×
       
       
        q
       
       
       
       
        
         m
        
        
         o
        
        
         d
        
         
       
        M
       
      
      
       ans=x×q mod M
      
     
    ans=x×qmodM 直接计算出明文。
 
已知 
    
     
      
       
        p
       
       
        ×
       
       
        q
       
       
       
       
        
         m
        
        
         o
        
        
         d
        
         
       
        M
       
       
        =
       
       
        1
       
      
      
       p×q mod M=1
      
     
    p×qmodM=1
 移项得，
 
    
     
      
       
        (
       
       
        p
       
       
        ×
       
       
        q
       
       
        −
       
       
        1
       
       
        )
       
       
       
       
        
         m
        
        
         o
        
        
         d
        
         
       
        M
       
       
        =
       
       
        0
       
      
      
       (p×q-1) mod M =0
      
     
    (p×q−1)modM=0
 
从 
    
     
      
       
        1
       
      
      
       1
      
     
    1 到 
    
     
      
       
        
         
          p
         
         
          ×
         
         
          q
         
         
          −
         
         
          1
         
        
       
      
      
       sqrt{p×q-1}
      
     
    p×q−1
           ​ 枚举因数 
    
     
      
       
        i
       
      
      
       i
      
     
    i ，质数的 
    
     
      
       
        (
       
       
        p
       
       
        ×
       
       
        q
       
       
        −
       
       
        1
       
       
        )
       
       
        /
       
       
        i
       
      
      
       (p×q-1)/i
      
     
    (p×q−1)/i 即为一个合法的
    
     
      
       
        M
       
      
      
       M
      
     
    M 。
 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
ll n,m;

bool isp(ll x){
	if(x<=1)return 0;
	
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0)return 0;
	}
	return 1;
}

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		ll p,q,x;
		cin>>p>>q>>x; // 私钥，公钥，密文 
		
		ll m=max(p,q); m=max(m,x); m++;
		 
		ll ansm=-1;
		ll pq1=p*q-1;
		
		for(int i=1;i<=sqrt(pq1);i++){ // 枚举 
			if(pq1%i==0){
				if(isp(pq1/i)){
					ansm=pq1/i;
					break;
				}
			}
		}

		if(ansm!=-1){
			cout<
			cout<<"shuanQ"< 
 
进阶题 
1003题 Copy / 复制 
题目大意
 给定一个数组 
    
     
      
       
        a
       
      
      
       a
      
     
    a ，
    
     
      
       
        q
       
      
      
       q
      
     
    q 次操作。初始答案 
    
     
      
       
        a
       
       
        n
       
       
        s
       
       
        =
       
       
        0
       
      
      
       ans=0
      
     
    ans=0 。
 
操作一：选择一段区间 
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
       
        (
       
       
        l
       
       
        ,
       
       
        r
       
       
        ≤
       
       
        l
       
       
        ,
       
       
        r
       
       
        ≤
       
       
        n
       
       
        )
       
      
      
       [l,r] (l,r le l,r le n)
      
     
    [l,r](l,r≤l,r≤n) ，在 
    
     
      
       
        r
       
      
      
       r
      
     
    r 后面紧跟着复制一段一样的区间。复制后超过 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的部分可以忽略。操作一的总数不超过20000次。
 
操作二：查询一个数字 
    
     
      
       
        a
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       a[x]
      
     
    a[x] ，令 
    
     
      
       
        a
       
       
        n
       
       
        s
       
       
        =
       
       
        a
       
       
        n
       
       
        s
       
       
        ⊕
       
       
        a
       
       
        [
       
       
        x
       
       
        ]
       
      
      
       ans=ans⊕a[x]
      
     
    ans=ans⊕a[x] 。
 
求异或和 
    
     
      
       
        a
       
       
        n
       
       
        s
       
      
      
       ans
      
     
    ans 。
 
考察内容
 暴力
 
分析
 直接暴力模拟即可。
 
#include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'n'
#define endl 'n'
using namespace std;
const int N=1e5+5;
int n,m,q,a[N];
int main(){ 
//	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
		scanf("%d%d",&n,&q);  
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]); 	
		}
		
		ll ans=0;
		int op,l,r,x;
		for(int i=1;i<=q;i++){
			scanf("%d",&op); 
			if(op==1){ // 区间更新，区间后面接一段一样的 
				scanf("%d%d",&l,&r); 

				if(r==n)continue; // 一整段复制，无意义，直接跳过 
				
				int F=l;
				int t1=r+r-l+1;
				if(t1
					for(int i=n;i>t1;i--){
						a[i]=a[i-(r-l+1)];
					}
				} 
				for(int i=r+1;i<=min(t1,n);i++){
					a[i]=a[F];
					F++;
				}
			}
			else{ // op==2，单点查询 
				scanf("%d",&x); 	
				ans=ans^a[x]; 
			}
		} 
		printf("%lldn",ans);
	}
	return 0;
}