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);
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；
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的路线。
T1:
直接模拟即可
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 5000
using namespace std;
int dx,dy;
int gx[]={,,-,};
int gy[]={,-,,};
//E S W N
int x,y;
int T;
char s[MAXN]; int main()
{
scanf("%s",s+);
scanf("%d",&T);
int len=strlen(s+);
for(int i=;i<=len;i++){
if('E'==s[i]){
dx+=gx[];
dy+=gy[];
}
else if('S'==s[i]){
dx+=gx[];
dy+=gy[];
}
else if('W'==s[i]){
dx+=gx[];
dy+=gy[];
}
else{
dx+=gx[];
dy+=gy[];
}
}
int q=T/len;
int p=T%len;
x+=(dx*q),y+=(dy*q);
if(p){
for(int i=;i<=p;i++){
if('E'==s[i]){
x+=gx[];
y+=gy[];
}
else if('S'==s[i]){
x+=gx[];
y+=gy[];
}
else if('W'==s[i]){
x+=gx[];
y+=gy[];
}
else{
x+=gx[];
y+=gy[];
}
}
}
printf("%d %d\n",x,y);
return ;
}
Code1
T2:
用矩阵快速幂优化，得公式
f x 1 0 1 f 3
(f x-1)=(1 0 0) ^ (x-3) * (f 2)
f x-2 0 1 0 f 1
时间复杂度O(T*logn)
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MOD 1000000007
#define ll long long
using namespace std;
struct Mat{
ll s[][];
Mat(){
memset(s,,sizeof(s));
}
friend Mat operator * (const Mat &A,const Mat &B){
Mat ret;
for(int i=;i<;i++){
for(int j=;j<;j++){
for(int k=;k<;k++){
ret.s[i][j]=(ret.s[i][j]+(A.s[i][k]*B.s[k][j])%MOD)%MOD;
}
}
}
return ret;
}
Mat operator = (const Mat &A){
for(int i=;i<;i++){
for(int j=;j<;j++){
s[i][j]=A.s[i][j];
}
}
}
};
int T;
Mat Power(Mat A,int p){
if(==p){
return A;
}
if(p&){
return Power(A*A,p>>)*A;
}
else{
return Power(A*A,p>>);
}
}
int main()
{
// freopen("data.in","r",stdin);
Mat A;
A.s[][]=,A.s[][]=,A.s[][]=;
A.s[][]=,A.s[][]=,A.s[][]=;
A.s[][]=,A.s[][]=,A.s[][]=;
scanf("%d",&T);
for(int i=;i<=T;i++){
int n;
scanf("%d",&n);
if(==n||==n||==n){
printf("1\n");
continue;
}
Mat t=Power(A,n-);
ll ans=(t.s[][]+t.s[][])%MOD;
ans=(ans+t.s[][])%MOD;
printf("%lld\n",ans);
}
return ;
}
Code2
T3:
这题就是个最短路，稍微修改下即可
我第一次用dijk写的，结果T了6个点
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 5005
#define MAXM 30005
#define INF 0x7f7f7f7f
using namespace std;
struct Node{
int s,u;
int d;
Node(int ss,int uu,int dd){
s=ss,u=uu,d=dd;
}
Node(){
s=u=;
d=INF;
}
friend bool operator < (const Node &p1,const Node &p2){
return (p1.d<p2.d);
}
friend bool operator > (const Node &p1,const Node &p2){
return !(p1.d<p2.d);
}
};
priority_queue<Node> q;
int d[][MAXN];
int V,E;
int s[MAXN];
int w[MAXN];
int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt;
int p[][MAXN];
// 0 not change 1 change
int Abs(int x){
return (x>)?x:-x;
}
void Add(int x,int y,int w){
Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;
//single edge
}
void dijk(){
d[][]=;
q.push(Node(,,));
while(!q.empty()){
Node t=q.top(); q.pop();
// now using t.s
int ds=(!t.s);
int x=t.u;
if(d[t.s][t.u]!=t.d){
continue;
}
//stay
if(!p[t.s][x]){
if(d[ds][x]>d[t.s][x]){
d[ds][x]=d[t.s][x];
q.push(Node(ds,x,d[ds][x]));
}
}
else{
if(d[ds][x]>d[t.s][x]+s[x]){
d[ds][x]=d[t.s][x]+s[x];
q.push(Node(ds,x,d[ds][x]));
}
}
for(int e=first[x];e;e=Next[e]){
int y=to[e];
int dw=W[e];
if(p[t.s][x]!=p[t.s][y]){
//0 white 1 black
//0->1 w-=delta w=max(w,0)
//1->0 w+=delta
if(!p[t.s][x]){
dw-=Abs(w[x]-w[y]);
dw=max(dw,);
}
else{
dw+=Abs(w[x]-w[y]);
}
}
if(d[ds][y]>d[t.s][x]+dw){
d[ds][y]=d[t.s][x]+dw;
q.push(Node(ds,y,d[ds][y]));
}
}
}
}
int main()
{
// freopen("data.in","r",stdin);
memset(d,0x7f,sizeof(d));
scanf("%d%d",&V,&E);
for(int i=;i<=V;i++){
scanf("%d",&p[][i]);
p[][i]=(!p[][i]);
}
for(int i=;i<=V;i++){
scanf("%d",&w[i]);
}
for(int i=;i<=V;i++){
scanf("%d",&s[i]);
}
for(int i=;i<=E;i++){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
Add(x,y,k);
}
dijk();
int ans=min(d[][V],d[][V]);
printf("%d\n",ans);
return ;
}
Code3
后来改用SPFA，AC了
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 5005
#define MAXM 30005
#define INF 0x7f7f7f7f
using namespace std;
struct Node{
int s,u;
int d;
Node(int ss,int uu,int dd){
s=ss,u=uu,d=dd;
}
Node(){
s=u=;
d=INF;
}
};
int d[][MAXN];
bool b[][MAXN];
queue<Node> q;
int V,E;
int s[MAXN];
int w[MAXN];
int first[MAXN],Next[MAXM],to[MAXM],W[MAXM],cnt;
int p[][MAXN];
// 0 not change 1 change
int Abs(int x){
return (x>)?x:-x;
}
void Add(int x,int y,int w){
Next[++cnt]=first[x]; first[x]=cnt; to[cnt]=y; W[cnt]=w;
//single edge
}
void SPFA(){
d[][]=;
b[][]=;
q.push(Node(,,));
while(!q.empty()){
Node t=q.front(); q.pop();
int S=t.s;
int ds=(!S);
int x=t.u;
b[S][x]=;
// now using t.s
//stay
if(!p[S][x]){
if(d[ds][x]>d[S][x]){
d[ds][x]=d[S][x];
if(!b[ds][x]){
b[ds][x]=;
q.push(Node(ds,x,d[ds][x]));
}
}
}
else{
if(d[ds][x]>d[S][x]+s[x]){
d[ds][x]=d[S][x]+s[x];
if(!b[ds][x]){
b[ds][x]=;
q.push(Node(ds,x,d[ds][x]));
}
}
}
for(int e=first[x];e;e=Next[e]){
int y=to[e];
int dw=W[e];
if(p[S][x]!=p[S][y]){
//0 white 1 black
//0->1 w-=delta w=max(w,0)
//1->0 w+=delta
if(!p[S][x]){
dw-=Abs(w[x]-w[y]);
dw=max(dw,);
}
else{
dw+=Abs(w[x]-w[y]);
}
}
if(d[ds][y]>d[S][x]+dw){
d[ds][y]=d[S][x]+dw;
if(!b[ds][y]){
b[ds][y]=;
q.push(Node(ds,y,d[ds][y]));
}
}
}
}
}
int main()
{
// freopen("data.in","r",stdin);
memset(d,0x7f,sizeof(d));
scanf("%d%d",&V,&E);
for(int i=;i<=V;i++){
scanf("%d",&p[][i]);
p[][i]=(!p[][i]);
}
for(int i=;i<=V;i++){
scanf("%d",&w[i]);
}
for(int i=;i<=V;i++){
scanf("%d",&s[i]);
}
for(int i=;i<=E;i++){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
Add(x,y,k);
}
SPFA();
int ans=min(d[][V],d[][V]);
printf("%d\n",ans);
return ;
}
Code4
可见SPFA效率比dijk高很多啊。。。