當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【AtCoder】AGC034

發布時間：2024/7/5 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了【AtCoder】AGC034 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

AGC034

刷了那么久AtCoder我發現自己還是只會ABCE（手動再見

A - Kenken Race

大意是一個橫列，每個點可以跳一步或者跳兩步，每個格子是空地或者石頭，要求每一步不能走到石頭或者有人的格子上，求是否能把\(A\)移動到\(C\)，\(B\)移動到\(D\)，\(A < C,B < D,A < B\)

看\(A\)到\(C\)和\(B\)到\(D\)的路上有沒有兩個連在一起的石頭，有就不合法

如果\(A\)需要越過\(B\)，則看\(B\)到\(D\)的路上有沒有三個連在一起的空格，沒有就不合法

B - ABC

每次選擇\(ABC\)可以變成\(BCA\)，問最多幾次操作

統計以\(i\)為開始的后綴緊跟著有多少\(BC\)

如果\(s[i] == B,s[i + 1] == C\)那么\(suf[i] = suf[i + 2] + 1\)

如果\(s[i] == A\)那么\(suf[i] = suf[i + 1]\)

答案是每個\(s[i] == A\)的\(suf[i]\)

C - Tests

大意是兩個人一起考試，第一個人可以給每科分數分配一個重要度（每科的重要度是一個區間，第一個人在這個區間里選），然后自己拼命學，每學一科一小時這科分數就會+1，分數有上限是X，要求最后第一個人每科分數乘每科重要度大于等于第二個人每科分數乘每科重要度，求第一個人至少要學多久

考慮一下，如果每科重要度固定了，第一個人肯定先把重要度最大的學到滿分，再學次大的，答案肯定會是若干個X，加上至多一科不到X的

有了答案的形式，我們回過頭來看這個問題，可以對于計算每一科學到X后領先了第二個人多少，貪心的選k個X使得再選一個X，第一個人就超過第二個了

然后枚舉每一科，加上除了自己之外最大的k個X，再枚舉這一科學多久能超過第二個人，是個單調的函數，可以二分，于是就做完了

D - Manhattan Max Matching

題意是平面上有n個紅點和n個藍點，每個紅點和藍點有若干個紅球或藍球，總數相等，要求紅藍球兩兩匹配，每個匹配的價值是兩點曼哈頓距離，總數不超過10000，n<=1000

水平低，看見費用流的題總是做不出來

由于費用流的優秀性質，很容易發現費用流可以幫助我們在四種曼哈頓距離展開式中選擇最大的那種，于是我們建立四種點表示四種展開式，邊數就不是\(N^2\)而是\(N\)了

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define eps 1e-10 #define MAXN 2005 #define ba 47 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 +c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } int S,T,Ncnt,N; int a[2][MAXN],ty[4]; struct node {int to,next,cap;int64 val; }E[MAXN * 100]; int head[MAXN * 2],sumE = 1; int rx[MAXN],ry[MAXN],rc[MAXN]; int bx[MAXN],by[MAXN],bc[MAXN]; int dx[4] = {1,1,-1,-1}; int dy[4] = {1,-1,1,-1};void add(int u,int v,int c,int64 a) {E[++sumE].to = v;E[sumE].next = head[u];E[sumE].cap = c;E[sumE].val = a;head[u] = sumE; } void addtwo(int u,int v,int c,int64 a) {add(u,v,c,a);add(v,u,0,-a); } int64 dis[MAXN];bool inq[MAXN]; int preE[MAXN]; queue<int> Q; int64 SPFA() {for(int i = 1 ; i <= Ncnt ; ++i) dis[i] = -1e18;memset(inq,0,sizeof(inq));dis[S] = 0;inq[S] = 1;Q.push(S);while(!Q.empty()) {int u = Q.front();Q.pop();inq[u] = 0;for(int i = head[u] ; i ; i = E[i].next) {int v = E[i].to;if(E[i].cap) {if(dis[v] < dis[u] + E[i].val) {dis[v] = dis[u] + E[i].val;preE[v] = i;if(!inq[v]) {Q.push(v);inq[v] = 1;}}}}}return dis[T]; } void Init() {read(N);S = ++Ncnt;for(int i = 0 ; i < 2 ; ++i) {for(int j = 1 ; j <= N ; ++j) {a[i][j] = ++Ncnt;}}for(int i = 0 ; i < 4 ; ++i) ty[i] = ++Ncnt;T = ++Ncnt;for(int i = 1 ; i <= N ; ++i) {read(rx[i]);read(ry[i]);read(rc[i]);}for(int i = 1 ; i <= N ; ++i) {read(bx[i]);read(by[i]);read(bc[i]);}for(int i = 1 ; i <= N ; ++i) {addtwo(S,a[0][i],rc[i],0);for(int j = 0 ; j < 4 ; ++j) {addtwo(a[0][i],ty[j],1e9,dx[j] * rx[i] + dy[j] * ry[i]);}}for(int i = 1 ; i <= N ; ++i) {addtwo(a[1][i],T,bc[i],0);for(int j = 0 ; j < 4 ; ++j) {addtwo(ty[j],a[1][i],1e9,-dx[j] * bx[i] - dy[j] * by[i]);}} } void Solve() {int64 ans = 0;while(SPFA() > 0) {int p = preE[T],f = 1e9;while(p) {f = min(f,E[p].cap);p = preE[E[p ^ 1].to];}ans += dis[T] * f;p = preE[T];while(p) {E[p].cap -= f;E[p ^ 1].cap += f;p = preE[E[p ^ 1].to];}}out(ans);enter; } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifInit();Solve(); }

