Codeforces Round #593 (Div. 2) 

第一次在学校打CF,和博哥一起打,九点半到十一点半,没想到回宿舍之后舍友都没睡。。。

总体来说这是一把体验比较刺激的CF,AB题很快切掉,C构造题结论猜错但是博哥立马切了,D题一眼大力模拟,在几近自闭之时,改了一些没开long long,没特判开局方向的错误后,在最后几分钟过掉了,直接从2000名左右跳到了300+名,但是由于提交次数过多,D的分比C少(什么破烂CF赛制),第二天早上起来发现很多人D被System Test给弄掉了,最后190+名苟且上紫。

博哥最后十几秒来了一发激情提交,但是由于某些变量未开long long而炸掉了,惨惨。

A

很讨厌又臭又长的英文题面,紧张的氛围之中静下心看题真是件难事。

贪心就完事了,两种策略,分别猛取其中一个方案,再尽可能取另一个方案,取个max

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define pii pair<int,int>
10 #define MP make_pair
11 using namespace std;
12 typedef long long ll;
13 int t,a,b,c,ans;
14 inline int read()
15 {
16     int x=0,f=1;
17     char c=getchar();
18     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
19     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
20     return f*x;
21 }
22 inline void write(int x)
23 {
24     if (x<0) putchar('-'),x=-x;
25     if (x>9) write(x/10);
26     putchar(x%10+'0');
27     return;
28 }
29 inline int solve()
30 {
31     int x,y,z,ret=0,tmp,sum;
32
33     sum=0;
34     x=a,y=b,z=c;
35     tmp=min(x,y/2);
36     sum+=3*tmp;
37     x-=tmp,y-=2*tmp;
38     tmp=min(y,z/2);
39     sum+=3*tmp;
40     ret=max(ret,sum);
41
42     sum=0;
43     x=a,y=b,z=c;
44     tmp=min(y,z/2);
45     sum+=3*tmp;
46     y-=tmp,z-=2*tmp;
47     tmp=min(x,y/2);
48     sum+=3*tmp;
49     ret=max(ret,sum);
50
51     return ret;
52 }
53 int main()
54 {
55     t=read();
56     while (t--)
57     {
58         a=read(),b=read(),c=read();
59         ans=solve();
60         write(ans),putchar('\n');
61     }
62     return 0;
63 }
View Code

B

快速幂直接完事$(2^m-1)^n$

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register ll i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register ll i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register ll j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define pii pair<ll,ll>
10 #define MP make_pair
11 using namespace std;
12 typedef long long ll;
13 const ll mod=1e9+7;
14 ll n,m,ans;
15 inline ll read()
16 {
17     ll x=0,f=1;
18     char c=getchar();
19     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
20     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
21     return f*x;
22 }
23 inline void write(ll x)
24 {
25     if (x<0) putchar('-'),x=-x;
26     if (x>9) write(x/10);
27     putchar(x%10+'0');
28     return;
29 }
30 inline ll qpow(ll x,ll y)
31 {
32     ll ret=1;
33     while (y)
34     {
35         if (y&1) ret=1LL*ret*x%mod;
36         y>>=1;
37         x=1LL*x*x%mod;
38     }
39     return ret;
40 }
41 int main()
42 {
43     n=read(),m=read();
44     m=qpow(2,m)-1;
45     m=(1LL*m+mod)%mod;
46     ans=qpow(m,n);
47     write(ans);
48     return 0;
49 }
View Code

C

猜了个循环移位分组,是错的。博哥来了个纵向蛇皮构造(蛇形构造),就过了。

 1 #include<bits/stdc++.h>
 2 #define FOR(i,a,b) for (register int i=(a);i<=(b);i++)
 3 #define For(i,a,b) for (register int i=(a);i>=(b);i--)
 4 #define mem(i,j) memset(i,j,sizeof(i))
 5 #define GO(u) for (register int j=f[u];j!=-1;j=nxt[j])
 6 #define fi first
 7 #define se second
 8 #define pb push_back
 9 #define pii pair<int,int>
10 #define MP make_pair
11 using namespace std;
12 typedef long long ll;
13 const int N=5050;
14 int n,a[N][N],pt=0;
15 inline int read()
16 {
17     int x=0,f=1;
18     char c=getchar();
19     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
20     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
21     return f*x;
22 }
23 inline void write(int x)
24 {
25     if (x<0) putchar('-'),x=-x;
26     if (x>9) write(x/10);
27     putchar(x%10+'0');
28     return;
29 }
30 int main()
31 {
32     n=read();
33     FOR(i,1,n)
34     {
35         if (i&1) For(j,n,1) a[j][i]=++pt;
36         else FOR(j,1,n) a[j][i]=++pt;
37     }
38     FOR(i,1,n)
39     {
40         FOR(j,1,n) write(a[i][j]),putchar(' ');
41         putchar('\n');
42     }
43     return 0;
44 }
View Code

