【CSP-J模拟赛十一】题解

本题解原创： SDLYA10305

原创 CSDN：

比赛传送门：

http://180.76.190.156/contest/337

A 石头剪刀布

没什么好说的，纯模拟（本蒟蒻懒得推通解，直接暴力判断了）。

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

int a,b;

int main()
{
	cin>>a>>b;
	if(a==b)cout<<"tie";
	else if(a==1){
		if((b==2))cout<<"win";
		else cout<<"lose";		
	}
	else if(a==2){
		if((b==3))cout<<"win";
		else cout<<"lose";		
	}
	else if(a==3){
		if((b==1))cout<<"win";
		else cout<<"lose";		
	}

	
	return 0;
}

B 保家卫国

同 A 题。

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

char a;
int b;

int main()
{
	cin>>a>>b;
	//if(b<160){
	//	cout<<"NO\n0";
	//	return 0;
	//}并没有关于这个特判的测试点，可有可无
	if(a=='V'){
		if(b<=170)
			printf("NO\n%.2lf",b*0.85);
		else if(b<=180)
			printf("NO\n%.2lf",b*0.8);
		else printf("YES\n%.2lf",b*0.75);
	}
	else {
		if(b<=170)
			printf("NO\n%.2lf",b*0.9);
		else printf("YES\n%.2lf",b*0.9);		
	}
	
	return 0;
}

C 数字游戏

本场比赛第一道非红题。话说 csp-j 模拟赛怎么越来越水了。

通过题意，我们发现最终的 值即为不小于初始 值得最小的最大质因子不大于 的数，即其质因数都为小于 的质数。

但是 的值太大，暴力枚举显然会 。因为数据范围中的 非常小，所以从此入手。 以内的质数只有 ，我们可以定义一个优先队列 （小顶堆），初始队列为所有不大于 的素数。然后每次弹出队头，即目前最小的满足条件的数，判断其是否不小于 ，不小于则输出，否则枚举小于 的素数，然后将两数相乘后放入 。根据素数唯一分解定理，生成的数不会重复。

关于时间复杂度... 反正能过（我不会证）。

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

int x,p;
priority_queue<ll,vector<int>,greater<int> >q;
int a[6]={0,2,3,5,7,11};//多写一个作为边界

int main()
{
	cin>>x>>p;
	ll ans;
	for(int i=1;a[i]<=p;i++)
		q.push(a[i]);
	while(1){
		int t=q.top();q.pop();
		if(t>=x){
			ans=t;
			break;
		}
		for(int i=1;a[i]<=p;i++)
			q.push(t*a[i]);
	}
	cout<<ans;
	
	return 0;
}

D 魔力碎片

每次操作都会使 的值减去 ，所以只要求出 即可...

显然，这是错误的。当进行到某次操作使 k-p<x<k 时，上面的式子会错误的多计算 点（这里的 为某次操作后得值而非初始值）。

所以，我们可以将计算分为两部分。先计算出当剩余值大于 时对答案的贡献，推得贡献为 。然后， 的值就只剩下 点，正好可以再进行一次操作，贡献为 。两次操作剩余值之和显然不会达到 。

所以，我们可以得到答案为：

此外，还有一个特判要注意。当 x<k 时，无法进行操作，直接输出 。

code(疯狂压行版)

#include<bits/stdc++.h>
using namespace std;
long long x,k,p;
int main()
{
	cin>>x>>k>>p;
	if(x<k)return !(cout<<0);
	return !(cout<<(x-k)/(k-p)+1);
}

E Present

直接用 的双端队列或手写双端队列模拟即可（我用的是 ）。需要注意的是，翻转队列使用一般写法可能会超时，记录一个变量 判断当前方向即可。

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

int n,id,io=1;
deque<int> q;

signed main()
{
	cin>>n>>id;
	while(n--){
		int op;cin>>op;
		if(op==0){
			int x;cin>>x;
			if(io==1)
				q.push_front(x);
			else q.push_back(x);
		}
		else if(op==1){
			if(q.empty())cout<<"0\n";
			else 
				if(io==1){
					cout<<q.front()<<"\n";
					q.pop_front();
				}
				else {
					cout<<q.back()<<"\n";
					q.pop_back();
				}
		}
		else if(op==2){
			int x;cin>>x;
			if(io==-1)
				q.push_front(x);
			else q.push_back(x);
		}
		else if(op==3){
			if(q.empty())cout<<"0\n";
			else 
				if(io==-1){
					cout<<q.front()<<"\n";
					q.pop_front();
				}
				else {
					cout<<q.back()<<"\n";
					q.pop_back();
				}
		}
		else if(op==4)
			io*=-1;
	}
	
	return 0;
}

F 人赢

初中数学题。

先排序（从小到大或从大到小皆可），然后从两边到中间依次选择结对对象，即对于第 个人，TA 的帮扶对象为第 个人。然后再算出答案即可。

如何证明？考虑当 时， ，考虑所有组合对答案的贡献，使用作差法易证 与 ， 与 结对的贡献是最大的。同理，可推得 更大的情况。

然后就是如何输出方案。因为数列已经排过序，所以按从两边到中间的顺序输出即可。

还有一点特别重要，答案的值可能超过 long long 的范围，需要 unsigned long long（卡了我一个小时 QWQ）。

具体细节见代码

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=2e5+5;

int n,flag,ans;
struct pl{
	int c,id;
}a[N];

bool cmp(pl x,pl y){
	return x.c<y.c;
}

signed main()
{
	cin>>n>>flag;
	for(int i=1;i<=n;i++){
		cin>>a[i].c;
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	int l=1,r=n;
	while(l<=r){
		ans=ans+(a[r].c-a[l].c)*(a[r].c-a[l].c);
		l++;
		r--;
	}
	cout<<ans<<"\n";
	if(flag){
		l=1,r=n;
		while(l<=r){
			cout<<a[r].id<<" "<<a[l].id<<"\n";
			l++,r--;
		}
	}
	
	return 0;
}