2020.10.16 【NOIP2014】普及组模拟赛总结

编号	题目
T1	小 X 的加法难题
T2	小 X 的密码破译
T3	小 X 的液体混合
T4	小 X 的 AK 计划

T1

思路

直接模拟
注意 L a r g e Large Large 的判断:

1. 第一个数或第二个数超过 1 0 8 10^8 108；
2. 和超过 1 0 8 10^8 108。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long a,b,c,tj,w;
string s;
int input()
{
	int dep=0;
	while(s[dep]!='+')   //读入+号前面的部分
	 {
	 	if('0'<=s[dep]&&s[dep]<='9')
	 	  a=a*10+s[dep]-48,tj++;
	 	if(tj>9)
	 	 {
	       cout<<"Large";
	       w=1;
	 	   return 0;
		 }
	 	dep++;
	 }
	if(a>100000000)
	 {
	    cout<<"Large";
	    w=1;
	 	return 0;
	 }
	dep++,tj=0;
	while(dep<=s.size())  //读入+号后面的部分
	 {
	 	if('0'<=s[dep]&&s[dep]<='9')
	 	  b=b*10+s[dep]-48,tj++;
	 	if(tj>9)
	 	 {
	       cout<<"Large";
	       w=1;
	 	   return 0;
		 }
	 	dep++;
	 }
	if(b>100000000)
	 {
	    cout<<"Large";
	    w=1;
	 	return 0;
	 }
	return a+b;
}
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	getline(cin,s);
	c=input();
	if(w==1)
	  return 0;
	if(c>100000000)
	  cout<<"Large";
	else
	  cout<<c;
	return 0;
}

T2

思路

直接模拟
注意点：

1. 要开 l o n g   l o n g long~long long long;
2. 数组要开 b o o l bool bool 类型;
3. 算密码从 0 0 0 开始算：当 a = 0 , b = 0 , c = 0 a=0,b=0,c=0 a=0,b=0,c=0， d d d_i = 0 =0 =0， e e e 数组会存到 0 0 0 号下标。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int P=11111111;
long long n,a,b,c,ans,js=1;
long long d[P+1];
bool e[P+1];
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++)
	 {
	   d[i]=(a*i*i%P+b*i%P+c)%P;
	   e[d[i]]=1;
	 }
	for(int i=0; i<=P; i++)
	 if(e[i]!=0)
	   ans=(ans+js*i)%P,js++;
	cout<<ans;
	return 0;
}

T3

思路

对于一个连通块，
我们加入的第一种液体一定不会使危险系数乘 2，
之后我们从这种液体出发dfs，
只要按遍历顺序加入其他液体，
每次加入都能使危险系数乘 2。
注意计算答案时要用到高精度乘法。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,m,x,y,js,wss=1;
long long gjc[101000],h[100100],c[100100];
long long tot;
struct node
{
	long long y,next;
}a[100100];
void add(long long x,long long y)
{
	a[++tot].y=y;
	a[tot].next=h[x];
	h[x]=tot;
}
void jgjc()
{
	int tj=0;
	for(long long i=1; i<=wss; i++)
	 {
	 	gjc[i]=gjc[i]*2+tj;
	 	tj=gjc[i]/10;
	 	gjc[i]%=10;
	 }
	if(tj!=0)
	  gjc[++wss]=tj;
}
void dfs(long long x)
{
	c[x]=1;
	for(long long i=h[x]; i; i=a[i].next)
	 {
	 	long long y=a[i].y;
	 	if(c[y]==0)
	 	 {
	 	 	dfs(y);
	 	 	jgjc();
		 }
	 }
}
int main()
{
	freopen("mixture.in","r",stdin);
	freopen("mixture.out","w",stdout);
	cin>>n>>m;
	for(int i=1; i<=m; i++)
	 {
	 	scanf("%lld%lld",&x,&y);
	 	add(x,y);
	 	add(y,x);
	 }
	gjc[1]=1;
    for(int i=1; i<=n; i++)
     if(c[i]==0)  //没跑过的才跑
       dfs(i);
    for(int i=wss; i>=1; i--)
       printf("%lld",gjc[i]);
	return 0;
}

T4

思路

首先按照当前地点到家的距离排序。
并建立一个大根用来维护 1 1 1 ~ i − 1 i-1 i−1 的AK所需时间。
然后遍历排好序的数据，要是这个房间能 AK ，那就加上AK时间。
要是这个机房时间不够了，就从 1 1 1 ~ i − 1 i-1 i−1 那里找一个时间最大的AK，
把时间拿回来给这个机房AK。在这个过程中，要不断取 max ⁡ \max max。
在决策过程中，要是出现就算怎么反还时间也不够的话，说明后面的所有机房都AK不了，
所以直接结束循环即可。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define pi pair<long long,long long>
#define ai make_pair
using namespace std;
priority_queue<pi>q;
long long n,m,now_t,js,ans;
struct node
{
	long long x,t;
}a[1000010];
bool cmp(const node&a,const node&b)
{
	return a.x<b.x;
}
int main()
{
	freopen("plan.in","r",stdin);
	freopen("plan.out","w",stdout);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
       scanf("%lld%lld",&a[i].x,&a[i].t);
	sort(a+1,a+1+n,cmp);
	for(int i=1; i<=n; i++)
	 {
	 	now_t+=a[i].x-a[i-1].x;    //距离所需时间
	 	js++;   //AK机房++
	 	q.push(ai(a[i].x,a[i].t));
	 	now_t+=a[i].t;
	 	while(now_t>m&&q.size()!=0)   //返还时间（大根堆堆头是最大的）
	 	 {
	 	 	js--;
	 	    now_t-=q.top().second;
	 	    q.pop();
		 }
		if(now_t>m)
		  break;
		ans=max(ans,js);
	 }
	cout<<ans;
	return 0;
}