2017-8-20 NOIP模拟赛

by coolyangzc

共3道题目，时间3.5小时

题目名

机器人

数列

虫洞

源文件

robot.cpp/c/pas

seq.cpp/c/pas

holes.cpp/c/pas

输入文件

robot.in

seq.in

holes.in

输出文件

robot.out

seq.out

holes.out

时间限制

1000MS

1000MS

1000MS

内存限制

256MB

256MB

256MB

测试点

20

10

10

测试点分值

5

10

10

评测环境

操作系统：Windows XP SP3

CPU: Pentium(R) Dual-Core CPU E5300 @ 2.60Ghz(2CPUs)

系统内存：2GB

Problem 1 机器人(robot.cpp/c/pas)

【题目描述】

早苗入手了最新的Gundam模型。最新款自然有着与以往不同的功能，那就是它能够自动行走，厉害吧。

早苗的新模型可以按照输入的命令进行移动，命令包括‘E’、‘S’、‘W’、‘N’四种，分别对应东南西北。执行某个命令时，它会向对应方向移动一个单位。作为新型机器人，它可以执行命令串。对于输入的命令串，每一秒它会按命令行动一次。执行完命令串的最后一个命令后，会自动从头开始循环。在0时刻时机器人位于（0,0）。求T秒后机器人所在位置坐标。

【输入格式】

第1行：一个字符串，表示早苗输入的命令串，保证至少有1个命令

第2行：一个正整数T

【输出格式】

2个整数，表示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
#include
#include

#define N 5001

using namespace std;
char s[N],c[N];
int n,m,ans,cnt1,cnt2,cnt3,cnt4,sx,sy;
long long t,x,y,len;

int main()
{
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
scanf("%s",s);len=strlen(s);
cin>>t;
x=t/len;y=t-x*len;
for(int i=;icnt2?(cnt1-cnt2):;
s2=cnt2>cnt1?(cnt2-cnt1):;
s3=cnt3>cnt4?(cnt3-cnt4):;
s4=cnt4>cnt3?(cnt4-cnt3):;
s1*=x,s2*=x,s3*=x,s4*=x;
sx+=s1-s2;sy+=s3-s4;
for(int i=;i<y;i++)
{
if(s[i]=='E') ++sx;
if(s[i]=='W') --sx;
if(s[i]=='S') --sy;
if(s[i]=='N') ++sy;
}
printf("%d %d\n",sx,sy);
fclose(stdin);fclose(stdout);
return ;
}

Problem 2 数列(seq.cpp/c/pas)

【题目描述】

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1]  (x>3)

求a数列的第n项对1000000007（10^9+7）取余的值。

【输入格式】

第一行一个整数T，表示询问个数。

以下T行，每行一个正整数n。

【输出格式】

每行输出一个非负整数表示答案。

【样例输入】

3

6

8

10

【样例输出】

4

9

19

【数据范围】

对于30%的数据 n<=100；

对于60%的数据 n<=2*10^7；

对于100%的数据 T<=100，n<=2*10^9；

/*
矩乘模板
0 0 0 1
0 0 1 0
a[i-1]=0*a[i]+1*a[i-1]+0*a[i-2]+)*a[i-3]
a[i]=1*a[i-1]+0*a[i-2]*1*a[i-3]+0*a[i-4]
*/
#include
#include
#include
#include
#include
#include

using namespace std;
const long long P=;
long long a[][],sum[][],k;
int T,flag;

void mul(long long x[][],long long y[][])//矩阵乘法，搬得快速幂的标程
{
long long c[][]={};
int i,j,k;
for(i=;i<=;i++)
for(j=;j<=;j++)
for(k=;k<=;k++)c[i][j]=(c[i][j]+x[i][k]*y[k][j])%P;
for(i=;i<=;i++)
for(j=;j<=;j++)x[i][j]=c[i][j];
}

int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
int i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&k);
if(k<=)//特判 { printf("1\n"); continue; } k-=;//注意乘方的次数要-3 memset(a,,sizeof(a));//注意每次重置转移矩阵 a[][]=a[][]=a[][]=a[][]=a[][]=; flag=false; while(k)//快速幂 { if(k%) { if(!flag) { for(i=;i<=;i++) for(j=;j<=;j++)sum[i][j]=a[i][j]; flag++; } else mul(sum,a); } k>>=;
if(k)mul(a,a);
}
long long s=((sum[][]+sum[][])%P+sum[][])%P;//由手推得
cout<<s<<endl;
}
return ;
}

Problem 3 虫洞(holes.cpp/c/pas)

【题目描述】

N个虫洞，M条单向跃迁路径。从一个虫洞沿跃迁路径到另一个虫洞需要消耗一定量的燃料和1单位时间。虫洞有白洞和黑洞之分。设一条跃迁路径两端的虫洞质量差为delta。

1.从白洞跃迁到黑洞，消耗的燃料值减少delta，若该条路径消耗的燃料值变为负数的话，取为0。

