NOIP模拟赛20161022

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=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int t,n,sx=,sy=,x=,y=,dx[],dy[];
char s[N];
int main(int argc, const char * argv[]){
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
scanf("%s%d",s+,&t);
dx['E']=;dy['E']=;
dx['S']=;dy['S']=-;
dx['W']=-;dy['W']=;
dx['N']=;dy['N']=;
n=strlen(s+);
for(int i=;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=;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+,INF=2e9;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
struct big{
ll l,d[N];
big(){l=;}
};
char s[N];
big a,b,c;
bool check(big &a,big &b){//a>=b
if(a.l>b.l) return ;
if(a.l<b.l) return ;
for(int i=a.l;i>=;i--){
if(a.d[i]>b.d[i]) return ;
if(a.d[i]<b.d[i]) return ;
}
return ;
}
//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=,l=a.l;
for(int i=;i<=l;i++){
ll t=a.d[i]*b+g;
a.d[i]=t%;
g=t/;
}
l++;
while(g){
a.d[l]=g%;
g/=;
l++;
}
a.l=l-;
}
void cpy(big &a,big &b){//a<---b
a.l=b.l;
for(int i=b.l;i>=;i--) a.d[i]=b.d[i];
}
int main(){
freopen("spring.in","r",stdin);
freopen("spring.out","w",stdout);
scanf("%s",s+);
int len=strlen(s+);
for(int i=;i<=len;i++) a.d[len-i+]=s[i]-'';
a.l=len; //printf("l %d\n",a.l);for(int i=a.l;i>=1;i--) printf("%c",a.d[i]+'0);
scanf("%s",s+);
len=strlen(s+);
for(int i=;i<=len;i++) b.d[len-i+]=s[i]-'';
b.l=len;
if(!check(a,b)) printf("");
else{
ll l=,r=INF,ans=-;
while(l<=r){//printf("%d %d\n",l,r);
ll m=(l+r)/;
cpy(c,b);
cheng(c,m); //printf("new\nl %d m %d\n",c.l,m);for(int i=c.l;i>=1;i--) printf("%c",c.d[i]+'0');cout<<"\n";
if(check(a,c)){ans=max(ans,m);l=m+;}
else r=m-;
}
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+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,l,r,w[N];
int f[N],q[N],head=,tail=;
void dp(){
n=n+r-;
for(int i=;i<=n/;i++) swap(w[i],w[n-i+]);
for(int i=;i<=n+;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+;
if(nw>=) while(head<=tail&&f[q[tail]]<f[nw]) tail--;
q[++tail]=nw;
//printf("%d %d %d %d %d\n",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=;i<=n;i++) w[i]=read();
dp();
printf("%d",f[n+]);
}



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=,M=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,a,b,flag,d[N][N];
void floyd(){
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;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=;i<=m;i++){
a=read();b=read();flag=read();
if(flag==) d[a][b]=;
else d[a][b]=d[b][a]=;
}
floyd();
for(int i=;i<=n;i++) fa[i]=mn[i]=i,size[i]=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(d[i][j]&&d[j][i]){//printf("%d %d\n",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\n",x,y,size[x]);
}
}
int mx=,ans;
for(int i=;i<=n;i++){
if(size[i]>mx){mx=size[i];ans=i;}
if(size[i]==mx&&mn[i]<mn[ans]) ans=i;
}
printf("%d\n",size[ans]);
for(int i=;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=,M=5e4+;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
struct edge{
int v,ne;
}e[M<<];
int h[N],cnt=;
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=;
void dfs(int u){//printf("dfs %d\n",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=;i<=m;i++){
a=read();b=read();flag=read();
if(flag==){add(a,b);}
else {add(a,b);add(b,a);}
}
for(int i=;i<=n;i++) if(!belong[i]) dfs(i);
int mx=,ans;
for(int i=;i<=n;i++) if(size[belong[i]]>mx){
mx=size[belong[i]];ans=belong[i];
}
printf("%d\n",mx);
for(int i=;i<=n;i++) if(belong[i]==ans) printf("%d ",i);
}
上一篇:(十七)迭代器模式详解(foreach的精髓)


下一篇:微信小程序开发系列教程三:微信小程序的调试方法