U37406.2024年 - 年赛 - 题解

编者：I love c++☺
注：题解中的 $freopen$ 为制作测试点时所用，正常答题时不用。

T1 - 签到题 原题链接

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

int main() {
    
    //freopen("qd000.in", "r", stdin);
	//freopen("qd000.out", "w", stdout);
	 
    cout << "Byebye 2024!";
    
    //fclose(stdin);
    //fclose(stdout);
    
    return 0;
}

T2 - 阿克曼（Ackermann）函数 原题链接

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

int m, n;

int akm(int m, int n) {
	if (m == 0) return n + 1;
	else if (m > 0 && n == 0) return akm(m - 1, 1);
	else return akm(m - 1, akm(m, n - 1));
}

int main() {
    
    //freopen("akm000.in", "r", stdin);
	//freopen("akm000.out", "w", stdout);
	 
    cin >> m >> n;
    cout << akm(m, n);
    
    //fclose(stdin);
    //fclose(stdout);
    
    return 0;
}

T3 - 找第一个只出现一次的字符 原题链接

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

string s;
int a[30];

int main() {
	
	//freopen("letter000.in", "r", stdin);
	//freopen("letter000.out", "w", stdout);
	 
	cin >> s;
	for (int i = 0; i < s.size(); i ++) {
		a[s[i] - 'a'] ++;
	}
	for (int i = 0; i < s.size(); i ++) {
		if (a[s[i] - 'a'] == 1) {
			cout << s[i];
        	return 0;
        }
	}
	cout << "no";

	//fclose(stdin); 
	//fclose(stdout);
	
	return 0;
} 

T4 - 计算阶乘 原题链接

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

long long t, n;

int main() {
	
	//freopen("jie000.in", "r", stdin);
	//freopen("jie000.out", "w", stdout);
	
	cin >> t;
	while (t--) {
		unsigned long long ans = 2;
		cin >> n;
		for (int i = n - 1; i > 0; i -= 2) {
			ans *= i;
		}
		cout << ans << endl;
	}
	
	//fclose(stdin);
	//fclose(stdout);
	
	return 0;
}

T5 - 点亮灯笼 原题链接

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

int n, m;
int a[1010];
 
int main() {
	
//	freopen("dian000.in", "r", stdin);
//	freopen("dian000.out", "w", stdout);

	cin >> n >> m;
	while(m--) {
		int x; 
		scanf("%d", &x);
		if(x == 1) a[1] = 1 - a[1], a[2] = 1 - a[2], a[n] = 1 - a[n];
		else if(x == n) a[n] = 1 - a[n], a[n - 1] = 1 - a[n - 1], a[1] = 1 - a[1];
		else a[x] = 1 - a[x], a[x + 1] = 1 - a[x + 1], a[x - 1] = 1 - a[x - 1];
	}
	for (int i = 1; i <= n; i ++) {
		cout << a[i] << " ";
	}
	
//	fclose(stdin);
//	fclose(stdout);

	return 0; 
}

T6 - 最大公约数和最小公倍数问题 原题链接

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

typedef long long ll;
int m, n, ans, flag;
ll gcd(ll x, ll y) {
    if (y == 0) {return x;}
    return gcd(y, x % y);
}

int main() {
	
//	freopen("daxiao000.in", "r", stdin);
//	freopen("daxiao000.out", "w", stdout); 
    
	cin >> n >> m;
    for (int i = 1; i <= sqrt(1ll * m * n); i ++) {
        if ((1ll * n * m) % i == 0 && gcd(i, (1ll * n * m) / i) == n) {
            ans ++;
            if (1ll * i * i == 1ll * n * m)  flag = 1;
        }
    }
    cout << ans * 2 - flag;
    
//    fclose(stdin);
//    fclose(stdout);
    
    return 0;
}

T7 - faebdc玩扑克 原题链接

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

queue<int> a;
int sc[1000005], ans[1000005];
int n;

int main() {
	
//	freopen("faebdc000.in", "r", stdin);
//	freopen("faebdc000.out", "w", stdout);
	
    cin >> n;
    for (int i = 1; i <= n; i ++) a.push(i);
	for (int i = 1; !a.empty(); i ++) {
        a.push(a.front());
        a.pop();
        sc[i] = a.front();
        a.pop();
    }
    for (int i = 1; i <= n; i ++) ans[sc[i]] = i;
    for (int i = 1; i <= n; i ++) cout << ans[i] << " ";
    
//    fclose(stdin);
//    fclose(stdout);
    
    return 0;
}

