學(xué)姐讓我打這個(gè)鍛煉思維，就做了一下，每四輪發(fā)一篇總結(jié)吧，也可以自己回憶一下，多吸取些經(jīng)驗(yàn)。

大概的狀況就是C,D秒切,E想一會(huì)兒，F做不來(lái)，但095F竟然想出來(lái)了。。

看英文題解結(jié)合lj谷歌翻譯真的鬼火氣

098

---

?

C - Attention

題意：有一些人面朝東方，一些人面朝西方站成一排，選一個(gè)人作為中點(diǎn)，反轉(zhuǎn)一些人，使所有人都面向中點(diǎn)，問(wèn)最少反轉(zhuǎn)多少人

題解：就是記錄一下面朝東方or西方的前綴和，O（n）枚舉每一個(gè)人作為中點(diǎn)的代價(jià)就好

代碼：

# include <iostream> # include <cstdio> using namespace std; const int N = 3e5 + 12; int sum[N],n; char str[N]; int main() {scanf("%d",&n);scanf("%s",str + 1);for(int i = 1;i <= n;i++)sum[i] = str[i] == 'E',sum[i] += sum[i - 1];int mx = N;for(int i = 1;i <= n;i++)mx = min(mx,i - 1 - sum[i - 1] + sum[n] - sum[i]);printf("%d\n",mx); } 098C

?

D - Xor Sum 2

題意：一個(gè)數(shù)列，選一個(gè)區(qū)間[l，r]使al ^ al + 1 ^ …… ^ ar ==?al + al + 1 + …… + ar，問(wèn)滿足的區(qū)間右多少個(gè)

題解：預(yù)處理每個(gè)位置開始往后第一次數(shù)里有2^k的位置，然后就可以每次枚舉左端點(diǎn)，并且對(duì)于每一位的右端點(diǎn)為第二次出現(xiàn)2^k的位置 - 1，取min即可

代碼：

# include <iostream> # include <cstdio> using namespace std; const int N = 3e5 + 12; int nex[N][22],a[N],n;long long ans; int main() {scanf("%d",&n);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);for(int j = 0;j <= 20;j++)nex[n + 1][j] = nex[n + 2][j] = n + 1;for(int i = n;i >= 1;i--)for(int j = 0;j <= 20;j++)nex[i][j] = (a[i] >> j & 1) ? i : nex[i + 1][j];for(int i = 1;i <= n;i++){int mx = N;for(int j = 0;j <= 20;j++)mx = min(nex[nex[i][j] + 1][j],mx);ans += mx - i;}printf("%lld\n",ans); } 098D

E - Range Minimum Queries

?題意：一個(gè)數(shù)列，每次可以選擇長(zhǎng)度為K的區(qū)間，刪掉其中最小值，可以刪至少Q(mào)次，使刪除數(shù)中最大值 - 最小值最小，輸出這個(gè)數(shù)

?題解：枚舉刪除最小值，那么比它還小的就一定不刪，這樣把數(shù)列分成了t個(gè)區(qū)間，找到t個(gè)區(qū)間所有能刪除的數(shù)中第Q小即可，復(fù)雜度O(n^2logn）

?代碼：

# include <iostream> # include <cstdio> # include <algorithm> using namespace std; const int N = 3e5 + 12; const int inf = 0x7fffffff; int a[N],n,k,q,ans = inf,b[N],c[N]; int solve(int w) {int l,r;c[0] = 0;for(int i = 1;i <= n;i = r + 1){l = i;while(l <= n && a[l] < w)l++;r = l;while(r <= n && a[r] >= w)r++;r--;b[0] = 0;for(int j = l;j <= r;j++)b[++b[0]] = a[j];if(b[0] < k)continue;sort(b + 1,b + b[0] + 1);for(int j = 1;j <= b[0] - k + 1;j++)c[++c[0]] = b[j];}if(c[0] < q)return inf;sort(c + 1,c + c[0] + 1);return c[q] - w; } int main() {scanf("%d %d %d",&n,&k,&q);for(int i = 1;i <= n;i++)scanf("%d",&a[i]);for(int i = 1;i <= n;i++)ans = min(ans,solve(a[i]));printf("%d\n",ans); } 098E

F - Donation

題意：一個(gè)簡(jiǎn)單無(wú)向圖，每個(gè)點(diǎn)有Ai和Bi兩個(gè)權(quán)值，當(dāng)?shù)竭_(dá)第i個(gè)點(diǎn)，所攜帶錢必須>=Ai，我們可以在第i個(gè)點(diǎn)捐贈(zèng)Bi的錢，任意起點(diǎn)和終點(diǎn)，問(wèn)把所有點(diǎn)都捐贈(zèng)一次Bi所攜帶的最小初始金額

