Monthly Archives: August 2015

HDOJ 5424-Rikka with Graph II

Leave a reply

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 If you doesn’t know what is Hamiltonian path, click here (https://en.wikipedia.org/wiki/Hamiltonian_path). Source BestCoder Round #53 (div.2) Recommend hujie | We have carefully selected several similar problems for you: 5426 5425 5424 5423 5422

这题题意很明确，判断一个无向图中是否存在哈密顿路径，注意不是哈密顿回路。
由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次，形成的路径称为哈密顿路径，闭合的哈密顿路径称作哈密顿回路，含有哈密顿回路的图称为哈密顿图。
本来判断一个常规图中是否存在哈密顿路径是NP完全问题，不可能有多项式解，所以如果依次对每个点DFS，肯定超时。 但是这题很特殊，图中只有n个点，n条边！如果存在哈密顿路径L，则路径长度为n-1条边，设L两个端点为A,B，此时还剩下一条边a，这条边有三种情况： 1）a在L的内部连接，这时A,B的度数都为1，其他点的度数为2或3； 2）a一端在A（或B），另一端在L的内部，这时L的另一个端点B（或A）的度数为1，其他点的度数为2或3； 3）a连接了A,B，此时所有点的度数都为2。 如果存在哈密顿路径，这三种情况下，L的某个端点的度数都是最少的。所以可以先找到度数最小的点，再从这个点开始DFS，这样只需要一次DFS就可以判断是否存在哈密顿路径。 当然要先判断这个图是否连通，我起初使用了并查集，但是超时，郁闷。后来发现，如果哈密顿路径存在，则肯定连通，且此时读数为1点不超过2个，所以可以用这个条件判断是否连通。 完整代码如下： [cpp] #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) bad_node_num++; } if (bad_node_num > 2) 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; } [/cpp] 本代码提交AC，用时93MS，内存1800K。]]>

HDOJ 5422-Rikka with Graph

Leave a reply

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

水题。 如果原来就有边(1,n)，则最短距离就是1，可以任选2个点构成一条新边，方案数$$C^2_n$$；如果原来没有边(1,n)，则添加的新边就是(1,n)，最短距离还是1，此时只有一种方案。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时0MS，内存1216K。]]>

hihoCoder 1139-二分·二分答案

Leave a reply

hihoCoder 1139-二分·二分答案 #1139 : 二分·二分答案 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回和上上回里我们知道Nettle在玩《艦これ》，Nettle在整理好舰队之后终于准备出海捞船和敌军交战了。 在这个游戏里面，海域是N个战略点(编号1..N)组成，如下图所示 其中红色的点表示有敌人驻扎，猫头像的的点表示该地图敌军主力舰队(boss)的驻扎点，虚线表示各个战略点之间的航线(无向边)。 在游戏中要从一个战略点到相邻战略点需要满足一定的条件，即需要舰队的索敌值大于等于这两点之间航线的索敌值需求。 由于提高索敌值需要将攻击机、轰炸机换成侦察机，舰队索敌值越高，也就意味着舰队的战力越低。 另外在每一个战略点会发生一次战斗，需要消耗1/K的燃料和子弹。必须在燃料和子弹未用完的情况下进入boss点才能与boss进行战斗，所以舰队最多只能走过K条航路。 现在Nettle想要以最高的战力来进攻boss点，所以他希望能够找出一条从起始点(编号为1的点)到boss点的航路，使得舰队需要达到的索敌值最低，并且有剩余的燃料和子弹。 特别说明：两个战略点之间可能不止一条航线，两个相邻战略点之间可能不止一条航线。保证至少存在一条路径能在燃料子弹用完前到达boss点。 提示：你在找什么？ 输入 第1行：4个整数N,M,K,T。N表示战略点数量，M表示航线数量，K表示最多能经过的航路，T表示boss点编号, 1≤N,K≤10,000, N≤M≤100,000 第2..M+1行：3个整数u,v,w，表示战略点u,v之间存在航路，w表示该航路需求的索敌值，1≤w≤1,000,000。 输出 第1行：一个整数，表示舰队需要的最小索敌值。 样例输入 5 6 2 5 1 2 3 1 3 2 1 4 4 2 5 2 3 5 5 4 5 3 样例输出 3

