普及组模拟赛

1.Problem 1. 小 X 的加法难题

Input file: sum.in
Output file: sum.out
Time limit: 1 second
Memory limit: 256 MB

第一节编程课上，老师要求大家写一个程序计算两个正整数的和。
看到小 X 不屑的眼神后，老师决定给小 X 增加难度。以求 12 和 3 的和为例，老师在 12 + 3 这个
原始式子里加入一些无用的空格，再把它交给小 X。
这下小 X 傻眼了，希望你帮帮他。

Input
第一行包含一个字符串，表示老师给小 X 的式子。

Output
若式子的结果不超过 108，则第一行包含一个整数，表示式子的结果；否则第一行包含一个字符串
“Large”。

Example

sum.in sum.out
1 2 + 3
15

23456789+98765432
Large

Scoring
• 对于 30% 的数据，式子中不包含无用的空格，式子的结果不超过 108。 • 对于 100% 的数据，字符串长度不超过 100。

题意分析
这题就是给出一个算式，然后求和，判断是否超过108

解题思路
这题可以用long long 来做
一个一个累加，如果超过108就退出

我这里用的是高精度
特判一下108 就行了

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int o,o1,a[205],b[205],c[205];
string s;
void add()//高精加
{
   
	int t=0;
	for(int i=200;i>=1;i--)
	{
   
		c[i]=(t+a[i]+b[i])%10;
		t=(a[i]+b[i]+t)/10;
	}
}
int main()
{
   
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	getline(cin,s);
	int len=s.size(),ok=0;
	for(int i=len-1;i>=0;i--)//取数
	if(s[i]!=' ')
	{
   
		if(s[i]!='+'&&ok==0){
   o++;a[201-o]=s[i]-48;}
		if(s[i]=='+')ok=1;
		if(s[i]!='+'&&ok==1){
   o1++;b[201-o1]=s[i]-48;}
	}
	add();//相加
	int j=1;
	while(c[j]==0)j++;//处理0
	ok=0;
	if(200-j+1==9)//特判
	{
   
	 	if(c[j]!=1)ok=1;
	 	for(int i=j+1;i<=200;i++)if(c[i]!=0){
   ok=1;break;} 
	}
	if(200-j+1>9)ok=1;
	if(ok==1)printf("Large");//输出
	else for(int i=j;i<=200;i++)printf("%d",c[i]);
	return 0;
}

2.Problem 2. 小 X 的密码破译

Input file: password.in
Output file: password.out
Time limit: 1 second
Memory limit: 256 MB

这天小 Y 有事外出，小 X 又忘记带电脑了，于是想使用小 Y 的电脑。不幸的是，小 Y 设了密码，
密码提示是四个整数，且输错后密码和提示就会重新生成。
正当小 X 一筹莫展的时候，他打开小 Y 的抽屉，发现里面有一张小纸条，上面写着：“给出提示
n, a, b, c，令 di = (ai2 + bi + c) mod 11111111(1 ≤ i ≤ n)，将序列 d 去除重复的数后从小到大排序得到
序列 e，设序列 e 有 m 个数，则密码为 (∑mi=1 iei) mod 11111111。”
小 X 十分激动，想立刻完成密码破译，希望你帮帮他。

Input
第一行包含四个整数 n, a, b, c。

Output
第一行包含一个整数，表示密码。

Example

password.in password.out
3 0 0 2
2

5 1 2 3
380

Scoring
• 对于 30% 的数据，n ≤ 103。 • 对于 60% 的数据，n ≤ 105。 • 对于 100% 的数据，1 ≤ n ≤ 107，0 ≤ a, b, c ≤ 100。

题意分析
这题就是给你一些数，然后按照它的提示模拟
注意：∑mi=1 iei 是 指for(int i=1;i<=m;i++)e[i]乘i;

解题思路
一遍一遍模拟

AC代码

