NOI Online2022 入门组题解

2022-03-26，CCF官方举行了NOI Online能力测试，因为我是个蒟蒻，才考了235分 ，最后一题也是看了题解才写出来
题目：
T1王国比赛
T2数学游戏
T3字符串
题解可以看 这个
就给大家展示一下我的满分代码吧

T1

#include
#define FO(x)\
freopen(#x".in","r",stdin);\
freopen(#x".out","w",stdout);
using namespace std;
int k[1100][1100];
bool s[1100],ss[1100];
int main(){
	ios::sync_with_stdio(false);
	FO(kingdom);
	int n,m,ans = 0;
	cin >> n >> m;
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			cin >> k[i][j];
	for(int i=1;i<=n;i++){
		int x = 0,y = 0;
		for(int j=1;j<=m;j++){
			if(k[j][i] == 1) x++;
			else y++;
		}
		s[i] = x>y;
	}
	for(int i=1;i<=n;i++)
		cin >> ss[i];
	for(int i=1;i<=n;i++)
		if(s[i] == ss[i])
			ans++;
	cout << ans;
	return 0;
}

T2

#include
#define FO(x)\
freopen(#x".in","r",stdin);\
freopen(#x".out","w",stdout);
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
	if(b != 0) return gcd(b,a%b);
	return a;
}
long long read(){
	long long f=1,r=0;
	char ch;
	do ch=getchar(); while(!isdigit(ch) && ch!='-');
	if(ch=='-') f=-1,ch=getchar();
	do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));
	return r*f;
}
void write(long long X) {
	if(X < 0) putchar('-'),X=-X;
    if(X>9) write(X/10); 
    putchar(X%10+'0'); 
}
int main(){
	FO(math19);
	//ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		ll x = read(),z = read();
		ll y = gcd(x*x,z/x);
		ll g = sqrt(y);
		if(g*g != y || z%x != 0) puts("-1");
		else{
			write(z/x/g);
			puts("");
		}
	}
	return 0;
}

T3 35分暴力解法

#include
#define FO(x)\
freopen(#x".in","r",stdin);\
freopen(#x".out","w",stdout);
using namespace std;
const int mod = 1e9+7;
int n,m,ans;
string s,t;
void dfs(int a,string r){
	if(a == n){
		if(r == t)
			ans++;
		return;
	}
	if(s[a] == '-'){
		dfs(a+1,r.substr(1,r.size()-1));
		dfs(a+1,r.substr(0,r.size()-1));
	}
	else dfs(a+1,r+s[a]);
}
int main(){
	//FO(string);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		cin >> n >> m;
		cin >> s >> t;
		ans = 0;
		dfs(0,"");
		cout << ans <<"\n";
	}
	return 0;
}

满分算法-----dp

这个方法是依照洛谷的题解写的，前两题是考场上写的，码风有点丑，请见谅

#include
#define FO(x)\
freopen(#x".in","r",stdin);\
freopen(#x".out","w",stdout);
using namespace std;
const int mod = 1e9+7;
const int MAX = 410;
int n,m,ans;
char a[MAX],b[MAX];
int c[MAX];
int f[MAX][MAX][MAX];
int main(){
	FO(string);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		cin >> n >> m;
		memset(f,0,sizeof(f));
		cin >> (a+1) >> (b+1);
		int sum = 0;
		for(int i=1;i<=n;i++)
			if(a[i] == '-')
				sum++;
		if(sum != (n-m)>>1){
			puts("0"); continue;
		}
		int len = 0;
		f[0][0][0] = 1;
		for(int i=1;i<=n;i++){
			if(a[i] == '-') len--;
			else len++;
			for(int j=0;j<=sum;j++)
				for(int k=0;k<=sum;k++){
					if(a[i] == '-')
						f[i][j][k] = (f[i-1][j+1][k]+f[i-1][j][k+1])%mod;
					else{
						if(k) f[i][j][k] = f[i-1][j][k-1];
						else if(a[i] == b[len-j]) f[i][j][k] = f[i-1][j][k];
						if(len == j) f[i][j][k] = (f[i][j][k]+f[i-1][j-1][k])%mod;
					}
				}
		}
		cout << f[n][0][0] << "\n";	
	}
	return 0;
}

好了，这就是三题代码，如有疑问，欢迎在评论区提出