【vjudge训练记录】11月个人训练赛2

训练情况

赛后反思

A题看错题导致我红温了，C题数组开小又导致我红温了，D题循环太早结束了，导致小数据没答案，我又红温了，F题刚好越界RE了，我又红温了，G题用string会RE，换成char数组就过了。

今天全场都在失误红温。。。

A题

这题是找 \(N \times N\) 的字符矩阵中是否包含 \(M \times M\) 的字符矩阵，我们考虑枚举左上角的点，然后循环遍历 \(M \times M\) 判断即可。

只要包含一次即可，不是说要平移了全部相同！！！

#include <bits/stdc++.h>

using namespace std;

const int N = 53;

int n,m;
string s[N],t[N];


int main(){
	cin>>n>>m;
	for(int i = 0;i<n;i++) cin>>s[i];
	for(int i = 0;i<m;i++) cin>>t[i];
	bool flag = false;
	for(int i = 0;i<n-m+1;i++){
		for(int j =0;j<n-m+1;j++){
			//cout<<i<<" "<<j<<" "<<i+m<<" "<<j+m<<endl;
			bool res = true;
			for(int k = i;k<i+m;k++){
				for(int l =j;l<j+m;l++){
					if(s[k][l] != t[k%m][l%m]) res = false;
				}
			}
			if(res) flag = true;
		}
	}
	if(flag) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

B题

求 \(n!\) 并对 \(10^9 + 7\) 取模，记得开 long long

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

const int mod = 1e9 + 7;

signed main(){
	int x; cin>>x;
	int ans = 1;
	for(int i = 1;i<=x;i++){
		ans*=i;
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

C题

图论DFS回溯，我们建双向边，然后深度优先搜索（DFS），同时开一个数组记录当前节点是否已经走过，如果走过就跳过，去连边的其他节点，然后再记录当前走过的节点数，如果走完了就答案+1即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 1E6;

int n,m;
int tot,head[N];
bool vis[N];
int ans;

struct node{
	int u,v,nxt;
}edge[N<<1];

void add_edge(int u,int v){
	edge[++tot].u = u;
	edge[tot].v = v;
	edge[tot].nxt = head[u];
	head[u] = tot;
}

void dfs(int x,int fa,int cnt){
//	cout<<x<<" "<<fa<<" "<<cnt<<endl;
	if(cnt == n-1 && (!vis[x])){
		ans++;
		return;
	}
	for(int i = head[x];i;i=edge[i].nxt){
		int u = edge[i].u;
		int v = edge[i].v;
		if(v == fa || vis[v]) continue;
		vis[u] = 1;
		dfs(v,u,cnt+1);
		vis[u] = 0;
	}
}

int main(){
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		int u,v,w; cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs(1,0,0);
	cout<<ans<<endl;
	return 0;
}

D题

这题我们显然发现，答案一定是 \(\le x\) 的，我们可以前面都不走，然后第 \(x\) 秒的时候走一步就到终点了，显然这个答案不是最优的，但是如果前面的和 \(\ge x\) 的话，我们就可以通过前面若干个之和走到 \(x\)，所以这题在求 \(\sum_{i=1}^{n}{a_i} \ge x\) 的最小 \(i\)，所以我们每次求和的时候判断一下，如果当前的和大于等于 \(x\) 的话，就输出 \(i\)。

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

signed main(){
	int x; cin>>x;
	int ans = 0;
	int sum = 0;
	for(int i = 1;i<=1E9;i++){
		if(sum>=x){
			cout<<ans<<endl;
			return 0;
		}
		sum += i;
		ans++;
	}
}

E题

这题我们观察到，我们可以每次把 \(m\) 掏两个出来，让 \(n\) 加一，问最后最多能组成多少个 S ，这题我们观察到二分单调性，我们首先优先满足 \(n\)，因为 \(x\) 个 S 需要 \(x\) 个 \(n\)，如果不够的话，我们先用 \(m\) 掏出来几个去凑，如果答案太大，我们的 \(m\) 就会不够用，如果答案太小，我们的 \(m\) 就会多出来，由此我们可以发现答案的二分单调性，所以我们考虑二分答案，如果满足条件就 l = m，不满足条件就 r = m - 1舍弃当前答案，注意一下 l = m 的话，(l + r) / 2 需要向上取整防止死循环。

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

int n,m; 

bool pd(int x){
	int le = max(0ll,x-n);
	int tm = m - le*2;
	return tm>=x*2;
}

signed main(){
	cin>>n>>m;
	int l = 0,r = 1E12,mm;
	while(l<r){
		mm = l + r + 1 >> 1;
		if(pd(mm)) l=mm;
		else r=mm-1;
	}
	cout<<l<<endl;
}

F题

这题我们容易得知，每种化学品我们都有两种状态选或不选，所以我们容易想到 01背包DP，此题的容量维度是二维，DP的状态转移方程为

dp[j][k] = min(dp[j][k],dp[j-a[i]][k-b[i]] + c[i]);

所以我们先求出 \(\sum{a_i}\) 和 \(\sum{b_i}\) 作为背包容量的上界，由于是 01 背包，我们容量需要倒着枚举，最后我们求答案的时候，我们只需要找最后所求比例的倍数即可，比如 1:2，我们就要求最后背包DP数组的 2:4，3:6，4:8，最后答案取一个最小值min即可。

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

const int N = 407;

int n,aa,bb;

int dp[N][N];
int a[N],b[N],c[N];

signed main(){
	memset(dp,INF,sizeof(dp));
	dp[0][0] = 0;
	cin>>n>>aa>>bb;
	int sum1 = 0,sum2 = 0;
	for(int i = 1;i<=n;i++) cin>>a[i]>>b[i]>>c[i],sum1+=a[i],sum2+=b[i];
	for(int i = 1;i<=n;i++){
		for(int j = sum1;j;j--){
			for(int k = sum2;k;k--){
				if(j-a[i] < 0 || k-b[i] < 0) continue;
				dp[j][k] = min(dp[j][k],dp[j-a[i]][k-b[i]] + c[i]);
			}
		}
	}
	int ans = INF;
	for(int i = 1;i*max(aa,bb)<N;i++){
		if(dp[aa*i][bb*i] == 0) continue;
		ans = min(ans,dp[aa*i][bb*i]);
		//cout<<dp[aa*i][bb*i]<<endl;
	}
	if(ans == INF) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}

G题

这题我最初的想法是暴力枚举，对于每个位置，不是羊就是狼，直接枚举 01 串即可，但是复杂度 \(O(2^n)\) 会超时，但是我们可以发现一个神奇的性质，如果只要最开始的两只动物确定的情况下，我们就可以依次算出剩下的动物了，所以我们枚举最开始的两只动物，SS，SW，WS，WW，再计算出剩下位置的动物，最后我们判断一下首尾相接的环，是否会自相矛盾即可，如果出现了合法情况就直接输出，如果四种情况都没有合法情况，就输出 -1。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;

int n; char s[N];

bool flag = false;
char ans[N];

bool pd(){
	bool fflag = true;
	if(s[0] == 'o' && ans[0] == 'S'){
		if(ans[1] != ans[n-1]) fflag = false;
	}
	if(s[0] == 'x' && ans[0] == 'S'){
		if(ans[1] == ans[n-1]) fflag = false;
	}
	if(s[0] == 'o' && ans[0] == 'W'){
		if(ans[1] == ans[n-1]) fflag = false;
	}
	if(s[0] == 'x' && ans[0] == 'W'){
		if(ans[1] != ans[n-1]) fflag = false;
	}
	//
	if(s[n-1] == 'o' && ans[n-1] == 'S'){
		if(ans[0] != ans[n-2]) fflag = false;
	}
	if(s[n-1] == 'x' && ans[n-1] == 'S'){
		if(ans[0] == ans[n-2]) fflag = false;
	}
	if(s[n-1] == 'o' && ans[n-1] == 'W'){
		if(ans[0] == ans[n-2]) fflag = false;
	}
	if(s[n-1] == 'x' && ans[n-1] == 'W'){
		if(ans[0] != ans[n-2]) fflag = false;
	}
	return fflag;
}

void mj(){
	for(int i = 1;i<n-1;i++){
		//for(int j = 0;j<n;j++) cout<<ans[j];
		if(ans[i] == 'S'){
			if(s[i] == 'o') ans[i+1] = ans[i-1];
			else {
				if(ans[i-1] == 'S') ans[i+1] = 'W';
				else ans[i+1] = 'S';
			}
		} else {
			if(s[i] == 'x') ans[i+1] = ans[i-1];
			else {
				if(ans[i-1] == 'S') ans[i+1] = 'W';
				else ans[i+1] = 'S';
			}
		}
	}
}

void SS(){
	if(flag) return;
	ans[0] = 'S'; ans[1] = 'S';
	mj();
	if(pd()){
		flag = true;
		for(int i = 0;i<n;i++) cout<<ans[i];
	}
}

void SW(){
	if(flag) return;
	ans[0] = 'S'; ans[1] = 'W';
	mj();
	if(pd()){
		flag = true;
		for(int i = 0;i<n;i++) cout<<ans[i];
	}
}

void WS(){
	if(flag) return;
	ans[0] = 'W'; ans[1] = 'S';
	mj();
	if(pd()){
		flag = true;
		for(int i = 0;i<n;i++) cout<<ans[i];
	}
}

void WW(){
	if(flag) return;
	ans[0] = 'W'; ans[1] = 'W';
	mj();
	if(pd()){
		flag = true;
		for(int i = 0;i<n;i++) cout<<ans[i];
	}
}

int main(){
	cin>>n;
	cin>>s;
	SS();
	SW();
	WS();
	WW();
	if(!flag) cout<<-1<<endl;
	return 0;
}