咕咕咕

C：普及組難度的題

D：給定$a_{1\cdots n}$，求有多少$1\leq l\leq r\leq n$滿足$x_l+\cdots+x_r=x_l\text^\cdots\text^x_r$

因為異或是不進位加法，所以枚舉左端點暴力拓展右端點即可，一旦發生進位就break即可，對$0$要特殊處理

#include<stdio.h> typedef long long ll; int a[200010],len[200010]; int main(){int n,i,j;ll ans,x;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",a+i);for(i=n;i>0;i--){if(a[i]==0)len[i]=len[i+1]+1;}ans=0;for(i=1;i<=n;i++){x=0;for(j=i;j<=n;){if(a[j]==0){ans+=len[j];j+=len[j];}else{if(x&a[j])break;x^=a[j];ans++;j++;}}}printf("%lld",ans); }

E：給定$a_{1\cdots n},k,q$，你要進行$q$次操作，每次操作可以選擇一個長度為$k$的區間并刪掉區間最小值，最小化刪掉的數的極差

枚舉刪掉的最小值$x$，那么可以刪掉的數必須處在連續$k$個$\geq x$的數中，對每個長度為$l(l\geq k)$的所有數都$\geq x$的極長區間排序后取前$l-k+1$小的數，最后把這些數選出來排序取第$q$小作為刪除的最大值更新答案即可

#include<stdio.h> #include<algorithm> using namespace std; const int inf=2147483647; int a[2010],t[2010],al[2010],n,k,q; int work(int x){int i,j,s,M;s=M=0;for(i=1;i<=n+1;i++){if(a[i]>=a[x]){if(s==0)s=i;}else if(s){if(i-s>=k){for(j=s;j<i;j++)t[j-s+1]=a[j];sort(t+1,t+i-s+1);for(j=1;j+k-1<=i-s;j++){M++;al[M]=t[j];}}s=0;}}if(M<q)return inf;sort(al+1,al+M+1);return al[q]-a[x]; } int main(){int i,ans;scanf("%d%d%d",&n,&k,&q);for(i=1;i<=n;i++)scanf("%d",a+i);ans=inf;for(i=1;i<=n;i++)ans=min(ans,work(i));printf("%d",ans); }

F：給定一個簡單連通無向圖，每個點有$a_i,b_i$，一個人可以帶$w$的錢從任意$w\geq a_x$的$x$開始走，每走一條邊要求目標節點$v$滿足$w\geq a_v$，他也可以選擇在$x$捐贈$b_i$，問捐贈完所有節點至少要多少錢

首先我們把$a_i$變成$\max(a_i-b_i,0)$并加一條限制：在$x$捐贈后也要滿足$w\geq a_x$，容易看出這是不會改變答案的

存在一個最優解使得任意節點在被捐贈后不會再被經過，因為如果這樣我們可以延遲捐贈，這并不會讓答案變大

假設$x$有最大的$a_x$且刪掉$x$后原圖被分成許多連通塊$G_{1\cdots k}$，那么存在這樣一種最優解：先捐$G_{1\cdots i-1},G_{i+1\cdots k}$，再捐$x$，再進入$G_i$捐贈且以后都不再走出$G_i$

假如存在$w\in G_i$且先捐$w$后捐$x$，那么我們可以先不捐$w$而是在捐$x$后立刻走到$w$并捐$w$，因為$x$有最大的$a_x$，所以這總是能實現的，并且不會讓答案變大

到這里思路就很清晰了，我們每次找出最大的$a_x$，把$x$作為根并遞歸進$G_{1\cdots k}$建出一棵樹，在這棵樹上的最優解就對應著原圖的最優解

考慮DP，因為答案肯定$\geq\sum b_i$，不妨設$s_i=\sum\limits_{j\in\text{subtree}(i)}b_j$，$f_i$表示要比$s_i$多帶多少錢，那么轉移就是$f_x\mathop\longleftarrow\limits^\min\max(f_y,a_x-s_y)$

首先在$x$捐完除了$y$以外的所有子樹后，帶的錢肯定要$\geq a_x$

如果$f_y+s_y\gt a_x$，那么要帶更多錢（這同時保證了即將從$x$到$y$的時候帶的錢$\geq a_x$），也就是直接按$y$的限制，所以一開始要帶$s_x+f_y$的錢，這樣到$y$就有$s_y+f_y$的錢，而這也是捐完子樹$y$的最小值

否則不需要考慮$y$的限制，因為剩下的錢肯定夠了，所以要帶$s_x+a_x-s_y$的錢，這樣捐完$x$后剛好剩下$a_x$，是足夠捐完子樹$y$的

#include<stdio.h> #include<algorithm> using namespace std; typedef long long ll; struct node{int x,v;node(int a=0,int b=0){x=a;v=b;} }p[100010]; int h[100010],nex[200010],to[200010],a[100010],b[100010],fa[100010],M; ll s[100010],f[100010]; bool v[100010]; void add(int a,int b){M++;to[M]=b;nex[M]=h[a];h[a]=M; } bool operator<(node a,node b){return a.v<b.v;} int get(int x){return x==fa[x]?x:(fa[x]=get(fa[x]));} int main(){int n,m,i,j,x,y;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){scanf("%d%d",a+i,b+i);a[i]=max(a[i]-b[i],0);p[i]=node(i,a[i]);}while(m--){scanf("%d%d",&x,&y);add(x,y);add(y,x);}sort(p+1,p+n+1);for(i=1;i<=n;i++){fa[i]=i;s[i]=b[i];f[i]=a[i];}for(i=1;i<=n;i++){v[p[i].x]=1;for(j=h[p[i].x];j;j=nex[j]){if(v[to[j]]){x=get(p[i].x);y=get(to[j]);if(x==y)continue;fa[y]=x;s[x]+=s[y];f[x]=min(f[x],max(f[y],a[x]-s[y]));}}}x=get(1);printf("%lld",f[x]+s[x]); }

咕咕咕

轉載于:https://www.cnblogs.com/jefflyy/p/9115550.html

總結

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

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