Codeforces Beta Round #70 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef unsigned long long ull;
14 
15 map<char,int>mp;
16 
17 int main(){
18     #ifndef ONLINE_JUDGE
19      //   freopen("input.txt","r",stdin);
20     #endif
21     std::ios::sync_with_stdio(false);
22     mp['a']=1,mp['e']=1,mp['i']=1,mp['o']=1,mp['u']=1;
23     string str;
24     getline(cin,str);
25     int num=0;
26     for(int i=0;i<str.length();i++){
27         num+=mp[str[i]];
28     }
29     if(num==5){
30         getline(cin,str);
31         num=0;
32         for(int i=0;i<str.length();i++){
33             num+=mp[str[i]];
34         }
35         if(num==7){
36             getline(cin,str);
37             num=0;
38             for(int i=0;i<str.length();i++){
39                 num+=mp[str[i]];
40             }
41             if(num==5) {
42                 cout<<"YES"<<endl;
43                 return 0;
44                 
45             }
46         }
47         
48     }
49     cout<<"NO"<<endl;
50 }

View Code

B

找规律

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef unsigned long long ull;
14 
15 map<char,int>mp;
16 
17 int main(){
18     #ifndef ONLINE_JUDGE
19      //   freopen("input.txt","r",stdin);
20     #endif
21     std::ios::sync_with_stdio(false);
22     int n;
23     cin>>n;
24     cout<<"ROYGBIV";
25     n-=7;
26     for(int i=0;i<n;i++){
27         if(i%4==0){
28             cout<<"G";
29         }
30         else if(i%4==1){
31             cout<<"B";
32         }
33         else if(i%4==2){
34             cout<<"I";
35         }
36         else {
37             cout<<"V";
38         }
39     } 
40 }

View Code

C

博弈如果n是偶数的话，后手必胜，因为他可以模仿先手，如果n是奇数的话，判断先手能否完成切割任务

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef unsigned long long ull;
14 
15 map<char,int>mp;
16 int n,m,k;
17 bool panduan(){
18     int sq=sqrt(m);
19     for(int i=1;i<=sq;i++){
20         if(m%i==0){
21             if(i>=k&&m/i>1) return 1;
22             else if(i>1&&m/i>=k) return 1;
23         }
24     }
25     return 0;
26     
27 }
28 
29 int main(){
30     #ifndef ONLINE_JUDGE
31      //   freopen("input.txt","r",stdin);
32     #endif
33     std::ios::sync_with_stdio(false);
34     cin>>n>>m>>k;
35     if(n%2==0)  cout<<"Marsel";
36     else {
37         if(panduan()){
38             cout<<"Timur";
39         } 
40         else{
41             cout<<"Marsel";
42         }
43         
44     }
45 }

View Code

D

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef unsigned long long ull;
14 
15 map<char,int>mp;
16 int n,m,k;
17 
18 
19 int main(){
20     #ifndef ONLINE_JUDGE
21      //   freopen("input.txt","r",stdin);
22     #endif
23     std::ios::sync_with_stdio(false);
24     ll n;
25     cin>>n;
26     ll ans=0;
27     for(double i=8.0/3;i<2*n/sqrt(3);i+=2){
28         double tmp=(sqrt(16.0*n*n/3-3*i*i)-i)/2.0-2.0/3;
29         if(tmp>0) ans+=(ll)tmp/2+1;
30     } 
31     cout<<ans*6+1<<endl;
32 }

View Code

E