#include<cstdio>
using namespace std;
const long long MOD=11111111;
long long n,a,b,c,s,n1,d[10000005],f[MOD+5];
int main()
{
   
	freopen("password.in","r",stdin);
	freopen("password.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
	for(int i=1;i<=n;i++)//暴力模拟
	{
   
		long long o=(i%MOD)*(i%MOD)%MOD;
		f[((a%MOD)*(o%MOD)%MOD+(b%MOD)*(i%MOD)%MOD+c)%MOD]=1;
	}
	for(int i=0;i<=MOD;i++)if(f[i]==1)d[++n1]=i;//模拟
	for(int i=1;i<=n1;i++)//模拟
	  s=((d[i]%MOD)*(i%MOD)%MOD+s)%MOD;
	printf("%lld",s%MOD);  
	return 0;
}

3.Problem 3. 小 X 的液体混合

Input file: mixture.in
Output file: mixture.out
Time limit: 1 second
Memory limit: 256 MB

虽然小 X 不喜欢化学原理，但他特别喜欢把一大堆液体倒在一起。
现在小 X 有 n 种液体，其中 m 对会发生反应。现在他想把这 n 种液体按某种顺序倒入一个容器
内，让他获得最刺激的体验，也就是使危险系数尽量大。
我们可以这样计算危险系数，一开始容器内没有任何液体，危险系数为 1。每次液体倒入容器时，
若容器内已有一种或多种液体会与这种液体发生反应，则危险系数会乘 2，否则危险系数不变。
最大危险系数小 X 不会算，希望你帮帮他。

Input
第一行包含两个整数 n, m。
接下来 m 行，每行包含两个整数 a, b，表示液体 a 和液体 b 会发生反应。

Output
第一行包含一个整数，表示最大危险系数。

Example

mixture.in mixture.out
3 2
1 2
2 3
4

Scoring
• 对于 30% 的数据，n ≤ 10。 • 对于 100% 的数据，1 ≤ n ≤ 1000，a = b，同种反应不会出现多次。

题意分析
这题就是将液体倒在一起
求2发生反应次数

解题思路
这题我们可以用连通分块来做
求一共有多少个集合
答案为2n-集合个数
注意要用高精乘（位数弄多一点>400）

AC代码

#include<cstdio>
using namespace std;
int a,b,o,n,m,c[2005],fa[1005];
int find(int x)//找祖先
{
   
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void gjc()//高精乘
{
   
	int t=0;
	for(int i=2000;i>=1;i--)
	{
   
		int x=c[i]*2+t;
		t=x/10;
		c[i]=x%10;
	}
}
int main()
{
   
	freopen("mixture.in","r",stdin);
	freopen("mixture.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
   
		scanf("%d%d",&a,&b);
		fa[find(a)]=find(b);//并查集求连通块
	}
	for(int i=1;i<=n;i++)
     if(fa[i]==i)o++;//连通块个数
    c[2000]=1; 
	for(int i=1;i<=n-o;i++)//乘2
	 gjc();
	int j=1;
	while(c[j]==0)j++;//高精度
	for(int i=j;i<=2000;i++)
	 printf("%d",c[i]); 
	return 0;
}

4.Problem 4. 小 X 的 AK 计划

Input file: plan.in
Output file: plan.out
Time limit: 1 second
Memory limit: 256 MB

在小 X 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 X 刚刷完
CodeChef，准备出来逛逛。
机房一条街有 n 个机房，第 i 个机房的坐标为 xi，小 X 的家坐标为 0。小 X 在街上移动的速度为
1，即从 x1 到 x2 所耗费的时间为 |x1 x2|。
每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 X 到达第 i 个机房后，可以花 ti 的时间
想题，然后瞬间 AK；当然，也可以过机房而不入。
小 X 现在只有 m 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多
少个机房 AK，希望你帮帮他。

Input
第一行包含两个整数 n, m。
接下来 n 行，每行包含两个整数 xi, ti。

Output
第一行包含一个整数，表示小 X 最多能 AK 的机房数量。

Example

plan.in plan.out
2 10
1 100
5 5

1

Scoring
• 对于 30% 的数据，n ≤ 20。 • 对于 60% 的数据，n ≤ 1000。 • 对于 100% 的数据，1 ≤ n ≤ 105，0 ≤ m, xi ≤ 1018，0 ≤ ti ≤ 109。

题意分析
有一条街道上面有n个机房
距离为 |x[i]-x[j]|
每个机房要用t[i]的时间AK
现在有m个时间
求最多AK几个机房

20分解题思路
dfs暴力

20代码

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,mmax,x[100005],t[100005],d[100005];
void dfs(long long xx,long long s,long long min)
{
   
	if(min<0)return;//时间为0就退出
	mmax=max(s,mmax);//找最多AK机房数
	if(mmax==n)return;
	for(long long i=1;i<=n;i++)//枚举每一个机房
	 if(d[i]==0)
	 {
   
	 	d[i]=1;
	 	long long y=abs(x[i]-xx)+t[i];
	 	if(y<=min)dfs(x[i],s+1,min-y);
	 	d[i]=0;
	 }
	return; 
}
int main()
{
   
	freopen("plan.in","r",stdin);
	freopen("plan.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++)
	 scanf("%lld%lld",&x[i],&t[i]);
	dfs(0,0,m);
	printf("%lld",mmax);
	return 0;
}

总结

这次比赛第二题没有发挥好
预估：100+100+30+30=260
实际：100+30+30+20=180
要多学会优化+剪枝

谢谢