CF807

这就没什么说的了，好好读题就行。

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n;
 9     cin>>n;
10     int a1,b1,a2,b2;
11     int ok=5;
12     cin>>a1>>b1;
13     if(a1!=b1) ok=0;
14     for(int i=1;i<n;i++)
15     {
16         cin>>a2>>b2;
17         if(a2!=b2) ok=0;
18         if(ok==5&&a1<a2) ok=1;
19         a1=a2;
20         b1=b2;
21     }
22     if(ok==1) puts("unrated");
23     if(ok==0) puts("rated");
24     if(ok==5) puts("maybe");
25 }

水

CodeForces - 807B

每一步转移时两种决策，加100或者减50

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<bits/stdc++.h>
 4 using namespace std;
 5 const int maxn=2000010;
 6 int vis[maxn];
 7 int p,x,y;
 8 int check(int n)
 9 {
10     int i=(n/50)%475;
11     int ct=0;
12     for(;ct<25;ct++)
13     {
14         i=(i*96+42)%475;
15         if(i+26==p) return 1;
16     }
17     return 0;
18 }
19 
20 struct node
21 {
22     int x,d;
23     bool operator<(const node &f)const
24     {
25         return d>f.d;
26     }
27 }now,nex;
28 
29 int bfs()
30 {
31     int ans=1e9;
32     memset(vis,0,sizeof(vis));
33     now.x=x;
34     now.d=0;
35     vis[x]=1;
36     priority_queue<node> q;
37     q.push(now);
38     while(!q.empty())
39     {
40         now=q.top();
41         q.pop();
42         int xx=now.x;
43         if(check(xx)) return now.d;
44         if(xx-50>=y&&!vis[xx-50])
45         {
46             nex.x=now.x-50;
47             nex.d=now.d;
48             vis[xx-50]=1;
49             q.push(nex);
50         }
51         if(!vis[xx+100])
52         {
53             nex.x=now.x+100;
54             vis[xx+100]=1;
55             nex.d=now.d+1;
56             q.push(nex);
57        }
58     }
59     return ans;
60 }
61 
62 int main()
63 {
64 
65     cin>>p>>x>>y;
66     int ok=bfs();
67     if(ok==1e9) printf("-1
");
68     else printf("%d
",ok);
69 
70 }

bfs

CodeForces - 807C

由题意可得，

(x+a)/(y+b)=p/q

x+a=k*p , y+b=k*q

a=k*p-x , b=k*q-y

我们要求的是b的最小值，显然b关于k单调，二分查找k的最小值即可。

（第一反应是扩展欧几里得-_-||）

 1 #include <cstdio>
 2 #include <cstring>
 3 #define LL long long
 4 
 5 int main()
 6 {
 7     int n;
 8     int x,y,p,q;
 9     scanf("%d",&n);
10     while(n--)
11     {
12         scanf("%d%d%d%d",&x,&y,&p,&q);
13         LL l=0,r=0x3f3f3f3f;
14         LL ans=-1;
15         while(l<=r)
16         {
17             LL m=(l+r)/2;
18             LL a=m*p-x;
19             LL b=m*q-y;
20             if(a>=0&&b>=0&&a<=b)
21             {
22                 r=m-1;
23                 ans=b;
24             }
25             else l=m+1;
26         }
27         printf("%lld
",ans);
28     }
29 }

二分