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)
