# HDOJ 1159-Common Subsequence

HDOJ 1159-Common Subsequence
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38564 Accepted Submission(s): 17705
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = <x1, x2, ..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X if there exists a strictly increasing sequence <i1, i2, ..., ik> of indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a, b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence <1, 2, 4, 6>. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.
The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
Source
Southeastern Europe 2003

#include<string>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
int lcs(const string &a, const string &b) {
int n = a.size(), m = b.size();
if (n == 0 || m == 0)return 0;
vector<int> dp(m + 1, 0);
for (int i = 1; i <= n; ++i) {
int pre = 0;
for (int j = 1; j <= m; ++j) {
int cur = 0;
if (a[i - 1] == b[j - 1])cur = pre + 1;
else cur = max(dp[j - 1], dp[j]);
pre = dp[j];
dp[j] = cur;
}
}
return dp[m]; // 最大值就是右下角的值
}
void construct_lcs(vector<vector<int>> &direction, const string &a, int i, int j, string &lcs) {
if (i == 0 || j == 0)return;
if (direction[i][j] == 3) {
construct_lcs(direction, a, i - 1, j - 1, lcs);
lcs += string(1, a[i - 1]); // direction下标1对应a下标0，所以i-1
}
else if (direction[i][j] == 2) {
construct_lcs(direction, a, i - 1, j, lcs);
}
else {
construct_lcs(direction, a, i, j - 1, lcs);
}
}
string lcs_string(const string &a, const string &b) {
int n = a.size(), m = b.size();
if (n == 0 || m == 0)return 0;
vector<int> dp(m + 1, 0);
vector<vector<int>> direction(n + 1, vector<int>(m + 1, 0)); // 1:left,2:up,3:diagonal
for (int i = 1; i <= n; ++i) {
int pre = 0;
for (int j = 1; j <= m; ++j) {
int cur = 0;
if (a[i - 1] == b[j - 1]) {
cur = pre + 1;
direction[i][j] = 3;
}
else {
if (dp[j - 1] > dp[j]) {
cur = dp[j - 1];
direction[i][j] = 1;
}
else {
cur = dp[j];
direction[i][j] = 2;
}
}
pre = dp[j];
dp[j] = cur;
}
}
string ans;
construct_lcs(direction, a, n, m, ans); // 从右下角递归往前找，LCRS P225
return ans;
}
int main() {
//freopen("input.txt", "r", stdin);
string a, b;
while (cin >> a >> b) {
cout << lcs(a, b) << endl;
//cout << lcs(a, b) << "\t" << lcs_string(a, b) << endl;;
}
return 0;
}


# HDOJ 5424-Rikka with Graph II

HDOJ 5424-Rikka with Graph II
Rikka with Graph II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 379 Accepted Submission(s): 94
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and n edges. Now he wants you to tell him if there exist a Hamiltonian path.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains a number n(1≤n≤1000).
Then n lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v.
Output
For each testcase, if there exist a Hamiltonian path print "YES" , otherwise print "NO".
Sample Input
4
1 1
1 2
2 3
2 4
3
1 2
2 3
3 1
Sample Output
NO
YES
Hint
For the second testcase, One of the path is 1->2->3
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

