[Jobdu OJ] 1006 ZOJ有关问题
[Jobdu OJ] 1006 ZOJ问题
- 题目描述：
-
对给定的字符串(只包含'z','o','j'三种字符),判断他是否能AC。
是否AC的规则如下：
1. zoj能AC；
2. 若字符串形式为xzojx，则也能AC，其中x可以是N个'o' 或者为空；
3. 若azbjc 能AC，则azbojac也能AC，其中a,b,c为N个'o'或者为空； - 输入：
-
输入包含多组测试用例，每行有一个只包含'z','o','j'三种字符的字符串，字符串长度小于等于1000。
- 输出：
-
对于给定的字符串，如果能AC则请输出字符串“Accepted”，否则请输出“Wrong Answer”。
- 样例输入：
-
zoj ozojo ozoojoo oozoojoooo zooj ozojo oooozojo zojoooo
- 样例输出：
-
Accepted Accepted Accepted Accepted Accepted Accepted Wrong Answer Wrong Answer
- 若azbjc 能AC，则azbojac也能AC，其中a,b,c为N个'o'或者为空。
- 由第二条规则知道，xzojx可以AC，因此，与azbjc对比，可以知道，当a=c=x,b=o时，azbjc可以AC，于是，azbojac=xzoojxx可以AC。
- 因此，三条规则变成只要满足下面三种条件的字符串可以AC：
- （1）zoj
- （2）xzojx
- （3）xzoojxx
- 其中，x是0个或者多个'o'。
- 第二条和第三条规则可以变成j后面的'o'的个数等于z前面‘o'的个数乘以z和j中间'o'的个数。
-
#include <iostream> #include <string> #include <iterator> using namespace std; int main() { string str; bool flag = false; unsigned int o_left = 0, o_mid = 0, o_right = 0; while(cin >> str) { string::iterator z_iter = str.end(), j_iter = str.end(); o_left = 0; o_mid = 0; o_right = 0; flag = false; for(string::iterator iter = str.begin(); iter != str.end(); ++iter) { if(*iter == 'z' && z_iter == str.end() && j_iter == str.end()) { z_iter = iter; } else if(*iter == 'o' && z_iter == str.end() && j_iter == str.end()) { ++o_left; } else if(*iter == 'o' && z_iter != str.end() && j_iter == str.end()) { ++o_mid; } else if(*iter == 'o' && z_iter != str.end() && j_iter != str.end()) { ++o_right; } else if(*iter == 'j' && z_iter != str.end() && j_iter == str.end()) { j_iter = iter; } else { cout << "Wrong Answer" << endl; flag = true; break; } } if(flag) continue; if(z_iter != str.end() && j_iter != str.end() && (o_mid == 1 || o_mid == 2) && o_right == o_left * o_mid) { cout << "Accepted" << endl; } else { cout << "Wrong Answer" << endl; } } return 0; }
注意：上面的代码并没有AC，不过，个人觉得已经考虑了大部分的情况，在九度论坛上，有的同学没有考虑一些情况还是AC了，估计是管理员又加了一些特殊的测试用例了吧。改了好长时间，都是WA，实在不知道哪儿有问题。
- 1楼w452367233昨天 22:01
- nice亲 要我来帮你解决吗 ：）