本题的目标是在无向图中，求从点1到T的路径中的索敌值的最大值的最小值，且经过的路径不能超过k段。 在输入的时候，我们能得到所有索敌值的最大值high和最小值low，high值显然能够成功到达T点，且不超过k段，因为题目说了保证至少存在一条路径能在燃料子弹用完前到达boss点；low就不一定了。所以二分答案的意思就是在区间[low,high]中二分查找最小可行解。 假设函数f(x)能判断当索敌值为x时，是否能成功到达T点且不超过k段。则每二分一次就求一次f(mid)，根据f(mid)的值调整区间[low,high]的端点。所以现在的关键就是函数f(x)。 f(x)可以使用广度优先搜索实现。实现的时候注意不能使用邻接矩阵保存图，有可能TLE或MLE，使用邻接表更好。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<queue> #include<vector> using namespace std; const int kMaxN = 10005, kINF = 0x3f, kMaxW = 1000005; vector<vector<int>> path; vector<vector<int>> powers; vector<bool> visit; int n, m, k, t; bool BFS(int power) { visit.clear(); visit.resize(n + 1, false); queue<int> Q; int u, v, len = 0;; Q.push(1); visit[1] = true; Q.push(-1); while (!Q.empty()&&len<k) { u = Q.front(); Q.pop(); if (u == -1) { if (Q.empty()) return false; else { len++; Q.push(-1); continue; } } for (int i = 0; i < path[u].size(); i++) { v = path[u][i]; if (!visit[v]&&powers[u][i] <= power) { if (v == t) return true; visit[v] = true; Q.push(v); } } } return false; } int main() { freopen("input.txt", "r", stdin); scanf("%d %d %d %d", &n, &m, &k, &t); path.resize(n + 1); powers.resize(n + 1); int u, v, w, low = kMaxW, high = 0; for (int i = 0; i < m; i++) { scanf("%d %d %d", &u, &v, &w); low = min(low, w); high = max(high, w); path[u].push_back(v); path[v].push_back(u); powers[u].push_back(w); powers[v].push_back(w); } while (low+1 < high) { int mid = (low + high) / 2; if (BFS(mid)) high = mid; else low = mid; } printf("%d\n", high); return 0; } [/cpp] 在BFS的时候可以单独保存每个点及该点此时的深度(len)，也可以共用一个len，只需额外加入一个标记-1，当碰到-1时，说明已经遍历完一层了，深度加1。 本代码提交AC，用时189MS，内存8MB。]]>

hihoCoder week 60-1-String Matching Content Length

Leave a reply

hihoCoder week 60-1-String Matching Content Length 题目1 : String Matching Content Length 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings. The first restriction here is that every common substring’s length should not be less than 3. For example: strA: abcdefghijklmn strB: ababceghjklmn The matching contents in strA and strB are substrings (“abc”, “jklmn”). Note that though “e” and “gh” are common substrings of strA and strB, they are not matching content because their lengths are less than 3. The second restriction is that the start indexes of all common substrings should be monotone increasing. For example: strA: aaabbbbccc strB: aaacccbbbb The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing. 输入 Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100. 输出 The maximum length of matching contents (the sum of the lengths of the common substrings). 样例输入 abcdefghijklmn ababceghjklmn 样例输出 8

