2019-ccpc秦皇岛现场赛
- 2019 年 10 月 5 日
- 筆記
https://www.cnblogs.com/31415926535x/p/11625462.html
昨天和队友模拟了下今年秦皇岛的区域赛，，，（我全程在演
D – Decimal
签到题，，，（感觉在cf上做过，，
（然后写反输出白白wa一发,,,,,emmmmmmmm
F – Forest Program
这题我感觉是第二道签到题，，，很简单，，但是我一个人读完题后就想着怎么写代码，，，然后wa了无数发才反应过来还要考虑树边的情况，，，丧失理智 ，，，，
题意就是给一个 仙人掌图 ，，仙人掌图就是对于每一条边都最多属于一个简单环中，，，然后问你删去一些边使得最后的图是一片森林的方案数，，，显然答案就是每一个环至少删去一个边，，这样每一个环的贡献就是 (2^i-1) ，，累乘每一个环便是环的情况，，，然后还要考虑剩余边的情况，，然后我就是忘记这个wa的怀疑人生，，，
找图的环直接dfs就可以个了，，用一个dis数组记录一下到最初的点的距离，，碰到一个环就直接相减就能得到到环的长度，，，(刚好前几天见过这样的dfs判环和求环大小的问题
（为什么弧优化后还慢了啊，，，emmmmm
#include <bits/stdc++.h> #define aaa cout<<233<<endl; #define endl 'n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; // mt19937 rnd(time(0)); const int inf = 0x3f3f3f3f;//1061109567 > 1e9 const ll linf = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-6; const double pi = 3.14159265358979; const int maxn = 4e5 + 5; const int maxm = 6e5 + 233; // const int mod = 1e9 + 7; const int mod = 998244353; struct edge { int to, nxt; bool flag; }edge[maxm << 1]; int tot, head[maxm << 1]; void init() { tot = 0; memset(head, -1, sizeof head); } void addedge(int u, int v) { edge[tot].to = v; edge[tot].flag = false; edge[tot].nxt = head[u]; head[u] = tot++; } vector<ll> ans; int vis[maxn]; ll dis[maxn]; void dfs(int u, ll len) { vis[u] = 1; dis[u] = len; for(int &i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].to; if(edge[i].flag)continue; edge[i].flag = edge[i ^ 1].flag = true; if(vis[v] == 1) { ans.push_back(len - dis[v] + 1); continue; } dfs(v, len + 1); } vis[u] = 2; } inline ll pow_(ll a, ll b) { ll ret = 1; while(b) { if(b & 1)ret = (ret * a) % mod; a = (a * a) % mod; b >>= 1; } return ret; } int main() { // double pp = clock(); // freopen("233.in", "r", stdin); // freopen("233.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n, m; cin >> n >> m; init(); int u, v; for(int i = 1; i <= m; ++i) { cin >> u >> v; addedge(u, v); addedge(v, u); } ans.clear(); for(int i = 1; i <= n; ++i)vis[i] = -1; for(int i = 1; i <= n; ++i) if(vis[i] != 2) dfs(i, 0); // for(auto i: ans)cout << i << " ";cout << endl; ll ret = 1; for(int i = 0; i < ans.size(); ++i) ret = ret * ((pow_(2, ans[i]) - 1) + mod) % mod; ll sum = 0; for(int i = 0; i < ans.size(); ++i)sum += ans[i]; sum = pow_(2, m - sum) % mod; if(ret == 0)ret = sum; else ret = (ret * sum) % mod; cout << ret << endl; // cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl; return 0; }I – Invoker
（在我自闭的时候 ，，队友过了这题，，这题的题目很像 （基本完全一致 我们的新生赛，，只是求得东西反了过来，，，队友想了暴力+dp过的，，
#include <bits/stdc++.h> #define aaa cout<<233<<endl; #define endl 'n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; // mt19937 rnd(time(0)); const int inf = 0x3f3f3f3f;//1061109567 > 1e9 const ll linf = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-6; const double pi = 3.14159265358979; const int maxn = 3e5 + 5; const int maxm = 5e5 + 233; // const int mod = 1e9 + 7; const int mod = 998244353; map<string, int> mp; map<char, int> special; const char skill[] = {'Q', 'W', 'E'}; int dis[30][30]; vector<int> g[15]; void init() { for(int i=0; i<3; i++) { for(int j=0; j<3; j++) for(int k=0; k<3; k++) { string tmp = ""; tmp += skill[i]; tmp += skill[j]; tmp += skill[k]; mp[tmp] = i*9 + j*3 + k; } } for(int a=0; a<27; a++) { for(int b=0; b<27; b++) { int i = a, j = b; string tmpi = ""; string tmpj = ""; tmpi += skill[i/9]; i %= 9; tmpi += skill[i/3]; i %= 3; tmpi += skill[i]; tmpj += skill[j/9]; j %= 9; tmpj += skill[j/3]; j %= 3; tmpj += skill[j]; if(tmpi == tmpj) dis[a][b] = 0; else if(tmpi[1] == tmpj[0] && tmpi[2] == tmpj[1]) dis[a][b] = 1; else if(tmpi[2] == tmpj[0]) dis[a][b] = 2; else dis[a][b] = 3; } } special['Y'] = 0; special['V'] = 1; special['G'] = 2; special['C'] = 3; special['X'] = 4; special['Z'] = 5; special['T'] = 6; special['F'] = 7; special['D'] = 8; special['B'] = 9; g[0].push_back(mp["QQQ"]); g[1].push_back(mp["QQW"]); g[1].push_back(mp["QWQ"]); g[1].push_back(mp["WQQ"]); g[2].push_back(mp["QQE"]); g[2].push_back(mp["QEQ"]); g[2].push_back(mp["EQQ"]); g[3].push_back(mp["WWW"]); g[4].push_back(mp["QWW"]); g[4].push_back(mp["WQW"]); g[4].push_back(mp["WWQ"]); g[5].push_back(mp["WWE"]); g[5].push_back(mp["WEW"]); g[5].push_back(mp["EWW"]); g[6].push_back(mp["EEE"]); g[7].push_back(mp["QEE"]); g[7].push_back(mp["EQE"]); g[7].push_back(mp["EEQ"]); g[8].push_back(mp["WEE"]); g[8].push_back(mp["EWE"]); g[8].push_back(mp["EEW"]); g[9].push_back(mp["QWE"]); g[9].push_back(mp["QEW"]); g[9].push_back(mp["WQE"]); g[9].push_back(mp["WEQ"]); g[9].push_back(mp["EWQ"]); g[9].push_back(mp["EQW"]); } char s[maxn]; int dp[maxn][6]; int main() { // double pp = clock(); // freopen("233.in", "r", stdin); // freopen("233.out", "w", stdout); init(); scanf("%s", s); int len = strlen(s); for(int i=0; i<len; i++) for(int j=0; j<6; j++) dp[i][j] = inf; for(int i=0; i<g[special[s[0]]].size(); i++) dp[0][i] = 3; for(int i=1; i<len; i++) { for(int j=0; j<g[special[s[i-1]]].size(); j++) for(int k=0; k<g[special[s[i]]].size(); k++) { int tmpj = g[special[s[i-1]]][j]; int tmpk = g[special[s[i]]][k]; dp[i][k] = min(dp[i][k], dp[i-1][j] + dis[tmpj][tmpk]); } } int ans = inf; for(int i=0; i<6; i++) ans = min(ans, dp[len-1][i]); printf("%dn", ans+len); return 0; }J – MUV LUV EXTRA
这题我读完题之后感觉是字符串的题，，不知道怎么搞，，最后队友弄出来的，，
枚举+kmp
#include <bits/stdc++.h> #define LL long long using namespace std; LL a, b; const LL inf=0x3f3f3f3f3f3f3f3f; const LL maxn=1e7+7; string tem,s=""; LL nex[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>a>>b; cin>>tem; for(LL i=tem.size()-1;i>=0;i--) { if(tem[i]!='.') s+=tem[i]; else break; } nex[0]=-1; for(LL i=1;i<=s.size();i++) { nex[i]=0; int k=nex[i-1]; while(k!=-1) { if(s[i-1]==s[k]) {nex[i]=k+1;break;} else k=nex[k]; } } for(int i=0;i<s.size();i++) nex[i]=nex[i+1]; //for(int i =0;i<s.size();i++) cout<<nex[i]<<' '; LL ans=-inf; for(LL i=0;i<s.size();i++) { LL tem=a*(i+1)-b*(i+1-nex[i]); ans=ans>tem?ans:tem; } if(ans==-inf) cout<<0<<endl; else cout<<ans<<endl; return 0; }E – Escape
晚上看的这题，，网络流简单题，，主要是建图的方式，，，
题意就是一个矩形的迷宫（或者地图），，有些障碍，，而其他的地方可以放置一个转向器，，这个转向器有4中类型，，然后地图的上方有a个机器人，，下方有b个出口，，问你在随意添加一些转向器后的地图中，，机器人能否全部进入出口，，
首先，，任意两个机器人如果在某一段的路线一致，，那么一定会进入同一个出口，，而且如果两个机器人的路线相反一定会去到对方的起点，，
于是，，可以看出如果一个机器人经过一个转向器，，其他的机器人是不会经过这个转向器的，，
因为一开始的机器人都是先下走的，，如果两个进入同一个转向器A，，那么其中一个一定之前经过一个转向器B，，而且这个转向器B会在A的一端的那个方向，，这样子的话前面那个机器人又到不了转向器A了，，，所以是矛盾的，，因此一个转向器上只会经过一个机器人，，，也就是说这个点只能经过一次，，，也就是说如果将这个点看成一个转向器的话，，他只能经过一次，，就是流量是1，，
再考虑某个点不是转向器的情况: 显然不是转向器的话，，这个点可以经过两次： 一次横的一次竖的，，，也就是说将这点看成两个边： 竖的一条边和横着一条边，，他们的流量都是1，，，
但是有了竖边和横边怎么表示转向呢，，直接将连起来不就行了，，，
这样，，如果一条流是经过竖边表示从这个点经过，，然后想着竖直方向走下去，，同理横边，，，而如果是经过竖边->中间边->横边，，或者反过来就表示是这个点是一个转向器，，而且，，，这样的网络也会保证每个点只可能是一个转向器或者不是，，
最后将机器人连向对应的最上面的点，，表示机器人只能竖直向下走，，同理出口，，加上源汇点跑最大流，，如果流量等于机器人数就是说有一种方案使得每一个机器人进入出口，，，
然后我第一次写的建图方式会访问到第0行和第n+1行，，只想了第0行不会产生影响，，忘记了后面的那行会被多组数据覆盖，，wa到怀疑板子抄错->建图有锅，，，
话说isap为什么会跑出 998ms ，，这个可怕，，，那现场赛不是会有一堆人T穿，，，hlpp 就是友好的 233ms ,, 好吧，，是数组开大了，，，，
#include <bits/stdc++.h> #define aaa cout<<233<<endl; #define endl 'n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; // mt19937 rnd(time(0)); const int inf = 0x3f3f3f3f;//1061109567 > 1e9 const ll linf = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-6; const double pi = 3.14159265358979; const int maxn = 2e5 + 5; const int maxm = 2e6 + 233; const int mod = 1e9 + 7; struct edge { int to, nxt, cap, flow; }edge[maxm]; int tot, head[maxm]; void init() { tot = 0; memset(head, -1, sizeof head); } void addedge(int u, int v, int w, int rw = 0) { // cout << u << " " << v << endl; edge[tot].to = v; edge[tot].cap = w; edge[tot].nxt = head[u]; edge[tot].flow = 0; head[u] = tot++; edge[tot].to = u; edge[tot].cap = rw; edge[tot].nxt = head[v]; edge[tot].flow = 0; head[v] = tot++; } int gap[maxm], dep[maxm], pre[maxm], cur[maxm]; int que[maxm]; void bfs(int s, int t) { memset(dep, -1, sizeof dep); memset(gap, 0, sizeof gap); gap[0] = 1; int front = 0, rear = 0; dep[t] = 0; que[rear++] = t; while(front != rear) { int u = que[front++]; for(int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].to; if(dep[v] != -1)continue; que[rear++] = v; dep[v] = dep[u] + 1; ++gap[dep[v]]; } } } int sta[maxn]; int isap(int s, int t, int n) { bfs(s, t); memcpy(cur, head, sizeof head); int u = s; int top = 0; int maxflow = 0; while(dep[s] < n) { if(u == t) { int mi = inf; int inser; for(int i = 0; i < top; ++i) { if(mi > edge[sta[i]].cap - edge[sta[i]].flow) { mi = edge[sta[i]].cap - edge[sta[i]].flow; inser = i; } } for(int i = 0; i < top; ++i) { edge[sta[i]].flow += mi; edge[sta[i] ^ 1].flow -= mi; } maxflow += mi; top = inser; u = edge[sta[top] ^ 1].to; continue; } bool flag = false; int v; for(int i = cur[u]; ~i; i = edge[i].nxt) { v = edge[i].to; if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) { flag = true; cur[u] = i; break; } } if(flag) { sta[top++] = cur[u]; u = v; continue; } int mi = n; for(int i = head[u]; ~i; i = edge[i].nxt) { if(edge[i].cap - edge[i].flow && dep[edge[i].to] < mi) { mi = dep[edge[i].to]; cur[u] = i; } } --gap[dep[u]]; if(!gap[dep[u]])return maxflow; dep[u] = mi + 1; ++gap[dep[u]]; if(u != s)u = edge[sta[--top] ^ 1].to; } return maxflow; } int n, m, a, b; char mp[105][105]; int bots[105], exits[105]; inline getidx(int x, int y){return x * m + y;} int main() { // double pp = clock(); // freopen("233.in", "r", stdin); // freopen("233.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int ca; cin >> ca; while(ca--) { cin >> n >> m >> a >> b; for(int i = 1; i <= n; ++i)cin >> mp[i] + 1; for(int i = 1; i <= a; ++i)cin >> bots[i]; for(int i = 1; i <= b; ++i)cin >> exits[i]; init(); for(int i = 1; i <= m; ++i)mp[n + 1][i] = '0'; int sum = (n + 2) * m; int s = 0, t = sum * 2 + 1; for(int i = 1; i <= a; ++i)addedge(s, bots[i], 1); for(int i = 0; i <= n; ++i) for(int j = 1; j <= m; ++j) if(mp[i][j] != '1' && mp[i + 1][j] != '1') addedge(getidx(i, j), getidx(i + 1, j), 1), addedge(getidx(i + 1, j), getidx(i, j), 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m - 1; ++j) if(mp[i][j] != '1' && mp[i][j + 1] != '1') addedge(getidx(i, j) + sum, getidx(i, j + 1) + sum, 1), addedge(getidx(i, j + 1) + sum, getidx(i, j) + sum, 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(mp[i][j] != '1') addedge(getidx(i, j), getidx(i, j) + sum, 1), addedge(getidx(i, j) + sum, getidx(i, j), 1); for(int i = 1; i <= b; ++i)addedge(getidx(n + 1, exits[i]), t, 1); if(isap(s, t, t + 1) == a)cout << "Yes" << endl; else cout << "No" << endl; } // cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl; return 0; }这个拆点的方式很不错，，，
(end)
