过题数	排名	A	B	C	D	E	F	G	H	I	J
4	258	B	√	√		√		√

|过题数|排名|A|B|C|D|E|F|G|H|I|J|K|L|M|
|-----|----|-|-|-|-|-|-|-|-|-|-|-|-|-|
|     |    | | | | | | | | | | | | | |
√ 赛时过了
B 补题过了

A Tree

题目要求你改变一些点的黑白（可以不改变），按照颜色分为两个集合后，你需要最大化 $\sum_{x\in V_1}\limits \sum_{y \in V_2} \limits val(x,y)$ 最小， $val(x,y)$ 表示两点之间路径中最大的边的边权。

这种题应该一开始就想到重构树，这样一条边的贡献就转化为了父节点到子节点之间，然后我们简单跑一个树形背包就可以了。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=6060;
const int inf=1e18;

int cost[maxn],col[maxn];
int val[maxn];
int sz[maxn];
int f[maxn][maxn],g[maxn];
int ans,n;

vector <int> c[maxn];

struct Graph{
	
	struct edge{
		int x,y,z;
		bool operator <(const edge mmm)
		{
			return z<mmm.z;
		}
	}e[maxn];
	
	int f[maxn];
	
	void init() {for(int i=1;i<=n*2;i++) f[i]=i;}
	
	int getf(int x)
	{
		if(x==f[x]) return x;
		return f[x]=getf(f[x]);
	}
	
}G;

void dfs(int t)
{
	if(c[t].empty())
	{
		sz[t]=1;
		f[t][col[t]]=0;
		f[t][col[t]^1]=-cost[t];
		return ;
	}
	f[t][0]=0;
	for(auto v : c[t])
	{
		dfs(v);
		memcpy(g,f[t],sizeof(f[t]));
		for(int i=0;i<=n;i++) f[t][i]=-inf;
		for(int i=0;i<=sz[t];i++)
		for(int j=0;j<=sz[v];j++)
		{
			int cross=i*(sz[v]-j)+j*(sz[t]-i);
			f[t][i+j]=max(f[v][j]+g[i]+cross*val[t],f[t][i+j]);
			ans=max(ans,f[t][i+j]);
		}
		sz[t]+=sz[v];
	}
	
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>col[i];
	for(int i=1;i<=n;i++) cin>>cost[i];
	for(int i=1;i<n;i++) cin>>G.e[i].x>>G.e[i].y>>G.e[i].z;
	sort(G.e+1,G.e+n);
	G.init();
	int tot=n;
	for(int i=1;i<n;i++)
	{
		int tx=G.getf(G.e[i].x);
		int ty=G.getf(G.e[i].y);
		c[++tot].push_back(tx);	
		c[tot].push_back(ty);
		G.f[tx]=G.f[ty]=tot;
		val[tot]=G.e[i].z;
	}
	n=tot;
	dfs(n);
	cout<<ans<<'\n';
}

B Distance

dp做法

定义 $f[i][j]$ 表示 $A$ 的第 $i$ 个元素匹配到 $B$ 的第 $j$ 个元素的所有的可能的花费之和。可以有转移方程

$f_{i,j}=cost(a_i,b_j)*G(i,j) + \sum_{x<i,y<i}\limits f_{x,y} $

$G(i,j)$ 表示匹配的方案数。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=2020;
const int modp=998244353;

int a[maxn],b[maxn],n;
int f[maxn][maxn],fsum[maxn][maxn],ans;
int g[maxn][maxn],gsum[maxn][maxn];

int chg(int x,int y)
{
	return abs(x-y);
} 

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	gsum[0][0]=1;
	for(int i=1;i<=n;i++) gsum[i][0]=gsum[0][i]=1;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		g[i][j]=gsum[i-1][j-1];
		f[i][j]=(fsum[i-1][j-1]+g[i][j]*chg(a[i],b[j]))%modp;
		ans=(ans+f[i][j])%modp;
		fsum[i][j]=(fsum[i][j-1]+fsum[i-1][j]-fsum[i-1][j-1]+f[i][j])%modp;
		gsum[i][j]=(gsum[i][j-1]+gsum[i-1][j]-gsum[i-1][j-1]+g[i][j])%modp;
	}
	cout<<ans<<'\n';
}

数学做法

咕咕咕。

C idol!!

做法比较奇怪，用的是找规律的，可以证明 $5$ 的个数一定低于 $2$ 的个数（否则只有2），因此就只需要寻找这个表达式中有多少个 $5$ 就可以了。

对于奇数，我们考虑能从中寻找到多少个 $5$ 。这个表达式大概可以写成

$sum = (5)1+(7)1+(9)1+...+(15)2+...+(25)3$ 可以看见满10一个周期加上一

对于偶数，也有一样的规律。注意 _int128 不能够使用标准io。

#include<bits/stdc++.h>

#define int __int128

using namespace std;

int ans=0,n;
long long tmpans[]={0,0,0,0,0,1,1,2,2,3,4,5,6,7,8,10};

int getsum(int x,int tmp)
{
	if(x<=0) return 0;
	int basans=tmp*x*(x+1)/2;
	return basans;
}

void read(int &x)
{
	x=0;
	char t=getchar();
	while(!isdigit(t)) t=getchar();
	while(isdigit(t)) x=x*10+t-'0',t=getchar();
}

void print(int x)
{
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}

signed main()
{
//	ios::sync_with_stdio(false);
//	cin>>n;
	read(n);
	int tmp=5;
	if(n<=15) 
	{
		cout<<tmpans[n]<<'\n';
		return 0;
	}
	while(tmp<=n)
	{
		int sz=0;
		int lk=((n-tmp)/(tmp*2)*(tmp*2))+tmp;
		sz=(n-lk)/2+1;
		ans+=sz*((n-tmp)/(tmp*2)+1);
		ans+=getsum((n-tmp)/(tmp*2),tmp);
		tmp*=5;
	}
	
	tmp=10;
	while(tmp<=n)
	{
		int sz=0;
		int lk=(n-tmp)/tmp*tmp+tmp;
		sz=(n-lk)/2+1;
		ans+=sz*((n-tmp)/tmp+1);
		ans+=getsum(lk/tmp-1,tmp/2);
		tmp*=5;
	}
	print(ans);
//	cout<<ans<<'\n';
}

E Sequence

在 $[l,r)$ 中找到 $k-1$ 个数，使得 $[l,k_1]+[k_1+1,k_2]...[k_k-1,r]$ 都是偶数。

直接利用前缀和即可。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int maxn=101000;

int n,m,a[maxn];
int cnt1,cnt2,T;
int place[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
    	cnt1=cnt2=0;
    	place[0]=++cnt2;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]+=a[i-1];
            if(a[i]%2==0) 
            {
                place[i]=++cnt2;
            }
            else 
            {
                place[i]=++cnt1;
            }
        }
        for(int i=1;i<=m;i++)
        {
            int l,r,k;
            cin>>l>>r>>k;
            if(a[l-1]%2!=a[r]%2) cout<<"NO\n";
            else 
            {
                if(place[r]-place[l-1]>=k) cout<<"YES\n";
                else cout<<"NO\n";
            }
        }
    }
}