本题在普通的最长公共子序列问题上添加了一个限制条件，构成最长公共子序列的每一个子串长度必须大于等于3。题目中下面这段的含义就是指求的是最长公共子序列，LCS就是从左往右依次扫描找相同的字母，ccc是公共子序列，但不是最长的，因为aaabbbb更长。
The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing.
至于题解，讨论里写得很清楚了，不过要让我自己想还真想不出来。代码实现也很简单，如下： [cpp] #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstdlib> using namespace std; const int kMaxLen = 2105; string a, b; int dp[kMaxLen][kMaxLen][2]; int f[kMaxLen][kMaxLen]; void Init() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { if (a[i] == b[j]) f[i][j] = f[i – 1][j – 1] + 1; else f[i][j] = 0; } } } void Lcs() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { dp[i][j][1] = 0; if (f[i][j] >= 3) { dp[i][j][1] = max(dp[i][j][1], dp[i – 3][j – 3][0] + 3); if (f[i][j]>3) dp[i][j][1] = max(dp[i][j][1], dp[i – 1][j – 1][1] + 1); } dp[i][j][0] = max(dp[i – 1][j][0], max(dp[i][j – 1][0], dp[i][j][1])); } } } int main() { cin >> a >> b; a = " " + a; b = " " + b; Init(); Lcs(); printf("%d\n", dp[a.size() – 1][b.size() – 1][0]); return 0; } [/cpp] 本代码提交AC，用时319MS，内存50MB。]]>

hihoCoder 1138-Islands Travel

Leave a reply

hihoCoder 1138-Islands Travel #1138 : Islands Travel 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 There are N islands on a planet whose coordinates are (X1, Y1), (X2, Y2), (X3, Y3) …, (XN, YN). You starts at the 1st island (X1, Y1) and your destination is the n-th island (XN, YN). Travelling between i-th and j-th islands will cost you min{|Xi-Xj|, |Yi-Yj|} (|a| denotes the absolute value of a. min{a, b} denotes the smaller value between a and b) gold coins. You want to know what is the minimum cost to travel from the 1st island to the n-th island. 输入 Line 1: an integer N. Line 2~N+1: each line contains two integers Xi and Yi. For 40% data, N<=1000，0<=Xi,Yi<=100000. For 100% data, N<=100000，0<=Xi,Yi<=1000000000. 输出 Output the minimum cost. 样例输入 3 2 2 1 7 7 6 样例输出 2

本题实质上是单源最短路径问题，只是两点间的距离需要自己算。我先后尝试了Dijkstra算法和朴素SPFA算法，都超时，后来参考这篇博客，在SPFA之前需要对数据进行预处理。 原始SPFA时，点(x,y)和其余n-1个点的边都需要尝试，这样计算量就很大，但是因为距离函数是min{|Xi-Xj|, |Yi-Yj|}这样的，和点(x,y)“距离”最近的点(x’,y’)是那些x’和x最近或者y’和y最近的点。所以点(x,y)实际上只需要尝试4条边，分别是靠近x的前后两个点和靠近y的上下两个点。 所以我们需要对所有点分别按x和y排序，然后重新构造一个图，这个图中，每个点只和另外4个点有边，这样使得图的复杂度大幅下降，再使用SPFA就不会超时了。 SPFA的介绍可以看我之前的题目。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<queue> #include<cstring> #include<vector> using namespace std; const int kMaxN = 100005, kINF = 0x3f; int n; typedef struct P { int x, y; }; typedef struct Node { int value; int id; bool operator <(const Node & t)const { return value < t.value; } }; Node X[kMaxN], Y[kMaxN]; P points[kMaxN]; int dist[kMaxN]; int used[kMaxN]; vector<vector<int>> path(kMaxN); inline int GetLength(int a, int b) { return min(abs(points[a].x – points[b].x), abs(points[a].y – points[b].y)); } int Spfa() { used[1] = 1; memset(dist, kINF, sizeof(dist)); dist[1] = 0; queue<int> Q; Q.push(1); while (!Q.empty()) { int u = Q.front(); Q.pop(); used[u] = 0; for (int i = 0; i < path[u].size(); i++) { int v = path[u][i]; if (dist[u] + GetLength(u, v) < dist[v]) { dist[v] = dist[u] + GetLength(u, v); if (used[v] == 0) { Q.push(v); used[v] = 1; } } } } return dist[n]; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d", &points[i].x, &points[i].y); X[i].value = points[i].x; X[i].id = i; Y[i].value = points[i].y; Y[i].id = i; } sort(X + 1, X + n + 1); sort(Y + 1, Y + n + 1); for (int i = 2; i <= n; i++) { path[X[i].id].push_back(X[i – 1].id); path[X[i – 1].id].push_back(X[i].id); } for (int i = 2; i <= n; i++) { path[Y[i].id].push_back(Y[i – 1].id); path[Y[i – 1].id].push_back(Y[i].id); } printf("%d\n", Spfa()); return 0; } [/cpp] 本代码提交AC，用时867MS，内存20MB。]]>

