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

比赛传送门
作者： fn

---

签到题

1002题 C++ to Python / C++到Python

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

考察内容
签到

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

#include<bits/stdc++.h>
#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<char,int> mp;

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll len2=s0.size();
	for(int i=0;i<len2;i++){
    
		mp[s0[i]]=1;
	}
	
	int t; cin>>t;
	while(t--){
    
		cin>>s; ll len=s.size();
		
		for(int i=0;i<len;i++){
    
			if(mp[s[i]]!=1){
    
				cout<<s[i];
			}
		}
		cout<<endl;
	}
	return 0;
}

---

1007题 Snatch Groceries / 抢菜

题目大意
给定 $n$ 个区间，按时间顺序，求区间重叠前有几个区间。端点重合也算重叠。

考察内容
排序

分析
按照区间左端点排序，然后暴力枚举即可。

#include<bits/stdc++.h>
#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.l<y.l;
	return x.r>y.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<<ans<<endl;
	}
	return 0;
}
/* 1 3 1 10 10 20 15 16 */ 

---

基本题

1012题 Luxury cruise ship / 豪华游轮

题目大意
用体积为7、31或365的物品装填容量为 $n$ 的背包，求把背包装满最少需要多少个物品。不能装满输出-1。

考察内容
dp，贪心

分析
7，31，365的最小公倍数为79205，所以 $n$ 中大于79205的部分使用体积为365的物品填充是最优的。剩下的79205以内的部分直接用一维dp解决。

#include<bits/stdc++.h>
#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<<n/365<<endl;
			continue;	
		}
		
		// n%79205!=0
		ll ans=0;
		ans+=n/79205*217; // 每一份用217个365面值的硬币 
		n%=79205; // 缩小n的范围， 
		
		if(f[n]>1e17){
    
			cout<<-1<<endl;
		}
		else{
    
			cout<<f[n]+ans<<endl;
		}	
	}
	return 0;
}

---

1009题 ShuanQ / “栓Q”

题目大意
rsa加密算法中，给定私钥 $p$ ，公钥 $q$ ，密文 $x$，求解明文 $ans$。若无法求解则输出 “ShuanQ” 。

其中 $p,q,x,ans$ 满足：
$p\times q\equiv 1\mathrm{mod}M$ ，其中 $M$ 为质数且 $M>p,M>q,M>x$ 。
$ans=x\times q\mathrm{mod}M$

考察内容
质数，数学知识

分析
思路：先找出M，然后可以通过 $ans=x\times q\mathrm{mod}M$ 直接计算出明文。

已知 $p\times q\mathrm{mod}M=1$
移项得，
$(p\times q-1)\mathrm{mod}M=0$

从 $1$ 到 $\sqrt{p\times q-1}$ 枚举因数 $i$ ，质数的 $(p\times q-1)/i$ 即为一个合法的$M$ 。

#include<bits/stdc++.h>
#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<<x*q%ansm<<endl;
		}
		else{
    
			cout<<"shuanQ"<<endl;
		}
	}
	return 0;
}
/* 1 1 1 1 1 2000000 2000000 2000000 1 1999999 1999999 1999999 */ 

---

进阶题

1003题 Copy / 复制

题目大意
给定一个数组 $a$ ，$q$ 次操作。初始答案 $ans=0$ 。

操作一：选择一段区间 $[l,r](l,r\le l,r\le n)$ ，在 $r$ 后面紧跟着复制一段一样的区间。复制后超过 $n$ 的部分可以忽略。操作一的总数不超过20000次。

操作二：查询一个数字 $a[x]$ ，令 $ans=ans\oplus a[x]$ 。

求异或和 $ans$ 。

考察内容
暴力

分析
直接暴力模拟即可。

#include<bits/stdc++.h>
#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<n){
    
					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("%lld\n",ans);
	}
	return 0;
}

---