E - Complete Compress

題意：每個點初始時可能有一個標記，每次可以選擇兩個至少有一個標記的點，初始的時候點要距離至少為2，然后同時往離的更近的地方走一步，問可不可能把所有點移到一個點上，并且求最小距離

枚舉終點\(u\)，如果所有帶標記的點和\(u\)的距離的和是\(x\)，那么如果\(x\)是奇數顯然走不到，如果\(x\)是偶數，那么答案一定是\(\frac{x}{2}\)現在我們只要判答案是否存在

存在的前提是\(u\)去掉后每個子樹中的點可以和不同子樹中的配對，滿足條件是含有點最多的子樹中的點的個數小于等于所有點的一半

但是可能子樹里也可以兩兩配對，減小一部分距離，我們就自底向上dp計算每個點最多可以減少多少的距離

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define eps 1e-10 #define MAXN 500005 #define ba 47 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 +c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } const int MAXV = 150000,LEN = 450000; int N,M; int a[MAXN],d; int cnt[LEN + 5]; int getpos(int x) {return x - d + MAXV; } struct node {int l,r,val,cnt,lz; }tr[LEN * 4 + 5]; void update(int u) {tr[u].val = min(tr[u << 1].val,tr[u << 1 | 1].val);tr[u].cnt = 0;if(tr[u].val == tr[u << 1].val) tr[u].cnt += tr[u << 1].cnt;if(tr[u].val == tr[u << 1 | 1].val) tr[u].cnt += tr[u << 1 | 1].cnt; } void build(int u,int l,int r) {tr[u].l = l;tr[u].r = r;if(l == r) {tr[u].cnt = 1;return;}int mid = (l + r) >> 1;build(u << 1,l,mid);build(u << 1 | 1,mid + 1,r);update(u); } void addlz(int u,int v) {tr[u].val += v;tr[u].lz += v; } void pushdown(int u) {if(tr[u].lz) {addlz(u << 1,tr[u].lz);addlz(u << 1 | 1,tr[u].lz);tr[u].lz = 0;} } void add(int u,int l,int r,int v) {if(tr[u].l == l && tr[u].r == r) {addlz(u,v);return;}pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(r <= mid) add(u << 1,l,r,v);else if(l > mid) add(u << 1 | 1,l,r,v);else {add(u << 1,l,mid,v);add(u << 1 | 1,mid + 1,r,v);}update(u); } pii Query(int u,int l,int r) {if(tr[u].l == l && tr[u].r == r) return mp(tr[u].val,tr[u].cnt);pushdown(u);int mid = (tr[u].l + tr[u].r) >> 1;if(r <= mid) return Query(u << 1,l,r);else if(l > mid) return Query(u << 1 | 1,l,r);else {pii a = Query(u << 1,l,mid),b = Query(u << 1 | 1,mid + 1,r);if(a.fi > b.fi) swap(a,b);if(a.fi == b.fi) a.se += b.se;return a;} } void Solve() {read(N);read(M);build(1,1,LEN);for(int i = 1 ; i <= N ; ++i) {read(a[i]);a[i] += MAXV;add(1,a[i] - cnt[a[i]],a[i] - cnt[a[i]],1);cnt[a[i]]++;}int p,x;for(int i = 1 ; i <= M ; ++i) {read(p);read(x);if(p == 0) {if(x == 1) {if(cnt[getpos(N)]) {add(1,getpos(N) - cnt[getpos(N)] + 1,getpos(N),-1);}}else {if(cnt[getpos(N + 1)]) {add(1,getpos(N + 1) - cnt[getpos(N + 1)] + 1,getpos(N + 1),1);}}d += x;}else {if(a[p] <= getpos(N)) {add(1,a[p] - cnt[a[p]] + 1,a[p] - cnt[a[p]] + 1,-1);}cnt[a[p]]--;a[p] = x - d + MAXV;if(a[p] <= getpos(N)) {add(1,a[p] - cnt[a[p]],a[p] - cnt[a[p]],1);}cnt[a[p]]++;}pii res = Query(1,getpos(1),getpos(N));int ans = 0;if(res.fi == 0) ans = res.se;out(ans);enter;} } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve(); }

F - RNG and XOR

題目大意：有一個隨機數生成器每個數以一定概率生成\(0\)到\(2^{N} - 1\)的整數值，初始有一個X，每次進行操作生成一個數\(v\)，然后\(X = X \oplus v\)那個符號是異或，問從\(X\)第一次到\([0,2^{N} - 1]\)的期望步數是多少