HDOJ 3535-AreYouBusy

Leave a reply

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

本题分三种集合，第0种集合内至少要取1个任务；第1种集合内至多取1一个任务；第2种集合内没有任何限制。 集合内部是背包问题，这3种集合之间也是一个背包问题。 假设dp[i][j]表示前i个集合中，耗时为j时取得的最大幸福数量，则： 在第0种集合中，因为至少要取1个任务（耗时c，幸福数g），这个任务可以是本集合的第一个任务dp[i-1][j-c]+g，因为是第一个任务，所以基准是上一个集合i-1；也可以不是第一个任务dp[i][j-c]+g，基准就是本集合i；可以不取这个任务dp[i][j]，所以dp[i][j]=max(dp[i][j], dp[i-1][j-c]+g, dp[i][j-c]+g)，为了至少取一个任务，dp[i][j]必须小于其他2个，所以令dp[i][j]的初始值为-INF。 在第1种集合中，至多取1个任务，都是基于上一个集合，所以不取dp[i-1][j]；取dp[i-1][j-c]+g。 在第2种集合中，是常规0/1背包问题，不取dp[i-1][j]；第一次取dp[i-1][j-c]+g；不是第一次取dp[i][j-c]+g。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时31MS，内存1616K。]]>

hihoCoder 1137-Recruitment

Leave a reply

hihoCoder 1137-Recruitment #1137 : Recruitment 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 A company plans to recruit some new employees. There are N candidates (indexed from 1 to N) have taken the recruitment examination. After the examination, the well-estimated ability value as well as the expected salary per year of each candidate is collected by the Human Resource Department. Now the company need to choose their new employees according to these data. To maximize the company’s benefits, some principles should be followed: 1. There should be exactly X males and Y females. 2. The sum of salaries per year of the chosen candidates should not exceed the given budget B. 3. The sum of ability values of the chosen candidates should be maximum, without breaking the previous principles. Based on this, the sum of the salary per year should be minimum. 4. If there are multiple answers, choose the lexicographically smallest one. In other words, you should minimize the smallest index of the chosen candidates; If there are still multiple answers, then minimize the second smallest index; If still multiple answers, then minimize the third smallest one; … Your task is to help the company choose the new employees from those candidates. 输入 The first line contains four integers N, X, Y, and B, separated by a single space. The meanings of all these variables are showed in the description above. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X + Y <= N, 1 <= B <= 1000. Then follows N lines. The i-th line contains the data of the i-th candidate: a character G, and two integers V and S, separated by a single space. G indicates the gender (either “M” for male, or “F” for female), V is the well-estimated ability value and S is the expected salary per year of this candidate. 1 <= V <= 10000, 0 <= S <= 10. We assure that there is always at least one possible answer. 输出 On the first line, output the sum of ability values and the sum of salaries per year of the chosen candidates, separated by a single space. On the second line, output the indexes of the chosen candidates in ascending order, separated by a single space. 样例输入 4 1 1 10 F 2 3 M 7 6 M 3 2 F 9 9 样例输出 9 9 1 2

