A ZYB's Biology
Problem Description
After getting 600 scores in NOIP ZYB(ZJ-267) begins to work with biological questions.Now he give you a simple biological questions: he gives you a DNA sequence and a RNA sequence,then he asks you whether the DNA sequence and the RNA sequence are
matched.
The DNA sequence is a string consisted of A,C,G,T;The RNA sequence is a string consisted of A,C,G,U.
DNA sequence and RNA sequence are matched if and only if A matches U,T matches A,C matches G,G matches C on each position.
Input
In the first line there is the testcase T.
For each teatcase:
In the first line there is one number N.
In the next line there is a string of length N,describe the DNA sequence.
In the third line there is a string of length N,describe the RNA sequence.
1 \leq T \leq 10,1 \leq N \leq 100
Output
For each testcase,print YES or NO,describe whether the two arrays are matched.
Sample Input
2
4
ACGT
UGCA
4
ACGT
ACGU
Sample Output
YES
NO
Source
题目类型：简单模拟
算法分析：直接按照题意模拟即可
|
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 |
#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 = 0x7FFFFFFF; const int MOD = 1e4 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; int main() { //CFF; string sa, sb; int n, t; cin >> t; while (t--) { cin >> n; cin >> sa >> sb; bool is_valid = true; for (int i = 0; i < n; i++) { if (sa[i] == 'A' && sb[i] == 'U') continue; if (sa[i] == 'T' && sb[i] == 'A') continue; if (sa[i] == 'C' && sb[i] == 'G') continue; if (sa[i] == 'G' && sb[i] == 'C') continue; else { is_valid = false; break; } } if(is_valid) puts ("YES"); else puts ("NO"); } return 0; } |
B ZYB's Game
Problem Description
ZYB played a game named NumberBomb with his classmates in hiking:a host keeps a number in [1,N] in mind,then
players guess a number in turns,the player who exactly guesses X loses,or the host will tell all the players that
the number now is bigger or smaller than X.After that,the range players can guess will decrease.The range is [1,N] at first,each player should guess in the legal range.
Now if only two players are play the game,and both of two players know the X,if two persons all use the best strategy,and the first player guesses first.You are asked to find the number of X that the second player
will win when X is in [1,N].
Input
In the first line there is the number of testcases T.
For each teatcase:
the first line there is one number N.
1≤T≤100000,1≤N≤10000000
Output
For each testcase,print the ans.
Sample Input
13
Sample Output
1
Source
题目类型：简单博弈
算法分析：两者若都是用最优策略的话，简单推一下会发现只有N为奇数时，后手才能获得一次必胜的机会，否则必败
|
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 |
#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 = 0x7FFFFFFF; const int MOD = 1e4 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 66; int main() { //CFF; int t; scanf("%d", &t); while (t--) { int n; scanf ("%d", &n); if (n & 1) puts ("1"); else puts ("0"); } return 0; } |
C ZYB's Premutation
Problem Description
ZYB has a premutation P,but he only remeber the reverse log of each prefix of the premutation,now he ask you to
restore the premutation.
Pair (i,j)(i<j) is considered as a reverse log if Ai>Aj is matched.
Input
In the first line there is the number of testcases T.
For each teatcase:
In the first line there is one number N.
In the next line there are N numbers Ai,describe the number of the reverse logs of each prefix,
The input is correct.
1≤T≤5,1≤N≤50000
Output
For each testcase,print the ans.
Sample Input
130 1 2
Sample Output
3 1 2
Source
题目类型：区间第k大查询
算法分析：从区间后面往前面看，可以找到当前数是前面数的第k大 (从大往小算的)，使用线段树可以找到序列1~n中剩余数中第k的是什么(开始所有的数都赋值为1，然后对于每次找到的数，将其值赋为0)
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
/************************************************* Author :supermaker Created Time :2015/12/7 23:13:56 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; #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r int aa[maxn], sum[maxn<<2], out[maxn], n; void PushUp (int rt) { sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void Build (int rt, int l, int r) { if (l == r) { sum[rt] = 1; return ; } int m = (l + r) >> 1; Build (lson); Build (rson); PushUp (rt); } void UpDate (int rt, int l, int r, int val) { if (l == r) { sum[rt] = 0; return ; } int m = (l + r) >> 1; if (val <= m) UpDate (lson, val); else UpDate (rson, val); PushUp (rt); } int Query (int rt, int l, int r, int val) { if (l == r) return l; int m = (l + r) >> 1; if (val <= sum[rt<<1|1]) return Query (rson, val); return Query (lson, val - sum[rt<<1|1]); } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d", &n); aa[0] = 0; for (int i = 1; i <= n; i++) scanf ("%d", &aa[i]); Build (1, 1, n); for (int i = n; i >= 1; i--) { int tt = aa[i] - aa[i-1]; int k = Query (1, 1, n, tt + 1); out[i] = k; UpDate (1, 1, n, k); } for (int i = 1; i <= n; i++) { if (i == 1) printf ("%d", out[i]); else printf (" %d", out[i]); } puts (""); } return 0; } |
D ZYB's Tree
Problem Description
ZYB has a tree with N nodes,now he wants you to solve the numbers of nodes distanced no more than K for each node.
the distance between two nodes(x,y) is defined the number of edges on their shortest path in the tree.
To save the time of reading and printing,we use the following way:
For reading:we have two numbers A and B,let fai be the father of node i,fa1=0,fai=(A∗i+B)%(i−1)+1 for i∈[2,N] .
For printing:let ansi be the answer of node i,you only need to print the xor sum of all ansi.
Input
In the first line there is the number of testcases T.
For each teatcase:
In the first line there are four numbers N,K,A,B
1≤T≤5,1≤N≤500000,1≤K≤10,1≤A,B≤1000000
Output
For T lines,each line print the ans.
Please open the stack by yourself.
N≥100000 are only for two tests finally.
Sample Input
1
3 1 1 1
Sample Output
3
Source
题目类型：树形DP
算法分析：dp[i][j]表示距离节点i长度为j的节点的个数。可以先使用后序遍历求出以i为根的子树中满足条件的个数，状态转移方程为dp[i][j] += Simga (dp[k][j-1]) k = son (i)，然后再使用先序遍历求出跨子树之间的值，状态转移方程为dp[i][j] += dp[k][j-1] - dp[i][j-2] k = par (i)，最后累加求异或和即可，注意在计算父节点时会超int！！！
|
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 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
/************************************************* Author :supermaker Created Time :2015/12/20 23:08: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 = 1e6 + 6666; struct node { int v, next; }; node edge[maxn]; int head[maxn], edgelen, dp[maxn][16]; int n, k, A, B, res; void Init () { memset (edge, -1, sizeof (edge)); memset (head, -1, sizeof (head)); edgelen = 0; } void AddEdge (int u, int v) { edge[edgelen].v = v; edge[edgelen].next = head[u]; head[u] = edgelen++; } void dfs (int cur) { dp[cur][0] = 1; for (int i = 1; i <= k; i++) dp[cur][i] = 0; for (int i = head[cur]; i != -1; i = edge[i].next) { dfs (edge[i].v); for (int j = 1; j <= k; j++) dp[cur][j] += dp[edge[i].v][j-1]; } } void SS (int cur) { for (int i = head[cur]; i != -1; i = edge[i].next) { for (int j = k; j >= 2; j--) dp[edge[i].v][j] += dp[cur][j-1] - dp[edge[i].v][j-2]; dp[edge[i].v][1]++; SS (edge[i].v); } int tt = 0; for (int i = 0; i <= k; i++) tt += dp[cur][i]; res ^= tt; } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d %d %d %d", &n, &k, &A, &B); Init (); for (int i = 2; i <= n; i++) { int tt = ((LL) A * i + B) % (i - 1) + 1; AddEdge (tt, i); } res = 0; dfs (1); SS (1); printf ("%d\n", res); } return 0; } |
- poj2182：下一篇 »