我們可以變成從一個數\(i\)到\(0\)的期望步數，這顯然是等價的
\[ x_{i} = (\sum_{j = 0}^{2^{N} - 1} p_{j}x_{j \oplus i}) + 1 \]
em，這個形式看起來沒什么幫助

于是我們把1移過去
\[ x_{i} - 1 = \sum_{j = 0}^{2^{N} - 1} p_{j}x_{j \oplus i} \]
于是我們可以想到。。。FWT的異或卷積
\[ (x_{0},x_1,x_2,x_3\cdots x_{2^{N} - 1})\bigoplus(p_{0},p_{1},p_{2},p_{3}\cdots p_{2^{N} - 1}) = (?,x_{1} - 1,x_{2} - 1,x_{3} - 1,\cdots x_{2^{N} - 1} - 1) \]
\(?\)應該是啥。。就是又發現前后的總和應該不變，于是\(?\)就是\(x_{0} + 2^{N} - 1\)

于是式子變成

\[ (x_{0},x_1,x_2,x_3\cdots x_{2^{N} - 1})\bigoplus(p_{0},p_{1},p_{2},p_{3}\cdots p_{2^{N} - 1}) = (x_{0} + 2^{N}-1,x_{1} - 1,x_{2} - 1,x_{3} - 1,\cdots x_{2^{N} - 1} - 1) \]
em，又有個小技巧，把\(p_0\)減去1，很容易發現我們把后面的變量都消掉了！
\[ (x_{0},x_1,x_2,x_3\cdots x_{2^{N} - 1})\bigoplus(p_{0} - 1,p_{1},p_{2},p_{3}\cdots p_{2^{N} - 1}) = (2^{N}-1,- 1,- 1,- 1,\cdots - 1) \]
這樣的話，我們相當于求一個FWT異或卷積的逆，這個可以類似的遞歸實現

但是最后呢有一層是
\[ x_{0} + x_1 + x_2 + x_3 + \cdots + x_{2^{N} - 1}\bigoplus(p_{0} - 1 + p_{1} + p_{2} + p_{3} + \cdots + p_{2^{N} - 1}) = 0 \]
這個時候沒有什么貢獻，于是我們選擇把每個\(x\)都加上一個常數，最后用\(x_{0} = 0\)把這個常數消掉，于是到了這一層可以返回一個任意的正數

#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int,int> #define mp make_pair #define pb push_back #define space putchar(' ') #define enter putchar('\n') #define eps 1e-10 #define MAXN 2005 #define ba 47 //#define ivorysi using namespace std; typedef long long int64; typedef unsigned int u32; typedef double db; template<class T> void read(T &res) {res = 0;T f = 1;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {res = res * 10 +c - '0';c = getchar();}res *= f; } template<class T> void out(T x) {if(x < 0) {x = -x;putchar('-');}if(x >= 10) {out(x / 10);}putchar('0' + x % 10); } const int MOD = 998244353,inv2 = (MOD + 1) / 2; int N,A[(1 << 18) + 5],S; int inc(int a,int b) {return a + b >= MOD ? a + b - MOD : a + b; } int mul(int a,int b) {return 1LL * a * b % MOD; } void update(int &x,int y) {x = inc(x,y); } int fpow(int x,int c) {int res = 1,t = x;while(c) {if(c & 1) res = mul(res,t);t = mul(t,t);c >>= 1;}return res; } vector<int> trans(vector<int> p,vector<int> m) {if(p.size() == 1) {if(p[0] == 0 && m[0] == 0) return (vector<int>){1};else return (vector<int>){mul(m[0],fpow(p[0],MOD - 2))};}vector<int> p0,p1,m0,m1;for(int i = 0 ; i < p.size() ; i += 2) {p0.pb(inc(p[i],p[i + 1]));p1.pb(inc(p[i],MOD - p[i + 1]));m0.pb(inc(m[i],m[i + 1]));m1.pb(inc(m[i],MOD - m[i + 1]));}p0 = trans(p0,m0);p1 = trans(p1,m1);vector<int> res;for(int i = 0 ; i < p0.size() ; ++i) {res.pb(mul(inc(p0[i],p1[i]),inv2));res.pb(mul(inc(p0[i],MOD - p1[i]),inv2));}return res; } void Solve() {read(N);for(int i = 0 ; i < (1 << N) ; ++i) {read(A[i]);update(S,A[i]);}S = fpow(S,MOD - 2);for(int i = 0 ; i < (1 << N) ; ++i) {A[i] = mul(A[i],S);}vector<int> a,b;b.pb((1 << N) - 1);for(int i = 1 ; i < (1 << N) ; ++i) b.pb(-1);for(int i = 0 ; i < (1 << N) ; ++i) {int t = A[i];if(i == 0) t = inc(t,MOD - 1);a.pb(t);}vector<int> ans = trans(a,b);for(int i = 0 ; i < (1 << N) ; ++i) {out(inc(ans[i],MOD - ans[0]));enter;} } int main() { #ifdef ivorysifreopen("f1.in","r",stdin); #endifSolve(); }

轉載于:https://www.cnblogs.com/ivorysi/p/10984113.html

總結

以上是生活随笔為你收集整理的【AtCoder】AGC034的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

AtCoder