T8 - 素数个数 原题链接

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

int N, sum, n;
bool a[100000000];

int main() {
	
	//freopen("su000.in", "r", stdin);
	//freopen("su000.out", "w", stdout);
	
    cin >> N;
	if (N < 2) {
		cout << "0";
		return 0;
	}
	sum = N;
	sum -= N / 2 - 1;
	a[1] = true;
	for (register int i = 3; i <= sqrt(N); i += 2) {
    	if (a[i]==false) {
    		for (register int j = i * 2; j <= N; j += i) {
    			if (a[j] == false && j % 2 != 0) {
    				sum --;
    			}
    			a[j] = true;
    		}
		}
	}
	cout << sum - 1;
	
	//fclose(stdin);
	//fclose(stdout);
	
	return 0;
}

T9 - 偶数 原题链接

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

long long n, i, f[200], j, t, s;
long long p = 1000003, l, k, pp;
long long aa(long long n) {
    long long i = 2LL, j = 1LL, q;
    if (n <= 2) return 0;
    while (i * 2 <= n) {i = i * 2; j ++;}
    return (2 * aa(n - i) % p + f[j + 1] - 2 * f[j] % p - ((i * 2 - n) % p) * ((i * 2 - n - 1) % p) * l + p * p * p) % p;
}

int main() {
	
	//freopen("ou000.in", "r", stdin);
	//freopen("ou000.out", "w", stdout);
	
    cin >> n;
	f[1] = 0;
	i = 2;
	j = 1;
    k = 2;
	l = 1;
	pp = p - 2;
    while (pp > 0) {
          if (pp % 2 == 1) l = l * k % p;
          k = k * k % p;
		  pp = pp / 2;
    }   
    while (i <= n) {
          j ++;
		  s = i % p;
		  t = s * (s - 1) % p;
          f[j] = ((f[j - 1] * 3 % p) + ((i % p) * ((i - 1) % p) % p) * l) % p;
          i = i * 2;
    }
    cout << aa(n);
    //system("pause");
    
    //fclose(stdin);
    //fclose(stdout);
    
    return 0;
}

T10 - 算24点 原题链接

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

int a[5];
char opt[5]= {' ', '+', '-', '*', '/'};

int F(int x,int k, int y) {
  if (k == 1)
    return x + y;
  if (k == 2)
    return max(x, y) - min(x, y);
  if (k == 3)
    return x * y;
  return (y == 0 || x < y || x % y != 0) ? -999999 : x / y;
}

void Out(int a, int b, int c, int d, int e, int f, int k1, int k2, int k3) {
  printf("%d%c%d=%d\n", max(a, b), opt[k1], min(a, b), F(max(a, b), k1, min(a, b)));
  printf("%d%c%d=%d\n", max(c, d), opt[k2], min(c, d), F(max(c, d), k2, min(c, d)));
  printf("%d%c%d=%d\n", max(e, f), opt[k3], min(e, f), F(max(e, f), k3, min(e, f)));
  exit(0);                                                  //直接退出程序
}

int main() {
	
	//freopen("suan000.in", "r", stdin);
	//freopen("suan000.out", "w", stdout);
	
	scanf("%d%d%d%d", &a[1], &a[2], &a[3], &a[4]);
	sort(a + 1, a + 5);                                            //保证遍历所有情况
	do {
	  for (int i = 1; i <= 4; i ++)                            //暴力枚举3个运算符
	    for (int j = 1; j <= 4; j ++)
	      for (int k = 1; k <= 4; k ++)
	        if (F(F(F(a[1], i, a[2]), j, a[3]), k, a[4]) == 24)       //((a?b)?c)?d
	          Out(a[1], a[2], F(a[1], i, a[2]), a[3], F(F(a[1], i, a[2]), j, a[3]), a[4], i, j, k);
	        else if (F(F(a[1], i, a[2]), k, F(a[3], j, a[4])) == 24)//(a?b)?(c?d)
	          Out(a[1], a[2], a[3], a[4], F(a[1], i, a[2]), F(a[3], j, a[4]), i, j, k);
	}  while (next_permutation(a + 1, a + 5));
	puts("No answer!");
	 
	//fclose(stdin);
	//fclose(stdout);
	
	return 0;
}