思路:
正向考虑容易漏情况,比如最后只剩下NEU三个字母,那是不是就也要把这三个字母都删掉,所以我们反向考虑,只考虑NEUQ四个字母都出现的情况,最后就总长度减去计算的长度就是答案
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 55; const double PI = acos(-1); int a[N]; int main() { IOS; string str = "NEUQ"; int n; string s; cin >> n >> s; int res = 0, pos = 0;//上一个字母的位置 for (int i = 0, j = 0; i < s.size(); i ++ ) { if(s[i] == str[j]) { if(j == 0) { pos = 0; j ++ ; } else if(j == 1) { pos = 1; j ++ ; } else if(j == 2) { pos = 2; j ++ ; } else { res += 4; j = 0; } } } cout << n - res << endl; return 0; }
思路:
推公式:n = ab + a + b, 那么n + 1 = ab + a + b + 1 = (a + 1) * (b + 1),从这个式子可以看出,n+1必定不是质数,所以我们特判前几个数,然后再判断n+1是不是质数就可以了
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false);cin.tie(0); using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 55; const double PI = acos(-1); int a[N]; bool prime(LL n) { if(n < 2) return false; for (int i = 2; i <= n / i; i ++ ) if(n % i == 0) return false; return true; } int main() { IOS; LL n; cin >> n; bool flag = true; if(n == 1 || n == 2 || n == 4) flag = false; else if(prime(n + 1)) flag = false; if(flag) cout << "Yes" << endl; else cout << "No" << endl; return 0; }