NOIP模拟赛2016-10-22
|
题目名 |
东风谷早苗 |
西行寺幽幽子 |
琪露诺 |
上白泽慧音 |
|
源文件 |
robot.cpp/c/pas |
spring.cpp/c/pas |
iceroad.cpp/c/pas |
classroom.cpp/c/pas |
|
输入文件 |
robot.in |
spring.in |
iceroad.in |
classroom.in |
|
输出文件 |
robot.out |
spring.out |
iceroad.out |
classroom.out |
|
时间限制 |
1000MS |
1000MS |
1000MS |
1000MS |
|
内存限制 |
64MB |
128MB |
128MB |
128MB |
|
测试点 |
20 |
20 |
10 |
10 |
|
测试点分值 |
5 |
5 |
10 |
10 |
|
Problem 1 |
东风谷早苗(robot.cpp/c/pas) |
|
|
题目描述 |
在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为新型机器人，自然不会只单单执行一个命令，它可以执行命令串。对于输入的命令串，每一秒它会按照命令行动一次。而执行完命令串最后一个命令后，会自动从头开始循环。在0时刻时早苗将钢达姆放置在了(0,0)的位置，并且输入了命令串。她想要知道T秒后钢达姆所在的位置坐标。 |
|
|
输入格式 |
第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令 第2行：一个正整数T |
|
|
输出格式 |
第1行：两个整数，表示T秒时，钢达姆的坐标 |
|
|
输入样例 |
NSWWNSNEEWN 12 |
|
|
输出样例 |
-1 3 |
|
|
数据范围 |
对于60%的数据：T <= 500,000且命令串长度 <= 5,000 对于100%的数据：T <= 2,000,000,000且命令串长度<= 5,000 |
|
|
注意 |
向东移动，坐标改变改变为(X+1,Y); 向南移动，坐标改变改变为(X,Y-1); 向西移动，坐标改变改变为(X-1,Y); 向北移动，坐标改变改变为(X,Y+1); |
|
很水的模拟 每一串命令位置变化是一样的
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=5005; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int t,n,sx=0,sy=0,x=0,y=0,dx[300],dy[300]; char s[N]; int main(int argc, const char * argv[]){ freopen("robot.in","r",stdin); freopen("robot.out","w",stdout); scanf("%s%d",s+1,&t); dx['E']=1;dy['E']=0; dx['S']=0;dy['S']=-1; dx['W']=-1;dy['W']=0; dx['N']=0;dy['N']=1; n=strlen(s+1); for(int i=1;i<=n;i++){ sx+=dx[s[i]];sy+=dy[s[i]]; } int k=t/n,b=t%n; while(k--){x+=sx;y+=sy;} for(int i=1;i<=b;i++){ x+=dx[s[i]];y+=dy[s[i]]; } printf("%d %d",x,y); }
|
Problem 2 |
西行寺幽幽子(spring.cpp/c/pas) |
|
|
题目描述 |
在幻想乡，西行寺幽幽子是以贪吃闻名的亡灵。不过幽幽子可不是只会吃，至少她还管理着亡灵界。话说在幽幽子居住的白玉楼有一颗常年不开花的樱树——西行妖。幽幽子决定去收集人间的春度，聚集起来让西行妖开花。很快，作为幽幽子家园艺师的魂魄妖梦收集到了M个单位的春度。并且在这段时间里，幽幽子计算出要让西行妖开出一朵花需要N个单位的春度。现在幽幽子想要知道，使用所有的春度，能够让西行妖开出多少朵花。 |
|
|
输入格式 |
第1行：一个正整数M 第2行：一个正整数N N,M的位数不超过L，L的范围在题目后面给出 |
|
|
输出格式 |
第1行：一个整数ans，表示能开出花的朵数 |
|
|
输入样例 |
73861758 12471 |
|
|
输出样例 |
5922 |
|
|
数据范围 |
对于60%的数据：L <= 2,000且ans <= 2,000 对于100%的数据：L <= 20,000且ans <= 2,000,000,000 |
|
高精度除法 二分答案来试探
没用ll只有60分不开心，因为2e9+2e9还有*2e9都会溢出
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=2e4+5,INF=2e9; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct big{ ll l,d[N]; big(){l=1;} }; char s[N]; big a,b,c; bool check(big &a,big &b){//a>=b if(a.l>b.l) return 1; if(a.l<b.l) return 0; for(int i=a.l;i>=1;i--){ if(a.d[i]>b.d[i]) return 1; if(a.d[i]<b.d[i]) return 0; } return 1; } //void jian(big &a,big &b){ // int g=0,l=b.l; // for(int i=1;i<=l;i++){ // if(a.d[i]<b.d[i]){ // a.d[i+1]--; // a.d[i]+=10; // } // a.d[i]-=b.d[i]; // } // l++; // while(a.d[l]<0){a.d[l]+=10;a.d[l+1]--;l++;} // while(a.d[a.l]==0) a.l--; //} void cheng(big &a,ll b){ ll g=0,l=a.l; for(int i=1;i<=l;i++){ ll t=a.d[i]*b+g; a.d[i]=t%10; g=t/10; } l++; while(g){ a.d[l]=g%10; g/=10; l++; } a.l=l-1; } void cpy(big &a,big &b){//a<---b a.l=b.l; for(int i=b.l;i>=1;i--) a.d[i]=b.d[i]; } int main(){ freopen("spring.in","r",stdin); freopen("spring.out","w",stdout); scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++) a.d[len-i+1]=s[i]-'0'; a.l=len; //printf("l %d ",a.l);for(int i=a.l;i>=1;i--) printf("%c",a.d[i]+'0); scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=len;i++) b.d[len-i+1]=s[i]-'0'; b.l=len; if(!check(a,b)) printf("0"); else{ ll l=1,r=INF,ans=-1; while(l<=r){//printf("%d %d ",l,r); ll m=(l+r)/2; cpy(c,b); cheng(c,m); //printf("new l %d m %d ",c.l,m);for(int i=c.l;i>=1;i--) printf("%c",c.d[i]+'0');cout<<" "; if(check(a,c)){ans=max(ans,m);l=m+1;} else r=m-1; } printf("%d",ans); } }
|
Problem 3 |
琪露诺(iceroad.cpp/c/pas) |
|
|
题目描述 |
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。每一个格子都有一个冰冻指数A[i]，编号为0的格子冰冻指数为0。当琪露诺停留在那一格时就可以得到那一格的冰冻指数A[i]。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。开始时，琪露诺在编号0的格子上，只要她下一步的位置编号大于N就算到达对岸。 |
|
|
输入格式 |
第1行：3个正整数N, L, R 第2行：N+1个整数，第i个数表示编号为i-1的格子的冰冻指数A[i-1] |
|
|
输出格式 |
第1行：一个整数，表示最大冰冻指数。保证不超过2^31-1 第2行：空格分开的若干个整数，表示琪露诺前进的路线，最后输出-1表示到达对岸 |
|
|
输入样例 |
5 2 3 0 12 3 11 7 -2 |
|
|
输出样例 |
11 0 3 -1 |
|
|
数据范围 |
对于60%的数据：N <= 10,000 对于100%的数据：N <= 200,000 对于所有数据 -1,000 <= A[i] <= 1,000且1 <= L <= R <= N |
|
|
注意 |
此题采用Special Judge |
|
改了一下题目不要求路径
很明显DP，暴力的话n^2不行，然后想到了单调队列
对于i，用单调队列维护[i-r,i-l]，然后入队i-l+1
因为只要超过n，所以最优解最远到N+r-1
f[i]表示到i的话有一个问题，不知道i这个店能不能从0到达，所以倒着来，答案就是f[0]
比赛时直接把w序列给倒过来了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=4e5+5; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,l,r,w[N]; int f[N],q[N],head=1,tail=0; void dp(){ n=n+r-1; for(int i=1;i<=n/2;i++) swap(w[i],w[n-i+1]); for(int i=1;i<=n+1;i++){ while(head<=tail&&q[head]<i-r) head++; if(head>tail) f[i]=w[i]; else f[i]=f[q[head]]+w[i]; int nw=i-l+1; if(nw>=0) while(head<=tail&&f[q[tail]]<f[nw]) tail--; q[++tail]=nw; //printf("%d %d %d %d %d ",i,w[i],f[i],q[head],q[tail]); } } int main(){ freopen("iceroad.in","r",stdin); freopen("iceroad.out","w",stdout); n=read();l=read();r=read(); for(int i=0;i<=n;i++) w[i]=read(); dp(); printf("%d",f[n+1]); }
|
Problem 4 |
上白泽慧音(classroom.cpp/c/pas) |
|
|
题目描述 |
在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。 |
|
|
输入格式 |
第1行：两个正整数N,M 第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。 |
|
|
输出格式 |
第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。 第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。 |
|
|
输入样例 |
5 5 1 2 1 1 3 2 2 4 2 5 1 2 3 5 1 |
|
|
输出样例 |
3 1 3 5 |
|
|
数据范围 |
对于60%的数据：N <= 200且M <= 10,000 对于100%的数据：N <= 5,000且M <= 50,000 |
|
第一眼，并查集、
第二眼，有向？！强连通分量.........完了tarjan完全忘了
打了一下暴力不太好做就弃疗了
60：floyd传递闭包+并查集维护
应该想到的
PS：字典序最小就是集合中最小点最小
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=5005,M=5e4+5; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m,a,b,flag,d[N][N]; void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=d[i][j]||(d[i][k]&&d[k][j]); } int fa[N],mn[N],size[N]; inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main(int argc, const char * argv[]){ freopen("classroom.in","r",stdin); freopen("classroom.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++){ a=read();b=read();flag=read(); if(flag==1) d[a][b]=1; else d[a][b]=d[b][a]=1; } floyd(); for(int i=1;i<=n;i++) fa[i]=mn[i]=i,size[i]=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]&&d[j][i]){//printf("%d %d ",i,j); int x=find(i),y=find(j); if(x!=y){ fa[y]=x; mn[x]=min(mn[x],mn[y]); size[x]+=size[y];//printf("f %d %d %d ",x,y,size[x]); } } int mx=0,ans; for(int i=1;i<=n;i++){ if(size[i]>mx){mx=size[i];ans=i;} if(size[i]==mx&&mn[i]<mn[ans]) ans=i; } printf("%d ",size[ans]); for(int i=1;i<=n;i++) if(d[i][ans]&&d[ans][i]) printf("%d ",i); }
100分：tarjan求强连通分量
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N=5005,M=5e4+5; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct edge{ int v,ne; }e[M<<1]; int h[N],cnt=0; inline void add(int u,int v){ cnt++; e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt; } int n,m,a,b,flag; int dfn[N],low[N],belong[N],size[N],dfc,scc; int st[N],top=0; void dfs(int u){//printf("dfs %d ",u); dfn[u]=low[u]=++dfc; st[++top]=u; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ dfs(v); low[u]=min(low[u],low[v]); }else if(!belong[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ scc++; while(true){ int x=st[top--]; belong[x]=scc; size[scc]++; if(x==u) break; } } } int main(int argc, const char * argv[]){ freopen("classroom.in","r",stdin); //freopen("classroom.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++){ a=read();b=read();flag=read(); if(flag==1){add(a,b);} else {add(a,b);add(b,a);} } for(int i=1;i<=n;i++) if(!belong[i]) dfs(i); int mx=0,ans; for(int i=1;i<=n;i++) if(size[belong[i]]>mx){ mx=size[belong[i]];ans=belong[i]; } printf("%d ",mx); for(int i=1;i<=n;i++) if(belong[i]==ans) printf("%d ",i); }