国赛专题训练

国赛专题训练

1.暴力-for

owo:

• 思路：暴力的时候，因为采用的random_shuffle来打乱再计数，那么for的次数越多越好，所以不必考虑最大的1e6,考虑5000即可，然后增加for的次数到5e3，这样通过的样例会更多。
• 字符串处理：random_shufle(begin, end), 可以打乱数组顺序。str.find(“owo”)返回找到第一个owo的位置， str.find(“owo”, p+1)返回从p+1开始找的第一个owo的位置。
• 代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e6+10;
int n;
int ans;
string str[N]; 
signed main()
{
	cin>>n;
	for(int i = 0; i < n; i++){
		cin>>str[i];
		for(int cnt = 1; cnt <= 5e3; cnt++){
			int count = 0;
			random_shuffle(str, str+1+i);
			string t = "";
			for(int j = 0; j <= i; j++) t = t + str[j];
			int p = t.find("owo");
			while(p != -1){
				count++;
				p = t.find("owo", p+1);
			}
			ans = max(ans, count);
		}
		cout<<ans<<endl;
	}
	
	return 0;
}

子串：

• 思路：使用hash，即map来存储所有的子串出现的次数，再对所有的map进行一个计数
• 字符串处理：取子串t = s.substr(begin, len)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
string s; 
unordered_map<string, int> mp;
int res[N];
int main()
{
	cin>>s;
	int n = s.size();
	for(int len = 1; len <= n; len++){
		for(int i = 0; i + len -1 < n; i++){
			string t = s.substr(i, len);
			mp[t]++;
		} 
	}
	for(auto i:mp){
		int cnt = i.second;
		res[cnt]++;
	}
	for(int i = 1; i <= n; i++){
		cout<<res[i]<<endl;
	}
	return 0;
}

2暴力：dfs

买瓜：

• 思路：首先是劈瓜涉及到/2，那么就对所有数*2来避免浮点数的问题。其次，对于每个瓜有三种可能，再加上排序剪枝优化。竟然可以过70%的数据，而且这次写的也比较顺利，思路清晰，很棒！
• 代码：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 35;
int n, m;
int a[N];
int ans = N;
void dfs(int u, int sum, int cnt){
	if(sum == m){
		ans = min(ans, cnt);
		return;
	}
	if(u == n+1) return;
	if(sum > m) return;
	dfs(u + 1, sum, cnt);
	if(sum + a[u]/2 <= m) dfs(u+1, sum+a[u]/2, cnt + 1);
	if(sum + a[u] <= m) dfs(u+1, sum + a[u], cnt);
	return;
}
signed main()
{
	cin>>n>>m;
	m = m*2;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		a[i] = a[i]*2;
	}
	sort(a+1, a+1+n);
	dfs(1, 0, 0);
	if(ans != N) cout<<ans<<endl;
	else cout<<"-1"<<endl;
	
	return 0;
}

01游戏：

• 主要采取dfs的方式，对于没填数的每个位子有两种可能，0或1，那么就分别进行dfs，记得恢复现场。当位置到达n+1,1时，根据3条要求进行判断，如果通过，flag= 1,之后的dfs都直接return。再加上fr,fc的剪枝。
• s(i)(j)!=’_’的return少些了，不能再往下走了，另外就是刚开始计数还要考虑下划线，所以if要说清楚。两个漏洞没能通过debug找出来，还是要更加仔细一点。
• 代码：

#include<bits/stdc++.h>
using namespace std;
int n; 
string s[15];
int fc[15][2], fr[15][2];
bool chk(int x, int y){
	if(x > 2&&s[x-1][y]==s[x][y]&&s[x-2][y]==s[x][y]) return false;
	if(y > 2&&s[x][y-1]==s[x][y]&&s[x][y-2]==s[x][y]) return false;
	return true;
}
int flag = 0;
int A[1050], B[1050];
void dfs(int x, int y){
	if(flag) return;
	if(x == n+1 && y == 1){
		int res = 1; 
		for(int i = 1; i <= n; i++){
			if(fr[i][0]!=n/2 || fr[i][1]!=n/2) res = 0;
			if(fc[i][0]!=n/2 || fc[i][1]!=n/2) res = 0;
		}
		if(res == 0) return;
		memset(A, 0, sizeof(A));
		for(int i = 1; i <= n; i++){
			int tmp = 0;
			for(int j = 1; j <= n; j++){
				tmp = tmp * 2 + s[i][j]-'0';
			}
			if(A[tmp]!=0) res = 0;
			A[tmp]++;
		}
		memset(B, 0, sizeof(B));
		for(int i = 1; i <= n; i++){
			int tmp = 0;
			for(int j = 1; j <= n; j++){
				tmp = tmp * 2 + s[j][i]-'0';
			}
			if(B[tmp]!=0) res = 0;
			B[tmp]++;
		}
		if(res == 0) return;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(i + 2 <= n){
					if(s[i][j] == s[i+1][j]&&s[i][j] == s[i+2][j]) res = 0;
				}
				if(j + 2 <= n){
					if(s[i][j] == s[i][j+1]&&s[i][j] == s[i][j+2]) res = 0;
				}
			}
		}
		if(res == 1){
			flag = 1;
			for(int i = 1; i <=n; i++){
				for(int j = 1; j <= n; j++){
					cout<<s[i][j];
				}
				cout<<endl;
			}
		}
		return;
	}
	int nx = x, ny = y + 1;
	if(ny == n+1){
		nx = x + 1;
		ny = 1;
	}

	if(s[x][y] != '_'){
		dfs(nx, ny);
		return;
	}
	
	s[x][y] = '0';
	fr[x][0]++;
	fc[y][0]++;
	if(fr[x][0]<=n/2&&fc[y][0]<=n/2&&chk(x, y)) dfs(nx, ny);
	fr[x][0]--;
	fc[y][0]--;
	
	s[x][y] = '1';
	fr[x][1]++;
	fc[y][1]++;
	if(fr[x][1]<=n/2&&fc[y][1]<=n/2&&chk(x, y)) dfs(nx, ny);
	fr[x][1]--;
	fc[y][1]--;
	s[x][y] = '_';
	return;
}
int main()
{
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>s[i];
		s[i] = ' '+ s[i];
		for(int j = 1; j <= n; j++){
			if(s[i][j] == '0'){
				fr[i][0]++;
				fc[j][0]++;
			}else if(s[i][j] == '1'){
				fr[i][1]++;
				fc[j][1]++;
			}
		}
	}
	dfs(1, 1);
	return 0;
}