最大流。先标记毒气到达每个实验室的时间，再判断科学家能否在毒气或规定时间内到达救生仓，然后建图

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson l,mid,rt<<1
  4 #define rson mid+1,r,rt<<1|1
  5 #define sqr(x) ((x)*(x))
  6 #define pb push_back
  7 #define eb emplace_back
  8 #define maxn 1000006
  9 #define eps 1e-8
 10 #define pi acos(-1.0)
 11 #define rep(k,i,j) for(int k=i;k<j;k++)
 12 typedef long long ll;
 13 typedef unsigned long long ull;
 14 #define MAXN 200005
 15 const int N=200005;
 16 const int M=200005;
 17 const int INF=0x3f3f3f3f;
 18 using namespace std;
 19 int n;
 20 struct Edge{
 21     int v,next;
 22     int cap,flow;
 23 }edge[MAXN*20];//注意这里要开的够大。。不然WA在这里真的想骂人。。问题是还不报RE。。
 24 int cur[MAXN],pre[MAXN],gap[MAXN],path[MAXN],dep[MAXN];
 25 int cnt=0;//实际存储总边数
 26 void isap_init()
 27 {
 28     cnt=0;
 29     memset(pre,-1,sizeof(pre));
 30 }
 31 void isap_add(int u,int v,int w)//加边
 32 {
 33     edge[cnt].v=v;
 34     edge[cnt].cap=w;
 35     edge[cnt].flow=0;
 36     edge[cnt].next=pre[u];
 37     pre[u]=cnt++;
 38 }
 39 void add(int u,int v,int w){
 40     isap_add(u,v,w);
 41     isap_add(v,u,0);
 42 }
 43 bool bfs(int s,int t)//其实这个bfs可以融合到下面的迭代里，但是好像是时间要长
 44 {
 45     memset(dep,-1,sizeof(dep));
 46     memset(gap,0,sizeof(gap));
 47     gap[0]=1;
 48     dep[t]=0;
 49     queue<int>q;
 50     while(!q.empty()) q.pop();
 51     q.push(t);//从汇点开始反向建层次图
 52     while(!q.empty())
 53     {
 54         int u=q.front();
 55         q.pop();
 56         for(int i=pre[u];i!=-1;i=edge[i].next)
 57         {
 58             int v=edge[i].v;
 59             if(dep[v]==-1&&edge[i^1].cap>edge[i^1].flow)//注意是从汇点反向bfs，但应该判断正向弧的余量
 60             {
 61                 dep[v]=dep[u]+1;
 62                 gap[dep[v]]++;
 63                 q.push(v);
 64                // if(v==sp)//感觉这两句优化加了一般没错，但是有的题可能会错，所以还是注释出来，到时候视情况而定
 65                // break;
 66             }
 67         }
 68     }
 69     return dep[s]!=-1;
 70 }
 71 int isap(int s,int t)
 72 {
 73     if(!bfs(s,t)) return 0;
 74     memcpy(cur,pre,sizeof(pre));
 75     //for(int i=1;i<=n;i++)
 76     //cout<<"cur "<<cur[i]<<endl;
 77     int u=s;
 78     path[u]=-1;
 79     int ans=0;
 80     while(dep[s]<n)//迭代寻找增广路,n为节点数
 81     {
 82         if(u==t)
 83         {
 84             int f=INF;
 85             for(int i=path[u];i!=-1;i=path[edge[i^1].v])//修改找到的增广路
 86                 f=min(f,edge[i].cap-edge[i].flow);
 87             for(int i=path[u];i!=-1;i=path[edge[i^1].v])
 88             {
 89                 edge[i].flow+=f;
 90                 edge[i^1].flow-=f;
 91             }
 92             ans+=f;
 93             u=s;
 94             continue;
 95         }
 96         bool flag=false;
 97         int v;
 98         for(int i=cur[u];i!=-1;i=edge[i].next)
 99         {
100             v=edge[i].v;
101             if(dep[v]+1==dep[u]&&edge[i].cap-edge[i].flow)
102             {
103                 cur[u]=path[v]=i;//当前弧优化
104                 flag=true;
105                 break;
106             }
107         }
108         if(flag)
109         {
110             u=v;
111             continue;
112         }
113         int x=n;
114         if(!(--gap[dep[u]]))return ans;//gap优化
115         for(int i=pre[u];i!=-1;i=edge[i].next)
116         {
117             if(edge[i].cap-edge[i].flow&&dep[edge[i].v]<x)
118             {
119                 x=dep[edge[i].v];
120                 cur[u]=i;//常数优化
121             }
122         }
123         dep[u]=x+1;
124         gap[dep[u]]++;
125         if(u!=s)//当前点没有增广路则后退一个点
126         u=edge[path[u]^1].v;
127      }
128      return ans;
129 }
130 
131 
132 int t;
133 
134 string people[15],cap[15];
135 int book[15][15];
136 struct sair{
137     int x,y,step;
138 };
139 int dir[4][2]={0,1,1,0,0,-1,-1,0};
140 
141 void bfs1(int x,int y){
142     sair s,e;
143     s.step=0,s.x=x,s.y=y;
144     memset(book,-1,sizeof(book));
145     queue<sair>Q;
146     Q.push(s);
147     book[s.x][s.y]=0;
148     while(!Q.empty()){
149         s=Q.front();
150         Q.pop();
151         if(s.step>=t) break;
152         for(int i=0;i<4;i++){
153             e.x=s.x+dir[i][0];
154             e.y=s.y+dir[i][1];
155             if(e.x>=0&&e.x<n&&e.y>=0&&e.y<n&&book[e.x][e.y]==-1&&people[e.x][e.y]!='Y'){
156                 e.step=s.step+1;
157                 book[e.x][e.y]=e.step;
158                 Q.push(e);
159             }
160         }
161     }
162 }
163 
164 void bfs2(int x,int y){
165     sair s,e;
166     int tmp[15][15];
167     memset(tmp,-1,sizeof(tmp));
168     s.x=x,s.y=y,s.step=0;
169     tmp[s.x][s.y]=0;
170     queue<sair>Q;
171     Q.push(s);
172     int w=people[x][y]-'0';
173     add(s.x*n+s.y,s.x*n+s.y+n*n,w);
174     while(!Q.empty()){
175         s=Q.front();
176         Q.pop();
177         if(s.step>=t) break;
178         for(int i=0;i<4;i++){
179             e.x=s.x+dir[i][0];
180             e.y=s.y+dir[i][1];
181             if(e.x<0||e.x>=n||e.y<0||e.y>=n||people[e.x][e.y]=='Z'||people[e.x][e.y]=='Y') continue;
182             if(tmp[e.x][e.y]==-1&&(book[e.x][e.y]==-1||book[e.x][e.y]>=s.step+1)){
183                 if(book[e.x][e.y]==s.step+1){
184                     if(cap[e.x][e.y]>='0'&&cap[e.x][e.y]<='9'){
185                         add(x*n+y,e.x*n+e.y+n*n,w);
186                     }
187                 }
188                 else{
189                     e.step=s.step+1;
190                     tmp[e.x][e.y]=e.step;
191                     add(x*n+y,e.x*n+e.y+n*n,w);
192                     Q.push(e);
193                 }
194             }
195         }
196     }
197 }
198 
199 int main(){
200     #ifndef ONLINE_JUDGE
201      //   freopen("input.txt","r",stdin);
202     #endif
203     std::ios::sync_with_stdio(false);
204     cin>>n>>t;
205     int sx,sy;
206     isap_init();
207     for(int i=0;i<n;i++){
208         cin>>people[i];
209         for(int j=0;j<n;j++){
210             if(people[i][j]=='Z'){
211                 sx=i,sy=j;
212             }
213         }
214     }
215     for(int i=0;i<n;i++) cin>>cap[i];
216     bfs1(sx,sy);
217     for(int i=0;i<n;i++){
218         for(int j=0;j<n;j++){
219             if(people[i][j]>='1'&&people[i][j]<='9'){
220                 bfs2(i,j);
221             }
222         }
223     }
224     int S=n*n*2;
225     int T=n*n*2+1;
226     for(int i=0;i<n;i++){
227         for(int j=0;j<n;j++){
228             if(people[i][j]>='0'&&people[i][j]<='9'){
229                 add(S,i*n+j,people[i][j]-'0');
230             }
231             if(cap[i][j]>='1'&&cap[i][j]<='9'){
232                 add(i*n+j+n*n,T,cap[i][j]-'0');
233             }
234         }
235     }
236     n=n*n*2+2;
237     int ans=isap(S,T);
238     cout<<ans<<endl;
239 }

View Code