NOIP 2014
水题模拟赛
（请选手务必仔细阅读本页内容）
一．题目概况
| 中文题目名称 |
数列 |
刷漆 |
排队 |
| 英文题目与子目录名 |
seq |
paint |
layout |
| 可执行文件名 |
seq |
paint |
layout |
| 输入文件名 |
seq.in |
paint.in |
layout.in |
| 输出文件名 |
seq.out |
paint.out |
layout.out |
| 每个测试点时限 |
2 秒 |
1 秒 |
1 秒 |
| 测试点数目 |
10 |
10 |
10 |
| 每个测试点分值 |
10 |
10 |
10 |
| 附加样例文件 |
无 |
无 |
无 |
| 结果比较方式 |
全文比较（过滤行末空格及文末回车） |
||
| 题目类型 |
传统 |
传统 |
传统 |
| 运行内存上限 |
128M |
128M |
128M |
二．提交源程序文件名
| 对于 C++语言 |
seq.cpp |
paint.cpp |
layout.cpp |
| 对于 C 语言 |
seq.c |
paint.c |
layout.c |
| 对于 pascal 语言 |
seq.pas |
paint.pas |
layout.pas |
三．编译命令（不包含任何优化开关）
| 对于 C++语言 |
g++ -o seq seq.cpp -lm |
g++ -o paint paint.cpp –lm |
g++ -o layout layout.cpp -lm |
| 对于 C 语言 |
gcc -o seq seq.c -lm |
gcc -o paint paint.c –lm |
gcc-o layout layout.c -lm |
| 对于 pascal 语言 |
fpc seq.pas |
fpc paint.pas |
fpc layout.pas |
注意事项：
1、文件名（程序名和输入输出文件名）必须使用英文小写。
2、C/C++中函数 main()的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
3、统一评测时采用的机器配置为：CPU Intel64 Family 6 Model 37 Stepping 5 GenuineIntel ~1199Mhz，内存 4G，上述时限以此配置为准。
5、特别提醒：评测在 Microsoft Windows Technical Preview (Build 9860)下进行。
1．数列
(seq.cpp/c/pas)
【题目描述】
Czy手上有一个长度为n的数列，第i个数为xi。
他现在想知道，对于给定的a,b,c，他要找到一个i，使得a*(i+1)*xi2+(b+1)*i*xi+(c+i)=0成立。
如果有多个i满足，Czy想要最小的那个i。
Czy有很多很多组询问需要你回答，多到他自己也不确定有多少组。所以在输入数据中a=b=c=0标志着Czy的提问的结束。
更加糟糕的是，Czy为了加大难度，决定对数据进行加密以防止离线算法的出现。
假设你在输入文件中读到的三个数为a0,b0,c0，那么Czy真正要询问的a=a0+LastAns,b=b0+LastAns,c=c0+LastAns.
LastAns的值是你对Czy的前一个询问的回答。如果这是第一个询问，那么LastAns=0。
所有的询问都将会按上述方式进行加密，包括标志着询问的结束的那个询问也是这样。
【输入】
输入文件为 seq.in
输入文件第一行包含一个整数n，表示数列的长度。
输入文件第二行包含n个整数，第i个数表示xi的值。
接下来若干行，每行三个数，表示加密后的a,b,c值（也就是上文所述的a0,b0,c0）
【输出】
输出文件为 seq.out
包含若干行，第i行的值是输入文件中第i个询问的答案。注意，你不需要对标志着询问结束的那个询问作答。
同时，标志着询问结束的询问一定是输入文件的最后一行。也就是，输入文件不会有多余的内容。
【输入输出样例】
| seq.in |
seq.out |
| 5 -2 3 1 -5 2 -5 -4 145 -1 -6 -509 -9 -14 40 -3 -13 21 -3 -3 -3 |
5 4 3 3 |
【数据范围】
对于40%的数据，满足N<=1000，需要作出回答的询问个数不超过1000.
对于100%的数据，满足N<=50000，需要作出回答的询问个数不超过500000，xi的绝对值不超过30000，解密后的a的绝对值不超过50000，解密后的b的绝对值不超过10^8，解密后的c的绝对值不超过10^18.
#include<iostream> #include<cstdio> #define maxn 50010 using namespace std; int w[maxn],n,ans=-1; long long a,b,c; long long qread(){ long long i=0;int j=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')j=-1;ch=getchar();} while(ch<='9'&&ch>='0'){i=i*10+ch-'0';ch=getchar();} return i*j; } bool check(int i){ if((c+i)%w[i]!=0)return 0; long long r=-(c+i)/w[i]; r-=1LL*a*w[i]+i; if(r%i!=0)return 0; r/=i; long long l=1LL*a*w[i]+b; if(l==r)return 1; return 0; } int main(){ //freopen("Cola.txt","r",stdin); freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&w[i]); while(1){ a=qread();b=qread();c=qread(); if(ans!=-1)a=a+ans,b=b+ans,c=c+ans; if(a==0&&b==0&&c==0)break; for(int i=1;i<=n;i++){ if(check(i)){ ans=i; printf("%d\n",i); break; } } } return 0; }
/* 我们考虑最后一行，因为其代表文件结束，所以解密后的a=b=c=0。那么我们可以知道倒数第二行的答案（LastAns=-a=-b=-c）。那么原始式子即转换成一个简单的三元一次式子（只和a,b,c有关），然后这解密后的值又可以由上一行的答案和输入的a0,b0,c0得到，于是就变成了一个只和LastAns有关系的一元一次式子，所以又可以得到了上一行的答案。所以这样一直算回去就好了。 */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define pa pair<int,int> #define inf 1000000000 typedef int real; #define int long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,top,ans; int v[50005],res[500005]; int a[500005],b[500005],c[500005]; real main() { //freopen("seq.in","r",stdin); //freopen("seq.out","w",stdout); n=read(); for(int i=1;i<=n;i++)v[i]=read(); cnt=1; while(scanf("%I64d%I64d%I64d",&a[cnt],&b[cnt],&c[cnt])!=EOF)cnt++; cnt--; res[++top]=ans=-a[cnt--]; for(int k=cnt;k;k--) { int xi=v[ans],i=ans; int t1=a[k]*(i+1)*xi*xi+(b[k]+1)*i*xi+(c[k]+i); int t2=(i+1)*xi*xi+i*xi+1; ans=-t1/t2; res[++top]=ans; } for(int i=top-1;i;i--)printf("%I64d\n",res[i]); return 0; }
2．刷漆
(paint.cpp/c/pas)
【问题描述】
Czy做完了所有的回答出了所有的询问，结果是，他因为脑力消耗过大而变得更虚了:)。帮助Czy恢复身材的艰巨任务落到了你的肩上。
正巧，你的花园里有一个由N块排成一条直线的木板组成的栅栏，木板从左到右依次标号1到N。这N块木板中，有M块木板前面放着一桶油漆。油漆有不同的颜色，每种颜色可以由一个大写字母表示(A到Z)。而你要求Czy用他的油漆刷子给栅栏刷上油漆。
已知Czy会选择一个前方放有油漆桶的木板开始他的任务。刷子蘸上油漆后，他开始随机地沿着栅栏走，他不会走出栅栏的范围。随机地走表示Czy会沿着他选择的方向一直走，然后随机在任何时候改变方向。沿着栅栏走只有两个方向，向前和向后。
你发现Czy刷油漆的过程总是符合下列规则:
- 每个油漆桶里装着无限多的油漆；
- 刷子上每次只有一种颜色的油漆，每次蘸油漆都会完全替换刷子上的油漆颜色；
- 当Czy走到一个油漆桶前，他会首先用刷子蘸这个油漆桶里的油漆；
- Czy每走过一个木板都会将这个木板刷成当前刷子上的油漆颜色。
已知木板可以被多次刷上油漆，每次都会完全覆盖之前的颜色。当所有木板都被刷上了油漆的时候，Czy才能停下来(当然他也可以继续刷到他想停下来为止)。你看着Czy在栅栏前来回舞动，突然想知道Czy停下来的时候栅栏有多少种可能的不同油漆方案。定义当至少有一块木板颜色不同时，两种油漆方案被视为是不同的。
请你输出不同的油漆方案数对109+9取模的值。
【输入】
输入文件为 paint.in。
输入的第一行包含两个整数N和M。
接下来M行，每行两个整数x和y，表示第y块木板前面有一个装着颜色为x的油漆的油漆桶。
【输出】
输出文件为 paint.out。
输出一行，包含一个整数，表示不同的油漆方案数对109 + 9取模的结果。
【输入输出样例】
| paint.in |
paint.out |
| 6 2 A 2 B 6 |
4 |
【数据范围】
对于30% 的数据，1 ≤ M ≤ N ≤ 100。
对于100% 的数据， 1 ≤ M ≤ N ≤ 100000。
x是A到Z之间的大写字母；1 ≤ y ≤ N。
/* 题目中有一个很重要的条件，当 Czy 走到一个油漆桶前，他会首先用刷子蘸这个油漆桶里的油漆，这就说明在两个紧挨着的油漆桶A,B之间的墙上，只有可能存在A,B两种颜色，而且两种颜色必须都是连续的，也就是有两块，那么，对于每一个这种区间都有len种方案，用分步乘法计数法则就可以了 */ #include<iostream> #include<cstdio> #include<algorithm> #define maxn 100010 #define mod 1000000009 using namespace std; int n,m; struct node{ int col,pos; bool operator < (const node b)const{ return pos<b.pos; } }a[maxn]; int main(){ //freopen("Cola.txt","r",stdin); freopen("paint.in","r",stdin); freopen("paint.out","w",stdout); scanf("%d%d",&n,&m); char ch;int x; for(int i=1;i<=m;i++){ getchar(); ch=getchar(); scanf("%d",&x); a[i].col=ch-'A'+1;a[i].pos=x; } sort(a+1,a+m+1); long long ans=1; for(int i=1;i<m;i++){ int len=a[i+1].pos-a[i].pos; if(a[i].col!=a[i+1].col&&len>=1){ ans=1LL*ans*len%mod; } } cout<<ans; return 0; }
3．排队
(layout.cpp/c/pas)
【问题描述】
Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸，编号为1至N。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。
因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值，MD个互相厌恶的妹纸对以及他们之间距离的最小值。
你的任务是计算在满足以上条件的前提下，帮助Czy计算出编号为1和编号为N的妹纸之间距离的最大可能值。
【输入】
输入文件为 layout.in。
第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 n,ML和DL ；
此后ML行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至多为D。
此后MD行，每行包含三个用空格分开的整数A,B和D，其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至少为D。
【输出】
输出文件名为 layout.out。
输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出-1。如果编号1和编号N的妹纸间距离可以任意，就输出-2 。否则输出他们之间的最大可能距离。
【输入输出样例】
| layout.in |
layout.out |
| 4 2 1 1 3 10 2 4 20 2 3 3 |
27 |
【数据范围】
对于40%的数据，N<=100；
对于100%的数据，N<=1000；ML,MN<=10000；D<=1000000。
/* 先跑了一遍最短路看有没有负环，又跑了一遍最长路求答案，T了 */ #include<iostream> #include<stack> #include<cstdio> using namespace std; #define maxn 1010 int n,p1,p2,num,head[maxn],dis[maxn],t[maxn]; bool vis[maxn],w[maxn]; struct node{ int to,v,pre; }e[maxn*(maxn-1)]; void Insert(int from,int to,int v){ e[++num].to=to; e[num].v=v; e[num].pre=head[from]; head[from]=num; } bool spfa(int s){ stack<int>q; for(int i=1;i<=n;i++)dis[i]=0x3fffffff; vis[1]=1;q.push(1);dis[1]=0;w[1]=1;t[1]++; while(!q.empty()){ int now=q.top();q.pop();vis[now]=0; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(dis[to]>dis[now]+e[i].v){ dis[to]=dis[now]+e[i].v; if(!vis[to]){ vis[to]=1; w[to]=1; t[to]++; if(t[to]>n)return 0; q.push(to); } } } } return 1; } void SPFA(int s){ stack<int>q; for(int i=1;i<=n;i++)dis[i]=-0x3fffffff; vis[1]=1;q.push(1);dis[1]=0; while(!q.empty()){ int now=q.top();q.pop();vis[now]=0; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(dis[to]<dis[now]+e[i].v){ dis[to]=dis[now]+e[i].v; if(!vis[to]){ vis[to]=1; q.push(to); } } } } } int main(){ freopen("layout.in","r",stdin); freopen("layout.out","w",stdout); scanf("%d%d%d",&n,&p1,&p2); int x,y,z; for(int i=1;i<=p1;i++){ scanf("%d%d%d",&x,&y,&z); Insert(x,y,z); } for(int i=1;i<=p2;i++){ scanf("%d%d%d",&x,&y,&z); Insert(y,x,-z); } int flag=spfa(1); if(flag==0)printf("-1"); else if(!w[n])printf("-2"); else { SPFA(1); printf("%d",dis[n]); } return 0; }