Codeforces Round 1305简要题解

A：略
B：略
C：略
D：略
E：考虑选择合适的$k$，先填$1$到$k$，补一个$k+1$到$2k$之间的数凑出$m$，剩下部分补上很大的数。

#include using namespace std;int sum[100005],id[100005];
int f[10005];int main() {int n,m;scanf("%d%d",&n,&m);if (!m) {for(int i=1;i<=n;i++) printf("%d ",n+i);printf("\n");return 0;}for(int i=1;i<=n;i++) f[i]=(((i*(i-1)>>1)-(i>>1))>>1);if (m>f[n]) {puts("-1");return 0;}for(int i=1;i<=n;i++)if (f[i]>=m) {int k=i-1;for(int j=1;j<=k;j++)for(int l=j+1;l<=k;l++) sum[j+l]++;for(int j=k+1;j<=2*k;j++) id[sum[j]]=j;for(int j=1;j<=k;j++) printf("%d ",j);printf("%d ",id[m-f[i-1]]);int s=5e8;for(int j=k+2;j<=n;j++) {printf("%d ",s);s+=3*n;}printf("\n");return 0;}return 0;
}

F：枚举$\gcd$中的一个质因子，容易$\mathcal{O}(n)$计算答案。注意到答案不超过$n$，因此至少有一半的位置变化量绝对值不超过$1$。多次随机一个位置，枚举变化量（$0$，$1$，$-1$），分解质因数后暴力计算即可，正确率是 1 − 2 − k 1-2^{-k} 1−2−k（$k$是随机次数）级别的。

#include 
#include using namespace std;typedef long long ll;int prime[1000005],tot;
bool check[1000005];void pre() {for(int i=2;i<=1e6;i++) {if (!check[i]) prime[++tot]=i;for(int j=1;j<=tot&&i*prime[j]<=1e6;j++) {check[i*prime[j]]=1;if (i%prime[j]==0) break;}}
}map <ll,bool> mp;
ll num[200005],ans;void solve(int n,ll k) {ll s=0;for(int i=1;i<=n;i++)if (num[i]<=k) s+=k-num[i];else s+=min(k-num[i]%k,num[i]%k);ans=min(ans,s);
}void getfact(int n,ll x) {ll t=x;for(int i=1;i<=tot&&(ll)prime[i]*prime[i]<=t;i++)if (t%prime[i]==0) {while (x%prime[i]==0) x/=prime[i];if (!mp.count(prime[i])) {mp[prime[i]]=1;solve(n,prime[i]);}}if (x>1) {if (!mp.count(x)) {mp[x]=1;solve(n,x);}}
}int main() {srand(time(0));pre();int n;scanf("%d",&n);for(int i=1;i<=n;i++) {scanf("%lld",&num[i]);if (num[i]&1) ans++;}if (n<=1e2) {for(int i=1;i<=n;i++) {int t=i;getfact(n,num[t]);if (num[t]>1) getfact(n,num[t]-1);getfact(n,num[t]+1);}}else {for(int i=1;i<=20;i++) {int t=(ll)rand()*rand()%n+1;getfact(n,num[t]);if (num[t]>1) getfact(n,num[t]-1);getfact(n,num[t]+1);}}printf("%lld\n",ans);return 0;
}

G：
有一个非常有趣的trick。
加入一个 a n + 1 = 0 a_{n+1}=0 an+1​=0，看起来问题是求一个有向图的有根最大树形图，这并不容易快速解决。
不过可以发现若存在$i->j$的边，也会同时存在$j->i$的边，且边权分别为 a i a_i ai​和 a j a_j aj​。如果将一条$i->j$的有向边视为无向，且边权设为 a i + a j a_i+a_j ai​+aj​，那么答案就是新图的MST减去所有 a i a_i ai​的和。
于是只用解决问题的无向版本，一个比较优秀的做法是用Borůvka算法，做$\mathcal{O}(\log n)$轮，每轮给每个点$i$找出满足 a i a_i ai​ AND a j = 0 a_j=0 aj​=0且$i$和$j$还未连通的最大的 a j a_j aj​缩起来。这个可以做一个类似高维前缀和的DP快速实现。
时间复杂度 O ( n log ⁡ 2 n ) \mathcal O(n\log^2n) O(nlog2n)。

