李老师求救

ykj12 2024-07-24 19:42:14 2024-07-24 20:03:41 15

洛谷 P5440 【XR-2】奇迹

为什么60分,我搞了一个多小时

#include <bits/stdc++.h>

using namespace std;

int day_run [] =  {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int day_ping [] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ans = 0;
const int N = 10;
int a[N], vis[N];

bool p () {
	const int d = a[1] * 1000 + a[2] * 100 + a[3] * 10 + a[4];
	if (d == 0) return false;
	if ((d % 4 == 0 and d % 100 != 0) or (d % 400 == 0)) {
		if ((a[5] * 10 + a[6]) <= 12 and (a[5] * 10 + a[6]) > 0 and (a[7] * 10 + a[8]) <= day_run[(a[5] * 10 + a[6])]) return true;
	}
	else {
		if ((a[5] * 10 + a[6]) <= 12 and (a[5] * 10 + a[6]) > 0 and (a[7] * 10 + a[8]) <= day_ping[(a[5] * 10 + a[6])]) return true;
	}
	return false;
}

bool ss (int x) {
	for (int i = 2; i <= x / i; i++) {
		if (x % i == 0) return false;
	}
	if (x < 2) return false;
	else return true;
}

bool f () {
	int n = a[1] * 10000000 + a[2] * 1000000 + a[3] * 100000 + a[4] * 10000 + a[5] * 1000 + a[6] * 100 + a[7] * 10 + a[8];
	int m = a[5] * 1000 + a[6] * 100 + a[7] * 10 + a[8];
	int p = a[7] * 10 + a[8];
	if (ss (n) and ss (m) and ss (p)) return true;
	else return false; 
} 

void dfs (int k, int u) {
	if (a[1] == a[2] and a[2] == a[3] and a[3] == a[4] and a[4] == 0) return;
	else if (a[5] * 10 + a[6] == 0) return;
	else if (a[7] * 10 + a[8] == 0) return;
	if (u == k + 1) {
		if (p ()) {
			if (f ()) ++ ans; 	
		}
		return;
	}
	for (int i = 0; i <= 9; i++) {
		a[vis[u]] = i;
		dfs (k, u + 1);
	}
} 

int main () {
	int t;
	cin >> t;
	while (t--) {
		int k = 0;
		string x;
		cin >> x;
		for (int i = 0; i < 8; i++) {
			if (x[i] != '-') a[i + 1] = int (x[i]) - '0';
			else if (x[i] == '-') {
				a[i + 1] = 10;
				vis[++k] = i + 1;
			}
		}
		if (k == 0) {
			//cout << (p ()) << endl;
			if (f ()) cout << 1 << endl;
			else cout << 0 << endl; 
		}
		else {
			dfs (k, 1);
			cout << ans << endl;
			ans = 0;
		}
	}
	return 0;
}
{{ vote && vote.total.up }}