2022牛客OI赛前集训营-提高组（第二场）赛后总结

躲避技能

https://ac.nowcoder.com/acm/contest/40646/A

时间	名称	赛制	组别	得分	排名
2022.10.06	2022牛客OI赛前集训营（第二场）	OI	提高组	118/400	27

A.躲避技能

考场还是想复杂了，用费用流打了个二分图最小权匹配，然而只有16pts。

正解其实真不难想……

显然子树内优先匹配，剩下的点要和外面的匹配就一定会经过子树最上面一条边，按这个算贡献即可。

高精度的话只要写个高精加高精和高精乘低精就行。

贴下代码吧：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
const int len=200;
struct bignum
{
    int num[205];
    friend bignum operator + (const bignum a,const bignum b)
    {
        bignum ret;
        memset(ret.num,0,sizeof(ret.num));
        for(int i=0;i<=len;++i)
        {
            ret.num[i]+=a.num[i]+b.num[i];
            ret.num[i+1]=ret.num[i]/10,ret.num[i]%=10;
        }
        return ret;
    }
    friend bignum operator * (const bignum a,const int b)
    {
        bignum ret;
        memset(ret.num,0,sizeof(ret.num));
        for(int i=0;i<=len;++i)
        {
            ret.num[i]+=a.num[i]*b;
            ret.num[i+1]=ret.num[i]/10,ret.num[i]%=10;
        }
        return ret;
    }
};
typedef pair<int,bignum> pa;
void read(bignum &w)
{
    memset(w.num,0,sizeof(w.num));
    char ch[205];
    scanf("%s",ch);
    int l=strlen(ch);
    for(int i=0;i<l;++i) w.num[i]=(ch[i]^48);
}
void print(bignum x)
{
    bool flag=0;
    for(int i=len;i>=0;--i)
    {
        if(flag) printf("%d",x.num[i]);
        else if(x.num[i]) printf("%d",x.num[i]),flag=1;
    }
}
vector<pa>G[MAXN];
int siz[MAXN];
bignum ans;
void dfs(int x,int father)
{
    for(auto i:G[x])
    {
        int y=i.first;
        bignum z=i.second;
        if(y!=father) dfs(y,x),siz[x]+=siz[y],ans=ans+z*abs(siz[y]);
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    int u,v,x;
    bignum w;
    for(int i=1;i<=m;++i) scanf("%d",&x),++siz[x];
    for(int i=1;i<=m;++i) scanf("%d",&x),--siz[x];
    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v),read(w);
        G[u].push_back({v,w}),G[v].push_back({u,w});
    }
    memset(ans.num,0,sizeof(ans.num));
    dfs(1,0);
    print(ans);
    return 0;
}

B.奶茶兑换券

考场自以为推出了正解然而并没有仔细分析复杂度结果和暴力同分……

考场的思路和题解的贪心有点像，也是把奶茶分成小于 $\dfrac{m}{2}$ 和大于 $\dfrac{m}{2}$ 的（对 $m$ 取模后）。

然后显然优先小的和大的匹配（小的从小到大，大的从大到小），最后小的自己匹配就行。

代码：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
struct node
{
	int a,b;
}p[MAXN];
bool cmp(node x,node y){return x.b<y.b;}
int main()
{
	int n,m;
	cin>>n>>m;
    long long ans=0;
	for(int i=1;i<=n;++i)
    {
		scanf("%d %d",&p[i].a,&p[i].b);
		p[i].b%=m;
		if(!p[i].b){--i,--n; continue;}
		ans+=(long long)p[i].a*(m-p[i].b);
	}
	sort(p+1,p+n+1,cmp);
	int i=1,j=n;
    while(i<j)
	{
        if(p[i].b+p[j].b>m){--j; continue;}
        int tmp=min(p[i].a,p[j].a);
        p[i].a-=tmp,p[j].a-=tmp,ans-=(long long)tmp*m;
        if(!p[i].a) ++i;
        if(!p[j].a) --j;
    }
    if(p[i].b*2<=m) ans-=(long long)p[i].a/2*m;
	printf("%lld\n", ans);
	return 0;
}

题外话：数据出锅，有几个点 $\sum a_i$ 不是偶数。

C.帮助

思路比较难想（个人觉得）：

首先 $t, a, b, c, d$ 给的很大肯定要离散化。

然后排序，预处理出每个人能帮助的区间和给予帮助的区间（因为排了序是一段连续的区间）。

用差分+树状数组维护每个人的贡献，详见代码注释：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define lowbit(x) x&(-x)
const int MAXN=1e5+5;
int f[MAXN],t[MAXN],num[MAXN],c[MAXN],d[MAXN];
ll ans[MAXN],sum[MAXN];
vector<int>h[MAXN],g[MAXN];
int len;
void add(int x,int val){while(x<=len+1){sum[x]+=val,x+=lowbit(x);}}
ll ask(int x){ll ret=0; while(x>0){ret+=sum[x],x-=lowbit(x);} return ret;}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d",&f[i]);
    for(int i=1;i<=n;++i) scanf("%d",&t[i]),num[i]=t[i];
    sort(num+1,num+n+1);
    len=unique(num+1,num+n+1)-num-1;
	for(int i=1;i<=n;++i)
    {
    	int a,b;
    	t[i]=lower_bound(num+1,num+len+1,t[i])-num;
    	h[t[i]].push_back(i);
		scanf("%d %d",&a,&b);
		a=lower_bound(num+1,num+len+1,a)-num;
		b=upper_bound(num+1,num+len+1,b)-num-1;
		if(a<=b)
		{
			g[b].push_back(i);     
			g[a-1].push_back(-i);   //成绩[a,b]以内的人能帮助的人
		}
		scanf("%d %d",&c[i],&d[i]);
		c[i]=lower_bound(num+1,num+len+1,c[i])-num;
		d[i]=upper_bound(num+1,num+len+1,d[i])-num-1;
		if(!(a<=t[i] && t[i]<=b && c[i]<=t[i] && t[i]<=d[i])) ans[i]=f[i];   //如果自己能帮自己，那要减掉这种情况
    }
    for(int i=1;i<=len;++i)
    {
    	for(auto j:h[i]) if(c[j]<=d[j]) add(c[j],f[j]),add(d[j]+1,-f[j]);    //统计在区间[c,d]有多少人能帮助
    	for(auto j:g[i])
    	{
    		int flag=(j<0)?-1:1;j=abs(j);
    		ans[j]+=ask(t[j])*flag;
    	}
    }
    for(int i=1;i<=n;++i) printf("%lld ",ans[i]);
    return 0;
}