526互联

2023 (ICPC) Jiangxi Provincial Contest -- Official Contest

发布时间 2023-12-09 19:19:14作者: 空気力学の詩

Preface

伟大的徐神终于来和我们一起训练了，然后这场中期一眼秒了可做题中最难的G

虽然中间因为我搞错了徐神的意图给徐神原来正确的主席树删了搞了个错的上去浪费了快一个小时

但无所谓最后结束前把所有可做题全写了强势捧杯（打弱省省赛打出自信了属于是）

A. Drill Wood to Make Fire

签到，判断\(s\times v\)和\(n\)的大小关系即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n,s,v;
int main()
{
	//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	scanf("%d%d%d",&n,&s,&v),puts(s*v>=n?"1":"0");
	return 0;
}

B. Wonderful Array

刚开始想了半天一点不会，后面看徐神写G看着看着就会了这题（？

考虑先把\(x\)和\(a_i\)都对\(m\)取模，但\(b_i\)计算过程中不取模，同时考虑容斥一下求\(b_i\bmod m>b_{i+1}\bmod m\)的方案数

由于\(b_{i+1}-b_i\in[0,m)\)，因此上述条件等价于\(\lfloor\frac{b_i}{m}\rfloor\ne \lfloor\frac{b_{i+1}}{m}\rfloor\)，那么最后答案的式子就是\(n-\lfloor\frac{b_n}{m}\rfloor\)

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

#define RI register int
#define CI const int
#define Tp template <typename T>
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++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        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()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;

const int N = 1e6+5;
int k, n, m, x, A[N], sum[N];
signed main(){
//	freopen("B.in", "r", stdin);
	F.read(k);
	for (int i=0; i<k; ++i) F.read(A[i]);
	F.read(n), F.read(m), F.read(x);
	x%=m;
	
	for (int i=0; i<k; ++i) A[i]%=m;
	sum[0]=A[0];
	for (int i=1; i<k; ++i) sum[i] = sum[i-1]+A[i];
//	for (int i=0; i<k; ++i) printf("%lld ", sum[i]); puts("");
	int bn = x + ((n-1)/k)*sum[k-1] + sum[(n-1)%k];
	
//	printf("bn=%lld\n", bn);
	printf("%lld\n", n-(bn/m));
	return 0;	
}

C. Battle

博弈论做不来怎么办，妈的直接打表干它

Nim游戏经典结论每堆独立，因此可以先对一堆求SG函数：

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int p,n,sg[N];
inline int SG(CI n)
{
	if (n==0) return 0;
	if (~sg[n]) return sg[n];
	static int vis[N]; RI i;
	for (i=0;i<=n;++i) vis[i]=0;
	if (p==1) vis[SG(n-1)]=1;
	else for (i=1;i<=n;i*=p) vis[SG(n-i)]=1;
	for (i=0;;++i) if (!vis[i]) return sg[n]=i;
}
int main()
{
	freopen("table.txt","w",stdout);
	for (p=1;p<=20;++p)
	{
		memset(sg,-1,sizeof(sg));
		for (n=0;n<=50;++n)
		printf("SG(p=%d,n=%d) = %d\n",p,n,SG(n));
	}
	return 0;
}

然后对着表小看一手规律首先会发现当\(p\)固定时，SG函数有长为\(p+1\)的周期

同时当且仅当\(p\)为偶数且\(n=p\)时，\(SG\)函数值为\(2\)，否则\(SG\)函数值仅与\(n\)的奇偶性有关

#include<cstdio>
#include<iostream>
#include<cctype>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
int n,p,x,ret;
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;
inline int SG(CI p,int n)
{
	n%=(p+1); if (p%2==0&&p==n) return 2; return n&1;
}
signed main()
{
	//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
	RI i; for (F.read(n),F.read(p),i=1;i<=n;++i) F.read(x),ret^=SG(p,x);
	return puts(ret?"GOOD":"BAD"),0;
}

D. Stack Out

DP之神徐神秒了此题

考虑容斥一下用总合法括号序列数（卡特兰数）减去不存在一段长度\(\ge k\)的右括号的方案数

后者的数量很容易想到DP，设\(f_{i,j}\)表示处理了前\(i\)个位置，左括号比右括号多出的数量为\(j\)的方案数

