學姐讓我打這個鍛煉思維，就做了一下，每四輪發一篇總結吧，也可以自己回憶一下，多吸取些經驗。

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

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

098

---

?

C - Attention

題意：有一些人面朝東方，一些人面朝西方站成一排，選一個人作為中點，反轉一些人，使所有人都面向中點，問最少反轉多少人

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

代碼：

# 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

題意：一個數列，選一個區間[l，r]使al ^ al + 1 ^ …… ^ ar ==?al + al + 1 + …… + ar，問滿足的區間右多少個

題解：預處理每個位置開始往后第一次數里有2^k的位置，然后就可以每次枚舉左端點，并且對于每一位的右端點為第二次出現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

?題意：一個數列，每次可以選擇長度為K的區間，刪掉其中最小值，可以刪至少Q次，使刪除數中最大值 - 最小值最小，輸出這個數

?題解：枚舉刪除最小值，那么比它還小的就一定不刪，這樣把數列分成了t個區間，找到t個區間所有能刪除的數中第Q小即可，復雜度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

題意：一個簡單無向圖，每個點有Ai和Bi兩個權值，當到達第i個點，所攜帶錢必須>=Ai，我們可以在第i個點捐贈Bi的錢，任意起點和終點，問把所有點都捐贈一次Bi所攜帶的最小初始金額

題解：

令Ci = max（Ai - Bi，0），即表示任意時刻在該點所攜帶的最少價錢為ai（包括已捐贈完畢時）

考慮Ci最大的點x，如果從圖中刪掉x后，圖變成了k個聯通塊，G1，G2……Gk

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

（因為如果一個點要經過多次，我們可以在最后一次再貢獻它，這樣可以為之前的貢獻提供更大的可能。）

然后我們發現這是一個樹的結構，把當前Ci最大點作為根節點，然后剩下各個聯通塊中ci最大的點和當前點連邊。

考慮把每個點按Ci升序排序，倒向從葉子節點構造樹，用dp和并查集，構造到根節點

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

因為我們要對每一個點貢獻，攜帶最少肯定是有s[i]的。考慮f[i]初始值，如果最后貢獻x，那么攜帶最少金錢得為Cx + sx。所以fi初始值為Cx

然后考慮把x貢獻提前到一個葉子節點之前，此時dp轉移式子為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]的錢，因為這樣捐完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

?

轉載于:https://www.cnblogs.com/lzdhydzzh/p/9178429.html

總結

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

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