Solutions to Three Questions A, B and C in the First Spring Selection Competition of 2019

Summary: "The elder personally worked out five questions, I personally performed how to sign the questions of blood and liver."
Food is the original sin.
Competition Links: 2009 Spring SMUACM Provincial Competition Reserve Player Selection Competition - First
A:

Topic: Give X, Z, find the smallest integer Y so that LCM (X, Y) = Z.
Idea: Find out the GCD of X and z, and then base on this gcd, every time + = gcd, until the current answer and the minimum common multiple of X equals Z, the output of - 1 is only one case that X is not a factor of Z.
Reflections: A very simple question, but because no LL has been WA, vomiting, after the end of the LL immediately changed AC.
AC Code:

#include<cstdio>

long long gcd(long long x, long long y){
	if(y == 0) return x;
	while(1){
		long long pos = x;
		if(y == 0) return x;
		x = y;
		y = pos % x;
	}
}
long long lcm(long long x, long long y){
	return x * y / gcd(x, y);
}

int main(){
	long long x, z, m;
	scanf("%lld", &m);
	while(m--){
		scanf("%lld %lld", &x, &z);
		if(z % x != 0) {
			printf("-1\n");
			continue;
		}
		long long pos = gcd(x, z);
		long long y = (z / pos) / (x / pos);
		for(long long i = y; i <= z; i += y) {
			if(lcm(i, x) == z){
				printf("%lld\n", i);
				break;
			}
		}
	}
	return 0;
}

B:

Topic: Fig.
Idea: If it's hard, you just need to push back step by step to see if you can restore the Sketchpad to its original shape (without B or W). Traversing through each point, if there is only one color in the k*k square where the current point is located, it can be transformed into colorless (expressed in'?').
Reflections: thinking is not broad enough, strong twisting melon is not sweet, strong questions will be wrong.
AC Code:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

char a[25][25];
bool flag;
int k, m, n;

void solve(int x, int y){
	int cntw = 0, cntb = 0;
	for(int i = x; i <= x + k - 1; i++){
		for(int j = y; j <= y + k - 1; j++){
			if(a[i][j] == 'B' || a[i][j] == '?'){
				cntb++;
			}
			if(a[i][j] == 'W' || a[i][j] == '?'){
				cntw++;
			}
		}
	}
	if(cntb == k * k || cntw == k * k) {
		for(int i = x; i <= x + k - 1; i++){
			for(int j = y; j <= y + k - 1; j++){
				a[i][j] = '?';
			}
		}
	}
}

int main(){
	scanf("%d %d %d", &k, &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%s", a[i] + 1);
	}
	for(int time = 1; time <= 100; time++){//It doesn't need to be so much, but since time complexity permits, it's just a few more times.
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				solve(i, j);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] != '?') flag = 1;
		}
	}
	if(flag) printf("NO\n");
	else printf("YES\n");
	return 0;
}

C:


Implication: Give X a multiple of X composed of 01.
Thought: Because the data will certainly be large, will explode LL, so the current answer has to be stored in strings, and to determine whether X can be divided, it is necessary to find the remainder of X, and record the remainder, if the remainder appears again, it does not need to be judged. If the result of the remainder of the current number pair X does not appear, the current number is added to the queue until the remainder is 0. Because it is a string of 01, it is actually multiplied by 10 or 10 + 1 of the previous number, and the remainder of the new number is equal to the remainder of the previous number multiplied by 10 or 10 + 1. All you need to do is use the structure to store the 01 string and the remainder of the string to X.
Algorithms: BFS, each time after the current string plus 0 or 1, to determine the remainder, according to the remainder of the choice to join the queue or not join the queue or output the answer.
Reflection: There was a slight mistake when filling up the question. The string in the structure was opened to 1e5, which led to MLE. In fact, it did not need 1E5, or even 100.

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
using namespace std;

int x;
struct NODE{
	char s[100];
	int ans;
};
queue<NODE> q;
bool mp[(int)1e6 + 5];

void bfs(){
	NODE flag;
	flag.s[1] = '1';
	flag.s[2] = '\0';
	flag.ans = 1 % x;
	q.push(flag);
	while(!q.empty()){
		NODE now = q.front();
		q.pop();
		mp[now.ans] = 1;
		int len = strlen(now.s + 1);
		NODE nex;
		/*0*/nex.s[len + 1] = '0';
			 nex.s[len + 2] = '\0';
			 for(int i = 1; i <= len; i++) nex.s[i] = now.s[i];
			 nex.ans = now.ans * 10 % x;
			 if(nex.ans == 0){
				 printf("%s\n", nex.s + 1);
				 return;
			 }
			 if(!mp[nex.ans]) q.push(nex);
		/*1*/nex.s[len + 1] = '1';
			 nex.s[len + 2] = '\0';
			 for(int i = 1; i <= len; i++) nex.s[i] = now.s[i];
			 nex.ans = (now.ans * 10 + 1) % x;
			 if(nex.ans == 0){
				 printf("%s\n", nex.s + 1);
				 return;
			 }
			 if(!mp[nex.ans]) q.push(nex);
	}
}

int main(){
	scanf("%d", &x);
	bfs();
	return 0;
}

The remaining two questions are a little unclear, but they are not filled for the time being. If you think of them later, you will come back to fill the pit qwq.

Keywords: Spring

Added by Orkan on Wed, 15 May 2019 06:33:28 +0300