Category Archives: hihoCoder

hihoCoder 1087 & week 63-1-Hamiltonian Cycle

Leave a reply

hihoCoder 1087 & week 63-1-Hamiltonian Cycle #1087 : Hamiltonian Cycle 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Given a directed graph containing n vertice (numbered from 1 to n) and m edges. Can you tell us how many different Hamiltonian Cycles are there in this graph? A Hamiltonian Cycle is a cycle that starts from some vertex, visits each vertex (except for the start vertex) exactly once, and finally ends at the start vertex. Two Hamiltonian Cycles C1, C2 are different if and only if there exists some vertex i that, the next vertex of vertex i in C1 is different from the next vertex of vertex i in C2. 输入 The first line contains two integers n and m. 2 <= n <= 12, 1 <= m <= 200. Then follows m line. Each line contains two different integers a and b, indicating there is an directed edge from vertex a to vertex b. 输出 Output an integer in a single line — the number of different Hamiltonian Cycles in this graph. 提示 额外的样例:

样例输入 样例输出
3 3 1 2 2 1 1 3 0
样例输入 4 7 1 2 2 3 3 4 4 1 1 3 4 2 2 1 样例输出 2
本题要求解一个有向图中存在多少个哈密顿回路，因为本题的n不超过12，所以可以暴力求解，但是可以用位运算和记忆化搜索提高搜索速度。 常规思路是从某一点DFS，计算所有哈密顿回路的数量，伪代码如下： [cpp] DFS(int nowVertex, bool visitedVertex, int path, int length) visitedVertex[ nowVertex ] = True; If (all Vertex is visited) Then Count = Count + 1 Else For (u is next vertex of nowVertex) If (not visitedVertex[ u ]) Then path[ length ] = u DFS(u, visitedVertex, path, length + 1) End If End For End If visitedVertex[ nowVertex ] = False [/cpp] 位运算的思路是用变量unused的二进制位表示一个点是否访问过，1未访问，0访问了。所以当DFS到unused==0时，找到一条哈密顿路径，如果该路径的终点能回到起点（默认为1），则构成一条哈密顿回路。部分代码如下： [cpp] const int MAXN = 14; int edge[ MAXN ];//edge[i]二进制中1的序号表示i能访问的节点编号 int p[1 << MAXN];//p[1<<i]=i+1表示只有i点访问了的情况为1<<i int cnt; void dfs(int nowVertex, int unused) { if (!unused) {//所有节点访问完了 cnt += (edge[nowVertex] & 1);//判断能否回到起始节点1 return ; } int rest = unused & edge[ nowVertex ];//剩余的能访问到的未访问节点 while (rest) { int tp = rest & (-rest);//依次取出可访问节点 dfs(p[ tp ], unused – tp);//访问 rest -= tp; } return ; } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[ 1 << i ] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1);//记录u能访问节点的情况 } dfs(1, (1 << n) – 2);//初始的时候访问了1号节点，所以-1-1=-2 printf("%d\n", cnt); return 0; } [/cpp] 这一版本的代码简洁易懂，效率也还可以，用时558MS，内存0MB。 但是还可以改进，在DFS过程中可能遇到某个节点的多次unused相同的情况，此时后面几次的DFS都是没有必要的，可以剪枝。 设f[i][j]为当前访问节点为i，已经访问过的节点情况为j时的方案数，则哈密顿路径的情况数为f[i][0]，i在[1,n]，哈密顿回路的情况数就是把所有i能回到1的f[i][0]情况数加起来。 那么怎么来计算f[i][j]呢，需要按照状态中1的个数来枚举，伪代码如下： [cpp] For numberOfOnes = n-1 .. 0 For (unused | the number of ones of unused equals numberOfOnes) For nowVertex = 1 .. n For prevVertex = 1 .. n If (unused & (1 << (nowVertex – 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex – 1)) != 0) Then f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex – 1))] End If End For End For End For End For [/cpp] 第二层for循环中的unused就是所有“在n位二进制中设置numberOfOnes位1”的所有状态，最内层的if判断该状态必须满足1)已经访问了当前节点2)前驱节点不等于当前节点3)前驱节点有到当前节点的边，则f[当前节点][访问情况为unused]+=f[前驱节点][访问情况为unused+还没访问当前节点]。 详细分析可以看官方题解。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> #include<iterator> using namespace std; const int MAXN = 14; int edge[MAXN]; int p[1 << MAXN]; int f[MAXN][1<<MAXN]; //n位二进制中出现k个1的所有排列情况 vector<int> dfs(int n, int k) { if (k == 0)//出现0个1，只有一种情况，全0 return vector<int>(1, 0); else { //********** n==k的情况 ************************** vector<int> r = dfs(n – 1, k – 1);//n-1位中出现k-1个1//将大问题分解成小问题 for (int &i : r) { i |= (1 << (n – 1));//补上第n位也为1 } //************************************************** if (n > k) { vector<int> t = dfs(n – 1, k);//此时第n位可以为0 copy(t.begin(), t.end(), back_inserter(r)); } return r; } } int main() { //freopen("input.txt", "r", stdin); int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) p[1 << i] = i + 1; while (m–) { int u, v; scanf("%d %d", &u, &v); edge[u] |= 1 << (v – 1); } f[1][(1 << n) – 2] = 1; for (int numberOfOnes = n – 1; numberOfOnes >= 0; numberOfOnes–) { vector<int> stat = dfs(n, numberOfOnes); for (int i = 0; i < stat.size(); i++) { int s = stat[i]; for (int nowVertex = 1; nowVertex <= n; nowVertex++) { for (int prevVertex = 1; prevVertex <= n; prevVertex++) { if ((s & (1 << (nowVertex – 1))) == 0 && prevVertex != nowVertex && (edge[prevVertex] & (1 << (nowVertex – 1))) != 0) f[nowVertex][s] += f[prevVertex][s | (1 << (nowVertex – 1))]; } } } } int cnt = 0; for (int i = 1; i <= n; i++) if (edge[i] & 1) cnt += f[i][0]; printf("%d\n", cnt); return 0; } [/cpp] 本代码提交AC，用时21MS，内存0MB，相比于上一版本，速度提升了一个数量级。]]>

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。]]>

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。]]>

