ECNA 2013 部分题解 | 训练记录

ECNA 2013 部分题解 | 训练记录

目录

​​提交链接​​​​B . Cuckoo for Hashing [递归]​​​​C . Playing Fair with Cryptography​​​​F . Super Phyllis​​​​H . The Urge to Merge​​​​I . Xenospeak [规律模拟]​​​​E . Stampede! [二分 + 网络最大流(拆点)]​​

提交链接

​​. 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

C . Playing Fair with Cryptography

​​队友传送门​​Code

#pragma GCC optimize(2)#includeusing 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"<>_; while(_--){ string ss,s="",t="",tt; if(Case==1) getchar(); getline(cin,ss); getline(cin,tt); // cout<='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='a'&&tt[i]<='z') t+=tt[i]-'a'+'A'; else if(tt[i]>='A'&&tt[i]<='Z') t+=tt[i]; } //cout<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 "<

F . Super Phyllis

#pragma GCC optimize(2)#includeusing namespace std;typedef long long ll;const int mod=1e9+7;int n,a[1100][1100],Case=0,idx=0;vectorg[1100]; mapmp;mapmpp;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){ queueq; 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>su>>sv; int u=cul(su),v=cul(sv); g[u].push_back(v); a[u][v]=1; } vectorans; for(int i=1;i<=idx;i++){ for(int j=0;j

H . The Urge to Merge

#include typedef long long ll;#pragma region Debugtemplatestd::istream& operator>> (std::istream& in, std::vector& vt){ for (auto& i : vt) in >> i; return in;}templatestd::ostream& operator<< (std::ostream& out, const std::vector& vt){ for (auto& i : vt) out << i << " "; out << std::endl; return out;}void printAll() { }templatevoid printAll(const T1& first, const T2&... second){ std::cout << first; if (sizeof...(second)) { std::cout << ", "; } printAll(second...);}templatevoid 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> v(3, std::vector(n)), f(n, std::vector(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& 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> allSta; std::vector allNum; for (int i = 0; i < 27; i++) { std::vector 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& 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& curSta, const std::vector& 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& curSta, const std::vector& 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! [二分 + 网络最大流(拆点)]

没有技巧，全是感情 可以参考：​​​博客1​​​ ​​博客2​​​​提交链接​​ Code:

/*** keep hungry and calm PushyTao!***/#pragma GCC optimize(2)#pragma G++ optimize(2)#include 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; vector 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 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。