YL 模拟赛总结 7

Problem

T1

预处理出前 \(10^4\) 个格子需要填什么数，然后输出即可。

具体地，我们记录 \(e\) 为当前层数，\(o\) 为上一层的最后一个的位置，\(last\) 为上一个填的格子的位置。

我们知道，一个格子要么在一层的起点，要么在一层的中间，要么在一层的末尾。

枚举 \(1 \sim 5\) 分别对这三种情形进行判断，在符合上述三种情形之一的数中取编号最小且出现次数最小的填入当前各自即可。

然后，因为每一层都有 \((e-1) \times 6\) 个格子，因此当 \((i-o)=(e-1) \times 6\)（\(i\) 为当前填的格子）时，更新 \(e \gets e+1,o \gets i\)。

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

int t,n;
int a[10031],vis[10031];

int main(){
	for(int i=1,e=1,o=1,last=1;i<=(int)(1e4);i++){
		int cnt=1e9,now=0;
		for(int j=1;j<=5;j++){
			if((j!=a[i-1]&&j!=a[last]&&((e!=1&&(i-o)%(e-1)==0&&(i-o)/(e-1)==6&&j!=a[last+1])||(e==1||((i-o)%(e-1)==0&&(i-o)/(e-1)!=6)||j!=a[last+1])))||(i-o==1&&j!=a[i-1]&&j!=a[last+1]))
				if(vis[j]<cnt)
					cnt=vis[j],now=j;
		}
		if(e!=1&&(i-o)%(e-1)!=0) last++;
		a[i]=now,vis[now]++;
		if((i-o)==(e-1)*6) e++,o=i;
	}
	for(cin>>t;t;t--) cin>>n,cout<<a[n]<<'\n';
	return 0;
}

T2

首先，求出数列的前缀和数组 \(\bmod \ k\) 的值，即为 \(sum_i\)。

若一个 \([l,r]\) 的区间和能被 \(k\) 整除，则根据同余的性质可得 \(sum_r=sum_{l-1}\)。

于是我们使用一个桶记录每个 \(sum_i\) 的出现次数，每个 \(sum_i\) 对于答案的贡献即为 \(\dfrac{cnt_{sum_i} \times (cnt_{sum_i}-1)}{2}\)，累加入答案输出即可。

T3

咕咕咕。。。

T4

模拟游戏过程进行 dfs 即可，需要进行记忆化。

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

int num[10][5];
double ans[5][5][5][5][5][5][5][5][5];
bool vis[5][5][5][5][5][5][5][5][5];

double dfs(int *xx){
	int x[10],tot=0;
	for(int i=1;i<=9;i++) x[i]=xx[i],tot+=x[i];
	if(!tot) return 1.0;
	if(vis[x[1]][x[2]][x[3]][x[4]][x[5]][x[6]][x[7]][x[8]][x[9]]) 
		return ans[x[1]][x[2]][x[3]][x[4]][x[5]][x[6]][x[7]][x[8]][x[9]];
	vis[x[1]][x[2]][x[3]][x[4]][x[5]][x[6]][x[7]][x[8]][x[9]]=1;
	tot=0;
	for(int i=1;i<=9;i++)
		if(x[i]!=0)
			for(int j=i+1;j<=9;j++)
				if(num[i][x[i]]==num[j][x[j]]) tot++;
	double cc=1.00/tot,ttot=0.0;
	for(int i=1;i<=9;i++)
		if(x[i]!=0)
			for(int j=i+1;j<=9;j++)
				if(num[i][x[i]]==num[j][x[j]]){
					x[i]--,x[j]--;
					ttot+=dfs(x)*cc;
					x[i]++,x[j]++;					
				}
	ans[x[1]][x[2]][x[3]][x[4]][x[5]][x[6]][x[7]][x[8]][x[9]]=ttot;
	return ttot;
}

int main(){
	for(int i=1;i<=9;i++){
		for(int j=1;j<=4;j++){
			string s; cin>>s;
			num[i][j]=(int)(s[0]);
		}
	}
	int x[10];
	for(int i=1;i<=9;i++) x[i]=4;
	dfs(x);
	cout<<setprecision(6)<<fixed<<ans[4][4][4][4][4][4][4][4][4];
	return 0;
}