Flow Problem
Problem Description
Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
Input 阅读全文 »
hdu3501
15
9月
2015
Calculation 2
Problem Description
Given a positive integer N, your task is to calculate the sum 阅读全文 »
hdu3292
15
9月
2015
No more tricks, Mr Nanguo
Problem Description
Now Sailormoon girls want to tell you a ancient idiom story 阅读全文 »
hdu3065
15
9月
2015
hdu2973
15
9月
2015
hdu2955
15
9月
2015
hdu2896
15
9月
2015
病毒侵袭
Problem Description
当太阳的光辉逐渐被月亮遮蔽，世界失去了光明，大地迎来最黑暗的时刻。。。。在这样的时刻，人们却异常兴奋——我们能在有生之年看到500年一遇的世界奇观，那是多么幸福的事儿啊~~ 阅读全文 »
hdu2888
15
9月
2015
Check Corners
Problem Description
Paul draw a big m*n matrix A last month, whose entries Ai,j are all integer numbers ( 1 <= i <= m, 1 <= j <= n ). Now he selects some sub-matrices, hoping to find the maximum number. Then he finds that there may be more than one maximum number, he also wants to know the number of them. But soon he find that it is too complex, so he changes his mind, he just want to know whether there is a maximum at the four corners of the sub-matrix, he calls this “Check corners”. It’s a boring job when selecting too many sub-matrices, so he asks you for help. (For the “Check corners” part: If the sub-matrix has only one row or column just check the two endpoints. If the sub-matrix has only one entry just output “yes”.)
Input
There are multiple test cases.
For each test case, the first line contains two integers m, n (1 <= m, n <= 300), which is the size of the row and column of the matrix, respectively. The next m lines with n integers each gives the elements of the matrix which fit in non-negative 32-bit integer.
The next line contains a single integer Q (1 <= Q <= 1,000,000), the number of queries. The next Q lines give one query on each line, with four integers r1, c1, r2, c2 (1 <= r1 <= r2 <= m, 1 <= c1 <= c2 <= n), which are the indices of the upper-left corner and lower-right corner of the sub-matrix in question.
Output
For each test case, print Q lines with two numbers on each line, the required maximum integer and the result of the “Check corners” using “yes” or “no”. Separate the two parts with a single space.
Sample Input
4 4
4 4 10 7
2 13 9 11
5 7 8 20
13 20 8 2
4
1 1 4 4
1 1 3 3
1 3 3 4
1 1 1 1
Sample Output
20 no
13 no
20 yes
4 yes
Source
2009 Multi-University Training Contest 9 - Host by HIT
题目类型：二维RMQ
算法分析：直接使用二维RMQ计算即可
|
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 |
#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> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const int MOD = 1000000000 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 366 + 6; int ans[maxn][maxn]; int dpmax[maxn][maxn][9][9];//最大值 void RMQ_ST (int n, int m) { for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) dpmax[i][j][0][0] = ans[i][j]; int mx = log(double(n)) / log(2.0); int my = log(double(m)) / log(2.0); for (int i = 0; i <= mx; i++) { for (int j = 0; j <= my; j++) { if (i == 0 && j ==0) continue; for (int p = 1; p + (1 << i) - 1 <= n; p++) { for(int q = 1; q + (1 << j) - 1 <= m; q++) { if (i == 0)//y轴二分 dpmax[p][q][i][j] = max (dpmax[p][q][i][j-1], dpmax[p][q+(1<<(j-1))][i][j-1]); else//x轴二分 dpmax[p][q][i][j] = max (dpmax[p][q][i-1][j], dpmax[p+(1<<(i-1))][q][i-1][j]); } } } } } int RMQ_Findmax (int x1, int y1, int x2, int y2) { int kx = log(double(x2-x1+1)) / log(2.0); int ky = log(double(y2-y1+1)) / log(2.0); int m1 = dpmax[x1][y1][kx][ky]; int m2 = dpmax[x2-(1<<kx)+1][y1][kx][ky]; int m3 = dpmax[x1][y2-(1<<ky)+1][kx][ky]; int m4 = dpmax[x2-(1<<kx)+1][y2-(1<<ky)+1][kx][ky]; return max (max(m1, m2), max (m3, m4)); } int main() { // freopen ("aaa.txt", "r", stdin); int x1, x2, y1, y2, m, n, q; while (scanf ("%d%d", &n, &m) != EOF) { for (int i = 1; i<= n; i++) for (int j = 1; j <= m; j++) scanf ("%d", &ans[i][j]); RMQ_ST (n, m); scanf ("%d", &q); for (int i = 1; i <= q; i++) { scanf ("%d%d%d%d", &x1, &y1, &x2, &y2); int temp = RMQ_Findmax (x1, y1, x2, y2); printf ("%d ", temp); if (ans[x1][y1] == temp || ans[x2][y1] == temp || ans[x1][y2] == temp || ans[x2][y2] == temp) puts ("yes"); else puts ("no"); } } return 0; } |
hdu2815
15
9月
2015
hdu2686
15
9月
2015
Matrix
Problem Description
Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix. 阅读全文 »
hdu2669
15
9月
2015
Romantic
Problem Description
The Sky is Sprite.
The Birds is Fly in the Sky.
The Wind is Wonderful.
Blew Throw the Trees 阅读全文 »
hdu2602
15
9月
2015
hdu2594
15
9月
2015
Simpsons’ Hidden Talents
Problem Description
Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.
Marge: Yeah, what is it?
Homer: Take me for example. I want to find out if I have 阅读全文 »
hdu2521
15
9月
2015
反素数
Problem Description
反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。
Input
第一行输入n,接下来n行测试数据 阅读全文 »
hdu2222
15
9月
2015
Keywords Search
Problem Description
In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.
Input
First line will contain one integer means how many cases will follow by.
Each case will contain two integers N means the number of keywords and N keywords follow. (N <= 10000)
Each keyword will only contains characters 'a'-'z', and the length will be not longer than 50.
The last line is the description, and the length will be not longer than 1000000.
Output
Print how many keywords are contained in the description.
Sample Input
1
5
she
he
say
shr
her
yasherhs
Sample Output
3
Author
Wiskey
题目类型：AC自动机
算法分析：直接将按照单词建立一个AC自动机，然后如果找到一个匹配的模式串，则不断寻找这个模式串的后缀，看能不能又找到一个匹配的模式串，防止漏解。注意使用G++会MLE！！！
|
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 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
#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> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 1e9 + 7; const int maxn = 26; char ss[1000000+maxn]; struct Node { Node *next[maxn]; Node *pre; int last; Node () { memset (next, 0, sizeof (next)); pre = 0, last = 0; } }; Node *root; void Init () { root = new Node; } void Insert (char *s) { if (!s[0]) return ; Node *p = root; for (int i = 0; s[i]; i++) { if (!p -> next[s[i]-'a']) p -> next[s[i]-'a'] = new Node; p = p -> next[s[i]-'a']; } p -> last++; } void Build () { queue <Node*> qu; Node *p = root; for (int i = 0; i < maxn; i++) if (p -> next[i]) { Node *pp = p -> next[i]; pp -> pre = root; qu.push (pp); } while (!qu.empty ()) { Node *temp = qu.front (); qu.pop (); for (int i = 0; i < maxn; i++) { Node *pp = temp -> next[i]; if (pp) { Node *par = temp -> pre; do { if (par -> next[i]) { pp -> pre = par -> next[i]; break; } else par = par -> pre; } while (par); if (!par) pp -> pre = root; qu.push (pp); } } } } int Query (char *s) { if (!s[0]) return 0; Node *p = root; int cnt = 0; for (int i = 0; s[i]; i++) { while (p != root && !p -> next[s[i]-'a']) p = p -> pre; p = p -> next[s[i]-'a']; if (!p) p = root; Node *pp = p; while (pp != root && pp -> last != -1) { cnt += pp -> last; pp -> last = -1; pp = pp -> pre; } } return cnt; } void DelTree (Node *s) { if (!s) return ; for (int i = 0; i < maxn; i++) { if (s -> next[i]) DelTree (s -> next[i]); } delete s; } int main() { // freopen ("aaa.txt", "r", stdin); int t; scanf ("%d", &t); while (t--) { int n; scanf ("%d",&n); Init (); for (int i = 1; i <= n; i++) { scanf ("%s", ss); Insert (ss); } gets (ss); gets (ss); Build (); printf ("%d\n", Query (ss)); DelTree (root); } return 0; } |
hdu2191
15
9月
2015