D

显然我们从起点出发后,由于每个位置只能经过一次,我们不得不走到底,能走就走,不能走就右转,直到一步都不能走。

这时候我们看一下经过的格子数是否正确即可,正确性应该显然吧。

用vector维护障碍物,每次lower_bound二分查找,再记录四个界限的标记,它们是不断往中间收拢的,最后注意开long long,以及一开始是可以往下走的。

ps:经过亲测,如果不判一开始往下走,会WA218,这是个hack点,终测时候会挂掉。

  1 #include<bits/stdc++.h>
  2 #define FOR(i,a,b) for (register LL i=(a);i<=(b);i++)
  3 #define For(i,a,b) for (register LL i=(a);i>=(b);i--)
  4 #define mem(i,j) memset(i,j,sizeof(i))
  5 #define GO(u) for (register LL j=f[u];j!=-1;j=nxt[j])
  6 #define fi first
  7 #define se second
  8 #define pb push_back
  9 #define pii pair<LL,LL>
 10 #define MP make_pair
 11 using namespace std;
 12 typedef long long LL;
 13 const LL N=2e5+5;
 14 LL n,m,k,x[N],y[N],a=1,b=1,now=1,cnt=1,hh[2],ll[2];
 15 vector <LL> h[N],l[N];
 16 inline LL read()
 17 {
 18     LL x=0,f=1;
 19     char c=getchar();
 20     while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
 21     while (c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
 22     return f*x;
 23 }
 24 inline void write(LL x)
 25 {
 26     if (x<0) putchar('-'),x=-x;
 27     if (x>9) write(x/10);
 28     putchar(x%10+'0');
 29     return;
 30 }
 31 inline void init()
 32 {
 33     FOR(i,1,n) h[i].pb(0),h[i].pb(m+1);
 34     FOR(i,1,m) l[i].pb(0),l[i].pb(n+1);
 35     FOR(i,1,k) h[x[i]].pb(y[i]),l[y[i]].pb(x[i]);
 36     FOR(i,1,n) sort(h[i].begin(),h[i].end());
 37     FOR(i,1,m) sort(l[i].begin(),l[i].end());
 38     hh[0]=0,hh[1]=n+1;
 39     ll[0]=0,ll[1]=m+1;
 40     return;
 41 }
 42 inline void solve()
 43 {
 44     LL pos;
 45     while (cnt<n*m-k)
 46     {
 47         switch (now)
 48         {
 49             case 1:
 50                 pos=upper_bound(h[a].begin(),h[a].end(),b)-h[a].begin();
 51                 pos=h[a][pos];
 52                 pos=min(pos,ll[1]);
 53                 if (pos-b==1) return;
 54                 cnt+=pos-b-1;
 55                 b=pos-1;
 56                 now=2;
 57                 hh[0]=max(hh[0],a);
 58                 break;
 59             case 2:
 60                 pos=upper_bound(l[b].begin(),l[b].end(),a)-l[b].begin();
 61                 pos=l[b][pos];
 62                 pos=min(pos,hh[1]);
 63                 if (pos-a==1) return;
 64                 cnt+=pos-a-1;
 65                 a=pos-1;
 66                 now=3;
 67                 ll[1]=min(ll[1],b);
 68                 break;
 69             case 3:
 70                 pos=lower_bound(h[a].begin(),h[a].end(),b)-h[a].begin();
 71                 pos--;
 72                 pos=h[a][pos];
 73                 pos=max(pos,ll[0]);
 74                 if (b-pos==1) return;
 75                 cnt+=b-pos-1;
 76                 b=pos+1;
 77                 now=4;
 78                 hh[1]=min(hh[1],a);
 79                 break;
 80             case 4:
 81                 pos=lower_bound(l[b].begin(),l[b].end(),a)-l[b].begin();
 82                 pos--;
 83                 pos=l[b][pos];
 84                 pos=max(pos,hh[0]);
 85                 if (a-pos==1) return;
 86                 cnt+=a-pos-1;
 87                 a=pos+1;
 88                 now=1;
 89                 ll[0]=max(ll[0],b);
 90                 break;
 91         }
 92     }
 93     return;
 94 }
 95 int main()
 96 {
 97     n=read(),m=read(),k=read();
 98     FOR(i,1,k) x[i]=read(),y[i]=read();
 99     init();
100     solve();
101     if (cnt==n*m-k) {printf("Yes\n");exit(0);}
102     hh[0]=0,hh[1]=n+1;
103     ll[0]=0,ll[1]=m+1;
104     a=b=1;
105     cnt=1;
106     now=2;
107     solve();
108     if (cnt==n*m-k)printf("Yes\n");
109     else printf("No\n");
110     return 0;
111 }
112 /*
113 4 2 4
114 1 2
115 2 2
116 3 2
117 4 2
118 */
View Code
01-16 09:57