| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴份代码,并提示一下可能导致WA的地方#include <iostream>
using namespace std;
int getresult(int k);
//记录原始数据
bool a[5000];
//表示在第i头牛处是否需要进行一次旋转操作
bool f[5000];
int N;
int main()
{
char m;//用于接收字符的变量
cin >> N;
for (int i = 0; i < N; i++)
{
//scanf_s(" %c", &m);//这种输入会Wrong Answer
//以下三种输入都可以Accept
scanf_s(" %c", &m, 1);
//scanf(" %c", &m);
//cin >> m;
a[i] = m - 70;//如果 m == 'F' ,则 a[i] = false ,否则 a[i] = true
}
int ansM = N + 1;//最小操作次数
int ansK, t;//对应的K , 记录getresult(i)的变量
for (int i = 1; i <= N; i++)
{
t = getresult(i);
if (t < ansM)
{
ansM = t;
ansK = i;
}
}
printf_s("%d %d\n", ansK, ansM);
return 0;
}
int getresult(int k)
{
int result = 0;
if (a[0])
{
f[0] = true;
result++;
}
for (int i = 1; i < k; i++)//对 在第 0 头牛的旋转的影响范围内 的操作
{
f[i] = a[i] ^ a[i - 1];
if (f[i])
{
result++;
}
}
int maxn = N - k + 1;//首个不可旋转的牛
for (int i = k; i < maxn; i++)//对 在第 0 头牛的旋转的影响范围之外 且 可以旋转的牛 的操作
{
f[i] = a[i] ^ a[i - 1] ^ f[i - k];
if (f[i])
{
result++;
}
}
bool m = a[maxn - 1];//最后一头可以旋转的牛最终是否被旋转了(与 a[maxn -1] 一致)
for (int i = maxn; i < k; i++)//对 从首个不能旋转的牛到最后一个可以被第 0 头牛的旋转影响的牛 进行检测
{
if (a[i] ^ m)
{
result = N + 1;
return result;
}
}
if (k > maxn)//确定不能旋转且超出第 0 头牛的旋转影响范围的牛的编号,并使用 maxn 记录
{
maxn = k;
}
for (int i = maxn; i < N; i++)//对 不能旋转 且 超出第 0 头牛的旋转影响范围的牛 进行检测
{
m = m ^ f[i - k];
if (a[i] ^ m)
{
result = N + 1;
break;
}
}
return result;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator