2018 ACM 网络选拔赛北京赛区

P.S:正统方法：n*m*6（at most five oxygens），bfs O(6nm)

类似题目 https://www.cnblogs.com/cmyg/p/11108069.html

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=110;
 4 
 5 struct node
 6 {
 7     int x,y,z,t;
 8 };
 9 
10 struct cmp
11 {
12     bool operator() (node a,node b)
13     {
14         return a.t>b.t;
15     }
16 };
17 
18 priority_queue<node,vector<node>,cmp>st;
19 
20 int dx[4]={-1,0,0,1};
21 int dy[4]={0,-1,1,0};
22 
23 int f[maxn][maxn][6];
24 char s[maxn][maxn];
25 
26 int main()
27 {
28     int n,m,x,y,z,t,xx,yy,zz,tt,i,j,k,r;
29     while (~scanf("%d%d",&n,&m))
30     {
31         if (n==0)
32             break;
33         while (!st.empty())
34             st.pop();
35 
36         for (i=1;i<=n;i++)
37             scanf("%s",s[i]+1);
38         for (i=1;i<=n;i++)
39             for (j=1;j<=m;j++)
40                 if (s[i][j]=='S')
41                 {
42                     x=i;
43                     y=j;
44                     break;
45                 }
46         for (i=1;i<=n;i++)
47             for (j=1;j<=m;j++)
48                 for (k=0;k<=5;k++)
49                     f[i][j][k]=1e9;
50         f[x][y][0]=0;
51         st.push({x,y,0,0});
52 
53         r=-1;
54         while (!st.empty())
55         {
56             x=st.top().x;
57             y=st.top().y;
58             z=st.top().z;
59             t=st.top().t;
60             st.pop();
61 
62             if (r!=-1 && r<=t)
63                 break;
64 
65             for (i=0;i<4;i++)
66             {
67                 xx=x+dx[i];
68                 yy=y+dy[i];
69                 zz=min(z+(s[xx][yy]=='B')-(s[xx][yy]=='#'),5);
70                 tt=t+1-(s[xx][yy]=='P')+(s[xx][yy]=='#');
71                 if (zz>=0 && xx>=1 && xx<=n && yy>=1 && yy<=m && f[xx][yy][zz]>tt)
72                 {
73                     if (s[xx][yy]=='T')
74                     {
75                         if (r==-1)
76                             r=tt;
77                         else
78                             r=min(r,tt);
79                     }
80 
81                     f[xx][yy][zz]=tt;
82                     st.push({xx,yy,zz,tt});
83                 }
84             }
85         }
86 
87         printf("%d
",r);
88     }
89     return 0;
90 }

队友的方法是某每一个点按氧气量分成6个点，并连接旁边的点和设置对应的值，跑一遍spfa

B Tomb Raider

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 1e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=1e6+10;
 25 
 26 struct node
 27 {
 28     char str[10];
 29     int _index;
 30 }f[maxn];
 31 
 32 int k,g,_index;
 33 char str[20],s[20];
 34 bool v[10];
 35 
 36 void dfs(int pos,int l)
 37 {
 38     int i;
 39     for (i=pos;i<=k;i++)
 40         if (i==k)
 41         {
 42             s[l]=0;
 43             g++;
 44             strcpy(f[g].str,s);
 45             f[g]._index=_index;
 46         }
 47         else
 48         {
 49             s[l]=str[i];
 50             dfs(i+1,l+1);
 51         }
 52 }
 53 
 54 int cmp(node a,node b)
 55 {
 56     return strcmp(a.str,b.str)<0;
 57 }
 58 
 59 int main()
 60 {
 61     int n,i,j,len,x,y;
 62     while (~scanf("%d",&n))
 63     {
 64         g=0;
 65         for (_index=1;_index<=n;_index++)
 66         {
 67             scanf("%s",str);
 68             len=strlen(str);
 69             strcpy(s,str);
 70             strcat(str,s);
 71             for (i=0;i<len;i++)
 72             {
 73                 s[0]=str[i];
 74                 j=1;
 75                 k=i+len;
 76                 dfs(i+1,j);
 77             }
 78         }
 79         sort(f+1,f+g+1,cmp);
 80 
 81         x=0;
 82         strcpy(f[g+1].str,"");
 83         for (i=1;i<=g;i++)
 84         {
 85             v[f[i]._index]=1;
 86 
 87             if (strcmp(f[i].str,f[i+1].str)!=0)
 88             {
 89                 for (_index=1;_index<=n;_index++)
 90                     if (!v[_index])
 91                         break;
 92                 if (_index==n+1)
 93                 {
 94                     len=strlen(f[i].str);
 95                     if (len>x)
 96                     {
 97                         x=len;
 98                         y=i;
 99                     }
100                 }
101 
102                 for (_index=1;_index<=n;_index++)
103                     v[_index]=0;
104             }
105         }
106         if (x==0)
107             printf("0
");
108         else
109             printf("%s
",f[y].str);
110     }
111     return 0;
112 }
113 /*
114 2
115 ab
116 ba
117 */

C Cheat

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=1e5+10;
  4 
  5 int f[4][53],_index,card;
  6 int value[15]={0,10,2,3,4,5,6,7,8,9,1,11,13,12};
  7 int cur,rep_card,rep_value;
  8 int hap[14];
  9 int c,cc[53];
 10 int claim;
 11 
 12 void replace_card()
 13 {
 14     int i;
 15     c++;
 16     cc[c]=f[_index][rep_card];
 17 
 18     for (i=rep_card;i<f[_index][0];i++)
 19         f[_index][i]=f[_index][i+1];
 20     f[_index][0]--;
 21 }
 22 
 23 int find_num(int j)
 24 {
 25     int g=0,i;
 26     for (i=1;i<=f[j][0];i++)
 27         if (f[j][i]==card)
 28             g++;
 29     return g;
 30 }
 31 
 32 bool judge1()
 33 {
 34     int i;
 35     for (i=1;i<=f[_index][0];i++)
 36         if (f[_index][i]==card)
 37         {
 38             rep_card=i;
 39             return 1;
 40         }
 41     return 0;
 42 }
 43 
 44 bool judge2()
 45 {
 46     int g=find_num(_index);
 47     if (g==3 || g==4)
 48         return 1;
 49     else
 50         return 0;
 51 }
 52 
 53 void get_rep_value()
 54 {
 55     int i;
 56     rep_value=100;
 57     for (i=1;i<=f[_index][0];i++)
 58         if (value[f[_index][i]]<rep_value)
 59         {
 60             rep_value=value[f[_index][i]];
 61             rep_card=i;
 62         }
 63 }
 64 
 65 void handle_value()
 66 {
 67     int i;
 68     claim=0;
 69     for (i=1;i<=f[_index][0];)
 70         if (value[f[_index][i]]==rep_value)
 71         {
 72             claim++;
 73             rep_card=i;
 74             replace_card();
 75         }
 76         else
 77             i++;
 78 }
 79 
 80 void handle_card()
 81 {
 82     int i;
 83     claim=0;
 84     for (i=1;i<=f[_index][0];)
 85         if (f[_index][i]==card)
 86         {
 87             claim++;
 88             rep_card=i;
 89             replace_card();
 90         }
 91         else
 92             i++;
 93 }
 94 
 95 ///one:value
 96 void work1()
 97 {
 98     get_rep_value();
 99     if (rep_value!=100)
100         replace_card();
101 }
102 
103 ///many:value
104 void work2()
105 {
106     get_rep_value();
107     handle_value();
108 }
109 
110 ///one:card
111 void work3()
112 {
113     replace_card();
114 }
115 
116 ///many:card
117 void work4()
118 {
119     handle_card();
120 }
121 
122 ///work2
123 void work5()
124 {
125     int g=100,i;
126     memset(hap,0,sizeof(hap));
127     for (i=1;i<=f[_index][0];i++)
128         hap[f[_index][i]]++;
129     rep_value=100;
130     for (i=1;i<=13;i++)
131         if (hap[i]!=0 && (hap[i]<g || (hap[i]==g && value[i]<rep_value)))
132         {
133             g=hap[i];
134             rep_value=value[i];
135         }
136     handle_value();
137 }
138 
139 void show()
140 {
141     bool vis;
142     if (_index==0)
143     {
144         vis=judge1();
145         if (vis)
146         {
147             work3();
148             cur=1;
149         }
150         else
151         {
152             work1();
153             cur=0;
154         }
155         claim=1;
156     }
157     else if (_index==1)
158     {
159         vis=judge1();
160         if (vis)
161         {
162             work4();
163             cur=1;
164         }
165         else
166         {
167             work1();
168             cur=0;
169             claim=1;
170         }
171     }
172     else if (_index==2)
173     {
174         vis=judge1();
175         if (vis)
176         {
177             work4();
178             cur=1;
179         }
180         else
181         {
182             work5();
183             cur=0;
184         }
185     }
186     else
187     {
188         vis=judge2();
189         if (vis)
190         {
191             work4();
192             cur=1;
193         }
194         else
195         {
196             work4();
197             work1();
198             if (rep_value!=100)
199             {
200                 claim++;
201                 cur=0;
202             }
203             else
204                 cur=1;
205         }
206     }
207 }
208 
209 bool next_lie(int j)
210 {
211     int next__index,next_card,i;
212     next__index=(_index+1)%4;
213     if (next__index!=j)
214         return 0;
215     next_card=card+1;
216     if (next_card==14)
217         next_card=1;
218     for (i=1;i<=f[next__index][0];i++)
219         if (f[next__index][i]==next_card)
220             return 0;
221     return 1;
222 }
223 
224 bool zhiyi(int j)
225 {
226     if (j==0)
227     {
228         if (next_lie(j) || claim+find_num(j)>4)
229             return 1;
230         else
231             return 0;
232     }
233     else if (j==1)
234     {
235         if (next_lie(j))
236             return 1;
237         else
238             return 0;
239     }
240     else if (j==2)
241     {
242         if (find_num(j)==4)
243             return 1;
244         else
245             return 0;
246     }
247     else
248     {
249         if (f[_index][0]==0)
250             return 1;
251         else
252             return 0;
253     }
254 }
255 
256 void add_card(int j)
257 {
258     int i;
259     for (i=1;i<=c;i++)
260         f[j][++f[j][0]]=cc[i];
261 }
262 
263 void pr(int v)
264 {
265     if (v==1)
266         printf("A");
267     else if (v==10)
268         printf("10");
269     else if (v==11)
270         printf("J");
271     else if (v==12)
272         printf("Q");
273     else if (v==13)
274         printf("K");
275     else
276         printf("%d",v);
277 }
278 
279 int main()
280 {
281     int i,j;
282     char ch[5];
283     while (~scanf("%s",ch))
284     {
285         for (i=0;i<4;i++)
286         {
287             for (j=1;j<=13;j++)
288             {
289                 if (!(i==0 && j==1))
290                     scanf("%s",ch);
291                 if (ch[0]=='1')
292                     f[i][j]=10;
293                 else if (ch[0]=='J')
294                     f[i][j]=11;
295                 else if (ch[0]=='Q')
296                     f[i][j]=12;
297                 else if (ch[0]=='K')
298                     f[i][j]=13;
299                 else if (ch[0]=='A')
300                     f[i][j]=1;
301                 else
302                     f[i][j]=ch[0]-48;
303             }
304             f[i][0]=13;
305         }
306         _index=0;
307         card=1;
308         c=0;
309 
310         while (1)
311         {
312 //            for (i=0;i<4;i++)
313 //            {
314 //                for (j=1;j<=f[i][0];j++)
315 //                {
316 //                    pr(f[i][j]);
317 //                    if (j==f[i][0])
318 //                        printf("
");
319 //                    else
320 //                        printf(" ");
321 //                }
322 //            }
323 //            printf("remain: ");
324 //            for (i=1;i<=c;i++)
325 //            {
326 //                pr(cc[i]);
327 //                if (i==c)
328 //                    printf("
");
329 //                else
330 //                    printf(" ");
331 //            }
332 //            printf("

");
333 //            printf("index=%d card=%d
",_index,card);
334 
335             show();
336 
337             for (i=(_index+1)%4;i!=_index;i=(i+1)%4)
338                 if (zhiyi(i))
339                 {
340                     if (cur)
341                         add_card(i);
342                     else
343                         add_card(_index);
344                     c=0;
345                     break;
346                 }
347 
348             if (f[_index][0]==0)
349                 break;
350 
351             _index=(_index+1)%4;
352             if (card==13)
353                 card=1;
354             else
355                 card++;
356         }
357 
358         for (i=0;i<4;i++)
359             if (f[i][0]==0)
360                 printf("WINNER
");
361             else
362             {
363                 sort(f[i]+1,f[i]+f[i][0]+1);
364                 for (j=1;j<=f[i][0];j++)
365                 {
366                     pr(f[i][j]);
367                     if (j==f[i][0])
368                         printf("
");
369                     else
370                         printf(" ");
371                 }
372             }
373     }
374     return 0;
375 }
376 /*
377 A A 2 2 3 3 4 4 5 5 6 6 7
378 7 8 8 9 9 10 10 J J Q Q K K
379 A A 2 2 3 3 4 4 5 5 6 6 7
380 7 8 8 9 9 10 10 J J Q Q K K
381 
382 A A A A 2 2 2 2 3 3 3 3 K
383 4 4 4 4 5 5 5 5 6 6 6 6 K
384 7 7 7 7 8 8 8 8 9 9 9 9 K
385 10 10 10 10 J J J J Q Q Q Q K
386 
387 4 4 4 4 5 5 5 5 6 6 6 6 K
388 7 7 7 7 8 8 8 8 9 9 9 9 K
389 10 10 10 10 J J J J Q Q Q Q K
390 A A A A 2 2 2 2 3 3 3 3 K
391 
392 A A 2 2 8 8 9 9 5 5 6 6 7
393 3 3 4 4 7 10 10 J J Q Q K K
394 A A 2 2 3 3 4 4 5 Q Q K K
395 5 6 6 7 7 8 8 9 9 10 10 J J
396 
397 */

比赛后的改进方法：统计每位选手中每张牌的数目

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define ll long long
  4 #define minv 1e-6
  5 #define inf 1e9
  6 #define pi 3.1415926536
  7 #define nl 2.7182818284
  8 const ll mod=1e9+7;//998244353
  9 const int maxn=1e5+10;
 10 
 11 int value[14]={0,10,2,3,4,5,6,7,8,9,1,11,13,12};
 12 int card[4][14],x,y,v,table[14],nexty;
 13 bool vis;
 14 
 15 void work1()
 16 {
 17     vis=1;
 18     v=1;
 19     table[y]++;
 20     card[x][y]--;
 21 }
 22 
 23 void work2()
 24 {
 25     int i;
 26     vis=0;
 27     for (i=1;i<=13;i++)
 28         if (card[x][value[i]])
 29             break;
 30     v=1;
 31     table[value[i]]++;
 32     card[x][value[i]]--;
 33 }
 34 
 35 void work3()
 36 {
 37     vis=1;
 38     v=card[x][y];
 39     table[y]+=card[x][y];
 40     card[x][y]=0;
 41 }
 42 
 43 void work4()
 44 {
 45     int p=14,q,i;
 46     vis=0;
 47     for (i=1;i<=13;i++)
 48         if (card[x][value[i]]!=0 && card[x][value[i]]<p)
 49             p=card[x][value[i]],q=value[i];
 50     v=card[x][q];
 51     table[q]+=card[x][q];
 52     card[x][q]=0;
 53 }
 54 
 55 void work5()
 56 {
 57     int i;
 58     for (i=1;i<=13;i++)
 59         if (card[x][value[i]])
 60             break;
 61     if (i!=14)
 62     {
 63         vis=0;
 64         v++;
 65         table[value[i]]++;
 66         card[x][value[i]]--;
 67     }
 68 }
 69 
 70 void fapai()
 71 {
 72     if (x==0)
 73     {
 74         if (card[x][y])
 75             work1();
 76         else
 77             work2();
 78     }
 79     else if (x==1)
 80     {
 81         if (card[x][y])
 82             work3();
 83         else
 84             work2();
 85     }
 86     else if (x==2)
 87     {
 88         if (card[x][y])
 89             work3();
 90         else
 91             work4();
 92     }
 93     else if (x==3)
 94     {
 95         if (card[x][y]>=3)
 96             work3();
 97         else
 98         {
 99             work3();
100             work5();
101         }
102     }
103 }
104 
105 bool faempty()
106 {
107     int i;
108     for (i=1;i<=13;i++)
109         if (card[x][i]!=0)
110             return 0;
111     return 1;
112 }
113 
114 bool zhiyi(int index)
115 {
116     if (index==0)
117     {
118         if (index==(x+1)%4 && card[index][nexty]==0)
119             return 1;
120         if (v+card[index][y]>4)
121             return 1;
122         return 0;
123     }
124     else if (index==1)
125     {
126         if (index==(x+1)%4 && card[index][nexty]==0)
127             return 1;
128         return 0;
129     }
130     else if (index==2)
131     {
132         if (card[index][y]==4)
133             return 1;
134         return 0;
135     }
136     else
137         return faempty();
138 }
139 
140 void add(int index)
141 {
142     int i;
143     for (i=1;i<=13;i++)
144     {
145         card[index][i]+=table[i];
146         table[i]=0;
147     }
148 }
149 
150 void print()
151 {
152     int i,j,k;
153     for (i=0;i<4;i++)
154     {
155         vis=0;
156         for (j=1;j<=13;j++)
157             for (k=1;k<=card[i][j];k++)
158             {
159                 if (vis)
160                     printf(" ");
161                 else
162                     vis=1;
163                 if (j==1)
164                     printf("A");
165                 else if (j==10)
166                     printf("10");
167                 else if (j==11)
168                     printf("J");
169                 else if (j==12)
170                     printf("Q");
171                 else if (j==13)
172                     printf("K");
173                 else
174                     printf("%c",j+48);
175             }
176         if (!vis)
177             printf("WINNER");
178         printf("
");
179     }
180 }
181 
182 int main()
183 {
184     int i,j,index;
185     char ch[5];
186     while (~scanf("%s",ch))
187     {
188         memset(card,0,sizeof(card));
189         memset(table,0,sizeof(table));
190         for (i=0;i<4;i++)
191         {
192             for (j=1;j<=13;j++)
193             {
194                 if (i!=0 || j!=1)
195                     scanf("%s",ch);
196                 if (ch[0]=='A')
197                     card[i][1]++;
198                 else if (ch[0]=='1')
199                     card[i][10]++;
200                 else if (ch[0]=='J')
201                     card[i][11]++;
202                 else if (ch[0]=='Q')
203                     card[i][12]++;
204                 else if (ch[0]=='K')
205                     card[i][13]++;
206                 else
207                     card[i][ch[0]-48]++;
208             }
209         }
210         x=0;
211         y=1;
212         nexty=2;
213         while (1)
214         {
215             fapai();
216             for (index=(x+1)%4;index!=x;index=(index+1)%4)
217                 if (zhiyi(index))
218                 {
219                     if (vis)
220                         add(index);
221                     else
222                         add(x);
223                 }
224             if (faempty())
225                 break;
226 //                printf("
x=%d y=%d
",x,y);
227 //                print();
228             x=(x+1)%4;
229             y=nexty;
230             if (nexty==13)
231                 nexty=1;
232             else
233                 nexty++;
234         }
235         print();
236     }
237     return 0;
238 }

D 80 Days

莫名其妙单调队列代码没有做对，

思路：

对于i+1~i+n要满足任意前缀和大于等于0，

需满足 any x in [i+1,i+n] sum(x)-sum(i)>=0，

也就是求 min(sum(x))。

当然线段树求区间最小值，但就是太麻烦了。(网络有大佬是这样做的)

单调队列：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <ctime>
 5 #include <cstring>
 6 #include <string>
 7 #include <map>
 8 #include <set>
 9 #include <list>
10 #include <queue>
11 #include <stack>
12 #include <bitset>
13 #include <vector>
14 #include <algorithm>
15 #include <iostream>
16 using namespace std;
17 #define ll long long
18 const int maxn=1e6+10;
19 
20 ll a[maxn<<1],tot[maxn<<1];
21 int q[maxn<<1];
22 
23 int main()
24 {
25     int t,i,n,m,head,tail;
26     ll c,b;
27     scanf("%d",&t);
28     while (t--)
29     {
30         scanf("%d%lld",&n,&c);
31         for (i=1;i<=n;i++)
32             scanf("%lld",&a[i]);
33         for (i=1;i<=n;i++)
34         {
35             scanf("%lld",&b);
36             a[i]-=b;
37         }
38         for (i=n+1;i<2*n;i++)
39             a[i]=a[i-n];
40         m=n<<1;
41         head=1;
42         tail=0;
43         tot[0]=0;
44         for (i=1;i<m;i++)
45         {
46             tot[i]=tot[i-1]+a[i];
47             while (head<=tail && q[head]<=i-n)
48                 head++;
49             while (tail>=head && tot[i]<tot[q[tail]])
50                 tail--;
51             tail++;
52             q[tail]=i;
53             if (i>=n && tot[q[head]]-tot[i-n]>=-c)
54                 break;
55         }
56         if (i==m)
57             i=-1;
58         else
59             i-=n-1;
60         printf("%d
",i);
61     }
62     return 0;
63 }
64 /*
65 100
66 3 0
67 3 4 5
68 5 4 3
69 
70 3 100
71 -3 -4 -5
72 30 40 50
73 
74 3 1
75 1 5 4
76 2 3 1
77 
78 5 3
79 1 2 3 4 100
80 2 4 5 10 5
81 
82 5 0
83 1 2 3 4 5
84 2 3 2 5 3
85 
86 1 1
87 3
88 4
89 
90 5 0
91 5 1 2 4 3
92 3 2 4 5 1
93 */

当莫名奇妙很多人做对时，考虑一下贪心(找规律)，或者就是数据范围开小了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=1e6;
 5 
 6 ll a[maxn<<1],c;
 7 int n;
 8 
 9 bool judge(int j)
10 {
11     int i,k=j+n;
12     ll m=c;
13     for (i=j;i<k;i++)
14     {
15         m+=a[i];
16         if (m<0)
17             return 0;
18     }
19     return 1;
20 }
21 
22 int main()
23 {
24     int t,i;
25     ll b;
26     scanf("%d",&t);
27     while (t--)
28     {
29         scanf("%d%lld",&n,&c);
30         for (i=1;i<=n;i++)
31             scanf("%lld",&a[i]);
32         for (i=1;i<=n;i++)
33         {
34             scanf("%lld",&b);
35             a[i]-=b;
36         }
37         for (i=n+1;i<2*n;i++)
38             a[i]=a[i-n];
39         for (i=1;i<=n;i++)
40             if (judge(i))
41                 break;
42         if (i==n+1)
43             i=-1;
44         printf("%d
",i);
45     }
46     return 0;
47 }

大佬的非常短的代码也看不懂(https://www.cnblogs.com/caomingpei/p/9691253.html)

写过的错误代码

https://paste.ubuntu.com/p/DkqyfqFXd6/

H K-Dimensional Foil II

2018 ACM 网络选拔赛 北京赛区

2018 ACM 网络选拔赛北京赛区