A-Card Stacking
示例1
3 9 2
3 7 8
题目大意 ：N个人， M张牌， （M一定能整除N）， 每发一张牌就将牌顶的P张牌放到牌堆底部，从小到大输出最后一个人获得的牌
思路 ： 直接模拟就好
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e2 + 5; queue <int> q; set <int> st; int n, k, p, cnt, ans = 1, temp; int main() { cin >> n >> k >> p; cnt = k / n; // 每个人cnt张牌 for (int i = 1; i <= k; i++) q.push(i); //入队 while (!q.empty()) { if (st.size() == cnt) break; for (int i = 1; i < n; i++) { // 发牌给前面的人并洗牌 q.pop(); // 发牌，不需要记录 for (int j = 0; j < p; j++) { // 洗牌 temp = q.front(); q.pop(); q.push(temp); } } st.insert(q.front()); // 加入 q.pop(); if (q.size()) { for (int j = 0; j < p; j++) { // 洗牌 temp = q.front(); q.pop(); q.push(temp); } } } for (auto it : st) cout << it << endl; return 0; }B-Bookshelf
64bit IO Format: %lld
Farmer John recently bought a bookshelf for cow library, but the shelf is getting filled up quite quickly, and now the only available space is at the top. Each of the N cows (1 <= N <= 20,000) has some height of Hi (1 <= Hi <= 10,000) and a total height summed across all N cows of S. The bookshelf has a height of B (1 <= B <= S < 2,000,000,007). To reach the top of the bookshelf taller than the tallest cow, one or more of the cows can stand on top of each other in a stack, so that their total height is the sum of each of their individual heights. This total height must be no less than the height of the bookshelf. Since more cows than necessary in the stack can be dangerous, your job is to find the set of cows that produces a stack of the smallest number of cows possible such that the stack can
示例1
6 40 6 18 11 13 19 11
3
题目大意 ： 输入N个数， 输出和小于等于M的数的最大值
思路 ：排序模拟
AC代码 ：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e4 + 5; ll p[MAXN], n, k, ans, sum; int main() { cin >> n >> k; for (ll i = 0; i < n; i++) cin >> p[i]; sort(p, p + n); for (ll i = n - 1; i >= 0; i--) { ans += p[i], sum++; if (ans >= k) break; } cout << sum << endl; return 0; }C-Bookshelf 2
Farmer John recently bought another bookshelf for the cow library, but the shelf is getting filled up quite quickly, and now the only available space is at the top. FJ has N cows (1 <= N <= 20) each with some height of Hi (1 <= Hi <= 1,000,000 - these are very tall cows). The bookshelf has a height of B (1 <= B <= S, where S is the sum of the heights of all cows). To reach the top of the bookshelf, one or more of the cows can stand on top of each other in a stack, so that their total height is the sum of each of their individual heights. This total height must be no less than the height of the bookshelf in order for the cows to reach the top. Since a taller stack of cows than necessary can be dangerous, your job is to find the set of cows that produces a stack of the smallest height possible such that the stack can reach the bookshelf. Your program should print the minimal 'excess' height between the optimal stack of cows and the bookshelf.
示例1
5 16 3 1 3 5 6
1
题目大意 ： 输入N个数， 选取其中部分数， 和大于M并使二者差值最小
思路 ： 01背包问题
AC代码 ：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6 + 5; ll p[MAXN], dp[MAXN], n, k, V; int main() { cin >> n >> k; for (ll i = 1; i <= n; i++) { cin >> p[i]; V += p[i]; } for (ll i = 1; i <= n; i++) { for (ll j = V; j >= p[i]; j--) dp[j] = max(dp[j], dp[j - p[i]] + p[i]); } for (int i = 1; i <= V; i++) { if (dp[i] >= k) { cout << dp[i] - k << endl; return 0; } } return 0; }D-迷路的牛
Farmer John的三头获奖奶牛Bessie、Elsie和Mildred，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据三个相邻的位置（例如，位置6、7、8）。
不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。
请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。
示例1
4 7 9
1 2
输入的数在[1,10^9]范围内
题目大意 ： 输入三个数分别表示三个数所在的位置，输出最小和最大的操作次数，使三者满足a + 1 == b， b + 1 == c， 每次只能让两边的数放入中间
思路 ： 最小操作次数只有三种情况，0， 1， 2。 要么已经分好， 要么差一步分好， 要么差的很远（差的远也可以将最外边的数移到我们想要的地方）， 剩下最大的情况就是两个数交替向中间靠拢
AC代码 ：
#include<bits/stdc++.h> typedef long long ll; using namespace std; ll ai, bi, ci; int main() { cin >> ai >> bi >> ci; if (ai + 1 == bi && ai + 2 == ci) cout << 0 << endl; else if (ai + 2 == bi || bi + 2 == ci) cout << 1 <<endl; else cout << 2 << endl; cout << max(bi - ai, ci - bi) - 1 << endl; return 0; }E-对牛排序
Farmer John正在尝试将他的N头奶牛（1≤N≤100），方便起见编号为1…N，在她们前往牧草地吃早餐之前排好顺序。
当前，这些奶牛以p1,p2,p3,…,pN的顺序排成一行，Farmer John站在奶牛p1前面。他想要重新排列这些奶牛，使得她们的顺序变为1,2,3,…,N奶牛1在Farmer John旁边。
今天奶牛们有些困倦，所以任何时刻都只有直接面向Farmer John的奶牛会注意听Farmer John的指令。每一次他可以命令这头奶牛沿着队伍向后移动k步，k可以是范围1…N−1中的任意数。她经过的k头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。
例如，假设N=4，奶牛们开始时是这样的顺序：
FJ: 4, 3, 2, 1唯一注意FJ指令的奶牛是奶牛4。当他命令她向队伍后移动2步之后，队伍的顺序会变成：
FJ: 3, 2, 4, 1现在唯一注意FJ指令的奶牛是奶牛3，所以第二次他可以给奶牛3下命令，如此进行直到奶牛们排好了顺序。
Farmer John急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出将奶牛们排好顺序所需要的最小操作次数。
示例1
4 1 2 4 3
3
题目大意 ： 需要将N头牛按递增排序， 一个人站在左边，所有牛面朝他， 每次只能将排头的牛移动任意步，输出最小需要多少次移动才可以排好序
思路 ： 每个数从左往右， 找第一个比他小的数，记录下标，输出最后的下标（因为当你找到这样的数时，前面已经排好队了）
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e2 + 5; int p[MAXN], n, ans; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> p[i]; for (int i = 1; i < n; i++) { for (int j = i + 1; j <= n; j++) { if (p[i] > p[j]) ans = i; } } cout << ans << endl; return 0; }F-Mud Puddles
Farmer John is leaving his house promptly at 6 AM for his daily milking of Bessie. However, the previous evening saw a heavy rain, and the fields are quite muddy. FJ starts at the point (0, 0) in the coordinate plane and heads toward Bessie who is located at (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500). He can see all N (1 ≤ N ≤ 10,000) puddles of mud, located at points (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) on the field. Each puddle occupies only the point it is on. Having just bought new boots, Farmer John absolutely does not want to dirty them by stepping in a puddle, but he also wants to get to Bessie as quickly as possible. He's already late because he had to count all the puddles. If Farmer John can only travel parallel to the axes and turn at points with integer coordinates, what is the shortest distance he must travel to reach Bessie and keep his boots clean? There will always be a path without mud that Farmer John can take to reach Bessie.
示例1
1 2 7 0 2 -1 3 3 1 1 1 4 2 -1 1 2 2
11
题目大意 ： 输入坐标轴上的若干个点，表示该点不可走， 每次只能朝上下左右 四个方向走， 输出起点到终点的最短路
思路 ： 将每个数的左边 + 505， 就可以用数组存了， 然后直接裸的BFS，注意边界处要扩大一圈
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e4 + 5; const int INF = 0x3f3f3f3f; struct node { int x, y, step; }; int ex, ey, ab = -INF, be = INF, ri = -INF, le = INF, n; int dir[4][2] = { 1, 0, -1, 0, 0, 1, 0, -1 }; bool vis[MAXN][MAXN], mp[MAXN][MAXN]; queue <node> q; void bfs() { q.push({ 505, 505, 0 }); while (!q.empty()) { node now = q.front(); q.pop(); if (now.x == ex && now.y == ey) { cout << now.step << endl; return; } for (int i = 0; i < 4; i++) { int xx = now.x + dir[i][0]; int yy = now.y + dir[i][1]; if (xx >= le && xx <= ri && yy >= be && yy <= ab && !vis[xx][yy] && !mp[xx][yy]) { vis[xx][yy] = 1; q.push({ xx, yy, now.step + 1 }); } } } } int main() { cin >> ex >> ey >> n; ex += 505, ey += 505; for (int i = 0; i < n; i++) { int ui, vi; scanf("%d%d", &ui, &vi); ui += 505, vi += 505; ab = max(ab, vi), ri = max(ri, ui); be = min(be, vi), le = min(le, ui); mp[ui][vi] = 1; } ab++, ri++, be--, le--; // 边界扩大一圈 bfs(); return 0; }G-Cow Yahtzee
奶牛们以它们一贯笨拙的方式玩Yahtzee，一种掷骰子的游戏。他们掷N次(1 <= N <= 20) S(1 <= S <= 8)面骰子。他们对于能满足一定标准的掷出骰子的结果的数量很感兴趣（类似“包含3个2”或者“包含一个2和两个3”）。 教他们学会概率。写一个程序，不仅读入N和S，而且还有一些说明这些标准的表达式。从骰子的所有可能的组合中找出符合表达式要求的组合的数量（3个2面骰子所有可能的组合是 {1,1,1; 1,1,2; 1,2,1; 1,2,2; 2,1,1; 2,1,2; 2,2,1; 2,2,2};）。 这种组合的最基本的形式表达了“希望至少有W份R”看上去像这样： WxR 这里满足(0 <= W <= N and 1 <= R <= S)。每次检验运行提供E个表达式(1 <= E <= 20)，每个包含1~10个由“+”分割的基本形式。“+”表示“且”(看下面)。行与行之间的关系是“或者”。这样，下面所示的表达式的意思是：“至少有三个5 或者 同时至少有1个3和至少2个4”： 3x5 1x3+2x4 这里有一些满足上述条件的4个5面骰可能的情况：5,5,5,1; 4,5,5,5; 3,4,4,2; 3,4,4,3;3,4,4,5; 4,4,5,3。 注意：确保你能从一行中读取2个整数并在下一行中能读取一个字符串。对有某些语言的I/O设计来说，这比看上去的更难。 同时注意所有骰子可能的组合数在提供的测试数据里不会超过1,512,768。
示例1
4 5 2 3x5 1x3+2x4
63
题目大意 ： 输入N行，行与行之间是或的关系， 每行里面是和的关系， 输出有多少种排列方式
思路： 直接暴力， 满足条件就 + 1， 用一个二维数组维护， 左表示行，右表示数字，值表示个数，这样就可以将或与和的关系体现出来了
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 30 + 5; int a[MAXN][MAXN], b[MAXN], c[MAXN]; int n, m, k, ans; string line; void dfs(int x) { if (x == n + 1) { memset(c, 0, sizeof(c)); for (int i = 1; i <= n; i++) c[b[i]]++; for (int i = 1; i <= k; i++) { bool flag = 1; for (int j = 1; j <= m; j++) { if (a[i][j] > c[j]) { flag = 0; break; } } if (flag) { ans++; return; } } } else { for (int i = 1; i <= m; i++) { b[x] = i; dfs(x + 1); } } } int main() { cin >> n >> m >> k; for (int i = 1; i <= k; i++) { cin >> line; for (int j = 0; j < line.size(); j+= 4) a[i][line[j + 2] - '0'] = line[j] - '0'; } dfs(1); cout << ans << endl; return 0; }H-Charm Bracelet
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880). Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
示例1
4 6 1 4 2 6 3 12 2 7
23
题目大意 ： 01背包模板题
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e4 + 5; int dp[MAXN], p[MAXN], val[MAXN], n, V; int main() { cin >> n >> V; for (int i = 1; i <= n; i++) cin >> p[i] >> val[i]; for (int i = 1; i <= n; i++) { for (int j = V; j >= p[i]; j--) dp[j] = max(dp[j], dp[j - p[i]] + val[i]); } cout << dp[V] << endl; return 0; }J-Sightseeing Cows
链接：https://ac.nowcoder.com/acm/contest/993/J 来源：牛客网
Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time. Fortunately, they have a detailed city map showing the L (2 ≤ L ≤ 1000) major landmarks (conveniently numbered 1.. L) and the P (2 ≤ P ≤ 5000) unidirectional cow paths that join them. Farmer John will drive the cows to a starting landmark of their choice, from which they will walk along the cow paths to a series of other landmarks, ending back at their starting landmark where Farmer John will pick them up and take them back to the farm. Because space in the city is at a premium, the cow paths are very narrow and so travel along each cow path is only allowed in one fixed direction. While the cows may spend as much time as they like in the city, they do tend to get bored easily. Visiting each new landmark is fun, but walking between them takes time. The cows know the exact fun values Fi (1 ≤ Fi ≤ 1000) for each landmark i. The cows also know about the cowpaths. Cowpath i connects landmark L1iL1i to L2iL2i (in the direction L1iL1i -> L2iL2i ) and requires time Ti (1 ≤ Ti ≤ 1000) to traverse. In order to have the best possible day off, the cows want to maximize the average fun value per unit time of their trip. Of course, the landmarks are only fun the first time they are visited; the cows may pass through the landmark more than once, but they do not perceive its fun value again. Furthermore, Farmer John is making the cows visit at least two landmarks, so that they get some exercise during their day off. Help the cows find the maximum fun value per unit time that they can achieve.
示例1
5 7 30 10 10 5 10 1 2 3 2 3 2 3 4 5 3 5 2 4 5 5 5 1 3 5 2 2
6.00
题目大意 ： 输入一个有向图， 每个点有权值， 每条边有权值， 存在环使得该环上点权值之和比上边权值之和最大， 输出该值
思路： spfa + 01规划
AC代码 ：
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int INF = 0x3f3f3f3f; struct node { int v, w, next; double wi; }e[MAXN]; int head[MAXN], scnt[MAXN], val[MAXN], n, m, cnt; double dis[MAXN]; bool vis[MAXN]; void add(int from, int to, int dis) { e[++cnt].v = to; e[cnt].w = dis; e[cnt].next = head[from]; head[from] = cnt; } bool spfa(double r) { queue <int> q; memset(scnt, 0, sizeof(scnt)); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) dis[i] = INF; q.push(1); dis[1] = 0.0, vis[1] = 1; while (!q.empty()) { int ans = q.front(); q.pop(); scnt[ans]++, vis[ans] = 0; if (scnt[ans] >= n) return true; for (int i = head[ans]; i != -1; i = e[i].next) { double sum = e[i].w * r - val[e[i].v]; // 更新权值 if (dis[e[i].v] > dis[ans] + sum) { dis[e[i].v] = dis[ans] + sum; if (!vis[e[i].v]) { vis[e[i].v] = 1; q.push(e[i].v); } } } } return false; } int main() { cin >> n >> m; memset(head, -1, sizeof(head)); for (int i = 1; i <= n; i++) scanf("%d", &val[i]); // 点权值 for (int i = 0; i < m; i++) { int ui, vi, wi; scanf("%d%d%d", &ui, &vi, &wi); add(ui, vi, wi); } double l = 0, r = INF * 1.0, mid; for (int i = 1; i <= 100; i++) { // 二分查找答案 mid = (l + r) / 2; if (spfa(mid)) l = mid; //有负环说明答案在右边 else r = mid; } printf("%.2f\n", mid); return 0; }K-Gourmet Grazers
Like so many others, the cows have developed very haughty tastes and will no longer graze on just any grass. Instead, Farmer John must purchase gourmet organic grass at the Green Grass Grocers store for each of his N (1 ≤ N ≤ 100,000) cows. Each cow i demands grass of price at least Ai (1 ≤ Ai ≤ 1,000,000,000) and with a greenness score at least Bi (1 ≤ Bi ≤ 1,000,000,000). The GGG store has M (1 ≤ M ≤ 100,000) different types of grass available, each with a price Ci (1 ≤ Ci ≤ 1,000,000,000) and a greenness score of Di (1 ≤ Di ≤ 1,000,000,000). Of course, no cow would sacrifice her individuality, so no two cows can have the same kind of grass. Help Farmer John satisfy the cows' expensive gourmet tastes while spending as little money as is necessary.
示例1
4 7 1 1 2 3 1 4 4 2 3 2 2 1 4 3 5 2 5 4 2 6 4 4
12
题目大意 ： 输入N头牛， 每头牛有两个权值，分别为期望的花费和期望的美味值， 有M种食物， 每种食物对应各自的花费与美味值，如果存在一种方案， 可以满足每头牛， 输出最小花费， 否则输出 -1
思路 ： 先按美味值和花费从大到小排序， 美味值优先级高，然后从第一头牛开始， 将美味值大于等于该牛期望的食物的花费加入set， 再二分查找最小的大于该牛期望的花费， 过程中如果有一个不符合条件， 直接退出输出-1
AC代码 ：
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int MAXN = 1e5 + 5; struct node { ll x, y; }e[MAXN], p[MAXN]; bool cmp(node a, node b) { if (a.y == b.y) return a.x > b.x; else return a.y > b.y; } ll n, m, ans, flag = 1; multiset <ll> st; int main() { cin >> n >> m; for (ll i = 1; i <= n; i++) scanf("%lld%lld", &e[i].x, &e[i].y); for (ll i = 1; i <= m; i++) scanf("%lld%lld", &p[i].x, &p[i].y); sort(e + 1, e + n + 1, cmp), sort(p + 1, p + m + 1, cmp); // 美味值优先级大 ll j = 1; // 如果前面的牛都满足， 后面的牛一定也满足 for (ll i = 1; i <= n; i++) { for (; j <= m; j++) { if (p[j].y >= e[i].y) { st.insert(p[j].x); } else break; } multiset <ll> ::iterator it; it = st.lower_bound(e[i].x); if (it == st.end()) { flag = 0; break; } // 不存在直接退出 else { ans += *it; st.erase(it); } } if (flag) cout << ans << endl; else cout << -1 << endl; return 0; }
