Article From:https://www.cnblogs.com/to-the-end/p/9906465.html

1. Why not?

(whether.pas/c/cpp)

【Problem Description)

 

“ I have traveled bridges in many places, seen clouds many times, drank many kinds of wine, but only loved a person of the right age.——Shen Congwen

 

K bought a new machine model。As the latest machine model, of course, with a new function different from the past, that is, it can walk automatically!!! Great. (Okay, I’m self-respecting.) The new machine model can follow small.KGive the command string. For the given command string, it will act on the command once per second. After executing the last command of the command string, the machine model will automatically start the cycle from scratch. stay0 Moment Placed in(0,0)Location, and enter the command string. Want to KnowT The position coordinates of the machine model in seconds.

 

【Input]

The first line reads in a string to represent Enter the command string, to ensure that at least there are1 A command.
Second line read inA Positive IntegerT。

 

【Output]

One line, outputTwo IntegersTIn seconds, the coordinates of the machine model.

 

【Input and Output Samples]

NSWWNSNEEWN

12

-1 3

 

 

【Data Scope]

100%Data: T< = 2,000,000,000 and command string length & lt; = 5,000

【Attention]

Moving eastward, coordinates changed to(X+1,Y);

Moving southward, coordinates changed to(X,Y-1);

Moving westward, coordinates changed to(X-1,Y);

Move northward, coordinates changed to(X,Y+1);