本题实质上是一个0/1背包问题，将男性和女性分别背包。 以男性为例，转换为从若干个（n1）人中取出X个男性，保证他们的工资总和不超过B，但最大化能力总和。每个应聘者相当于一个物品，工资总和为B相当于容量为B的背包。常规的0/1背包是从这n1个应聘者中挑任意多个，使得工资总和不超过B，但能力总和最大。但是本题的背包限定了取且只取X个应聘者，使得工资总和不超过B，但能力总和最大。 DP的状态转移过程为：假设dpm[i][j]表示从【当前】所有男性中选取i个，工资总和为j时获得的最大能力总和。 假设X=5，当前正好来了5个男性，已经求到了dpm[X][j]，当再来一位男性应聘者a（能力为v，工资为s）时，dpm[X][j]含义就是从当前6位应聘者中选5位满足限定条件。此时有两个选择，要或者不要a，如果不要a，则dpm[X][j]结果不变；如果要a，则前5个只能取4个，加上a就是5个，此时能力总和就是dpm[X-1][j-s]+v，所以最终dpm[X][j]=max{dpm[X][j], dpm[X-1][j-s]+v}。 当把所有男性应聘者都测试过之后，dpm[X][j]就是从所有n1个男性中选X个，其工资总和为j时的能力总和。 最后把男性和女性的情况一组合，再满足总预算不超过B，取全局最优结果。 因为应聘者N最多为100，所以使用数组unsigned long long id[2]来记录应聘者选取情况，unsigned long long 为64位，每位二进制代表一名应聘者，为1选中，id[0]记录前50位，id[1]记录后50位。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int kMaxN = 105, kMaxB = 1005; int dpf[kMaxN][kMaxB], dpm[kMaxN][kMaxB];//dpf[i][j]从所有女性应聘者中选取i个，工资总和为j时的最大能力和 unsigned long long idf[kMaxN][kMaxB][2];//记录女性选取情况 unsigned long long idm[kMaxN][kMaxB][2];//记录男性选取情况 int N, X, Y, B, V, S; char G[2]; int ans_v = 0, ans_s = 0;//总能力，总工资 unsigned long long ans_id[2] = { 0 };//总选取情况 void DP() { dpf[0][0] = dpm[0][0] = 0; int cnt_f = 0, cnt_m = 0, sum_s = 0; for (int i = 1; i <= N; i++) { scanf("%s %d %d", G, &V, &S); sum_s += S; sum_s = min(sum_s, B); if (G[0] == ‘F’) { cnt_f++; cnt_f = min(cnt_f, Y);//最多选取Y位 for (int j = cnt_f; j >= 1; j–) { for (int k = sum_s; k >= S; k–) { if (dpf[j – 1][k – S] < 0) continue; if (dpf[j – 1][k – S] + V > dpf[j][k]) { dpf[j][k] = dpf[j – 1][k – S] + V; idf[j][k][0] = idf[j – 1][k – S][0]; idf[j][k][1] = idf[j – 1][k – S][1]; if (i <= 50) idf[j][k][0] |= 1LL << (i – 1);//选中第i位 else idf[j][k][1] |= 1LL << (i – 1 – 50);//选中第i位 } } } } else { cnt_m++; cnt_m = min(cnt_m, X); for (int j = cnt_m; j >= 1; j–) { for (int k = sum_s; k >= S; k–) { if (dpm[j – 1][k – S] < 0) continue; if (dpm[j – 1][k – S] + V > dpm[j][k]) { dpm[j][k] = dpm[j – 1][k – S] + V; idm[j][k][0] = idm[j – 1][k – S][0]; idm[j][k][1] = idm[j – 1][k – S][1]; if (i <= 50) idm[j][k][0] |= 1LL << (i – 1); else idm[j][k][1] |= 1LL << (i – 1 – 50); } } } } } } void Match() { for (int i = 0; i <= B; i++) { if (dpf[Y][i] == -1) continue; for (int j = 0; j + i <= B; j++) { if (dpm[X][j] == -1) continue; if (dpf[Y][i] + dpm[X][j] > ans_v)//能力更强 { ans_v = dpf[Y][i] + dpm[X][j]; ans_s = i + j; ans_id[0] = idf[Y][i][0] | idm[X][j][0]; ans_id[1] = idf[Y][i][1] | idm[X][j][1]; } else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) < ans_s)//能力相同，但工资更少 { ans_s = i + j; ans_id[0] = idf[Y][i][0] | idm[X][j][0]; ans_id[1] = idf[Y][i][1] | idm[X][j][1]; } else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) == ans_s)//能力和工资都相同 { int id0 = idf[Y][i][0] | idm[X][j][0]; int id1 = idf[Y][i][1] | idm[X][j][1]; if (ans_id[0] > id0)//排序靠前 { ans_id[0] = id0; ans_id[1] = id1; } else if (ans_id[1] > id1)//排序靠前 { ans_id[0] = id0; ans_id[1] = id1; } } } } } void FormatOut() { printf("%d %d\n", ans_v, ans_s); for (int i = 1; i <= 50; i++) { if (ans_id[0] & 1) printf("%d ", i); ans_id[0] >>= 1; } for (int i = 51; i <= 100; i++) { if (ans_id[1] & 1) printf("%d ", i); ans_id[1] >>= 1; } } int main() { memset(dpf, -1, sizeof(dpf)); memset(dpm, -1, sizeof(dpm)); memset(idf, 0, sizeof(idf)); memset(idm, 0, sizeof(idm)); scanf("%d %d %d %d", &N, &X, &Y, &B); DP(); Match(); FormatOut(); return 0; } [/cpp] 代码大部分参考此博客，感谢。 本代码提交AC，用时33MS，内存4MB。]]>