1）a在L的内部连接，这时A,B的度数都为1，其他点的度数为2或3；
2）a一端在A（或B），另一端在L的内部，这时L的另一个端点B（或A）的度数为1，其他点的度数为2或3；
3）a连接了A,B，此时所有点的度数都为2。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;
const int kMaxN = 1005;
int degree[kMaxN];
vector<vector<int>> path;
int visit[kMaxN];
int n, done;
bool DFS(int s)
{
done++;
visit[s] = 1;
if (done == n)
return true;
int v;
for (int i = 0; i < path[s].size(); i++)
{
v = path[s][i];
if (!visit[v])
{
if (DFS(v))
return true;
}
}
done--;
visit[s] = 0;
return false;
}
bool CheckHamiltonian()
{
int min_degree = n + 1, bad_node_num = 0, id;
for (int i = 1; i <= n; i++)
{
if (degree[i] && degree[i] < min_degree)
{
min_degree = degree[i];
id = i;
}
if (degree[i] <= 1)
}
return false;
memset(visit, 0, sizeof(visit));
done = 0;
return DFS(id);
}
int main()
{
//freopen("input.txt", "r", stdin);
while (~scanf("%d", &n))
{
memset(degree, 0, sizeof(degree));
path.clear();
path.resize(n + 1);
int u, v;
for (int i = 0; i < n; i++)
{
scanf("%d %d", &u, &v);
if (u == v)
continue;
degree[u]++;
degree[v]++;
path[u].push_back(v);
path[v].push_back(u);
}
if (CheckHamiltonian())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}


# HDOJ 5422-Rikka with Graph

HDOJ 5422-Rikka with Graph
Rikka with Graph
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 144 Accepted Submission(s): 72
Problem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Yuta has a non-direct graph with n vertices and m edges. The length of each edge is 1. Now he wants to add exactly an edge which connects two different vertices and minimize the length of the shortest path between vertice 1 and vertice n. Now he wants to know the minimal length of the shortest path and the number of the ways of adding this edge.
It is too difficult for Rikka. Can you help her?
Input
There are no more than 100 testcases.
For each testcase, the first line contains two numbers n,m(2≤n≤100,0≤m≤100).
Then m lines follow. Each line contains two numbers u,v(1≤u,v≤n) , which means there is an edge between u and v. There may be multiedges and self loops.
Output
For each testcase, print a single line contains two numbers: The length of the shortest path between vertice 1 and vertice n and the number of the ways of adding this edge.
Sample Input
2 1
1 2
Sample Output
1 1
Hint
You can only add an edge between 1 and 2.
Source
BestCoder Round #53 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main()
{
int n, m;
while (~scanf("%d %d", &n, &m))
{
bool connected = false;
int u, v;
while (m--)
{
scanf("%d %d", &u, &v);
if ((u == 1 && v == n) || (u == n&&v == 1))
connected = true;
}
if (connected)
printf("1 %d\n", n*(n - 1) / 2);
else
printf("1 1\n");
}
return 0;
}


# HDOJ 3535-AreYouBusy

HDOJ 3535-AreYouBusy
AreYouBusy
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3450 Accepted Submission(s): 1342
Problem Description
Happy New Term!
As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad.
What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as "jobs". A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss's advice)?
Input
There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once.
Output
One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 .
Sample Input
3 3
2 1
2 5
3 8
2 0
1 0
2 1
3 2
4 3
2 1
1 1
3 4
2 1
2 5
3 8
2 0
1 1
2 8
3 2
4 4
2 1
1 1
1 1
1 0
2 1
5 3
2 0
1 0
2 1
2 0
2 2
1 1
2 0
3 2
2 1
2 1
1 5
2 8
3 2
3 8
4 9
5 10
Sample Output
5
13
-1
-1
Author
hphp
Source
2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU
Recommend
zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int kMaxN = 105, kINF = 0x7ffffff;
int dp[kMaxN][kMaxN];
int main()
{
//freopen("input.txt", "r", stdin);
int n, t;
while (~scanf("%d %d", &n, &t))
{
for (int i = 0; i < kMaxN; i++)
for (int j = 0; j < kMaxN; j++)
dp[i][j] = -kINF;
for (int i = 0; i < kMaxN; i++)
dp[0][i] = 0;
int m, s, c, g;
for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m--) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
else if (s == 1)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + g);
}
}
else if (s == 2)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
}
printf("%d\n", max(dp[n][t], -1));
}
return 0;
}


# HDOJ 5418-Victor and World

HDOJ 5418-Victor and World
Victor and World
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 643 Accepted Submission(s): 268
Problem Description
After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are n countries on the earth, which are numbered from 1 to n. They are connected by m undirected flights, detailedly the i-th flight connects the ui-th and the vi-th country, and it will cost Victor's airplane wi L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country.
Victor now is at the country whose number is 1, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.
Input
The first line of the input contains an integer T, denoting the number of test cases.
In every test case, there are two integers n and m in the first line, denoting the number of the countries and the number of the flights.
Then there are m lines, each line contains three integers ui, vi and wi, describing a flight.
1≤T≤20.
1≤n≤16.
1≤m≤100000.
1≤wi≤100.
1≤ui,vi≤n.
Output
Your program should print T lines : the i-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.
Sample Input
1
3 2
1 2 2
1 3 3
Sample Output
10
Source
BestCoder Round #52 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5416 5415

$dp[s|(1<

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int kMaxN = 17, kINF = 0x3f3f3f3f;
int dis[kMaxN][kMaxN], dp[1 << kMaxN][kMaxN];
int n, m;
void Init()
{
memset(dis, 0x3f, sizeof(dis));
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++)
dis[i][i] = 0;
}
void Floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j]);
}
int main()
{
freopen("input.txt", "r", stdin);
int t, u, v, w;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
Init();
while (m--)
{
scanf("%d %d %d", &u, &v, &w);
dis[u][v] = min(w, dis[u][v]);
dis[v][u] = dis[u][v];
}
Floyd();
dp[1][1] = 0;
for (int status = 1; status < (1 << n); status++)//枚举状态
{
for (int i = 1; i <= n; i++)//枚举最后访问的城市
{
//if (status&(1 << (i-1))==0)//(1)
if ((status&(1 << (i-1)))==0)//(2)i有没有访问过都可以
{
for (int j = 1; j <= n; j++)//枚举中间转折点
{
if (status&(1 << (j-1)))//(3)转折点j一定要访问过
dp[status | (1 << (i-1))][i] = min(dp[status | (1 << (i-1))][i], dp[status][j] + dis[i][j]);
}
}
}
}
int ans = kINF;
for (int i = 1; i <= n; i++)
ans = min(ans, dp[(1 << n) - 1][i] + dis[i][1]);
printf("%d\n", n == 1 ? 0 : ans);
}
return 0;
}


# HDOJ 5417-Victor and Machine