#include 
#define FR first
#define SE second
#define inf 0x3f3f3f3fusing namespace std;typedef pair<int,int> pr;
typedef long long ll;int num[200005],col[200005];inline pr merge(pr x,pr y) {if (num[x.FR]<num[y.FR]) swap(x,y);if (col[x.FR]!=col[y.FR]&&num[y.FR]>num[x.SE]) return pr(x.FR,y.FR);else if (col[x.SE]!=y.SE&&num[y.SE]>num[x.SE]) return pr(x.FR,y.SE);else return x; 
}pr f[1<<18];void fwt(int len) {for(int i=1;i<len;i<<=1)for(int j=0;j<len;j++)if (j&i) f[j]=merge(f[j],f[j^i]);
}int p[200005],val[200005];
vector <int> e[200005];
int bel[200005];bool vis[200005],vis2[200005];ll dfs(int x) {vis[x]=1;ll s=0;for(int i=0;i<e[x].size();i++)if (!vis[e[x][i]]) {int u=e[x][i];bel[u]=bel[x];s+=dfs(u)+val[u];}return s;
}int main() {int n;scanf("%d",&n);ll ans=0;int maxn=0;for(int i=1;i<=n;i++) {scanf("%d",&num[i]);ans-=num[i];maxn=max(maxn,num[i]);}int len=1;while (len<=maxn) len<<=1;n++;for(int i=1;i<=n;i++) col[i]=i;int sz=n;num[0]=-1;val[0]=inf;while (sz>1) {for(int i=0;i<len;i++) f[i]=pr(0,0);for(int i=1;i<=n;i++) f[num[i]]=merge(f[num[i]],pr(i,0));fwt(len);for(int i=1;i<=sz;i++) {p[i]=0;val[i]=-1;}for(int i=1;i<=n;i++) {pr t=f[(len-1)^num[i]];int v=((col[t.FR]!=col[i])?t.FR:t.SE);if (v&&num[i]+num[v]>val[col[i]]) {p[col[i]]=col[v];val[col[i]]=num[i]+num[v];}}for(int i=1;i<=sz;i++) e[i].clear();for(int i=1;i<=sz;i++) {vis[i]=vis2[i]=0;e[p[i]].push_back(i);}int sz2=0;for(int i=1;i<=sz;i++)if (!vis[i]) {int x=i;do {vis2[x]=1;x=p[x];} while (!vis2[x]);int id=0;int y=x;do {if (val[x]<val[id]) id=x;x=p[x];} while (y!=x);bel[id]=++sz2;ans+=dfs(id);}for(int i=1;i<=n;i++) col[i]=bel[col[i]];sz=sz2;} printf("%lld\n",ans);return 0;
}

H：
先考虑一个很有意思的问题。
对于一个二分图上下界网络流的问题，左右两侧的点到源汇流量都有上下界，中间的边流量有上界。如何判定是否有合法的流，如果有的话最大流是多少？
第一个问题，结论是存在合法流的充要条件为：忽略右部图到汇点边的下界，将左部图到源点边的上界改为原来的下界（新图没有下界），新图能使左部图到源点边满流；且忽略左部图到源点边的下界，将右部图到汇点边的上界改为原来的下界（新图没有下界），新图能使右部图到汇点边满流。必要性显然，充分性考虑用得到的两个流，构造一个合法流，将两个流消掉公共部分后，第一个流剩余的从左往右连，第二个流剩余的从右往左连，得到一个图。不断消掉偶环，可以得到一个森林，每次取出两个叶子间路径调整即可。
第二个问题，结论为若存在合法流，最大流与忽略所有下界后得到的图最大流相等。证明与上面的充分性证明类似。
有了这个结论，考虑若钦定$m$个人的成绩分别为 a 1 ≥ a 2 ≥ a 3 . . . ≥ a m a_1\geq a_2\geq a_3...\geq a_m a1​≥a2​≥a3​...≥am​，利用最小割最大流定理，则合法的条件为：

1. ∑ i = 1 n a i = t \sum_{i=1}^{n} a_i=t ∑i=1n​ai​=t
2. 将 l i l_i li​从小到大排序后，$\forall 0\le i\le n$，$1\le j\le m$， ∑ k = 1 i l k + ∑ k = j m a k + ( n − i ) ( j − 1 ) ≥ ∑ i = 1 n l i \sum_{k=1}^{i}l_k+\sum_{k=j}^{m}a_k+(n-i)(j-1)\geq \sum_{i=1}^{n}l_i ∑k=1i​lk​+∑k=jm​ak​+(n−i)(j−1)≥∑i=1n​li​
3. 将 r i r_i ri​从小到大排序后，$\forall 0\le i\le n$，$1\le j\le m$， ∑ k = 1 i r k + ∑ k = j m a k + ( n − i ) ( j − 1 ) ≥ t \sum_{k=1}^{i}r_k+\sum_{k=j}^{m}a_k+(n-i)(j-1)\geq t ∑k=1i​rk​+∑k=jm​ak​+(n−i)(j−1)≥t

