CF上的3道小题(1)

CF上的3道小题

终于调完了啊....

T1:CF702E Analysis of Pathes in Functional Graph

题意：你获得了一个n个点有向图，每个点只有一条出边。第i个点的出边指向fi，边权为wi。分别求从每个点出发走k步经过的边权和以及最小的边权值。

分析：倍增嘛...f[i][j]表示j走$2^i$步到达哪个点，然后用这个求出h[i][j]表示j走$2^i$步边权最小值，g[i][j]表示j走$2^i$步边权和。

然后把K二进制拆分一下即可。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long ll;

#define N 100050

int f[44][N],g[44][N],n;

ll h[44][N],K;

int main() {

    // freopen("today.in","r",stdin);

    // freopen("today.out","w",stdout);

    scanf("%d%lld",&n,&K);

    int i,x,j;

    for(i=1;i<=n;i++) {

        scanf("%d",&f[0][i]); f[0][i]++;

    }

    for(i=1;i<=n;i++) {

        scanf("%d",&x); g[0][i]=h[0][i]=x;

    }

    for(i=1;(1ll<<i)<=K;i++) {

        for(j=1;j<=n;j++) {

            f[i][j]=f[i-1][f[i-1][j]];

            g[i][j]=min(g[i-1][j],g[i-1][f[i-1][j]]);

            h[i][j]=h[i-1][j]+h[i-1][f[i-1][j]];

        }

    }

    for(i=1;i<=n;i++) {

        ll t=K;

        int x=i;

        int ans1=1<<30;

        ll ans2=0;

        for(j=0;j<=40;j++) {

            if(t&(1ll<<j)) {

                ans1=min(ans1,g[j][x]);

                ans2+=h[j][x];

                x=f[j][x];

            }

        }

        printf("%lld %d\n",ans2,ans1);

    }

}

/*

7 3

2 3 4 5 4 3 7

6 3 1 4 2 2 3

*/

T2:CF671B Robin Hood

题意：你拥有n堆石子，第i堆石子有ai个，你要操作k次，每次从有最多石子的堆拿出一个石子放入有最少石子的堆。求操作后石子最多的堆和石子最少的堆的石子差。

分析：考虑二分最大值/最小值，然后判断能否铺平(将小于/大于的部分加起来和K比)。

注意所有石子都相等的时候要停止，以及一堆特判。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 500050

typedef long long ll;

int n,a[N],K,b[N],c[N],d[N];

bool check1(int x) {

	int i,re=0;

	for(i=1;i<=n;i++) {

		if(a[i]>x) re+=a[i]-x;

		if(re>K) return 0;

	}

	return 1;

}

bool check2(int x) {

	int i,re=0;

	for(i=1;i<=n;i++) {

		if(a[i]<x) re+=x-a[i];

		if(re>K) return 0;

	}

	return 1;

}

ll Abs(ll x) {return x>0?x:-x;}

int main() {

	// freopen("problem.in","r",stdin);

	// freopen("problem.out","w",stdout);

	scanf("%d%d",&n,&K);

	int i;

	ll sum=0;

	ll cha=0;

	for(i=1;i<=n;i++) {

		scanf("%d",&a[i]);

		sum+=a[i]; sum%=n;

	}

	for(i=1;i<=n;i++) cha+=Abs(a[i]-sum/n);

	sum%=n;

	if(!sum&&2*K>=cha) {

		puts("0"); return 0;

	}

	int flg=0;

	for(i=2;i<=n;i++) if(a[i]!=a[i-1]) flg=1;

	if(!flg) {

		printf("%d\n",0); return 0;

	}

	// sort(a+1,a+n+1);

	int l=0,r=1<<30;

	while(l<r) {

		int mid=(l+r)>>1;

		if(check1(mid)) r=mid;

		else l=mid+1;

	}

	int ans1=l;

	l=0,r=1<<30;

	while(l<r) {

		int mid=(l+r)>>1;

		if(check2(mid)) l=mid+1;

		else r=mid;

	}

	int ans2=l-1;

	// if(ans1>ans2) swap(ans1,ans2);

	if(ans1<=ans2) {

		printf("%d\n",sum?1:0);

	}else

	printf("%d\n",ans1-ans2);

}

T3:CF671C Ultimate Weirdness of an Array