HDOJ 5417-Victor and Machine
Victor and Machine
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 177 Accepted Submission(s): 91
Problem Description
Victor has a machine. When the machine starts up, it will pop out a ball immediately. After that, the machine will pop out a ball every w seconds. However, the machine has some flaws, every time after x seconds of process the machine has to turn off for y seconds for maintenance work. At the second the machine will be shut down, it may pop out a ball. And while it's off, the machine will pop out no ball before the machine restart.
Now, at the 0 second, the machine opens for the first time. Victor wants to know when the n-th ball will be popped out. Could you tell him?
Input
The input contains several test cases, at most 100 cases.
Each line has four integers x, y, w and n. Their meanings are shown above。
1≤x,y,w,n≤100.
Output
For each test case, you should output a line contains a number indicates the time when the n-th ball will be popped out.
Sample Input
2 3 3 3
98 76 54 32
10 9 8 100
Sample Output
10
2664
939
Source
BestCoder Round #52 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5421 5420 5419 5418 5416

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int x, y, w, n;
while (scanf("%d %d %d %d", &x, &y, &w, &n) != EOF)
{
if (w > x)
printf("%d\n", (n - 1)*(x + y));
else if (w == x)
{
if (n & 1)
printf("%d\n", ((n - 1) / 2)*(x + y));
else
printf("%d\n", ((n - 2) / 2)*(x + y) + x);
}
else
{
int num = x / w + 1;
if (n % num == 0)
printf("%d\n", (n / num - 1)*(x + y) + w * (num - 1));
else
printf("%d\n", (n / num)*(x + y) + (n % num - 1) * w);
}
}
return 0;
}


# HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town
Infoplane in Tina Town
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1636 Accepted Submission(s): 385
Problem Description
There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device).
Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her.
Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime).
Input
The first line is an integer T representing the number of test cases. T≤5
For each test case, the first line is an integer n representing the length of permutation. n≤3∗106
The second line contains n integers representing a permutation A1...An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ).
Output
For each test case, print a number ans representing the answer.
Sample Input
2
3
1 3 2
6
2 3 4 5 6 1
Sample Output
2
6
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389

60=2×2×3×5
18=2×3×3
lcm(60,18)=180=2×2×3×3×5

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int kMaxN = 3000005, kNumPrime = 269;
const ULL kMod = 3221225473;
bool visited[kMaxN];
int permutation[kMaxN];
int prime[kNumPrime] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723 };
int prime_times[kMaxN];
//求x的所有质因子及其频率
void GetPrimeFactor(int x)
{
for (int i = 0; i < kNumPrime; i++)
{
int tmp = 0;
while (x%prime[i] == 0)
{
tmp++;
x /= prime[i];
}
if (tmp > prime_times[prime[i]])
prime_times[prime[i]] = tmp;
if (x == 1)
return;
}
prime_times[x]++;
}
//快速幂取模x^ymod(kMod)
ULL QuickPow(ULL x, ULL y)
{
ULL ans = 1;
while (y)
{
if (y & 1)
ans = (ans*x)%kMod;
x = (x*x) % kMod;
y >>= 1;
}
return ans;
}
int main()
{
int t, n, len;
ULL ans;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
memset(visited, false, kMaxN);
memset(prime_times, 0, kMaxN);
for (int i = 1; i <= n; i++)
scanf("%d", &permutation[i]);
for (int i = 1; i <= n; i++)
{
if (!visited[i])
{
visited[i] = true;
int j = permutation[i];
len = 1;
while (j != i)
{
visited[j] = true;
j = permutation[j];
len++;
}
GetPrimeFactor(len);
}
}
ans = 1;
for (int i = 2; i < n; i++)
if (prime_times[i] != 0)
ans = (ans*QuickPow(i, prime_times[i])) % kMod;
printf("%I64un", ans);
}
return 0;
}


# HDOJ 5391-Zball in Tina Town

HDOJ 5391-Zball in Tina Town
Zball in Tina Town
Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 817 Accepted Submission(s): 471
Problem Description
Tina Town is a friendly place. People there care about each other.
Tina has a ball called zball. Zball is magic. It grows larger every day. On the first day, it becomes 1 time as large as its original size. On the second day,it will become 2 times as large as the size on the first day. On the n-th day,it will become n times as large as the size on the (n-1)-th day. Tina want to know its size on the (n-1)-th day modulo n.
Input
The first line of input contains an integer T, representing the number of cases.
The following T lines, each line contains an integer n, according to the description.
T≤$10^5$,2≤n≤$10^9$
Output
For each test case, output an integer representing the answer.
Sample Input
2
3
10
Sample Output
2
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5392 5390

On the n-th day,it will become n times as large as the size on the (n-1)-th day.

#include<iostream>
#include<cstdio>
using namespace std;
bool IsPrime(int x)
{
for (int i = 2; i*i <= x; i++)
if (x%i == 0)
return false;
return true;
}
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
if (n == 2)
printf("1n");
else if (n == 4)
printf("2n");
else if (IsPrime(n))
printf("%dn", n - 1);
else
printf("0n");
}
return 0;
}