这样，我们可以对每个$i$得出 ∑ j = i m a j \sum_{j=i}^{m}a_j ∑j=im​aj​的下界，设为 b o u n d i bound_i boundi​，暴力求是平方的，注意到$l$和$r$是单调的，可以用斜率优化加速。
问题转化为给定 b o u n d i bound_i boundi​，总和和若干位置的值，先判定是否有合法解，若有解，求出符合条件的非增 a i a_i ai​中，最多有多少个 a i = a 1 a_i=a_1 ai​=a1​，以及此时最大的 a 1 a_1 a1​。
先考虑判定是否有合法解，考虑倒序贪心，我们会在满足一个后缀$i$的条件的时候，尽可能最小化总和以及此时的 a i a_i ai​，容易线性时间内完成贪心。
若有解，给定一个$k$，要求 a 1 = a 2 . . . = a k a_1=a_2...=a_k a1​=a2​...=ak​且最大化 a 1 a_1 a1​，可以对$k+1$到$m$的部分贪心最小化后判定。
枚举$k$的过程可以二分，也可以预处理一些信息后直接线性解决。
时间复杂度瓶颈是排序的$\mathcal{O}(n\log n)$。

#include 
#define last last2using namespace std;typedef long long ll;struct Point {ll x,y;Point() {}Point(ll a,ll b):x(a),y(b) {}Point operator - (Point b) {return Point(x-b.x,y-b.y);}
};ll cross(Point x,Point y) {return x.x*y.y-x.y*y.x;
}Point st[100005];
int top;ll calc(Point x,ll k) {return x.x*k+x.y;
}void insert(Point p) {while (top>1&&cross(p-st[top],st[top]-st[top-1])>=0) top--;st[++top]=p;
}int a[100005],b[100005],num[100005];
ll up[100005];void convex(int n,int m,ll lb,ll rb) {ll s=0;for(int i=1;i<=n;i++) s+=a[i];top=0;for(int i=n;i>=0;i--) {insert(Point(n-i,s));s-=a[i];}int r=1;for(int i=1;i<=m;i++) {while (r<top&&calc(st[r+1],m-i)<=calc(st[r],m-i)) r++;up[i]=max(up[i],lb-calc(st[r],m-i));}s=0;for(int i=1;i<=n;i++) s+=b[i];top=0;for(int i=n;i>=0;i--) {insert(Point(n-i,s));s-=b[i];}r=1;for(int i=1;i<=m;i++) {while (r<top&&calc(st[r+1],m-i)<=calc(st[r],m-i)) r++;up[i]=max(up[i],rb-calc(st[r],m-i));}
}bool solve1(int n,ll rb) {ll s1=0,s2=0,maxn=0;int last=0;for(int i=1;i<=n;i++)if (num[i]!=-1) {if (maxn>num[i]) return 0;s1+=num[i];s2+=(ll)(i-last-1)*(num[i]-maxn);if (s1<up[i]) {if (s1+s2<up[i]) return 0;s2-=up[i]-s1;s1=up[i];}last=i;maxn=num[i];}else {s1+=maxn;if (s1<up[i]) {if (s1+s2>=up[i]) {s2-=up[i]-s1;s1=up[i];}else {ll v=up[i]-s1-s2,t=(v+i-last-1)/(i-last);maxn+=t;s1=up[i];s2=t*(i-last)-v;}}}return s1<=rb&&(s1+s2>=rb||num[n]!=-1);
}int solve2(int n,int k,ll rb) {ll s1=0,s2=0,maxn=0;int last=0;for(int i=1;i<=n-k;i++)if (num[i]!=-1) {s1+=num[i];s2+=(ll)(i-last-1)*(num[i]-maxn);if (s1<up[i]) {s2-=up[i]-s1;s1=up[i];}last=i;maxn=num[i];}else {s1+=maxn;if (s1<up[i]) {if (s1+s2>=up[i]) {s2-=up[i]-s1;s1=up[i];}else {ll v=up[i]-s1-s2,t=(v+i-last-1)/(i-last);maxn+=t;s1=up[i];s2=t*(i-last)-v;}}}ll t=-1;for(int i=n-k+1;i<=n;i++)if (num[i]!=-1) {if (t==-1) t=num[i];else if (t!=num[i]) return -1;}if (t==-1) t=(rb-s1)/k;ll v=rb-(ll)t*k;if (s1>v||maxn>t) return -1;return (s1+s2+(ll)(n-k-last)*(t-maxn)>=v)?t:-1;
}int main() {memset(num,255,sizeof(num));int n,m;scanf("%d%d",&n,&m);ll lb=0,s=0;for(int i=1;i<=n;i++) {scanf("%d%d",&a[i],&b[i]);lb+=a[i];s+=b[i];}sort(a+1,a+n+1);sort(b+1,b+n+1);int k;scanf("%d",&k);for(int i=1;i<=k;i++) {int x,y;scanf("%d%d",&x,&y);num[m-x+1]=y;}ll rb=0;scanf("%lld",&rb);if (lb>rb||s<rb) {puts("-1 -1");return 0;}convex(n,m,lb,rb);if (!solve1(m,rb)) {puts("-1 -1");return 0;}int l=1,r=m;while (l<r) {int mid=((l+r)>>1)+1;if (solve2(m,mid,rb)!=-1) l=mid; else r=mid-1;}int ans=solve2(m,l,rb);printf("%d %d\n",l,ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！