2.从黑洞跃迁到白洞，消耗的燃料值增加delta。

3.路径两端均为黑洞或白洞，消耗的燃料值不变化。

作为压轴题，自然不会是如此简单的最短路问题，所以每过1单位时间黑洞变为白洞，白洞变为黑洞。在飞行过程中，可以选择在一个虫洞停留1个单位时间，如果当前为白洞，则不消耗燃料，否则消耗s[i]的燃料。现在请你求出从虫洞1到N最少的燃料消耗，保证一定存在1到N的路线。

【输入格式】

第1行：2个正整数N,M

第2行：N个整数，第i个为0表示虫洞i开始时为白洞，1表示黑洞。

第3行：N个整数，第i个数表示虫洞i的质量w[i]。

第4行：N个整数，第i个数表示在虫洞i停留消耗的燃料s[i]。

第5..M+4行：每行3个整数，u,v,k，表示在没有影响的情况下，从虫洞u到虫洞v需要消耗燃料k。

【输出格式】

一个整数，表示最少的燃料消耗。

【样例输入】

4 5

1 0 1 0

10 10 100 10

5 20 15 10

1 2 30

2 3 40

1 3 20

1 4 200

3 4 200

【样例输出】

130

【数据范围】

对于30%的数据： 1<=N<=100,1<=M<=500

对于60%的数据： 1<=N<=1000,1<=M<=5000

对于100%的数据： 1<=N<=5000，1<=M<=30000

其中20%的数据为1<=N<=3000的链

1<=u,v<=N, 1<=k,w[i],s[i]<=200

【样例说明】

按照1->3->4的路线。

/*
好题。
首先必须进行题目说明，如果当前在白洞，要走白洞->黑洞这条路，那么走过去后黑洞就摆成了白洞，但花费还是白洞到黑洞的花费。
最短路模型 因为可以不走，所以考虑拆点，把一个点拆成黑白两点，不动的情况就可以搞。
当前为白到黑，就连白到白(走过去改变)，权值为白到黑的权值。
后面同理。
*/

#include
#include
#include
#include

#define N 10007
#define M 300007

using namespace std;
int head[M],q[M],col[N],head2[M],si[N],w[N];
int cnt1,n,m,ans,cnt;
bool inq[N];long long d[N];
struct edge
{
int u,v,next,dis;
}e[M];
struct node
{
int u,v,next,dis;
}ed[M];

inline int read()
{
int x=,f=;char c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();} while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}

inline void add(int u,int v,int dis)
{
e[++cnt].v=v;e[cnt].dis=dis;e[cnt].next=head[u];head[u]=cnt;
}

inline void add2(int u,int v,int dis)
{
ed[++cnt1].v=v;ed[cnt1].dis=dis;ed[cnt1].next=head2[u];head2[u]=cnt1;
}

void dfs(int x)
{
add(x,x+n,si[x]);//起点连边
add(x+n,x,);
for(int i=head2[x];i;i=ed[i].next)
{
int v=ed[i].v;
int del=abs(w[x]-w[v]);
if(col[x]!=col[v])
{
add(x,v,ed[i].dis+del);
add(x+n,v+n,max(,ed[i].dis-del));
}
else
{
add(x,v+n,ed[i].dis);
add(x+n,v,ed[i].dis);
}
}
}

void spfa()
{
memset(d,,sizeof d);
int he=,ta=;
if(col[]){q[]=;d[]=;inq[]=;}
else {q[]=n+;d[n+]=;inq[n+]=;}
while(he!=ta)
{
int now=q[he];he++;if(he==) he=;
for(int i=head[now];i;i=e[i].next)
{
int v=e[i].v;
if(d[v]>d[now]+e[i].dis)
{
d[v]=d[now]+e[i].dis;
if(!inq[v])
{
inq[v]=,q[ta++]=v;
if(ta==) ta=;
}
}
}inq[now]=;
}printf("%I64d",min(d[n],d[n+n]));
}

int main()
{
freopen("holes.in","r",stdin);
freopen("holes.out","w",stdout);
int x,y,z;
n=read();m=read();
for(int i=;i<=n;i++) col[i]=read();
for(int i=;i<=n;i++) w[i]=read();
for(int i=;i<=n;i++) si[i]=read();
for(int i=;i<=m;i++)
{
x=read();y=read();z=read();
add2(x,y,z);
}
for(int i=;i<=n;i++) dfs(i);
spfa();
fclose(stdin);fclose(stdout);
return ;
}

/*得分:100+60+0…=160
生无可恋。
不想说什么了，矩阵乘法不熟，T2只敢打暴力。T3读完后认定了题目描述有误，然后就坚定地没有写……搞了半天是题目没读懂。这是能力问题……做题少啊！如果读懂了我也是做不出来的…因为我想到dp上去了……呜呜呜……
今天高一的孩孩儿们来学校了。
加油 加油！*/

conclusion