AtCoder Regular Contest 098
學姐讓我打這個鍛煉思維,就做了一下,每四輪發一篇總結吧,也可以自己回憶一下,多吸取些經驗。
大概的狀況就是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); } 098DE - 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); } 098EF - 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的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: IDEA mybatis-generat
- 下一篇: executing an update/