題解：

令Ci = max（Ai - Bi，0），即表示任意時(shí)刻在該點(diǎn)所攜帶的最少價(jià)錢為ai（包括已捐贈(zèng)完畢時(shí)）

考慮Ci最大的點(diǎn)x，如果從圖中刪掉x后，圖變成了k個(gè)聯(lián)通塊，G1，G2……Gk

我們貢獻(xiàn)的順序一定是從中挑選出一個(gè)Gi，然后按G1，G2 ……Gi-1 ，Gi + 1 ……Gk ，x，Gi，這樣貢獻(xiàn)

（因?yàn)槿绻粋€(gè)點(diǎn)要經(jīng)過(guò)多次，我們可以在最后一次再貢獻(xiàn)它，這樣可以為之前的貢獻(xiàn)提供更大的可能。）

然后我們發(fā)現(xiàn)這是一個(gè)樹的結(jié)構(gòu)，把當(dāng)前Ci最大點(diǎn)作為根節(jié)點(diǎn)，然后剩下各個(gè)聯(lián)通塊中ci最大的點(diǎn)和當(dāng)前點(diǎn)連邊。

考慮把每個(gè)點(diǎn)按Ci升序排序，倒向從葉子節(jié)點(diǎn)構(gòu)造樹，用dp和并查集，構(gòu)造到根節(jié)點(diǎn)

設(shè)s[i]為以i為根的子樹內(nèi)bi和，f[i]為攜帶初始價(jià)錢最少要比s[i]多多少。

因?yàn)槲覀円獙?duì)每一個(gè)點(diǎn)貢獻(xiàn)，攜帶最少肯定是有s[i]的。考慮f[i]初始值，如果最后貢獻(xiàn)x，那么攜帶最少金錢得為Cx + sx。所以fi初始值為Cx

然后考慮把x貢獻(xiàn)提前到一個(gè)葉子節(jié)點(diǎn)之前，此時(shí)dp轉(zhuǎn)移式子為f[x] = min（f[x]，max（f[v]，C[x] - s[v]）);

首先在x捐完除了v以外的所有子樹后，所剩錢肯定要≥C[x]

如果f[v]?+?s[v]?>? C[x]，一開始要帶s[x]?+?f[v]的錢，因?yàn)檫@樣捐完x后剩下錢剛好為s[y] + f[v]。

如果f[v]?+?s[v] <=? C[x]，一開始要帶s[x]?+ C[x]???s[y]的錢，這樣捐完x后剩下C[x]的錢，是一定夠的

最后輸出f[root] + s[root]即可

代碼：

# include <iostream> # include <cstdio> # include <algorithm> using namespace std; const int N = 3e5 + 12; const int inf = 0x7fffffff; int a[N],b[N],id[N],n,m,head[N],dt,fa[N];bool vis[N]; long long f[N],s[N]; int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);} struct Edge{int to,nex;}edge[N << 2]; void AddEdge(int u,int v){edge[++dt] = (Edge){v,head[u]};head[u] = dt;} bool cmp(int x,int y){return a[x] < a[y];} int main() {scanf("%d %d",&n,&m);for(int i = 1;i <= n;i++)scanf("%d %d",&a[i],&b[i]),a[i] = max(a[i] - b[i],0),id[i] = fa[i] = i;sort(id + 1,id + n + 1,cmp);int u,v;for(int i = 1;i <= m;i++)scanf("%d %d",&u,&v),AddEdge(u,v),AddEdge(v,u);for(int t = 1;t <= n;t++){u = id[t];vis[u] = true;f[u] = a[u];s[u] = b[u];for(int i = head[u];i;i = edge[i].nex)if(vis[edge[i].to]){v = find(edge[i].to);if(u == v)continue;fa[v] = u;s[u] += s[v];f[u] = min(f[u],max(f[v],a[u] - s[v])); }}printf("%lld\n",f[id[n]] + s[id[n]]); } 098F

?

轉(zhuǎn)載于:https://www.cnblogs.com/lzdhydzzh/p/9178429.html

總結(jié)

以上是生活随笔為你收集整理的AtCoder Regular Contest 098的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。