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

---

签到题

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，背包，贪心

分析
$n$ 较小，直接背包dp。
$n$ 很大时，用365填充到一个较小的范围，再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[160005];

int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	for(int i=0;i<=160000;i  ){
		f[i]=1e18 10;
	}
	
	f[0]=0;
	for(int i=365;i<160000;i =365){
		f[i]=f[i-365] 1;
	}
	for(int i=31;i<160000;i  ){
		f[i]=min(f[i],f[i-31] 1);
	}
	for(int i=7;i<160000;i  ){
		f[i]=min(f[i],f[i-7] 1);
	}
	
	int t; cin>>t;
	while(t--){
		cin>>n;
		if(ny205==0){ // 每一份
			cout<<n/365<<endl;
			continue;	
		}
		
		// ny205!=0时 
		
		ll ans=0;
		if(n>79205){ // n很大
			ans  = (n-79205)/365; // 优先用365面值的硬币 
			n -= ans*365;
		}
		
		if(f[n]>1e17){
			cout<<-1<<endl;
		}
		else{
			cout<<f[n] ans<<endl;
		}	
	}
	return 0;
}
/*
输入： 
1
79211

输出： 
245

*/ 

---

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$ 到 p × q − 1 \sqrt{p×q-1} p×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](1\le l,r\le n)$ ，在 $r$ 后面紧跟着复制一段一样的区间，复制后超过 $n$ 的部分可以忽略。操作一的总数不超过20000次。

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

求异或和 $ans$ 。

考察内容
离线，dp，bitset优化，暴力

分析
方法一：
暴力模拟。

方法二(官方解法)：
一个修改操作对后续的查询操作的影响：如果 $x\le r$ 就没影响，如果 $x＞r$ ，相当于查询 $x-(r-l1)$ ，然后去掉修改操作。

因此可以离线，倒着处理所有修改操作，每个修改操作都让它之后的所有 $x＞r$ 的询问 $x-=r-l1$ 。

但是这么处理还是 O ( n 2 ) O(n^2) O(n2) 的。考虑到我们只要答案的异或和，就有，两个相同的查询可以抵消，因此同一位置至多只会查询一次。这样每个位置用 1 bit 的信息表示即可，也就是 bitset。
我们令 dp 第 i 位为 1 表示答案需要对 $a[i]$ 异或。倒着遍历所有操作，如果是查询操作， $dp[x]$ ^= $1$ ，如果是修改操作，那么就让 $r\mathrm{1...}n$ 这些比特右移 $r-l1$，代码如下：

low = dp & (~bitset<N>(0) >> (N - r - 1));
high = dp & (~bitset<N>(0) << (r   1));
dp = low ^ (high >> (r   1 - l));

方法一完整代码：

#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;
}

方法二完整代码：

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

const int N = 100010;

int a[N];
bitset<N> dp, low, high;
array<int, 3> v[N];

void solve() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i  ) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= q; i  ) {
        scanf("%d", &v[i][0]);
        if (v[i][0] == 1) {
            scanf("%d%d", &v[i][1], &v[i][2]);
        } else {
            scanf("%d", &v[i][1]);
        }
    }
    dp = 0;
    for (int i = q; i >= 1; i--) {
        if (v[i][0] == 1) {
            int l = v[i][1], r = v[i][2];
            low = dp & (~bitset<N>(0) >> (N - r - 1));
            high = dp & (~bitset<N>(0) << (r   1));
            dp = low ^ (high >> (r   1 - l));
        } else {
            int x = v[i][1];
            dp[x] = !dp[x];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i  ) {
        if (dp[i]) {
            ans ^= a[i];
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

---

这篇好文章是转载于：学新通技术网