hihoCoder 1133-二分·二分查找之k小数

Leave a reply

hihoCoder 1133-二分·二分查找之k小数 #1133 : 二分·二分查找之k小数 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在上一回里我们知道Nettle在玩《艦これ》，Nettle的镇守府有很多船位，但船位再多也是有限的。Nettle通过捞船又出了一艘稀有的船，但是已有的N(1≤N≤1,000,000)个船位都已经有船了。所以Nettle不得不把其中一艘船拆掉来让位给新的船。Nettle思考了很久，决定随机选择一个k，然后拆掉稀有度第k小的船。 已知每一艘船都有自己的稀有度，Nettle现在把所有船的稀有度值告诉你，希望你能帮他找出目标船。 提示：非有序数组的二分查找之二 输入 第1行：2个整数N,k。N表示数组长度， 第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。 输出 第1行：一个整数t，表示t在数组中是第k小的数，若K不在数组中，输出-1。 样例输入 10 4 1732 4176 2602 6176 1303 6207 3125 1 1011 6600 样例输出 1732

给定一个无序序列，问序列中第k小的数是哪个。简单粗暴的方法是排序直接取a[k]，复杂度为O(nlgn)；还有一种O(lgn)的方法，采用了和hihoCoder 1128-二分·二分查找类似的方法，将序列不断二分成小于某个数和大于某个数的两部分，直到某一部分长度为k。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; int n, k; vector<int> a; int GetNumberK(int p, int q) { int m = a[p], i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == i + 1)//(1) return m; else if (k < i + 1) return GetNumberK(p, i – 1); else { //k = k – (i – p + 1);//(2)，因为(1)处判等的时候i取p，但分割之后p并没有从0开始，所以k还是k return GetNumberK(i + 1, q); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); if (k > n||k < 1) printf("-1\n"); else printf("%d\n", GetNumberK(0, n – 1)); return 0; } [/cpp] 本代码提交AC，用时69MS，内存3MB。 需要注意一点，代码中(2)不能出现，虽然递归在[i+1,q]内部查找第k – (i – p + 1)小的数，但是(1)处判等的时候，使用的i（即p）是相对[0,n-1]长度的，所以这里的k不需要剪短]]>

hihoCoder 1128-二分·二分查找

Leave a reply

hihoCoder 1128-二分·二分查找 #1128 : 二分·二分查找 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 Nettle最近在玩《艦これ》，因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金，开了无数个船位)。去除掉重复的船之后，还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值，任意两艘船的稀有值都不相同，稀有值越小的船越稀有，价值也就越高。 Nettle现在通过大建又造出了一艘船，他想知道这艘船是不是重复的。如果是重复的，那么这艘船在Nettle所有的船里面稀有值排多少位。 问题一 Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N])，我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中，且有对应的a[i]=K时，i为多少？ 提示一：有序数组的二分查找 问题二 因为Nettle的船太多了，他不愿意去给所有船按照稀有值排序，而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢？ 提示二：非有序数组的二分查找 输入 第1行：2个整数N,K。N表示数组长度，K表示需要查找的数； 第2行：N个整数，表示a[1..N]，保证不会出现重复的数，1≤a[i]≤2,000,000,000。 输出 第1行：一个整数t，表示K在数组中是第t小的数，若K不在数组中，输出-1。 样例输入 10 5180 2970 663 5480 4192 4949 1 1387 4428 5180 2761 样例输出 9