hihoCoder 1136-Professor Q's Software

Leave a reply

hihoCoder 1136-Professor Q’s Software #1136 : Professor Q’s Software 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Professor Q develops a new software. The software consists of N modules which are numbered from 1 to N. The i-th module will be started up by signal Si. If signal Si is generated multiple times, the i-th module will also be started multiple times. Two different modules may be started up by the same signal. During its lifecircle, the i-th module will generate Ki signals: E1, E2, …, EKi. These signals may start up other modules and so on. Fortunately the software is so carefully designed that there is no loop in the starting chain of modules, which means eventually all the modules will be stoped. Professor Q generates some initial signals and want to know how many times each module is started. 输入 The first line contains an integer T, the number of test cases. T test cases follows. For each test case, the first line contains contains two numbers N and M, indicating the number of modules and number of signals that Professor Q generates initially. The second line contains M integers, indicating the signals that Professor Q generates initially. Line 3~N + 2, each line describes an module, following the format S, K, E1, E2, … , EK. S represents the signal that start up this module. K represents the total amount of signals that are generated during the lifecircle of this module. And E1 … EK are these signals. For 20% data, all N, M <= 10 For 40% data, all N, M <= 103 For 100% data, all 1 <= T <= 5, N, M <= 105, 0 <= K <= 3, 0 <= S, E <= 105. Hint: HUGE input in this problem. Fast IO such as scanf and BufferedReader are recommended. 输出 For each test case, output a line with N numbers Ans1, Ans2, … , AnsN. Ansi is the number of times that the i-th module is started. In case the answers may be too large, output the answers modulo 142857 (the remainder of division by 142857). 样例输入 3 3 2 123 256 123 2 456 256 456 3 666 111 256 256 1 90 3 1 100 100 2 200 200 200 1 300 200 0 5 1 1 1 2 2 3 2 2 3 4 3 2 4 5 4 2 5 6 5 2 6 7 样例输出 1 1 3 1 2 2 1 1 2 3 5

