2024山东省赛回顾

2024 CCPC 全国邀请赛（山东）暨山东省大学生程序设计竞赛是我参加的第一场线下赛

但是当时以几名之差痛失Cu牌，之前一直没有补题，现在来回看一下

题目链接：https://codeforces.com/gym/105385

顺序由简到难：I，A，K，F，C，J

I - Left Shifting

签到题，若无相邻字符则无解，否则枚举左移次数 0≤d<n0 ≤ d < n，判断是否 sd=sd+n−1modns_d = s_{d+n−1 mod n} 即可。

#include <bits/stdc++.h>
using namespace std;
int n;
char a[500005];
void solve()
{
	cin>>a;
	n=strlen(a);
	int ans=0;
	if(a[0]==a[n-1]){
		cout<<ans<<"\n";
		return;
	}
	for(int i=0;i<n-1;i++)
		if(a[i]==a[i+1])
		{
			ans=i+1;
			break;
		}
	if(ans) cout<<ans<<"\n";
	else cout<<"-1\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

A - Printer

二分答案，注意二分上限是2e18，这题考场上一发过了，但是补题的时候又被二分上限卡了好几发罚时

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
struct N{
	ll t;
	ll l;
	ll w;
}a[105];
int n;
ll k;
int check(ll now)
{
	ll tot=0;
	for(int i=1;i<=n;i++)
	{
		ll tmp=(now/(a[i].t*a[i].l+a[i].w)*a[i].l);
		if(now%(a[i].t*a[i].l+a[i].w)>=a[i].t*a[i].l) tmp+=a[i].l;
		else tmp+=((now%(a[i].t*a[i].l+a[i].w))/a[i].t);
		tot+=tmp;
		if(tot>=k) return 1;
	}
	return 0;
}
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].t>>a[i].l>>a[i].w;
	ll L=0,R=2e18;
	while(L<R)
	{
		ll mid=(L+R)/2;
		if(check(mid)) R=mid;
		else L=mid+1;
	}
	cout<<L<<"\n";
	return;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

K - Matrix

这道题场上想了好久，最后队友想出来的构造方法

构造，可采取如下构造方式：

 1  2  6  8 10
 3  4  6  8 10
 6  6  5  8 10
 8  8  8  7 10
10 10 10 10  9

初始矩阵为1234\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}，作为唯一的没有相同数字的矩阵，

然后依次将 2n+12n+1 填入右下，然后将 2n+22n+2 填入剩余空位补齐即可

发现并不存在构造不出的情况

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
int n;
int a[55][55];
void solve()
{
	cin>>n;
	a[1][1]=1;
	a[1][2]=2;
	a[2][1]=3;
	a[2][2]=4;
	int idx=5;
	for(int i=3;i<=n;i++)
	{
		a[i][i]=idx++;
		for(int j=1;j<i;j++)
			a[i][j]=idx;
		for(int j=1;j<i;j++)
			a[j][i]=idx;
		idx++;
	}
	cout<<"Yes\n";
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<a[i][j]<<" ";
		cout<<"\n";
	}
	return;
}
int main()
{
	int T=1;
	// cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}

F - Divide the Sequence

k=1k=1 时，anskans_k 是数组所有元素之和，kk 由 11 变为 22 可以看做在 ans1ans_1上加上一个原数组的某个后缀和，要让每个答案最大化的话，只需要将 22 到 nn 的后缀和从大到小排序，依次加入即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[500005];
ll pre[500005];
int cmp(ll aa,ll bb)
{
	return aa>bb;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	pre[n+1]=0;
	for(int i=n;i>=1;i--)
		pre[i]=pre[i+1]+a[i];
	sort(pre+2,pre+n+1,cmp);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=pre[i];
		cout<<ans<<" ";
	}
	cout<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

C - Colorful Segments 2

将线段按左端点从小到大排序，用小根堆维护当前的最小右端点，枚举到某个左端点时，将小于当前左端点的右端点依次弹出，颜色总数-堆的大小即为当前线段可选的颜色数，累乘到 ansans 中即可，最后把当前线段的右端点加入小根堆

这道题场上的思路是对的，但是没调出来，现在再回看的话其实是小儿科了 ，痛失Cu牌QwQ

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct N{
	ll l;
	ll r;
}a[500005];
int n;
ll k;
ll ans;
ll mod=998244353;
int cmp(N aa,N bb)
{
	return aa.l<bb.l||aa.l==bb.l&&aa.r<bb.r;
}
priority_queue<ll,vector<ll>,greater<ll>> q;
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	while(!q.empty()) q.pop();
	ans=1;
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.top()<a[i].l)
		{
			k++;
			q.pop();
		}
		ans=(ans*k)%mod;
		q.push(a[i].r);
		k--;
	}
	cout<<ans<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct N{
	ll l;
	ll r;
}a[500005];
int n;
ll k;
ll ans;
ll mod=998244353;
int cmp(N aa,N bb)
{
	return aa.l<bb.l||aa.l==bb.l&&aa.r<bb.r;
}
priority_queue<ll,vector<ll>,greater<ll>> q;
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i].l>>a[i].r;
	sort(a+1,a+n+1,cmp);
	while(!q.empty()) q.pop();
	ans=1;
	for(int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.top()<a[i].l)
		{
			k++;
			q.pop();
		}
		ans=(ans*k)%mod;
		q.push(a[i].r);
		k--;
	}
	cout<<ans<<"\n";
	return;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