转移考虑枚举一次放\(t(t<k)\)个右括号，然后观察到转移后两维的和是一个和\(t\)无关的值，因此直接做一个前缀和优化下即可

#include <bits/stdc++.h>

using llsi = long long signed int;

constexpr int mod = 998244353;
constexpr int $n = 6005;

int dp[$n][$n];

inline void add(int &a, const int &b) {
	a += b;
	if(a >= mod) a -= mod;
}

llsi ksm(llsi a, llsi b) {
	llsi res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

llsi fac[$n], facinv[$n];

void prep(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
	facinv[n] = ksm(fac[n], mod - 2);
	for(int i = n; i > 0; --i) facinv[i - 1] = facinv[i] * i % mod;
	return ;
}

llsi C(int a, int b) {
	return fac[a] * facinv[b] % mod * facinv[a - b] % mod;
}

int main(void) {
	int n, k, hn;
	std::cin >> hn >> k;
	n = hn << 1;
	prep(n);
	dp[0][0] = 1;
	for(int i = 0; i <= n; ++i) for(int j = 0; j <= i; ++j) {
		if(i) add(dp[i][j], dp[i - 1][j + 1]);
		// std::cerr << dp[i][j] << char(j == i ? 10 : 32);
		add(dp[i + 1][j + 2 - 1], dp[i][j]);
		if(i + k + 1 <= n && j + 2 - k - 1 >= 0)
			add(dp[i + k + 1][j + 2 - k - 1], mod - dp[i][j]);
	}
	std::cout << (C(n, hn) + mod - C(n, hn - 1) + mod - dp[n][0]) % mod << char(10);
	return 0;
}

E. Segment-tree

防AK题全场没人过，但据说就是个模拟题？策不清楚

F. Cities

这题的DP状态很好想，但转移的细节比较多需要耐心思考下：

当确定了前\(i\)个城市，其中有\(j\)个城市是向右匹配，设\(f_{i,j}\)表示满足上述状态的方案数，\(g_{i,j}\)是总贡献

转移根据\(i+1\)是向左还是向右匹配讨论下即可，注意所有状态均要满足\(0\le j\le s_i\)

具体转移方程看代码吧，复杂度\(O(n^2)\)

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

const int N = 2005,mod = 998244353;
int n, x[N], s[N];
int f[N][N],g[N][N];

inline void inc(int& x,int y)
{
	if ((x+=y)>=mod) x-=mod;
}

signed main(){
	//freopen("F.in","r",stdin); freopen("F.out","w",stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; ++i) cin >> x[i];
	for (int i=1; i<n; ++i) cin >> s[i];
	f[1][1]=1; g[1][1]=0;
	for (int i=1; i<n; ++i){
		for (int j=0; j<=s[i]; ++j){
			inc(f[i+1][j+1],f[i][j]);
			inc(f[i+1][j-1],1LL*f[i][j]*j%mod);
			inc(g[i+1][j+1],(g[i][j]+1LL*(x[i+1]-x[i])*j%mod*f[i][j]%mod)%mod);
			inc(g[i+1][j-1],(1LL*g[i][j]*j%mod+1LL*(x[i+1]-x[i])*j%mod*j%mod*f[i][j]%mod)%mod);
		}
	}
	/*for (int i=1;i<=n;++i) for (int j=0;j<=s[i];++j)
	printf("f[%d][%d]=%d;g[%d][%d]=%d\n",i,j,f[i][j],i,j,g[i][j]);*/
	return printf("%d",g[n][0]),0;	
}

G. Copy and Paste

论徐神为什么是神，什么压轴字符串我String Master直接秒了

徐神的做法好像和题解的不太一样，用Z函数+调和级数枚举+主席树写的，总之牛逼就对了

#include <bits/stdc++.h>

constexpr int $n = 100000 + 5;

constexpr int INF = 0x7fffffff;
using pii = std::pair<int, int>;

namespace smt {
	constexpr int $node = $n * 40;
	int lc[$node], rc[$node], O = 0;
	int mv[$node] = { INF };
	
	int newVersion(int now, int p, int info, int l, int r) {
		int res = ++O;
		if(l == r) return lc[res] = rc[res] = 0, mv[res] = info, res;
		int mid = (l + r) >> 1;
		if(p > mid) lc[res] = lc[now], rc[res] = newVersion(rc[now], p, info, mid + 1, r);
		else        rc[res] = rc[now], lc[res] = newVersion(lc[now], p, info, l, mid);
		mv[res] = std::min(mv[lc[res]], mv[rc[res]]);
		return res;
	}
	
	int checkOut(int now, int ql, int qr, int l, int r) {
		if(!now || ql > r || l > qr) return INF;
		if(ql <= l && r <= qr) return mv[now];
		int mid = (l + r) >> 1;
		return std::min(
			checkOut(lc[now], ql, qr, l, mid),
			checkOut(rc[now], ql, qr, mid + 1, r)
		);
	}
}

std::vector<int> z_function(const std::string& s) {
	int n = (int)s.length();
	std::vector<int> z(n);
	for (int i = 1, l = 0, r = 0; i < n; ++i) {
		if (i <= r && z[i - l] < r - i + 1) {
			z[i] = z[i - l];
		} else {
			z[i] = std::max(0, r - i + 1);
			while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
		}
		if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
	}
	return z;
}

int main() {
	std::string s;
	std::cin >> s;
	int n = s.size(), ans = n;
	auto z = z_function(s);
	std::vector<int> ug(n + 5);
	ug[n] = 0;
	for(int i = n - 1; i >= 0; --i) ug[i] = smt::newVersion(ug[i + 1], z[i], i, 0, n);
	std::vector<int> dp(n + 5);
	for(int i = 0; i < n; ++i) dp[i] = i + 1;
	for(int i = 2; i <= n; ++i) {
		dp[i] = std::min(dp[i], dp[i - 1] + 1);
		int cur = i - 1, cost = dp[cur] + 1;
		
		for(
			int nxt = smt::checkOut(ug[cur + 1], i, n, 0, n);
			nxt != INF;
			nxt = smt::checkOut(ug[cur + 1], i, n, 0, n)
		) {
			int nc = nxt + i - 1;
			cost += nc - cur - i + 1;
			dp[nc] = std::min(dp[nc], cost);
			ans = std::min(ans, cost + (n - 1) - nc);
			cur = nc;
			// std::cerr << "nxt = " << nxt << char(10);
			// std::cerr << "(cur, cost, i) = (" << cur << ", " << cost << ", " << i << ")\n";
		}
	}
	// for(int i = 0; i < n; ++i) std::cerr <<  z[i] << char(i == n - 1 ? 10 : 32);
	// for(int i = 0; i < n; ++i) std::cerr << dp[i] << char(i == n - 1 ? 10 : 32);
	std::cout << ans << char(10);
	return 0;
}

H. Permutation

祁神手玩后发现题目可以这样转化，先对所有位置求出其前缀最大值，发现所有前缀最大值相同的位置必须放在一起

因此现在题目变成，给定若干个物品，它们的体积和为\(n\)，要求是否存在一种方案能选出体积和为\(\frac{n}{2}\)的物品

利用经典结论，不同的物品种类数是\(\sqrt n\)级别的，然后对于体积相同的物品用二进制分组优化多重背包即可

#include<cstdio>
#include<iostream>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=500005;
int t,n,p[N],pre[N],cnt[N],bkt[N],f[N],ans;
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;
int main()
{
	//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
	for (F.read(t);t;--t)
	{
		RI i,j,k; for (F.read(n),i=1;i<=n;++i)
		F.read(p[i]),pre[i]=max(pre[i-1],p[i]);
		for (i=1;i<=n;++i) cnt[i]=bkt[i]=0;
		for (i=1;i<=n;++i) ++cnt[pre[i]];
		for (i=1;i<=(n>>1);++i) f[i]=0; f[0]=1;
		for (i=1;i<=n;++i) if (cnt[i]) ++bkt[cnt[i]];
		for (i=1;i<=n;++i) if (bkt[i])
		{
			int sum=0; for (j=0;sum+(1<<j)<=bkt[i];++j)
			{
				int V=i*(1<<j); sum+=(1<<j);
				for (k=n>>1;k>=V;--k) f[k]|=f[k-V];
			}
			if (sum!=bkt[i])
			{
				int V=i*(bkt[i]-sum);
				for (k=n>>1;k>=V;--k) f[k]|=f[k-V];
			}
		}
		puts(f[n>>1]?"Yes":"No");
	}
	return 0;
}

I. Tree

签到题，不难发现修改操作只会对两个端点的询问值造成影响

#include<cstdio>
#include<iostream>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=500005;
int n,q,x,y,w,s[N],opt;
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++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        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()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;
int main()
{
	//freopen("I.in","r",stdin); freopen("I.out","w",stdout);
	RI i; for (F.read(n),F.read(q),i=1;i<n;++i)
	F.read(x),F.read(y),F.read(w),s[x]^=w,s[y]^=w;
	for (i=1;i<=q;++i)
	{
		F.read(opt); F.read(x);
		if (opt==2) F.write(s[x]); else
		F.read(y),F.read(w),s[x]^=w,s[y]^=w;
	}
	return F.flush(),0;
}

J. Function

刚开始写了半天的李超线段树，连WA七发怀疑人生，后面冷静了一下仔细自考后发现原来是个思博题(所以我李超树板子TMD好像有问题)

注意到每次询问我们只要暴力枚举检验区间\([a-\sqrt n,a+\sqrt n]\)即可

因为\(a,b\)都在\([1,n]\)内，因此当\(|x-a|>\sqrt n\)时，\((x-a)^2\)带来的影响将超过\(b\)的不同带来的影响，因此一定不优

#include<cstdio>
#include<iostream>
#include<cctype>
#include<cmath>
#define int long long
#define RI register int
#define CI const int
#define Tp template <typename T>
using namespace std;
const int N=100005;
int n,b[N],q,opt,x,y,S;
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++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        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()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;
signed main()
{
	//freopen("J.in","r",stdin); freopen("J.out","w",stdout);
	RI i; for (F.read(n),i=1;i<=n;++i) F.read(b[i]);
	auto f=[&](CI x,CI i)
	{
		return (x-i)*(x-i)+b[i];
	};
	for (S=(int)sqrt(n)+1,F.read(q);q;--q)
	{
		F.read(opt); F.read(x); if (opt==1)
		{
			int ret=f(x,x);
			for (i=1;i<=S&&x-i>=1;++i) ret=min(ret,f(x,x-i));
			for (i=1;i<=S&&x+i<=n;++i) ret=min(ret,f(x,x+i));
			F.write(ret);
		} else F.read(y),b[x]=min(b[x],y);
	}
	return F.flush(),0;
}

K. Split

好像也是个思博题，祁神开局写的我题意都不知道

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

#define RI register int
#define CI const int
#define Tp template <typename T>
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++)
        #define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
        char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
    public:
        inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
        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()));
        }
        Tp inline void write(T x,const char ch='\n')
        {
            RI ptop=0; while (pt[++ptop]=x%10,x/=10);
            while (ptop) pc(pt[ptop--]+48); pc(ch);
        }
        inline void flush(void)
        {
            fwrite(Fout,1,Ftop-Fout,stdout);
        }
        #undef tc
        #undef pc
}F;

const int N = 1e6+5;
int n, m, A[N], B[N], sum[N];
signed main(){
//	freopen("1.in", "r", stdin);
	F.read(n);
	for (int i=1; i<=n; ++i) F.read(A[i]);
	for (int i=n-1; i>=1; --i) B[i] = A[i]-A[i+1];
	sort(B+1, B+n, greater<int>());
	for (int i=1; i<=n-1; ++i) sum[i]=sum[i-1]+B[i];
	F.read(m);
//	printf("n=%d m=%d\n", n, m);
	for (int i=1; i<=m; ++i){
		int typ, x; F.read(typ); F.read(x);
		if (0==typ) continue;
		printf("%d\n", sum[n-1]-sum[x-1]);	
	}
	return 0;	
}

L. Zhang Fei Threading Needles - Thick with Fine

签到，输出\(n-1\)即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int n;
int main()
{
	//freopen("L.in","r",stdin); freopen("L.out","w",stdout);
	return scanf("%d",&n),printf("%d",n-1),0;
}

Postscript

这就是徐神，又是写压轴DP又是写压轴字符串（怎么和合肥一模一样），强势带领我们走向胜利