Official Interpretation:

  Observed topic, obviously, this is a very simple simulation.
  But the simulation is too slow. We can make it faster.
  First run a cycle, record its displacement at the end of the cycle, then compare its time with the time required for the cycle, skip all the cycles directly, then run a broken cycle, or find the displacement directly, add the answer directly.
  Is it very simple?

  (Yeah, it’s easy, but how do you skip the whole cycle???

My own BB’s problem:

  How to skip the cycle???

  Of course, the redundancy operation!!!

  I can figure out the commands that the entire command string integrates (for example, the entire command string requires you to take a few steps to North or South and East or West)* ((T-(T%strlen(s))/ strlen(s))(s denotes the length of the command string);

  Then the remaining commands are executed through the redundancy operation.

 

  Okay, code…

  

 1 #include<bits/stdc++.h>
 2 #define Re register int 
 3 using namespace std;
 4 long long T,Len,E,S,W,N,t,x,y;
 5 char s[5005];
 6 int main(){
 7     Re i,j;
 8     scanf("%s",s);scanf("%lld",&T);
 9     Len=strlen(s);
10     if (T<=Len){
11         for (i=0;i<Len;i++){
12             if (s[i]=='E') E++;
13             if (s[i]=='W') W--;
14             if (s[i]=='N') N++;
15             if (s[i]=='S') S--;    
16         }
17         printf("%lld %lld",E+W,N+S);
18         return 0;
19     }//In fact, the first judgment is pure boredom.
20     for (i=0;i<Len;i++){
21         if (s[i]=='E') E++;
22         if (s[i]=='W') W--;
23         if (s[i]=='N') N++;
24         if (s[i]=='S') S--;    
25     }
26     x=E+W;y=N+S; t=int(T/Len); x*=t; y*=t;
27     E=W=N=S=0;
28     for (i=0;i<T%Len;i++){
29         if (s[i]=='E') E++;
30         if (s[i]=='W') W--;
31         if (s[i]=='N') N++;
32         if (s[i]=='S') S--;
33     }
34     printf("%lld %lld",x+E+W,y+N+S);
35     return 0;
36 }

View Code

 

  2.Twilight

  The second question is too horrible. What is this ghost? It turns number theory into graph theory.

  Give me a link: Alkri is invincible

  Give me a code…

  SPFAEdition

  

 1 //NOIPRP++
 2 #include<bits/stdc++.h>
 3 #define Re register int
 4 using namespace std;
 5 int X,Y,Z,Num,head[100005],vis[100005];
 6 long long H,dis[100005],ans;
 7 queue<int> q;
 8 struct Edge{
 9     int To,Next,w;
10 }edge[200005];
11 inline void AddNum(int u,int v,int w){
12     edge[++Num].Next=head[u];
13     edge[Num].To=v;
14     edge[Num].w=w;
15     head[u]=Num;
16 }
17 int main(){
18     Re i,j;
19     scanf("%lld%d%d%d",&H,&X,&Y,&Z);
20     for (i=0;i<X;i++) AddNum(i,(i+Y)%X,Y),AddNum(i,(i+Z)%X,Z);
21     memset(dis,63,sizeof(dis)); memset(vis,false,sizeof(vis));
22     dis[1%X]=1; vis[1%X]=true; q.push(1%X);
23     while (!q.empty()){
24         int Now=q.front(); q.pop(); vis[Now]=false;
25         for (i=head[Now];i;i=edge[i].Next){
26             int k=edge[i].To;
27             if (dis[k]>dis[Now]+edge[i].w){
28                 dis[k]=dis[Now]+edge[i].w;
29                 if (!vis[k]){
30                     vis[k]=true;
31                     q.push(k);
32                 }
33             }
34         }
35     }
36     for (i=0;i<X;i++) if (dis[i]<=H) ans+=(H-dis[i])/X+1;
37     printf("%lld",ans);
38     return 0;
39 }
40 //NOIPRP++

View Code

  dijkstraVersion, running slower than SPFA, metaphysics…

 1 //NOIPRP++
 2 #include<bits/stdc++.h>
 3 #define Re register int
 4 #define pa pair<int,int>
 5 using namespace std;
 6 int X,Y,Z,Num,head[100005],vis[100005];
 7 long long H,dis[100005],ans;
 8 priority_queue<pa , vector<pa> ,greater<pa> > q;
 9 struct Edge{
10     int To,Next,w;
11 }edge[200005];
12 inline void AddNum(int u,int v,int w){
13     edge[++Num].Next=head[u];
14     edge[Num].To=v;
15     edge[Num].w=w;
16     head[u]=Num;
17 }
18 int main(){
19     Re i,j;
20     scanf("%lld%d%d%d",&H,&X,&Y,&Z);
21     for (i=0;i<X;i++) AddNum(i,(i+Y)%X,Y),AddNum(i,(i+Z)%X,Z);
22     memset(dis,63,sizeof(dis)); memset(vis,false,sizeof(vis));
23     dis[1%X]=1; vis[1%X]=true; q.push(make_pair(dis[1%X],1%X));
24     while (!q.empty()){
25         int Now=q.top().second; q.pop(); vis[Now]=false;
26         for (i=head[Now];i;i=edge[i].Next){
27             int k=edge[i].To;
28             if (dis[k]>dis[Now]+edge[i].w){
29                 dis[k]=dis[Now]+edge[i].w;
30                 if (!vis[k]){
31                     vis[k]=true;
32                     q.push(make_pair(dis[k],k));
33                 }
34             }
35         }
36     }
37     for (i=0;i<X;i++) if (dis[i]<=H) ans+=(H-dis[i])/X+1;
38     printf("%lld",ans);
39     return 0;
40 }
41 //NOIPRP++

View Code

  Big Guy’s version runs fastest…

 1 #include<cstdio>
 2 #define ll long long
 3 #include<cstring>
 4 ll n,ans,t[100050];
 5 int x,y,z;
 6 int main(){
 7     scanf("%lld%d%d%d",&n,&x,&y,&z);
 8     if (y>z)y^=z,z^=y,y^=z;
 9     if (x>y)x^=y,y^=x,x^=y;
10     memset(t,-1,sizeof t);
11     if (x==1)t[0]=1;else t[1]=1;
12     for (int i=0;i<x;i++){
13         int lt=(i-y%x+x)%x,p=i;
14         while (t[lt]>0&&(t[lt]+y<t[p]||t[p]<0)){
15             t[p]=t[lt]+y;
16             lt=p;
17             p=(p+y%x)%x;
18         }
19     }
20     for (int i=0;i<x;i++){
21         int lt=(i-z%x+x)%x,p=i;
22         while (t[lt]>0&&(t[lt]+z<t[p]||t[p]<0)){
23             t[p]=t[lt]+z;
24             lt=p;
25             p=(p+z%x)%x;
26         }
27     }
28     for (int i=0;i<x;i++)if (t[i]>0&&t[i]<=n)ans+=(n-t[i])/x+1;
29     printf("%lld\n",ans);
30 }

View Code

 

 

 

Link of this Article: NOIP Review Simulated Contest Day2

Leave a Reply

Your email address will not be published. Required fields are marked *