题意：给你一个长度为n的序列，定义f(i,j)表示把序列的i到j这段扣掉后序列选出两个数做gcd的最大值。

求$\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n} f(i,j)$。

分析：设$h(i$)表示有多少对$l,r$使得$f(l,r)<=i$，nxt[j]表示使得$f(j,k)<=i$成立的最小的$k$。

于是$h(i)=\sum\limits_{j=1}^{n}n-nxt[j]+1$，且答案$=\sum\limits_{i=1}^{maxn}i*(h(i)-h(i-1))$

考虑从h(i)->h(i-1)会发生什么，发生变化的一定是原来nxt的位置上的数是i的倍数的那些数。

把是i的倍数那些位置的第一个，第二个，倒数第二个和倒数第一个拿出来，然后分析一通。

发现这其实是区间取max，同时维护区间和。

并且nxt随i的减小单调不降，故每次修改相当于区间覆盖。

线段树维护nxt即可。

代码：

#include <cstdio>

#include <string.h>

#include <algorithm>

#include <vector>

using namespace std;

#define N 200050

#define ls p<<1

#define rs p<<1|1

typedef long long ll;

int mx[N<<2],mn[N<<2],cov[N<<2],n;

ll sum[N<<2],h[N];

int a[N],cnt[N],fs[N],se[N],lst[N],cls[N];

vector<int>v[N];

void pushup(int p) {

    mx[p]=max(mx[ls],mx[rs]); mn[p]=min(mn[ls],mn[rs]); sum[p]=sum[ls]+sum[rs];

}

void pushdown(int l,int r,int p) {

    if(cov[p]) {

        int mid=(l+r)>>1;

        int d=cov[p];

        mn[ls]=mx[ls]=d; sum[ls]=1ll*d*(mid-l+1); cov[ls]=d;

        mn[rs]=mx[rs]=d; sum[rs]=1ll*d*(r-mid); cov[rs]=d;

        cov[p]=0;

    }

}

void build(int l,int r,int p) {

    if(l==r) {

        mx[p]=mn[p]=sum[p]=l; return ;

    }

    int mid=(l+r)>>1;

    build(l,mid,ls); build(mid+1,r,rs);

    pushup(p);

}

void update(int l,int r,int x,int y,int v,int p) {

    if(mn[p]>=v) return ;

    if(x<=l&&y>=r&&mx[p]<=v) {

        mn[p]=mx[p]=v; sum[p]=1ll*(r-l+1)*v; cov[p]=v; return ;

    }

    pushdown(l,r,p);

    int mid=(l+r)>>1;

    if(x<=mid) update(l,mid,x,y,v,ls);

    if(y>mid) update(mid+1,r,x,y,v,rs);

    pushup(p);

}

int main() {

    scanf("%d",&n);

    int i,maxn=0,j;

    for(i=1;i<=n;i++) scanf("%d",&a[i]),maxn=max(maxn,a[i]);

    for(i=1;i<=maxn;i++) {

        for(j=0;j<=maxn;j+=i) {

            v[j].push_back(i);

        }

    }

    for(i=1;i<=n;i++) {

        int lim=v[a[i]].size();

        for(j=0;j<lim;j++) {

            int tmp=v[a[i]][j];

            cnt[tmp]++;

            cls[tmp]=lst[tmp];

            lst[tmp]=i;

            if(cnt[tmp]==1) fs[tmp]=i;

            if(cnt[tmp]==2) se[tmp]=i;

        }

    }

    ll tot=n*(n+1);

    build(1,n,1); h[maxn]=tot-sum[1];

    ll ans=0;

    for(i=maxn;i;i--) {

        if(cnt[i]>=2) {

            // printf("%d %d %d %d\n",fs[i],se[i],cls[i],lst[i]);

            update(1,n,se[i]+1,n,n+1,1);

            update(1,n,fs[i]+1,se[i],lst[i],1);

            update(1,n,1,fs[i],cls[i],1);

        }

        h[i-1]=tot-sum[1];

        // printf("%lld\n",h[i-1]);

        ans+=i*(h[i]-h[i-1]);

    }

    // puts("________________");

    // for(i=1;i<=20;i++) printf("%lld\n",h[i]);

    // for(i=1;i<maxn;i++) ans+=(i)*(h[i+1]-h[i]);

    printf("%lld\n",ans);

}

巴特西

CF上的3道小题(1)

最新文章

热门文章