526互联

COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)

发布时间 2023-09-11 16:09:16作者: 空気力学の詩

Preface

这场比赛本来想着周日晚上带着队友打一下的，但当天下午已经VP练了一场了晚上就休息了

后面有时间大概花了5~6天的空闲时间才陆陆续续把这场补了，感觉题目还是不错的

A. Ambitious Kid

签到题，找一个数把它变成\(0\)即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
int n,a[N],ans=1e5;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]),ans=min(ans,abs(a[i]));
	return printf("%d",ans),0;
}

B. Battling with Numbers

签到题，注意到对于某个质数的指数，\(\gcd\)相当于取\(\min\)，\(\operatorname{lcm}\)相当于取\(\max\)

那么分类讨论下，如果对于某个质数，\(B_i<D_i\)则答案为\(0\)；若\(B_i=D_i\)则贡献为\(1\)；若\(B_i>D_i\)则贡献为\(2\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=2000005,mod=998244353;
int n,m,p,A[N],B[N],C[N],D[N],pa[N],pb[N],ans=1;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&A[i]);
	for (i=1;i<=n;++i) scanf("%d",&B[i]),pa[A[i]]=B[i];
	for (scanf("%d",&m),i=1;i<=m;++i) scanf("%d",&C[i]);
	for (i=1;i<=m;++i) scanf("%d",&D[i]),pb[C[i]]=D[i];
	for (i=1;i<=2000000;++i)
	if (pa[i]<pb[i]) ans=0; else if (pa[i]>pb[i]) ans=2LL*ans%mod;
	return printf("%d",ans),0;
}

C. Completely Searching for Inversions

不难发现可以把对一个点的操作后带来的影响压缩成三个数\((x,y,z)\)，分别表示\(0/1\)的个数，以及逆序对的个数

那么合并的情况就很简单了，\((x_1,y_1,z_1)+(x_2,y_2,z_2)\to (x_1+x_2,y_1+y_2,z_1+z_2+y_1\times x_2)\)，用记搜维护这个过程即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005,mod=998244353;
struct ifo
{
	int x,y,z;
	inline ifo(CI X=0,CI Y=0,CI Z=0)
	{
		x=X; y=Y; z=Z;
	}
	friend inline ifo operator + (const ifo& A,const ifo& B)
	{
		return ifo((A.x+B.x)%mod,(A.y+B.y)%mod,(1LL*A.y*B.x+A.z+B.z)%mod);
	}
}f[N]; int n,d,x,y,vis[N]; vector <pi> v[N];
inline ifo DFS(CI now)
{
	if (vis[now]) return f[now];
	for (auto [to,w]:v[now]) f[now]=f[now]+(w?ifo(0,1,0):ifo(1,0,0))+DFS(to);
	return vis[now]=1,f[now];
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
	for (scanf("%d",&d),j=1;j<=d;++j)
	scanf("%d%d",&x,&y),v[i].push_back(pi(x,y));
	return printf("%d",DFS(1).z),0;
}

D. Digital Wallet

这题一定要仔细观察数据范围，发现\(k\le 10\)就很好做了

有一个很naive的想法就是按列转移的DP，每列可以先把数排个序贪心地取较大的那些

朴素的方程就是用\(f_{i,j}\)表示处理了前\(i\)列，一共选了\(j\)个数时的最大贡献，乍一看这个状态是\(O(M^2)\)的

但实际上由于每个数都大于\(0\)，因此一定不会出现不拿比拿了更优的情况，同时也要关注只选了前\(i\)列时取的数的个数有上界

稍微推一下会发现对于某个\(i\)，它有价值的第二维\(j\)的取值就在\([\max(0,i-k+1),i]\)中，实际上最多只有\(k\)个数

