提交链接
https://codeforces.com/gym/100291/submit
B . Cuckoo for Hashing [递归]
int n1, n2, m; int a1[maxn], a2[maxn]; void modify(int f,int val) { if(f == 0) { if(a1[val % n1] == -1) a1[val % n1] = val; else { int pre = a1[val % n1]; a1[val % n1] = val; modify(1,pre); } } else { if(a2[val % n2] == -1) a2[val % n2] = val; else { int pre = a2[val % n2]; a2[val % n2] = val; modify(0,pre); } } } int main() { int _ = 0; while (~scanf("%d%d%d", &n1, &n2, &m) && m) { memset(a1, -1, sizeof a1); memset(a2, -1, sizeof a2); printf("Case %d:\n", ++_); for (int i = 1; i <= m; i++) { modify(0,read); } int c1 = 0,c2 = 0; for(int i=0;i<max(n1,n2);i++) { if(a1[i] != -1) c1 ++; if(a2[i] != -1) c2 ++; } if(c1) { puts("Table 1"); for(int i=0; i<n1; i++) { if(a1[i] != -1) { printf("%d:%d\n",i,a1[i]); } } } if(c2) { puts("Table 2"); for(int i=0; i<n2; i++) { if(a2[i] != -1) { printf("%d:%d\n",i,a2[i]); } } } } return 0; } /** **/
C . Playing Fair with Cryptography
队友传送门Code
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; char a[10][10]; int b[27]; int tx[27],ty[27]; char getNext(char ch,int &idx){ if(idx==ch-'A') idx=(idx+1)%26; if(idx==9) idx++; ch=idx+'A'; idx=(idx+1)%26; if(idx==9) idx++; return ch; } void cul(char u,char v,char &x,char &y){ int tu=u-'A',tv=v-'A'; if(tx[tu]==tx[tv]){ //cout<<"1"<<endl; //cout<<tu<<" "<<tx[tu]<<" "<<ty[tu]<<endl; //cout<<tv<<" "<<tx[tv]<<" "<<ty[tv]<<endl; //cout<<(ty[tu]+1)%5<<"***"<<(ty[tv]+1)%5<<endl; x=a[tx[tu]][(ty[tu]+1)%5]; y=a[tx[tv]][(ty[tv]+1)%5]; //cout<<x<<" "<<y<<endl; }else if(ty[tu]==ty[tv]){ //cout<<"2"<<endl; x=a[(tx[tu]+1)%5][ty[tu]]; y=a[(tx[tv]+1)%5][ty[tv]]; }else{ //cout<<"3"<<endl; x=a[tx[tu]][ty[tv]]; y=a[tx[tv]][ty[tu]]; } } int main(){ int _,Case=1;cin>>_; while(_--){ string ss,s="",t="",tt; if(Case==1) getchar(); getline(cin,ss); getline(cin,tt); // cout<<ss<<endl; // cout<<tt<<endl; for(int i=0;i<ss.size();i++){ if(ss[i]>='a'&&ss[i]<='z'){ s+=ss[i]-'a'+'A'; } else if(ss[i]>='A'&&ss[i]<='Z'){ s+=ss[i]; } } for(int i=0;i<tt.size();i++){ if(tt[i]=='J') tt[i]='I'; if(tt[i]>='a'&&tt[i]<='z') t+=tt[i]-'a'+'A'; else if(tt[i]>='A'&&tt[i]<='Z') t+=tt[i]; } //cout<<s<<endl; //cout<<t<<endl; int idx=0; memset(b,0,sizeof b); b[9]=1; for(int i=0;i<5;i++) for(int j=0;j<5;j++) a[i][j]='*'; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ while(b[s[idx]-'A']&&idx<s.size()) idx++; if(idx<s.size()){ a[i][j]=s[idx],b[s[idx]-'A']=1; } else break; } } idx=0; for(int i=0;i<5;i++) for(int j=0;j<5;j++){ if(a[i][j]!='*') continue; while(b[idx]) idx++; a[i][j]=idx+'A'; b[idx]=1; } for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ //cout<<a[i][j]<<" "; tx[a[i][j]-'A']=i; ty[a[i][j]-'A']=j; } //cout<<"\n"; } idx=0; char x,y; string ans=""; for(int i=0;i<t.size();i+=2){ if(t[i]==t[i+1]){ cul(t[i],getNext(t[i],idx),x,y); i--; } else if(i+2>t.size()){ cul(t[i],getNext(t[i],idx),x,y); } else cul(t[i],t[i+1],x,y); ans=ans+x+y; } cout<<"Case "<<Case++<<": "<<ans<<endl; } return 0; }
F . Super Phyllis
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=1e9+7; int n,a[1100][1100],Case=0,idx=0; vector<int>g[1100]; map<string,int>mp; map<int,string>mpp; bool vis[1100]; void init(){ idx=0;mp.clear();mpp.clear(); memset(a,0,sizeof a); for(int i=0;i<1100;i++) g[i].clear(); } int cul(string s){ if(!mp.count(s)) mp[s]=++idx,mpp[idx]=s; return mp[s]; } bool bfs(int s,int t){ queue<int>q; memset(vis,0,sizeof vis); vis[s]=1;q.push(s); while(!q.empty()){ int now=q.front();q.pop(); if(now==t) return true; for(int i=0;i<g[now].size();i++){ int j=g[now][i]; if(!a[now][j]) continue; if(!vis[j]){ vis[j]=1;q.push(j); } } } return false; } int main(){ while(~scanf("%d",&n)){ if(n==0) break; init(); for(int i=1;i<=n;i++){ string su,sv; cin>>su>>sv; int u=cul(su),v=cul(sv); g[u].push_back(v); a[u][v]=1; } vector<string>ans; for(int i=1;i<=idx;i++){ for(int j=0;j<g[i].size();j++){ int now=g[i][j]; a[i][now]=0; if(!bfs(i,now)) a[i][now]=1; else ans.push_back(mpp[i]+","+mpp[now]); } } sort(ans.begin(),ans.end()); cout<<"Case "<<++Case<<": "<<ans.size(); for(int i=0;i<ans.size();i++) cout<<" "<<ans[i]; cout<<"\n"; } return 0; }
H . The Urge to Merge
#include <bits/stdc++.h> typedef long long ll; #pragma region Debug template<typename T> std::istream& operator>> (std::istream& in, std::vector<T>& vt) { for (auto& i : vt) in >> i; return in; } template<typename T> std::ostream& operator<< (std::ostream& out, const std::vector<T>& vt) { for (auto& i : vt) out << i << " "; out << std::endl; return out; } void printAll() { } template<typename T1, typename... T2> void printAll(const T1& first, const T2&... second) { std::cout << first; if (sizeof...(second)) { std::cout << ", "; } printAll(second...); } template<typename T1, typename... T2> void print(const T1& first, const T2&... second) { std::cout << "["; printAll(first, second...); std::cout << "]" << std::endl; } #pragma endregion #define N (int)(5e2 + 10) int main() { int n; while (std::cin >> n && n) { static int cas = 1; std::vector<std::vector<int>> v(3, std::vector<int>(n)), f(n, std::vector<int>(27)); for (auto& str : v) { for (auto& ch : str) { std::cin >> ch; } } /* f[i][j] : 1 - i 列所有的数据，最后一列状态为j的最大值 f[i][j] = max(f[i - 1][k] + val(j)) */ auto judge = [](const std::vector<int>& tmp) { for (int i = 0; i < tmp.size() - 1; i++) { if (tmp[i] == 1) { if (tmp[i + 1] != 1) { return false; } i += 1; } } return true; }; std::vector<std::vector<int>> allSta; std::vector<int> allNum; for (int i = 0; i < 27; i++) { std::vector<int> tmp; int num = i; while (num) { tmp.push_back(num % 3); num /= 3; } while (tmp.size() != 3) tmp.push_back(0); std::reverse(tmp.begin(), tmp.end()); if (judge(tmp)) { allSta.push_back(tmp); allNum.push_back(i); } } auto calc1 = [&](const std::vector<int>& sta, int col) { int res = 0; for (int i = 0; i < sta.size() - 1; i++) { if (sta[i] == 1) { res += v[i][col] * v[i + 1][col]; i += 1; } } return res; }; //print(calc1({ 0,1,1 }, 0)); for (auto& tmp : allSta) { //print(tmp[0], tmp[1], tmp[2]); } const int& si = allNum.size(); for (int i = 0; i <= 0; i++) { for (int j = 0; j < si; j++) { auto& sta = allSta[j]; auto& num = allNum[j]; f[i][num] = calc1(sta, i); } } auto judge2 = [](const std::vector<int>& curSta, const std::vector<int>& preSta) { for (int i = 0; i < curSta.size(); i++) { if (curSta[i] == 2) { if (preSta[i] == 1) { return false; } if (preSta[i] == 2) { return false; } } } return true; }; auto calc2 = [&](const std::vector<int>& curSta, const std::vector<int>& preSta, int col) { int res = 0; for (int i = 0; i < curSta.size() - 1; i++) { if (curSta[i] == 1) { res += v[i][col] * v[i + 1][col]; i += 1; } else if (curSta[i] == 2) { res += v[i][col] * v[i][col - 1]; } } if (curSta[curSta.size() - 1] == 2) { res += v[curSta.size() - 1][col] * v[curSta.size() - 1][col - 1]; } return res; }; /* 0 : 先不合并 1 : 上下合并 2 : 突出 */ int mx = 0; for (int i = 1; i < n; i++) { for (int j = 0; j < si; j++) { auto& curSta = allSta[j]; auto& curNum = allNum[j]; for (int k = 0; k < si; k++) { auto& preSta = allSta[k]; auto& preNum = allNum[k]; if (judge2(curSta, preSta)) { f[i][curNum] = std::max(f[i][curNum], f[i - 1][preNum] + calc2(curSta, preSta, i)); } } if (i == n - 1) { mx = std::max(mx, f[i][curNum]); } } } printf("Case %d: %d\n", cas++, mx); //std::cout << f[0][4] << std::endl; } return 0; }
I . Xenospeak [规律模拟]
其中，num[i]表示长度为i的字符串有多少个
然后确定了字符串的长度进行构造
如果说前一个为a开头的，那么说后面可以拼接任意的字符串，转移到len-1的情况
如果说是b开头的，只能是bb并且转移到len-2的情况
根据规律进行模拟
ll num[1007]; string get(ll a) { int len = 1; while (num[len] < a) a -= num[len],len++; string s; s.clear(); int fa = 0; for (int i = len; i >= 1; i--) { ll need = num[i-1];/// 看两位，注意没有两位的情况，比如当前i为1 if(i > 1) need += num[i-2]; if(need >= a) s.push_back('a'),fa = 1; else { if(fa == 0) { s.push_back('b'); s.push_back('b'); a -= need; -- i;/// 加了两个需要再减去一个长度 }else { s.push_back('b'); a -= need; } } } return s; } int main() { num[0] = num[1] = 1; for (int i = 2; i <= 1000; i++) num[i] = num[i - 1] + num[i - 2] + num[i - 2]; ll n, m; int _ = 0; while (cin >> n >> m && (n || m)) { printf("Case %d: %s %s\n", ++_, get(n * (m - 1) + 1).c_str(), get(n * m).c_str()); } return 0; } /** **/
E . Stampede! [二分 + 网络最大流(拆点)]
没有技巧，全是感情
Code:
/*** keep hungry and calm PushyTao!***/ #pragma GCC optimize(2) #pragma G++ optimize(2) #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf = 9223372036854775807; const ll INF = 0x3f3f3f3f; const int maxn = 1e6 + 7000; struct Edge { int u, v; ll cap, flow; Edge(int _u, int _v, ll _cap, ll _flow) { u = _u, v = _v; cap = _cap, flow = _flow; } }; struct Dinic { vector<Edge> edge; vector<int> G[maxn << 1]; ll dis[maxn << 1], cur[maxn << 1]; int n, s, t; bool vis[maxn << 1]; void init(int x, int _s, int _t) { n = x; for (int i = 0; i <= n; i++) G[i].clear(); s = _s, t = _t; edge.clear(); } void add(int u, int v, ll cap) { edge.push_back(Edge(u, v, cap, 0)); edge.push_back(Edge(v, u, 0, 0)); G[u].push_back(edge.size() - 2); G[v].push_back(edge.size() - 1); } bool bfs(int s, int t) { queue<int> que; memset(vis, 0, sizeof vis); // memset(dis,0,sizeof dis); dis[s] = 0; que.push(s); vis[s] = 1; while (que.size()) { int u = que.front(); que.pop(); for (int i = 0; i < (int)G[u].size(); i++) { int id = G[u][i]; int to = edge[id].v; if (!vis[to] && edge[id].cap > edge[id].flow) { dis[to] = dis[u] + 1; que.push(to); vis[to] = 1; } } } return vis[t]; } ll dfs(int s, int t, ll rest) { if (s == t || rest == 0) return rest; ll Flow = 0, f; for (ll &i = cur[s]; i < G[s].size(); i++) { Edge &e = edge[G[s][i]]; if (dis[s] + 1 == dis[e.v] && (f = dfs(e.v, t, min(rest, e.cap - e.flow))) > 0) { e.flow += f; edge[G[s][i] ^ 1].flow -= f; Flow += f; rest -= f; if (rest == 0) break; } } return Flow; } ll getMaxFlow(int s, int t) { ll ans = 0; while (bfs(s, t)) { memset(cur, 0, sizeof cur); ans += dfs(s, t, 0x3f3f3f3f); } return ans; } } solve; int n; string s[maxn]; int getId(int x, int y, int f) { return x * n + y + 1 + f * n * n; } int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; bool in(int x, int y) { if (x >= 0 && x <= n - 1 && y >= 0 && y <= n - 1 && s[x][y] == '.') return true; return false; } bool check(int v) { int st = 0, ed = n * n * (v + 1) + 1; solve.init(1000001, st, ed); for (int i = 0; i < n; i++) { solve.add(st, getId(i, 0, 0), 1); solve.add(getId(i, n - 1, v), ed, 1); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (s[i][j] == '.') { for (int k = 0; k < v; k++) { solve.add(getId(i, j, k), getId(i, j, k + 1), 1); for (int t = 0; t < 4; t++) { int tox = i + dx[t]; int toy = j + dy[t]; if (in(tox, toy)) { solve.add(getId(i, j, k), getId(tox, toy, k + 1), 1); } } } } } } return solve.getMaxFlow(st, ed) == n; } int main() { int _ = 0; while (cin >> n && n) { for (int i = 0; i < n; i++) cin >> s[i]; int l = 0, r = n * n + 10; int ans = 0; while (l < r) { int mid = ((l + r) >> 1); if (check(mid)) ans = mid, r = mid; else l = mid + 1; } printf("Case %d: %d\n", ++_, ans); } return 0; }
