2021藍橋杯國賽B組C/C++個人記錄

以下為個人場上所提交答案，歡迎大家指出錯誤，后續會更正正確題解，

個人提交：25

說明： Mbps是M bit per second, MB是 M Byte，bit是位元，Byte是位元組，1Byte=8bit， 200/8=25

個人提交：21844 (有誤)
改正：1903

說明：只有每個位都為1、3、5、7之一才是題目所說的純質數，還有一個條件當時沒注意到，這個數本身也要是素數，應該先用埃氏篩法，

代碼：

#include<cstdio>
#include<cstring>

const int MAX_N = 20210605;
int num[MAX_N + 1];
int sum = 0;

void solve(int x) {
	int isPrime = 1;
	while(x > 0) {
		int b = x%10; //b為x的個位數字
		if(!(b == 2 || b == 3 || b == 5 || b == 7)) {
			isPrime = 0;
			break;
		}
		x = x/10;
	}
	if(isPrime) sum++;
}

int main() {
	memset(num, 1, sizeof(num));
	for(int i = 2; i < 20210605; i++) {
		for(int j = 2; i*j <= 20210605; j++) {
			num[i*j] = 0;
		}
	}
	for(int i = 1; i <= 20210605; i++) {
		if(num[i]) solve(i);
	}
	printf("%d\n", sum);
	return 0;
}

個人提交：977

說明：現場寫日期類太麻煩，直接用excel搞資料，然后用c處理

先在excel中敲入這兩格內容，第三格做個差，看看一共有多少天


得7699，從A1格往下拉7669行，得到從2001/1/1到2021/12/31的每一天
為了方便處理資料，把剛才不用的刪掉，并且把表格另存為.csv檔案

資料有了，直接全選復制，接下來用c/c++處理

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

int res = 0;

void solve(int x) {
	for(int i = 0; i < 100; i++) {
		if(i * i == x) res++;
	}
}

int main() {
	string line;
	while(getline(cin, line)) {
		int len = line.length();
		int sum = 0;
		for(int i = 0; i < len; i++) {
			if(isdigit(line[i])) sum += line[i] - '0';
		}
		solve(sum);
		cout << res << endl;
	}
}

得出結果977





個人提交：2667336761

說明：不會dp，賭了一把完全二叉樹

#include<iostream>
using namespace std;

const int MAX_N = 2021; //結點個數,用完全二叉樹的編號代表結點 

long long C(long long x) {
	if(x > MAX_N) return 0;
	return 1 + C(2*x) + C(2*x+1);
}

long long W(long long x) {
	if(x > MAX_N) return 0;
	return 1 + 2*W(2*x) + 3*W(2*x+1) + C(2*x)*C(2*x)*C(2*x+1);
}

int main() {
	cout << W(1) << endl;
	return 0;
}

代碼：

#include<cstdio>
#include<cstring>
#include<ctype.h>

char s[110];

int main() {
	scanf("%s", s);
	for(int i = 0; i < strlen(s); i++)
		printf("%c", toupper(s[i]));
	return 0;
}

常規寫法，過40%用例，評論區大佬說二分法，我在考場想到利用等引數列前n項和并根據R-L的值取分段函式，但是沒來得及改，后期補上

#include<cstdio>

const int MAX_N = 200000000;
int a[MAX_N], sum = 0;

void solve() {
	int maxn = 1, n = 1;
	for(int i = 1; i < MAX_N; i++) {
		a[i] = n++;
		if(n > maxn) {
			maxn++;
			n=1;
		}
	}
}

int main() {
	solve();
	int T;
	scanf("%d", &T);
	for(int i = 0; i < T; i++) {
		int l, r;
		sum = 0;
		scanf("%d%d", &l, &r);
		for(int i = 0; l+i <= r; i++) {
			sum += a[l+i];
		}
		printf("%d\n", sum);
	}
	return 0;
}

沒找到規律，硬寫，過40%用例
評論區大佬說找回圈節，后期補上

#include<cstdio>
#include<cstring>

const int MAX_N = 200000000;
char s[MAX_N];
char s2[MAX_N];
int n, t;

void reverse() {
	s2[0] = s[0];
	for(int i = 1; i < n; i++) {
		s2[i] = (s[i] - '0') ^ (s[i-1] - '0') + '0';
	}
	strncpy(s, s2, n);
}

int main() {
	scanf("%d%d", &n, &t);
	scanf("%s", s);
	for(int i = 0; i < t; i++) reverse();
	printf("%s", s);
	return 0;
}

不會dp，硬寫過30%用例

#include<cstdio>
using namespace std;

int N, K, res = 0;

void solve(int x) {
	int sum = 0;
	while(x > 0) {
		if(x % 2 == 1) sum++;
		x = x/2;
	}
	if(sum == K) res++;
}

int main() {
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; i++) solve(i);
	printf("%d\n", res);
	return 0;
}

簡單的括號匹配（堆疊），不知道能過多少用例
評論區說線段樹，后期補上

#include<cstdio>
#include<stack>
using namespace std;

const int MAX_N = 1000000+10;
int n, m, L, R;;
char s[MAX_N];

void rev() {
	for(int i = 0; L+i <= R; i++) {
		if(s[L+i] == '(') s[L+i] = ')';
		else s[L+i] = '(';
	}
}

int isLawful(int R) {
	stack<int> s1;
	for(int i = 0; L+i <= R; i++) {
		int ch = s[L+i];
		if(ch == '(') s1.push(ch);
		else if(!s1.empty() && ch==')' && s1.top() == '(') {
			s1.pop();
		} else {
			s1.push(ch);
		}
	}
	if(s1.empty()) return 1;
	else return 0;
}

void solve() {
	for(int i = n; i > L; i--) {
		if(isLawful(i))  {
			printf("%d\n", i);
			return;
		}
	}
	printf("%d\n", 0);
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", s+1); // 使索引和L、R一致 
	for(int i = 0; i < m; i++) {
		int k = 0;
		scanf("%d", &k);
		if(k == 1) {
			scanf("%d%d", &L, &R);
			rev();
		} else {
			scanf("%d", &L);
			solve();
		}
	}
	return 0;
}

硬寫，勉強過10%用例吧

考場上理解錯了耗了一個多小時，還弄了個結構體，放到set里去重，然后運算子多載，最后發現根本不用，哈哈哈，以后還是應該先寫個大概，看看樣例輸入輸出，再往下做，

對了，異或運算子 ^ 優先級較低，記得加括號

#include<cstdio>
#include<algorithm>
using namespace std;

int T, n, res = 0;

void solve() {
	for(int a = 1; a <= n; a++) {
		for(int b = 1; b <= n; b++) {
			for(int c = 1; c <= min(n, a+b-1); c++) {
				if(a+b<=c || a+c<=b || b+c<=a) continue;
				if((a^b^c) == 0) res++;
			}
		}
	}
}

int main() {
	scanf("%d", &T);
	for(int i = 0; i < T; i++) {
		scanf("%d", &n);
		solve();
		printf("%d\n", res);
	}
	return 0;
}

先寫到這，我要去準備期末考試了~
考完繼續更正

出了，菜雞國三，明年再戰~