A N bulbs
Problem Description
N bulbs are in a row from left to right,some are on, and some are off.The first bulb is the most left one. And the last one is the most right one.they are numbered from 1 to n,from left to right.
in order to save electricity, you should turn off all the lights, but you're lazy.
coincidentally,a passing bear children paper(bear children paper means the naughty boy), who want to pass here from the first light bulb to the last one and leave.
he starts from the first light and just can get to the adjacent one at one step.
But after all,the bear children paper is just a bear children paper. after leaving a light bulb to the next one, he must touch the switch, which will change the status of the light.
your task is answer whether it's possible or not to finishing turning off all the lights, and make bear children paper also reach the last light bulb and then leave at the same time.
Input
The first line of the input file contains an integer T, which indicates the number of test cases.
For each test case, there are 2 lines.
The first line of each test case contains 1 integers n.
In the following line contains a 01 sequence, 0 means off and 1 means on.
* 1≤T≤10
* 1≤N≤1000000
Output
There should be exactly T lines in the output file.
The i-th line should only contain "YES" or "NO" to answer if it's possible to finish.
Sample Input
1
5
1 0 0 0 0
Sample Output
YES
HintChild's path is: 123234545
all switchs are touched twice except the first one.
Source
题目类型：数学构造
算法分析：简单分析可知序列中需要出现偶数个0，这样序列总数和”1”的个数只要满足同奇偶即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
/************************************************* Author :supermaker Created Time :2016/1/9 20:24:16 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { int a = 0, b = 0, val, n; scanf ("%d", &n); for (int i = 1; i <= n; i++) { scanf ("%d", &val); if (val) b++; a++; } int vala = a % 2, valb = b % 2; if ((vala && valb) || (!vala && !valb)) puts ("YES"); else puts ("NO"); } return 0; } |
B N*M bulbs
Problem Description
N*M bulbs are in a rectangle, some are on, and some are off.
in order to save electricity, you should turn off all the lights, but you're lazy.
coincidentally,a passing bear children paper(bear children paper means the naughty boy), who want to pass here from the top left light bulb to the bottom right one and leave.
he starts from the top left light and just can get to the adjacent one in one step.
But after all,the bear children paper is just a bear children paper. after leaving a light bulb to the next one, he must touch the switch, which will change the status of the light.
your task is answer whether it's possible or not to finishing turning off all the lights, and make bear children paper also reach the bottom right light bulb and then leave at the same time.
Input
The first line of the input file contains an integer T, which indicates the number of test cases.
For each test case, there are n+1 lines.
The first line of each test case contains 2 integers n,m.
In the following n line contains a 01 square, 0 means off and 1 means on.
* T≤10
* N,M≤1000
Output
There should be exactly T lines in the output file.
The i-th line should only contain "YES" or "NO" to answer if it's possible to finish.
Sample Input
1
1 5
1 0 0 0 0
Sample Output
YES
HintChild's path is: (1,1)(1,2)(1,3)(1,2)(1,3)(1,4)(1,5)(4,5)
all switches are touched twice except the first one.
Source
题目类型：数学构造
算法分析：和上面的题很类似，这里”1”的个数表示要对其翻转的次数，而通过题面可知每操作一次就会使得预计到达(n, m)点的数字发生翻转。所以只要满足到达(n,m - 1)或(n - 1, m)点处的时候和翻转的次数同奇偶，则有解。反之，则无解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
/************************************************* Author :supermaker Created Time :2016/1/9 21:06:15 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { int n, m; int a = 0; scanf ("%d%d", &n, &m); int val; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf ("%d", &val); if (val) a++; } int vala = a % 2, valb = (n + m - 1) % 2; if ((vala & valb) || (!vala && !valb)) puts ("YES"); else puts ("NO"); } return 0; } |
- poj2104：下一篇 »