再加上这题\(n\)的范围也很小，可以暴力枚举每列拿了几个数，因此可以在\(O(nmk)\)的复杂度内通过此题

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005,mod=998244353;
int n,m,k,x; vector <int> l[N],w[N]; unordered_map <int,int> f[N];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,s; for (scanf("%lld%lld%lld",&n,&m,&k),i=1;i<=n;++i)
	for (j=1;j<=m;++j) scanf("%lld",&x),l[j].push_back(x);
	for (i=1;i<=m;++i)
	{
		sort(l[i].begin(),l[i].end(),greater <int>());
		for (w[i].resize(n+1),j=1;j<=n;++j) w[i][j]=w[i][j-1]+l[i][j-1];
	}
	for (f[0][0]=0,i=1;i<=m;++i) for (j=max(0LL,i-k+1);j<=i;++j)
	for (s=0;s<=n;++s) if (f[i-1].count(j-s)) f[i][j]=max(f[i][j],f[i-1][j-s]+w[i][s]);
	return printf("%lld",f[m][m-k+1]),0;
}

E. Elevators of Tamem

好题，本来以为是难点的电梯状态的改变原来根本不是难点，被虐了

首先考虑如果没有电梯状态的变化该怎么做，朴素的想法就是把三个电梯所在的高度记录下来，但这样显然会爆炸

稍加思索我们会发现由于\(Q\)的范围很小，因此可以记录下每个电梯上次完成了哪个操作，即用\(f_{i,j,k}\)表示电梯\(1,2,3\)分别上次完成的操作的状态下的最小代价

我们按顺序枚举当前的操作\(d\)，它的前驱状态就是所有满足\(\max(i,j,k)=d-1\)的\((i,j,k)\)，这个枚举显然是\(O(Q^2)\)的

而对于某个状态的合法转移显然有三种，就是挑选某个电梯用来完成第\(d\)次操作，以选第一个电梯为例，转移为：

\[\min_\limits{i\le s\le d} a_s\times |y_i-x_d|+a_d\times |y_d-x_d| \]

后面那部分很好理解，前面部分就是在这个时间段内找一个电费最少的时候把电梯开到对应的楼层，这部分可以暴力预处理一下

然后这题没有修改电梯使用状态的版本就做完了，而考虑加入这一限制其实也很简单，我们对于三部电梯分别维护其每一天的电费，如果某一天该电梯不可用的话就把电费置为\(\infty\)即可