给出一串数字，问某个数字K在该序列中是第几小的。 最简单的解法，遍历一遍数组，找出比K小的数的个数n，则K是第n+1小的数。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int main() { scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; int ans = 0; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; if (a[i] < k) ans++; } if (!is_exist) printf("-1\n"); else printf("%d\n", ans + 1); return 0; } [/cpp] 本代码提交AC，用时58MS，内存3MB。 但是题意显然不是用这种方法，为了配合下一题的求第k小数，提示使用快排的中间步骤，依次将序列划分成比某个数大和比某个数小的两部分，再在其中某个子序列中递归求解。完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<vector> using namespace std; vector<int> a; int n, k; int GetOrder(int p, int q) { int m = a[p]; int i = p, j = q; while (i < j) { while (i < j&&a[j] > m) j–; a[i] = a[j]; while (i < j&&a[i] < m) i++; a[j] = a[i]; } if (k == m) return i; else if (k < m) return GetOrder(p, i – 1); else return GetOrder(i + 1, q); } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &k); a.resize(n); bool is_exist = false; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); if (a[i] == k) is_exist = true; } if (!is_exist) printf("-1\n"); else printf("%d\n", GetOrder(0, n – 1) + 1); return 0; } [/cpp] 本代码提交AC，用时57MS，内存3MB。]]>

hihoCoder 1124-好矩阵

Leave a reply

hihoCoder 1124-好矩阵 #1124 : 好矩阵 时间限制:3000ms 单点时限:1000ms 内存限制:256MB 描述 给定n, m。一个n × m矩阵是好矩阵当且仅当它的每个位置都是非负整数，且每行每列的和 ≤ 2。求好矩阵的个数，模$$10^9$$ + 7 输入 第一行一个整数T，表示测试点个数。下面T个测试点。每个测试点一行，包含两个整数n，m。1 ≤ T ≤ $$10^4$$. 1 ≤ n, m ≤ 100. 输出 T行。每行是对应测试点的答案。 样例输入 1 2 2 样例输出 26

这一题的题意也很明确，如果是单个测试数据，可以考虑用DFS，但是本题测试数据最多有$$10^4$$，当n和m不同时，DFS的结果不能复用，所以超时妥妥的。 要想中间结果复用，一定是DP，所以考虑用DP来做，我是参考了题解和此博客。 完整代码如下： [cpp] #include<iostream> #include<cstdio> using namespace std; const int kMaxMN = 105, kMod = 1000000007; typedef long long ll; ll f[kMaxMN][kMaxMN][kMaxMN]; ll ans[kMaxMN][kMaxMN]; void Init() { for (int m = 1; m < kMaxMN; m++) { for (int n = 0; n < kMaxMN; n++) for (int a = 0; a <= m; a++) for (int b = 0; a + b <= m; b++) f[n][a][b] = 0; f[0][m][0] = 1; for (int n = 1; n < kMaxMN; n++) { //f[n][m][0] = 1;//如果f[n-1][m][0]=0，即不存在全为0的情况，则f[n][m][0]不等于1而是等于0 for (int a = 0; a <= m; a++) { for (int b = 0; a + b <= m; b++) { f[n][a][b] += f[n – 1][a][b];//(1) f[n][a][b] %= kMod; if (a > 0) { //(2.1) f[n][a – 1][b + 1] += (ll)a*f[n – 1][a][b]; f[n][a – 1][b + 1] %= kMod; //(4) f[n][a – 1][b] += (ll)a*f[n – 1][a][b]; f[n][a – 1][b] %= kMod; } if (b > 0)//(2.2) { f[n][a][b – 1] += (ll)b*f[n – 1][a][b]; f[n][a][b – 1] %= kMod; } if (a > 1)//3.1 { f[n][a – 2][b + 2] += (ll)(a*(a – 1) / 2)*f[n – 1][a][b]; f[n][a – 2][b + 2] %= kMod; } if (a > 0 && b > 0)//3.2 { f[n][a – 1][b] += (ll)a*(ll)b*f[n – 1][a][b]; f[n][a – 1][b] %= kMod; } if (b > 1)//3.3 { f[n][a][b – 2] += (ll)(b*(b – 1) / 2)*f[n – 1][a][b]; f[n][a][b – 2] %= kMod; } } } ans[n][m] = 0; for (int a = 0; a <= m; a++) { for (int b = 0; a + b <= m; b++) { ans[n][m] += f[n][a][b]; ans[n][m] %= kMod; } } } } } int main() { Init(); int t,n,m; scanf("%d", &t); while (t–) { scanf("%d %d", &n, &m); printf("%lldn", ans[n][m]); } return 0; } [/cpp] 转换情况较多，代码和题解对照查看。 本代码提交AC，用时1698MS，内存9MB。]]>