By

12届集美大学校赛题解

官方难度排序参考：

  • Easy：GBJHD
  • Medium：CAEL
  • Hard：KIF

A、地砖

题意：m 的矩形，向每个格子中填充字母，使得：所有同字母联通块必须为正方形。

最小化从上到下，从左到右的字典序。

题解：

最小化字典序是经典的贪心问题。

我们按照从上到下，从左到右的顺序枚举每一个未填充格子的颜色，判断是否可行，需要的时候将已有的正方形向右方和下方扩充一行和一列。

填到一个格子的时候，其左右上方紧邻格子都可能填充过。

如果该颜色与上方或右方相同，这种情况不合法。

如果它与左边颜色不同，那么可以构成 1*1 方块。

如果它与左边颜色相同，我们就要进一步考察左边的方块。

如果左边的方块不是一个已有正方形的右上角，那么不合法。

否则我们将该正方形向右方和下方扩充一行和一列，无法扩充则不合法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
int sn,sm;
char a[N][N];
char get_color(char lc,char uc,char rc){
	for(char i='A';i<='Z';i++){
		if(i!=lc&&i!=uc&&i!=rc){
			return i;
		}
	}
} 
void work(int x,int y){
	char c=get_color(a[x-1][y],a[x][y-1],a[x][y+1]);
	int len=1;
	while(a[x+len][y-1]!=c&&a[x-1][y+len]!=c&&x+len<=sn&&y+len<=sm&&!a[x+len][y]&&!a[x][y+len]){
		char t=get_color(c,a[x-1][y+len],0);
		if(t<c)break;
		len++;
	}
	for(int i=x;i<=x+len-1;i++){
		for(int j=y;j<=y+len-1;j++){
			a[i][j]=c;
		}
	}
	return;
}
int main(){
	cin>>sn>>sm;
	int cn,cm;
	cn=sn,cm=sm;
	for(int i=1;i<=sn;i++){
		for(int j=1;j<=sm;j++){
			if(!a[i][j])work(i,j);
		}
	}
	for(int i=1;i<=cn;i++){
		for(int j=1;j<=cm;j++){
			cout<<a[i][j];
		}
		cout<<"\n";
	}
}

B、逃离蜂巢

题意：有𝑛个陷阱，每拆除一个陷阱，生命值先加 𝑎 再减去 𝑏。任意时刻生命值必须为正数，求一个最优顺序，在初始生命值为ℎ的情况下拆除最多陷阱。

题解：

按 a-b 从大到小排序，按顺序拿取即可。

ll n,h,ans=0;cin>>n>>h;
vector<ll> c(n);
for(int i=0;i<n;i++){
    ll a,b;cin>>a>>b;
    c[i]=a-b;
}
sort(c.begin(),c.end());
for(int i=n-1;i>=0;i--){
    h+=c[i];
    ans++;
    if(h<=0) {ans--;break;}
}
cout<<ans<<"\n";

C、加密通讯

题意：给出一个 01 字符串若干子串 1 个数的奇偶性，构造最小字典序的解。

题解：

考虑该串的前缀异或和 \(s[i]\)，则 \(parity[l,r]=s[r] \wedge s[l-1]\)。

这是一个经典的2-SAT问题。

其最小字典序的解可以从前向后逐位确定，注意限制 s[0]=0。

考虑异或前缀和是否相同的限制，题目保证有解的话就可以从任意已知的位置的值得到所有相关位置的值，位置 0 的前缀和为 0，所以从 0 开始计算，如果遇到一个没算过的位置 i，为了最小化答案字典序，就让位置 i 的前缀和与位置 i -1 的前缀和值相等，这样答案里 位置 i 的值就是 0 了，扫一遍就可以。

//第一种代码
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int n, k;
int head[N], to[N << 1],nxt[N << 1], tot = 0; 
int s[N], ans[N];
void add(int u, int v){
	nxt[++tot] = head[u];
	to[tot] = v;
	head[u] = tot;
}
void dfs(int u){
	for(int i = head[u];i;i=nxt[i]){
		int v = to[i];
		if(!s[v]){
			s[v] = 1;
			dfs(v);
		} 
	}
}
int main(){
	int n, k;cin >> n >> k;
	n+=1;
	for(int i = 1; i <= k; i ++){
		int l, r, val;cin >> l >> r >> val;
		if(val == 0){
			add(r, l - 1);
			add(l - 1, r);
			add(r + n, l - 1 + n);
			add(l - 1 + n, r + n);
		}
		else{
			add(r, l - 1 + n);
			add(l - 1, r + n);
			add(r + n, l - 1);
			add(l - 1 + n, r);
		}
	}
	int st = 0;
	dfs(n);
	for(int i = 1; i<= n; i ++){
		int node = (!st)*n + i;
		if(!s[i] && !s[i + n]){
			ans[i] = st;
			dfs(node);
		}
		else if(s[i]){
			ans[i] = 1;
			dfs(i);
			st = 1;
		}
		else{
			ans[i] = 0;
			dfs(i + n);
			st = 0;
		}
	}
	for(int i = 1; i < n - 1; i ++)
		cout << (ans[i] ^ ans[i - 1]) << ' ';
	cout << (ans[n - 1] ^ ans[n - 2]);
	return 0;
}