总复杂度\(O(Q^3)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=305,INF=1e12,INFF=1e18;
int n,q,a[N],c[3],g[3][N][N],f[N][N][N],cnt,id[N],x[N],y[N],opt,p,ans=INFF;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; for (scanf("%lld%lld",&n,&q),i=1;i<=q;++i) scanf("%lld",&a[i]);
	for (c[0]=c[1]=c[2]=i=1;i<=q;++i)
	{
		if (scanf("%lld",&opt),opt==2) scanf("%lld",&p),c[p-1]^=1;
		else scanf("%lld%lld",&x[i],&y[i]),id[++cnt]=i;
		for (j=0;j<3;++j) g[j][i][i]=c[j]?a[i]:INF;
	}
	//for (k=0;k<3;++k) for (i=1;i<=q;++i) printf("%lld%c",g[k][i][i]," \n"[i==q]);
	for (k=0;k<3;++k) for (g[k][0][0]=INF,i=0;i<=q;++i) for (j=i+1;j<=q;++j)
	g[k][i][j]=min(g[k][i][j-1],g[k][j][j]);
	for (i=0;i<=cnt;++i) for (j=0;j<=cnt;++j) for (k=0;k<=cnt;++k) f[i][j][k]=INFF;
	for (f[0][0][0]=0,y[0]=1,i=1;i<=cnt;++i)
	{
		for (RI a=i-1,b=0,c;b<=a;++b) for (c=0;c<=a;++c)
		if (f[a][b][c]!=INFF)	
		{
			f[i][b][c]=min(f[i][b][c],f[a][b][c]+g[0][id[a]][id[i]]*abs(y[id[a]]-x[id[i]])+g[0][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][i][c]=min(f[a][i][c],f[a][b][c]+g[1][id[b]][id[i]]*abs(y[id[b]]-x[id[i]])+g[1][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][b][i]=min(f[a][b][i],f[a][b][c]+g[2][id[c]][id[i]]*abs(y[id[c]]-x[id[i]])+g[2][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
		}
		for (RI b=i-1,a=0,c;a<=b;++a) for (c=0;c<=b;++c)
		if (f[a][b][c]!=INFF)	
		{
			f[i][b][c]=min(f[i][b][c],f[a][b][c]+g[0][id[a]][id[i]]*abs(y[id[a]]-x[id[i]])+g[0][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][i][c]=min(f[a][i][c],f[a][b][c]+g[1][id[b]][id[i]]*abs(y[id[b]]-x[id[i]])+g[1][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][b][i]=min(f[a][b][i],f[a][b][c]+g[2][id[c]][id[i]]*abs(y[id[c]]-x[id[i]])+g[2][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
		}
		for (RI c=i-1,a=0,b;a<=c;++a) for (b=0;b<=c;++b)
		if (f[a][b][c]!=INFF)
		{
			f[i][b][c]=min(f[i][b][c],f[a][b][c]+g[0][id[a]][id[i]]*abs(y[id[a]]-x[id[i]])+g[0][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][i][c]=min(f[a][i][c],f[a][b][c]+g[1][id[b]][id[i]]*abs(y[id[b]]-x[id[i]])+g[1][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
			f[a][b][i]=min(f[a][b][i],f[a][b][c]+g[2][id[c]][id[i]]*abs(y[id[c]]-x[id[i]])+g[2][id[i]][id[i]]*abs(y[id[i]]-x[id[i]]));
		}
		//for (auto [a,b,c]:s[i]) if (f[a][b][c]!=INF) printf("f[%lld][%lld][%lld] = %lld\n",a,b,c,f[a][b][c]);
	}
	for (RI a=i-1,b=0,c;b<=a;++b) for (c=0;c<=a;++c) ans=min(ans,f[a][b][c]);
	for (RI b=i-1,a=0,c;a<=b;++a) for (c=0;c<=b;++c) ans=min(ans,f[a][b][c]);
	for (RI c=i-1,a=0,b;a<=c;++a) for (b=0;b<=c;++b) ans=min(ans,f[a][b][c]);
	return printf("%lld",ans),0;
}

F. Freak Joker Process

做不来，好难的说

G. Grouped Carriages

最大值最小，一眼二分答案转化为判定性问题，然后考虑怎么check(x)

首先可以把问题抽象一下，有一个新数组\(\{B_n\}\)，每个位置的容量都是\(x\)，然后对于原数组\(\{A_n\}\)中的每个\(i\)，都可以将它们放置到\(\{B_n\}\)的区间\([i-D_i,i+D_i]\)中

考虑从左往右枚举\(B_i\)中的位置，考虑对于所有覆盖到它的区间，我们总是找右端点最小的优先放置，这样一定不会更劣

用扫描线+堆维护这个过程即可，总复杂度\(O(n\log n\log a_i)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,a[N],d[N],l[N],r[N],res[N]; vector <pi> tag[N];
inline bool check(CI lim)
{
	RI i; priority_queue <pi,vector <pi>,greater <pi>> hp;
	for (i=1;i<=n;++i) res[i]=a[i];
	for (i=1;i<=n;++i)
	{
		for (auto [tp,id]:tag[i])
		if (tp<0)
		{
			if (res[id]) return 0;
		} else if (res[id]) hp.push(pi(r[id],id));
		int cur=0; while (!hp.empty())
		{
			auto [R,ID]=hp.top(); hp.pop();
			int dlt=min(lim-cur,res[ID]); cur+=dlt; res[ID]-=dlt;
			if (res[ID]) hp.push(pi(R,ID));
			if (cur==lim) break;
		}
	}
	return hp.empty();
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (i=1;i<=n;++i)
	{
		scanf("%d",&d[i]); l[i]=max(1,i-d[i]); r[i]=min(n,i+d[i]);
		tag[l[i]].push_back(pi(1,i)); tag[r[i]+1].push_back(pi(-1,i));
	}
	for (i=1;i<=n;++i) sort(tag[i].begin(),tag[i].end());
	int l=0,r=1e9,ret,mid; while (l<=r)
	if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
	return printf("%d",ret),0;
}

H. Happy Sets

小清新数数题

首先解决重排的方案问题，可以先计算不重排的方案，不难发现除了空集以外其它元素总是不同，因此可以枚举空集个数\(x\)，再计算剩下部分的方案数

注意到我们可以用二元组\((i,j)\)来表示\(j\in s_i\)，那么我们发现如果\((i,j)\)存在，则\((i+1,j+1),(i+2,j+2),\cdots\)也一定存在

因此我们可以把满足这种关系的二元组看作同一类，设某一类中有\(c\)个元素，则其对答案的贡献为\(c+1\)

注意到正常情况下\(c\)的贡献是呈阶乘关系的，但由于一共剩下\(n-x\)个位置，因此推一下贡献的式子其实是：

\[(n-x+1)!\times (n-x+1)^{k-(n-x)} \]

但要注意这样算出来的其实是至少有\(x\)个空集的方案数，因此我们还需要对相邻两项做差得到最后恰好有\(x\)个空集的方案数

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int n,k,fact[N],ifac[N],g[N],ans;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; scanf("%d%d",&n,&k); init(n+1);
	for (i=0;i<=n;++i) if (k<n-i) g[i]=fact[k+1];
	else g[i]=1LL*fact[n-i+1]*quick_pow(n-i+1,k-(n-i))%mod;
	for (i=0;i<=n;++i) (ans+=1LL*(g[i]-g[i+1]+mod)*fact[n]%mod*ifac[i]%mod)%=mod;
	return printf("%d",ans),0;
}

I. Imagination Castle

看到博弈就想到划分必胜态必败态，在这题中显然可以给所有特殊位置以及\((n,m)\)定义为必败态

考虑一个位置\((i,j)\)的转移其实只和它右边和下边的所有状态中是否有必败态有关，我们可以用以下递推方式来处理重复的转移

定义二元组\((x,y)\)，表示目前未知状态为\((1,1)\sim (x,y)\)这个矩阵，考虑转移：

  • 若\((x,y)\)位置右侧存在特殊位置且下侧也存在特殊位置，则第\(x\)行和第\(y\)列的剩下所有未知状态都是必胜态，同时可以将\(x,y\)均减去\(1\)
  • 若\((x,y)\)位置右侧存在特殊位置但下侧不存在特殊位置，则第\(x\)行剩下所有未知状态都是必胜态，可以将\(x\)减去\(1\)
  • 若\((x,y)\)位置下侧存在特殊位置但右侧不存在特殊位置，则第\(y\)列剩下所有未知状态都是必胜态，可以将\(y\)减去\(1\)
  • 若\((x,y)\)位置下侧及右侧都不存在特殊位置，则\((x,y)\)为必败态，同时第\(x\)行和第\(y\)列剩下的未知状态失去意义，可以将\(x,y\)均减去\(1\)

预处理一下然后直接模拟即可

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,m,k,x,y,h[N],c[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d%d",&n,&m,&k),i=1;i<=k;++i)
	scanf("%d%d",&x,&y),h[x]=max(h[x],y),c[y]=max(c[y],x);
	for (x=n,y=m;x>=1&&y>=1;)
	{
		if (h[x]>=y&&c[y]>=x) --x,--y; else
		if (h[x]>=y) --x; else if (c[y]>=x) --y; else
		{
			if (x==1&&y==1) return puts("Bhinneka"),0; --x; --y;
		}
	}
	return puts("Chaneka"),0;
}

J. Jackets and Packets

好劲的DP题，一点做不来的说

首先考虑把问题形式化，有一个初始时在第一个元素左边的指针，每次操作可以花费\(Y\)的代价把指针向左向右移动，或者花费\(X\)的代价将指针左侧或右侧紧挨着的所有相同元素删除

考虑区间DP，设\(f_{l,r}\)表示将原数组\([l,r]\)中的元素全部删除且初始时指针位于\(l\)左侧的最小代价

若\(a_l\ne a_r\)，则转移形式比较简单，只要找某个划分方案\(p\)使得\(f_{l,p}+f_{p+1,r}\)最小即可

否则若\(a_l=a_r\)，则可以考虑把这两个数放在一次删除操作中，此时需要将\([l+1,r-1]\)中和\(a_l,a_r\)不同的数先删除掉

考虑另外设计两个DP数组，令\(f1_{l,r}\)表示要删完\([l,r]\)区间内的所有数，且初始时满足\(a_l=a_r\)，最后删完后指针在\(a_r\)右侧的最小代价，\(f2_{l,r}\)表示删完后指针在\(a_l\)左侧的最小代价

对于\(f1_{l,r}\)，其转移为：

  • 若\([l,r]\)中的所有元素都相同，则\(f1_{l,r}=Y\times (r-l+1)+X\)
  • 否则，枚举所有\(p\in[l+1,r]\and a_p=a_l\)，则找\(Y+f_{l+1,p-1}+f1_{p,r}\)最小的转移即可

对于\(f2_{l,r}\)，其转移为：

  • 若\([l,r]\)中的所有元素都相同，则\(f1_{l,r}=X\)
  • 否则，枚举所有\(p\in[l+1,r]\and a_p=a_l\)，则找\(Y\times 2+f_{l+1,p-1}+f2_{p,r}\)最小的转移即可

总复杂度\(O(n^3)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=405,INF=1e18;
int n,x,y,c[N],f[N][N],f1[N][N],f2[N][N];
inline int DP1(CI l,CI r);
inline int DP2(CI l,CI r);
inline int DP(CI l,CI r)
{
	if (l>r) return 0; if (~f[l][r]) return f[l][r];
	int ret=INF; for (RI i=l;i<r;++i) ret=min(ret,DP(l,i)+DP(i+1,r));
	if (c[l]==c[r]) ret=min(ret,min(DP1(l,r),DP2(l,r)));
	return f[l][r]=ret;
}
inline int DP1(CI l,CI r)
{
	if (l>r) return 0; if (~f1[l][r]) return f1[l][r];
	RI i; for (i=l;i<r;++i) if (c[i]!=c[r]) break;
	if (i==r) return f1[l][r]=y*(r-l+1)+x;
	int ret=INF; for (i=l;i<r;++i) if (c[i+1]==c[r])
	ret=min(ret,y+DP(l+1,i)+DP1(i+1,r));
	return f1[l][r]=ret;
}
inline int DP2(CI l,CI r)
{
	if (l>r) return 0; if (~f2[l][r]) return f2[l][r];
	RI i; for (i=l;i<r;++i) if (c[i]!=c[r]) break;
	if (i==r) return f2[l][r]=x;
	int ret=INF; for (RI i=l;i<r;++i) if (c[i+1]==c[r])
	ret=min(ret,y*2+DP(l+1,i)+DP2(i+1,r));
	return f2[l][r]=ret;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%lld%lld%lld",&n,&x,&y),i=1;i<=n;++i) scanf("%lld",&c[i]);
	memset(f,-1,sizeof(f)); memset(f1,-1,sizeof(f1)); memset(f2,-1,sizeof(f2));
	return printf("%lld",DP(1,n)),0;
}

K. Keen Tree Calculation

+22艰难过题，又卡空间又卡时间，答应我下次不写乱搞做法了好吗

首先可以求出不做修改时树的直径，那么每次询问考虑经过该点的答案变化

不难发现若假设\(x\)和它的一个邻居\(y\)之间的边权为\(A\)，\(y\)在不经过\(x\leftrightarrow y\)这条边的情况下到最远的点的距离为\(B\)，则\(y\)带来的贡献就是\(A\times k+B\)，显然可以把每个二元组\((A,B)\)看作直线的斜率和截距

那么考虑现在就是要找两条直线，使得当\(X=k\)时值最大，如果只是找最大值那就是很经典的求下凸壳然后二分

那要找最大和次大怎么做呢，可以考虑以下乱搞做法，我们不妨对于每个点的二元组都建立两个凸壳

对于每条直线，随机地把它扔进两个凸包中的一个，最后查询的时候把两个凸包的最大值加起来更新答案即可

注意到这样的做法在最后答案的两条直线被分到不同的凸包中时都能得到正确答案，因此做一次的错误的概率是\(\frac{1}{2}\)，那多做几次出错率就很低了

我这里为了兼顾时间和空间选择做\(25\)次，总复杂度\(O(25\times n\log n)\)，实测可以卡着限制通过

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005;
const LL INF=1e18;
class FileInputOutput
{
	private:
		static const int S=1<<21;
		#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
		char Fin[S],*A,*B;
	public:
		Tp inline void read(T& x)
		{
			x=0; char ch; while (!isdigit(ch=tc()));
			while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
		}
		#undef tc
}F;
struct Line
{
	int k; LL b;
	inline Line(CI K=0,const LL& B=0)
	{
		k=K; b=B;
	}
	friend inline bool operator < (const Line& A,const Line& B)
	{
		return A.k!=B.k?A.k<B.k:A.b<B.b;
	}
	inline LL get(CI x)
	{
		return 1LL*k*x+b;
	}
}; int n,q,x,y,z; LL ans; vector <pi> v[N]; multiset <LL> s[N];
inline double get_x(const Line& A,const Line& B)
{
	if (A.k==B.k) return A.b>B.b?-INF:INF;
	return 1.0*(B.b-A.b)/(A.k-B.k);
}
struct Convex
{
	vector <Line> stk; vector <double> p;
	inline void insert(const Line& L)
	{
		if (stk.empty()) return stk.push_back(L),p.push_back(-INF);
		while (stk.size()>1&&get_x(L,stk.back())<p.back()) stk.pop_back(),p.pop_back();
		p.push_back(get_x(L,stk.back())); stk.push_back(L);
	}
	inline LL query(CI x)
	{
		if (stk.empty()) return 0;
		return stk[upper_bound(p.begin(),p.end(),1.0*x)-p.begin()-1].get(x);
	}
}C[N][25][2]; vector <Line> l[N];
mt19937 rnd(20030909);
inline void DFS1(CI now=1,CI fa=0)
{
	for (auto [to,w]:v[now]) if (to!=fa)
	{
		DFS1(to,now); s[now].insert((s[to].empty()?0LL:*(--s[to].end()))+w);
		l[now].push_back(Line(w,s[to].empty()?0LL:*(--s[to].end())));
	}
}
inline void DFS2(CI now=1,CI fa=0,const LL& out=0)
{
	if (out) s[now].insert(out);
	if (s[now].size()==1) ans=max(ans,*(--s[now].end())); else
	{
		LL mx=*(--s[now].end()); auto it=s[now].end();
		--it; --it; ans=max(ans,mx+*it);
	}
	for (auto [to,w]:v[now]) if (to!=fa)
	{
		LL mx=*(--s[now].end());
		if (mx!=((s[to].empty()?0LL:*(--s[to].end()))+w))
		DFS2(to,now,mx+w),l[to].push_back(Line(w,mx)); else
		{
			LL smx=0LL; auto it=--s[now].end();
			if (s[now].size()>1) smx=*(--it);
			DFS2(to,now,smx+w); l[to].push_back(Line(w,smx));
		}
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (F.read(n),i=1;i<n;++i)
	F.read(x),F.read(y),F.read(z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
	for (DFS1(),DFS2(),i=1;i<=n;++i) if (l[i].size()>1)
	{
		sort(l[i].begin(),l[i].end());
		for (j=0;j<25;++j) for (auto it:l[i]) C[i][j][rnd()&1].insert(it);
	}
	/*for (i=1;i<=n;++i)
	{
		printf("%d\n",i);
		for (auto [k,b]:l[i]) printf("%lld %lld\n",k,b);
	}*/
	for (F.read(q),i=1;i<=q;++i)
	{
		F.read(x); F.read(y); LL ret=ans;
		if (l[x].size()==1) ret=max(ret,1LL*l[x][0].k*y+l[x][0].b); else
		for (j=0;j<25;++j) ret=max(ret,C[x][j][0].query(y)+C[x][j][1].query(y));
		printf("%lld\n",ret);
	}
	return 0;
}

L. Lihmuf Balling

很丁真的一个题，不知道为什么过的人不多

考虑枚举\(K\)后模拟取数这个过程，但直接一步一步模拟肯定不可取，我们不妨在每次\(y\)从后面跳回到前面的时候计算一次贡献

考虑此时应该分两步，第一步是\(y\)花\(\lceil\frac{j-y+1}{k-1}\rceil\)次操作先跑到\(j\)的后面，然后再拿走剩下的部分的贡献，这里稍微手推一下等差数列的式子即可

但如果只是这样还是没法保证模拟的次数，但我们仔细一想会发现每次模拟的时候会把所有下标对\(K\)取模相同的位置全部经过一遍

那么如果当某次跳回的时候发现这个位置对\(K\)取模的值已经经过一次了，就可以直接退出了

这样就可以保证每次模拟次数是\(O(K)\)的，因此总复杂度\(O(M^2)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int M=2005;
int n,m,num=1,mx; bool vis[M];
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,k; for (scanf("%lld%lld",&n,&m),k=2;k<=m;++k)
	{
		int ret=0,j=1; for (i=0;i<k;++i) vis[i]=0;
		while (j<=n)
		{
			int y=(j*k-1)%n+1; if (vis[y]) break; vis[y]=1;
			if (j>=y)
			{
				int d=(j-y+1+k-2)/(k-1); j+=d; y+=d*k;
			}
			if (j>n) break; if (y>n) continue;
			int t=(n-y)/k; ret+=y*(t+1)+t*(t+1)/2LL*k; j+=t+1;
		}
		//printf("%lld %lld\n",k,ret);
		if (ret>mx) mx=ret,num=k;
	}
	return printf("%lld",num),0;
}

M. Mighty Rock Tower

好，经典成环期望题，不会，寄

考虑设\(f_i\)表示把高为\(i-1\)的塔变成高为\(i\)的塔的期望操作次数，则有：

  • 对\(j\in[0,i-1]\)，有\((p_i)^k\times (1-p_i)\)的概率恰好会塌\(j\)层
  • 有\((p_i)^i\)的概率恰好会塌\(i\)层

考虑如果一次操作后掉落了\(j\in[1,i]\)层，那么它的贡献为\(f(i-j+1)+\cdots+f(i-1)+f(i)\)，因此我们可以列出转移方程：

\[f_i=1+(p_i)^i\times (f_i+f_{i-1}+\cdots+f_1)+\\\sum_{j=1}^{i-1}(p_i)^j\times (1-p_i)\times (f_i+f_{i-1}+\cdots+f_{i-j+1}) \]

然后耐心一点合并下同类项，可以得到简化后的方程：

\[f_i=1+\sum_{j=1}^i(p_i)^j\times f_{i-j+1} \]

移项去掉成环的部分后得到：

\[f_i=\frac{1+\sum_{j=2}^i(p_i)^j\times f_{i-j+1}}{1-p_i} \]

乍一看这个式子的计算需要\(O(n^2)\)并且不太好优化，但仔细看一眼题目会发现题目特意把概率表示成百分数的形式就是为了告诉你不同的\(p_i\)只有\(100\)种

因此我们可以预处理\(g_{i,j}\)表示处理到\(x\)时，\(\sum_{j=2}^x(\frac{i}{100})^j\times f_{x-j+1}\)的值，转移可以直接递推，这样复杂度就变成\(O(100\times n)\)的了

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int n,rp[N],p[N],inv100,prob[105],f[N],g[105][N];
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),inv100=quick_pow(100),i=1;i<=n;++i)
	scanf("%d",&rp[i]),p[i]=1LL*rp[i]*inv100%mod;
	for (i=1;i<100;++i) prob[i]=1LL*i*inv100%mod;
	for (f[1]=quick_pow((1-p[1]+mod)%mod),i=1;i<100;++i)
	g[i][2]=1LL*f[1]*prob[i]%mod*prob[i]%mod;
	for (j=2;j<=n;++j)
	{
		f[j]=1LL*(1+g[rp[j]][j])*quick_pow((1-p[j]+mod)%mod)%mod;
		for (i=1;i<100;++i) g[i][j+1]=(1LL*g[i][j]*prob[i]%mod+1LL*f[j]*prob[i]%mod*prob[i]%mod)%mod;
	}
	int ans=0; for (i=1;i<=n;++i) (ans+=f[i])%=mod;
	return printf("%d",ans),0;
}

Postscript

感觉最近要补的题目好多啊，有点力不从心了