此题需要厘清模块和信号之间的关系，一个信号可以触发多个模块，一个模块也可以产生多个信号。利用空间换时间，再搜索的时候快速找出关系。使用广度优先搜索解决。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<queue> using namespace std; const int kMaxNMSE = 100005, kMaxK = 5, kMod = 142857; int t, n, m, s, k; int ans[kMaxNMSE]; int signals[kMaxNMSE]; vector<vector<int>> model_signals; vector<vector<int>> signal_models; queue<int> sgls; void Init() { memset(ans, 0, sizeof(ans)); memset(signals, 0, sizeof(signals)); model_signals.clear(); model_signals.resize(kMaxNMSE); signal_models.clear(); signal_models.resize(kMaxNMSE); } void BFS(int sgl) { sgls.push(sgl); while (!sgls.empty()) { int tmp = sgls.front(); sgls.pop(); if (signal_models[tmp].size()) { for (int i = 0; i < signal_models[tmp].size(); i++) { int mdl = signal_models[tmp][i]; ans[mdl]++; for (int j = 0; j < model_signals[mdl].size(); j++) sgls.push(model_signals[mdl][j]); } } } } int main() { //freopen("input.txt", "r", stdin); scanf("%d", &t); while (t–) { Init(); scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d", &signals[i]); for (int i = 1; i <= n; i++) { scanf("%d %d", &s, &k); signal_models[s].push_back(i); int tmp; while (k–) { scanf("%d", &tmp); model_signals[i].push_back(tmp); } } for (int i = 1; i <= m; i++) BFS(signals[i]); for (int i = 1; i <= n; i++) printf("%d ", ans[i] % kMod); printf("\n"); } return 0; } [/cpp] 本代码提交AC，用时899MS，内存24MB。]]>

hihoCoder 1135-Magic Box

Leave a reply

hihoCoder 1135-Magic Box #1135 : Magic Box 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 The circus clown Sunny has a magic box. When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever. For example, let’s assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish. 输入 Line 1: x y z Line 2: the sequence consisting of only three characters ‘R’, ‘Y’ and ‘B’. For 30% data, the length of the sequence is no more than 200. For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20. 输出 The maximum number of balls in the box ever. 提示 Another Sample

Sample Input Sample Output
0 0 0 RBYRRBY 4
样例输入 1 2 3 RRYBRBRYBRY 样例输出 7
简单逻辑题，每增加一个字母更新box中球的数量，并判断是否可以vanish。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<algorithm> using namespace std; int num_r=0,num_y=0,num_b=0,ans=0; int xyz[3],diff[3]; string line; void Work() { ans=max(ans,num_r+num_y+num_b); diff[0]=abs(num_r-num_y); diff[1]=abs(num_r-num_b); diff[2]=abs(num_y-num_b); sort(diff,diff+3); if(diff[0]==xyz[0]&&diff[1]==xyz[1]&&diff[2]==xyz[2]) { num_r=0; num_y=0; num_b=0; } } int main() { cin>>xyz[0]>>xyz[1]>>xyz[2]>>line; sort(xyz,xyz+3); for(int i=0;i<line.size();i++) { switch(line[i]) { case ‘R’: num_r++; break; case ‘Y’: num_y++; break; case ‘B’: num_b++; break; } Work(); } printf("%d\n",ans); return 0; } [/cpp] 本代码提交AC，用时5MS，内存0MB。]]>

HDOJ 5418-Victor and World

Leave a reply

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

此题是可重复访问城市的旅行商问题（TSP），即从1号城市开始，经过每个城市至少一次，然后回到1号，问飞机消耗的最少燃料是多少。 根据题解，首先使用Floyd算法求出所有点对的最短路径dis[i][j]，然后DP算法求解。 用一个整数s的二进制表示当前走过城市的状态，第i位为1表示第i个城市已经访问过，为0表示没访问过。dp[s][i]表示当前走过城市状态为s，且最后走过的城市编号为i，即到达了城市i。则有状态转移方程： $$dp[s|(1<<i)][i]=min(dp[s][j]+dis[i][j])$$ 条件为s&(1<<j)!=0且s&(1<<i)==0。 含义为：在s已经访问过j但是没有访问过i的情况下，转移到访问i的状态s|(1<<i)消耗的燃料为所有“s最后访问的是j消耗的燃料dp[s][j]，加上从j走到i消耗的燃料之和”情况中的最小值。 最终结果就是s中所有位为1的状态，再从该状态回到城市1的燃料之和的最小值，即min(dp[(1<<n)-1][i]+dis[i][1])。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时717MS，内存10284K。 代码中需要注意一点，代码(2)一定不要写成了(1)，要不然WA到死，&的优先级低于==，切记！ 其实(2)处的if可以不要，因为本TSP问题可以重复访问某个城市，所以这里可以不判断下一步需要访问的城市之前有没有访问过，只是加了if能缩短时间；但是(3)处的if判断一定要，因为需要在城市j中转，j之前必须访问过。 另外查看大神的代码，发现很喜欢用0x3f3f3f3f而不是0x7fffffff作为程序中的无穷大，这是有道理的，详情看这篇博客。]]>