J - Colorful Spanning Tree

这道题赛时没思路，赛后看的官方题解补题

这里附上官方题解

  • 对每种颜色需要维护：这个颜色的所有点是否在同一连通块 里，以及颜色之间的并查集。
  • 模仿 KurskalKurskal 算法的过程，按边权从小到大考虑每对颜色 (u,v)(u, v) 的连边，并分类讨论。

情况一：u=vu=v

  • 若颜色 u 所有点已在同一连通块内则跳过。
  • 否则连 (au−1)(a_u −1) 条边，标记这个颜色所有点在同一连通块内。

情况二：u≠vu\neq v

  • 若颜色 u 和 v 在同一连通块内则跳过。
  • 否则若 u 和 v 所有点都不在同一连通块内，连 (au+av−1)(a_u + a_v − 1) 条边。
  • 否则若 u 所有点都不在同一连通块内，连 (au−1)(a_u − 1) 条边。v 同理。
  • 否则连 1 条边即可。
  • 连边结束后，标记 u 和 v 的所有点在同一连通块内，并连接 颜色的并查集。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct E{
	int u;
	int v;
	int w;
};
int n;
int a[1005];
int uni[1005];
int fa[1005];
int k;
ll ans;
int find(int aa)
{
	if(fa[aa]==aa) return aa;
	fa[aa]=find(fa[aa]);
	return fa[aa];
}
void un(int aa,int bb)
{
	aa=find(aa);
	bb=find(bb);
	fa[bb]=aa;
}
int cmp(E aa,E bb)
{
	return aa.w<bb.w;
}
void solve()
{
	cin>>n;
	vector<E> e;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		uni[i]=0;
		fa[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>k;
			if(i<=j)
			{
				e.push_back({i,j,k});
			}
		}
	}
	sort(e.begin(),e.end(),cmp);
	ans=0;
	for(auto &it:e)
	{
		int u=it.u;
		int v=it.v;
		int w=it.w;
		if(u==v)
		{
			if(!uni[u]) ans+=1LL*(a[u]-1)*w;
			uni[u]=1;
			continue;
		}
		else
		{
			if(find(u)==find(v)) continue;
			un(u,v);
			ans+=w;
			if(!uni[u]) ans+=1LL*(a[u]-1)*w;
			uni[u]=1;
			if(!uni[v]) ans+=1LL*(a[v]-1)*w;
			uni[v]=1;
		}
	}
	cout<<ans<<"\n";
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
	while(t--)
	{	
		solve();
	}
	return 0;
}