//第2种代码
vector<pair<int,int> > v[3005];
int n,m,e[3005],ans[3005];
bool on[3005];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int l,r,x;cin>>l>>r>>x;
		l--;
		v[l].push_back({r,x});
		v[r].push_back({l,x});
	}
	for(int i=0;i<=n;i++)
		if(on[i]==0){
			on[i]=1;
			if(i!=0) e[i]=e[i-1];
			queue<int> q;
			for(q.push(i);!q.empty();q.pop()){
				int now=q.front();
				for(auto [to,w]:v[now])
					if(on[to]==0){
					e[to]=e[now]^w;
					on[to]=1,q.push(to);
				}
			}
		}
	for(int i=1;i<=n;i++) ans[i]=e[i-1]^e[i];
	for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
}

D、简易量筒

题意：有一条河以及 n 个杯子，每个杯子有一个容量。使用这些杯子，能否量出对应体积的水？Q 组询问。

题解：

使用容积为 A 的杯子，我们既可以将水增加 A 也可以减少 A。

因此能够量出的体积为 \(\sum_{i=1}^nA_ix_i，x_i是整数\)。

按照扩展欧几里得定理，其一定为 \(gcd(A_1,A_2,...,A_n)\) 的倍数。

cin>>n>>q;
cin>>ans;
for(int i=2;i<=n;i++){
    ll x;cin>>x;
    ans=__gcd(ans,x);
}
while(q--){
    ll x;cin>>x;
    if(x%ans==0) cout<<"Yes\n";
    else cout<<"No\n";
}

E、复杂量筒

题意：有 n 个量筒，第 i 个量筒为 \(i!\)。

在凑出一定体积的液体的所有方案中，我们选择使用的量筒总数最小的那个。

求量出 \(l \sim r\) 中所有整数体积各一次每个量筒需要用几次，q 组询问。

题解：

最优方案容易贪心，优先选取 n 号量筒，不够时再选取 n-1 号，以此类推。

因此对于 \(l\sim r\) 中的每个数，都把它写出 \(k*n!+b(b<n!)\) 的形式。

k 的部分是等差数列求和。

对 b 的部分，预处理 \(0 \sim n!-1\) 的结果，其呈现周期排布，使用前缀和数组可以快速得出答案。

G、电话

题意：给出一个电话键盘和一个号码，求手指移动的总长。

题解：

打表预处理按键的位置，直接计算，时间复杂度 \(O(n)\)。

//按键位置，不知为什么，页面放这段代码就报错
string s;cin>>s;
int x=a[s[0]-'0'][0],y=a[s[0]-'0'][1],sum=0;
for(int i=1;i<s.size();i++){
    sum+=abs(x-a[s[i]-'0'][0])+abs(y-a[s[i]-'0'][1]);
    x=a[s[i]-'0'][0],y=a[s[i]-'0'][1];
}
cout<<sum<<"\n";

H、花坛

题意：求有多少种合法的方案在 n*m 花坛中放满至多 4 种花，满足不存在同行同种花距离 <=3 ，不存在同列同种花距离 <=3 。

题解：

考虑任意同行或同列连续四格，其必定互异。

然后可以发现，确定左上了 4*4 格，其余格子全部固定。

暴搜左上格子即可。

//暴搜代码
void dfs(ll x,ll y){
	if(y==m+1&&x!=n){
		dfs(x+1,1);
		return;
	}else if(y==m+1&&x==n){
		ans++;
		return ;
	}
	for(int i=1;i<=4;i++){
		ll x1= x-3>=1ll ?b[x-3][y]:-1ll;
		ll x2= x-2>=1ll ?b[x-2][y]:-1ll;
		ll x3= x-1>=1ll ?b[x-1][y]:-1ll;
		ll y1= y-3>=1ll ?b[x][y-3]:-1ll;
		ll y2= y-2>=1ll ?b[x][y-2]:-1ll;
		ll y3= y-1>=1ll ?b[x][y-1]:-1ll;
		if(x1==i||x2==i||x3==i||y1==i||y2==i||y3==i){
			continue;
		}else{
			b[x][y]=i;
			dfs(x,y+1);
			b[x][y]=0;
		}
	}
}

