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);
}