ICPC2018青岛站
回家参加icpc。
这次总体发挥还可以吧,获得了银奖。
C.Flippy Sequence
只有\(s\)串和\(t\)串有至多连续2段不同时才可行。分情况讨论即可。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; char s[1000010],t[1000010]; int main() { int T; scanf("%d",&T); for (; T--;) { int n; scanf("%d%s%s",&n,s + 1,t + 1); int l[3],r[3]; l[1] = l[2] = -1; r[1] = r[2] = -1; int flag = 0; for (int i = 1; i <= n; i++) if (s[i] != t[i]) { if (s[i - 1] == t[i - 1]) { flag++; if (flag > 2) break; l[flag] = 1; } } else if (s[i - 1] != t[i - 1]) r[flag] = i - 1; if (s[n] != t[n]) r[flag] = n; if (flag > 2) puts("0"); else if (flag == 0) printf("%lld\n",(long long)n * (n - 1) / 2 + n); else if (flag == 1) printf("%lld\n",2ll * (l[1] - 1 + (n - r[1]) + (r[1] - l[1]))); else puts("6"); } return 0; }
E.Plants vs. Zombies
二分答案判断即可。
#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN=100000+10; LL m,a[MAXN],d[MAXN]; int T,n; inline bool check(LL x) { LL t=m,now; for (int i=1;i<=n;++i) d[i]=0; for (int i=1;i<=n;++i) if (d[i]+a[i]<x) { if (t==0) break; now=(x-d[i])/a[i]; if ((x-d[i])%a[i]!=0) ++now; if (t<now*2-1) return 0; t-=now*2-1; d[i]+=a[i]*now; d[i+1]+=a[i+1]*(now-1); } else { if (t==0) break; t-=1; d[i]+=a[i]; } for (int i=1;i<=n;++i) if (d[i]<x) return 0; return 1; } int main() { scanf("%d",&T); while (T--) { scanf("%d%lld",&n,&m); for (int i=1;i<=n;++i) scanf("%lld",&a[i]); LL l=0,r=1e17,mid; /*check(6); for (int i=1;i<=n;++i) cout<<d[i]<<endl;*/ while (l<r) { mid=(l+r+1)/2; if (check(mid)) l=mid; else r=mid-1; } printf("%lld\n",l); } return 0; }
F.Tournament
最多安排的轮数显然与lowbit有关。若\(n=2^xy\),其中\(y\)为奇数,则最多安排的轮数为\(2^x-1\)。按照顺序构造安排方案即可。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; int p[1010][1010]; void work(int id,int st1,int st2,int k) { if (k == 0) { p[id][st1] = st2; p[id][st2] = st1; return; } work(id,st1,st2,k - 1); work(id,st1 + (1 << (k - 1)),st2 + (1 << (k - 1)),k - 1); work(id + (1 << (k - 1)),st1,st2 + (1 << (k - 1)),k - 1); work(id + (1 << (k - 1)),st1 + (1 << (k - 1)),st2,k - 1); } int main() { int T; scanf("%d",&T); for (; T--;) { int n,m; scanf("%d%d",&n,&m); int k = 0; int tn = n; for (; ! (tn & 1); tn >>= 1) k++; if (m >= (1 << k)) { puts("Impossible"); continue; } for (int i = 1; i <= k; i++) for (int j = 1; j <= n; j += (1 << i)) work((1 << (i - 1)),j,j + (1 << (i - 1)),i - 1); for (int i = 1; i <= m; i++) { for (int j = 1; j < n; j++) printf("%d ",p[i][j]); printf("%d\n",p[i][n]); } } return 0; }
J.Books
如果价格为\(0\)的书的数量大于\(m\),则不可能。如果\(n=m\),则输出Richman。否则,答案为前m本书的价格和加上后面的书的最小价格减一。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int oo = 0x7fffffff; int a[100010]; int main() { int T; scanf("%d",&T); for (; T--;) { int n,m; scanf("%d%d",&n,&m); for (int i = 1; i <= n; i++) { scanf("%d",&a[i]); if (! a[i]) { n--; i--; m--; } } if (m < 0) { puts("Impossible"); continue; } if (n == m) { puts("Richman"); continue; } long long ans = 0; for (int i = 1; i <= m; i++) ans += a[i]; int mn = oo; for (int i = m + 1; i <= n; i++) mn = min(mn,a[i]); ans += mn - 1; printf("%lld\n",ans); } return 0; }
M.Function and Function
显然当次数很大的时候就会变成01交替。一直暴力计算直到变为0,然后根据剩下的次数计算即可。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int f[10] = {1,0,0,0,1,0,1,0,2,1}; int cal(int x) { if (x == 0) return 1; int res = 0; for (; x > 0; x /= 10) res += f[x % 10]; return res; } int main() { int T; scanf("%d",&T); for (; T--;) { int x,k; scanf("%d%d",&x,&k); int i = 1; for (; i <= k; i++) { x = cal(x); if (x == 0) break; } if (i > k) printf("%d\n",x); else if ((k - i) & 1) puts("1"); else puts("0"); } return 0; }