//AC代码
void init(){
	a[1][1]=4;a[1][2]=12;a[1][3]=24;a[1][4]=24;
	a[2][1]=12;a[2][2]=84;a[2][3]=264;a[2][4]=216;
	a[3][1]=24;a[3][2]=264;a[3][3]=1056;a[3][4]=576;
	a[4][1]=24;a[4][2]=216;a[4][3]=576;a[4][4]=576;
}
int main(){
	init();
	cin>>n>>m;
	if(n>=4&&m>=4) cout<<a[4][4]<<"\n";
	else if(n>=4) cout<<a[4][m]<<"\n";
	else if(m>=4) cout<<a[n][m]<<"\n";
	else cout<<a[n][m]<<"\n";
}

J、分子测序

题意：求三维空间中任意三点不共线，任意四点不共面的 𝑛 个顶点的凸多面体有多少个面。

题解：

考虑新添加一个顶点，其可以看作是在其中一面上向外扩展出一个四面体，新增加 \(4-2=2\) 个面，答案为 \(2n-4\) 。

int test;cin>>test;
while(test--){
    int n;cin >> n;
    cout<<2*n-4<<"\n";
}

L、董事会

题意：有 n 个石子组成一个环，每个石子有一个颜色。

对于每个 0≤k≤n ，判断是否能删除连续的 k 个石子，使得剩下的任意相邻两个石子不同色。

const int maxn = 1e6+114;
const ll mod = 1e9+7;
const ll base = 131;
ll pre[maxn],a[maxn],_pow[maxn];
int n;
int nxt[maxn],lst[maxn];
int ans[maxn];
bool chk(int l,int r,int L,int R){
	return ((pre[r]+mod-pre[l-1])%mod*_pow[L]%mod)==((pre[R]+mod-pre[L-1])%mod*_pow[l]%mod);
}		
void work(){
	cin>>n;
	_pow[0]=1;
	for(int i=1;i<=n;i++) _pow[i]=_pow[i-1]*base%mod;
	for(int i=1;i<=n;i++) cin>>a[i],pre[i]=(pre[i-1]+a[i]*_pow[i]%mod)%mod;
	nxt[n]=n;
	for(int i=n-1;i>=1;i--){
		if(a[i]==a[i+1]) nxt[i]=i;
		else nxt[i]=nxt[i+1];
	}
	lst[1]=1;
	for(int i=2;i<=n;i++){
		if(a[i]==a[i-1]) lst[i]=i;
		else lst[i]=lst[i-1];
	}
	ans[0]=(lst[n]==1&&a[1]!=a[n]);
	for(int i=n-1;i>1;i--){
		bool flag=false;
		for(int l=1,r=i;l<=n;l=r+1,r=min(n,l+i-1)){
			if(nxt[l]>=r&&a[l]!=a[r]&&r-l+1==i) flag=true;
			int L=r+1,R=min(n,L+i-1);
			if(L>R) continue;
			if(a[r]==a[L]) continue;
			int liml=r-max(lst[r],l)+1;
			int limr=min(nxt[L],R)-L+1;
			int xl=(r-l+1)-liml+1,xr=r-l+1;
			int yl=(r-l+1)+1,yr=(r-l+1)+limr;
			yl-=(i-1),yr-=(i-1);
			xl=max(xl,yl);
			xr=min(xr,yr);
			if(xl<=xr){
				if(chk(l-1+xl,l-1+xr,l-1+xl+i-1,l-1+xr+i-1)==false) flag=true;
			}
		}
		ans[n-i]=flag;
	}
	ans[n-1]=1;
	for(int i=1;i<n-1;i++){
		int xl=1,xr=nxt[1],yl=lst[n],yr=n;
		yl-=(i+1),yr-=(i+1);
		xl=max(xl,yl);
		xr=min(xr,yr);
		if(xl<=xr){
			if(chk(xl,xr,xl+i+1,xr+i+1)==false&&a[1]!=a[n]) ans[i]=true;
		}
	}
	for(int i=0;i<n;i++) cout<<ans[i];
	for(int i=0;i<n;i++) ans[i]=0;
}