洛谷P1125[NOIP2008 提高组]
刚开始学，想不明白哪里错了，求解答
//P1125
#include<iostream>
#include<cstring>
using namespace std;
char a[200];
int b = strlen(a);
int sum[26] = {};
int isPrime(int n) {//判断素数
int isP =1;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
isP = 0;
break;
}
//else
// isP = 1;
}
if (n == 1||n==0)
isP = 0;
return isP;
}
int maxn(const char a[200]) {//判断出现次数最多的字母
int max=0;
for (int i = 0; i < b; i++) {
sum[a[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (sum[i] > max)
max = sum[i];
}
return max;
}
int minn(const char a[200]) {//判断出现次数最少的字母
int min=110;
for (int i = 0; i < b; i++) {
sum[a[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (sum[i] < min&&sum[i]>0)
min = sum[i];
}
return min;
}
int main() {
cin >> a;
int b = maxn(a) - minn(a);
//cout << b;
if (isPrime(b) == 1)
cout << "Lucky Word" << endl << b;
else if (isPrime(b) == 0)
cout << "No Answer" << endl << "0";
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
char a[200];
int b = strlen(a);
int sum[26] = {};
int isPrime(int n) {//判断素数
int isP =1;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
isP = 0;
break;
}
//else
// isP = 1;
}
if (n == 1||n==0)
isP = 0;
return isP;
}
int maxn(const char a[200]) {//判断出现次数最多的字母
int max=0;
for (int i = 0; i < b; i++) {
sum[a[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (sum[i] > max)
max = sum[i];
}
return max;
}
int minn(const char a[200]) {//判断出现次数最少的字母
int min=110;
for (int i = 0; i < b; i++) {
sum[a[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (sum[i] < min&&sum[i]>0)
min = sum[i];
}
return min;
}
int main() {
cin >> a;
int b = maxn(a) - minn(a);
//cout << b;
if (isPrime(b) == 1)
cout << "Lucky Word" << endl << b;
else if (isPrime(b) == 0)
cout << "No Answer" << endl << "0";
else
cout << "Invalid Input" << endl << "0";
return 0;
}
这题暴力竟然有95分……
做了95分的做法 用哈希即可
哈希可以O（1）判断一个串的两个部分是否相等
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
typedef unsigned long long ull;
const int N = 2e3 + 10;
ull p[N], Hash[N], base = 131;
int f[N], g[N], n;
char s[N];
ull get(int l, int r)
{
return Hash[r] - Hash[l - 1] * p[r - l + 1];
}
int main()
{
p[0] = 1;
rep(i, 1, N) p[i] = p[i - 1] * base;
int T; scanf("%d", &T);
while(T--)
{
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
scanf("%s", s + 1);
n = strlen(s + 1);
Hash[1] = s[1];
_for(i, 2, n) Hash[i] = Hash[i - 1] * base + s[i];
_for(i, 1, n)
_for(j, 1, n)
{
if(i - 2 * j + 1 >= 1 && get(i - 2 * j + 1, i - j) == get(i - j + 1, i)) f[i]++;
if(i + 2 * j - 1 <= n && get(i, i + j - 1) == get(i + j, i + 2 * j - 1)) g[i]++;
}
int ans = 0;
_for(i, 1, n - 1) ans += f[i] * g[i + 1];
printf("%d\n", ans);
}
return 0;
}
代码本身没有错，可以正常运行。如果出现了错误可能是因为输入格式不对或者输入数据有误。可以尝试重新检查一下输入数据是否符合题目要求，或者运行其他数据检查程序是否有问题。