训练营3，

切割木棒

分数 10

全屏浏览

切换布局

作者 HBU_DS_刘哲轩_赵润朔

单位 河北大学

黑涩会老大Arbalest给了Rain Sure一个长度为n的木棒，要求他求出将这个木棒切割为12段(每段的长度必须是一个正整数)的方案数。

Rain Sure表示这个问题太简单了，请你帮他求出答案。

输入格式

输入为一个正整数表示n。

12≤n≤200

输出格式

请你输出方案数

测试样例一 12 1 测试样例二 13 12 测试样例三 17 4368 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 205; int f[N][13]; signed main() { int n; cin >> n; for(int i = 0; i < N; i++) { for(int j = 0; j <= i && j < 13; j++) { if(!j) f[i][j] = 1; else f[i][j] = f[i - 1][j - 1] + f[i - 1][j]; } } cout << f[n - 1][11]; }

买木棒

分数 20

全屏浏览

切换布局

作者 HBU_DS_刘哲轩_赵润朔

单位 河北大学

Rain Sure同学想去商店买木棒，他需要长度1 ~ n的木棒各一个。商店现在有长度为1 ~ n+1的木棒各一个，且售价均为1元。

Rain Sure买下一个木棒后，可以回家将它分成任意多段，比如一根长度为L的木棒，如果将其分成k段，长度分别为L1​,L2​,⋯,Lk​，需要满足L1​+L2​+⋯+Lk​=L。

Rain Sure想要花尽可能少的钱得到长度为1 ~ n的木棒各一个，请你帮他算出他最少需要花多少钱。

输入格式

输入一个正整数，代表n。

1≤n≤1018

输出格式

输出最少需要花费多少钱。

测试样例一 4 3 测试样例二 109109109109109109 109109108641970782 #include <bits/stdc++.h> using namespace std; #define int long long signed main() { int n; cin >> n; int sum = n + 1; int i = 1; while(sum >= i) { sum -= i; i++; } cout << n - i + 2; }

旅游规划

分数 25

全屏浏览

切换布局

作者 陈越

单位 浙江大学

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第 1 行给出 4 个正整数 n、m、s、d，其中 n（2≤n≤500）是城市的个数，顺便假设城市的编号为 0~(n−1)；m 是高速公路的条数；s 是出发地的城市编号；d 是目的地的城市编号。随后的 m 行中，每行给出一条高速公路的信息，分别是：城市 1、城市 2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过 500。输入保证解的存在。

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例: 4 5 0 3 0 1 1 20 1 3 2 30 0 3 4 10 0 2 2 20 2 3 1 20 输出样例: 3 40 #include <bits/stdc++.h> using namespace std; const int N = 505, M = N * 2; // struct node // { // dist, cost; // }g[N][N]; int n, m, s, d; int g[N][N], c[N][N]; typedef pair<int, int> pii; // int h[N], e[M], ne[M], idx, w[M], c[M]; int dist[N], cost[N], st[N]; priority_queue<pii, vector<pii>, greater<pii>> heap; // void add(int a, int b, int g, int f) // { // e[idx] = b, ne[idx] = h[a], w[idx] = g, c[idx] = f, h[a] = idx++; // } void dijkstra() { // heap.push({0, s}); memset(dist, 0x3f, sizeof(dist)); // memset(cost, 0, sizeof(cost)); dist[s] = 0; // while(!heap.empty()) // { // auto t = heap.top(); // int ver = t.second; // heap.pop(); // if(!st[ver]) // { // st[ver] = true; // for(int i = h[ver]; i != -1; i = ne[i]) // { // int j = e[i]; // if(dist[j] > dist[ver] + w[i]) // { // dist[j] = dist[ver] + w[i]; // cost[j] = cost[ver] + c[i]; // heap.push({dist[j], j}); // } // else if(dist[j] == dist[ver] + w[i]) // { // if(cost[j] > cost[ver] + c[i]) // cost[j] = cost[ver] + c[i]; // } // } // } // } for(int i = 0; i < n; i++) { int t = -1; for(int j = 0; j < n; j++) { if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j; } st[t] = true; for(int j = 0; j < n; j++) { if(dist[j] > dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j] ; cost[j] = cost[t] + c[t][j] ; } else if(dist[j] == dist[t] + g[t][j]) { if(cost[j] > cost[t] + c[t][j]) cost[j] = cost[t] + c[t][j] ; } } } cout << dist[d] << " " << cost[d]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // memset(h, -1 ,sizeof(h)); memset(g, 0x3f, sizeof(g)); memset(c, 0x3f, sizeof(c)); cin >> n >> m >> s >> d; while(m--) { int a, b,e, f; cin >> a >> b >> e >> f; // add(a, b, e, f); // add(b, a, e, f); g[a][b] = g[b][a] = min(e, g[a][b]); c[a][b] = c[b][a] = min(f, c[a][b]); } dijkstra(); }

热水器

分数 15

全屏浏览

切换布局

作者 HBU_DS_刘哲轩_赵润朔

单位 河北大学

C1教学楼的5楼有一个热水器，学生们可以在课间来这里接热水喝。

这个热水器可以在每分钟提供W升的热水。

现在有n名同学来这里打水，第i名同学打算在Si​ ~ Ti​(不包括第Ti​分钟)的时间内接热水，每分钟接走Pi​的热水。热水器并不会储存热水，也就是说每分钟只有W升的热水，可以多名同学在同一分钟同时接水。

现在请你判断这个热水器能不能满足所有同学的打水的需求呢？

输入格式

第一行两个正整数，分别代表n和W.

后面n行，每行三个整数，分别为Si​,Ti​,Pi​。

1≤n≤2×105

0≤Si​≤Ti​≤2×105

1≤Wi​,Pi​≤109

所有输入均为整数

输出格式

如果可以满足所有同学的打水的需求，输出Yes，否则输出No。

测试样例一 4 10 1 3 5 2 4 4 3 10 6 2 4 1 No 测试样例二 4 10 1 3 5 2 4 4 3 10 6 2 3 1 Yes 测试样例三 6 1000000000 0 200000 999999999 2 20 1 20 200 1 200 2000 1 2000 20000 1 20000 200000 1 Yes #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; #define int long long int n, w; unordered_map<int, int> mp; int b[N]; void insert(int l , int r, int c) { b[l] += c; b[r + 1] -= c; } signed main() { cin >> n >> w; int flag = 0; int mx = 0; // fill(b, b + N, w); for(int i = 0; i < N; i++) { insert(i, i, w); } while(n--) { int s, t, p; cin >> s >> t >> p; // for(int i = s; i < t; i++) // { // mp[i] += p; // if(mp[i] > w) flag = true; // } insert(s, t - 1, -p); // mx = max(mx, t + 1); } for(int i = 0; i < N; i++) { if(i) b[i] += b[i - 1]; if(b[i] < 0) { flag = true; break; } } // for(auto &it : mp) // cout << it.first << " " << it.second << endl; if(flag) cout << "No" << endl; else cout << "Yes" << endl; return 0; }

最短工期

分数 25

全屏浏览

切换布局

作者 陈越

单位 浙江大学

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：

首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：

如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1： 9 12 0 1 6 0 2 4 0 3 5 1 4 1 2 4 1 3 5 2 5 4 0 4 6 9 4 7 7 5 7 4 6 8 2 7 8 4 输出样例 1： 18 输入样例 2： 4 5 0 1 1 0 2 2 2 1 3 1 3 4 3 2 5 输出样例 2： Impossible #include <iostream> #include <cstring> using namespace std; const int N=510; int res; int n,m; int dist[N]; int g[N][N]; bool st[N]; void dijkstra() { // memset(dist,-1,sizeof(dist)); dist[0]=0; for(int i=0;i<n;i++) { int t=-1; for(int j=0;j<n;j++) { if(!st[j]&&(t==-1||dist[j]>dist[t])) { t=j; } } // st[t]=true; for(int j=0;j<n;j++) { dist[j]=max(dist[j],dist[t]+g[t][j]); // cout << j << " " << dist[j] << endl; } } int flag = 1; for(int i = 0; i < n; i++) { // cout << i << " "<< dist[i] << endl; if(dist[i] == -1) { flag = false; break; } res = max(res, dist[i]); } if(!flag) cout << "Impossible"; else cout << res << endl; } int main() { memset(g, -1,sizeof(g)); cin>>n >>m; while(m--) { int x,y,z; cin>>x>>y>>z; g[x][y]=max(g[x][y],z); } dijkstra(); }

这是二叉搜索树吗？

分数 25

全屏浏览

切换布局

作者 陈越

单位 浙江大学

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

其左子树中所有结点的键值小于该结点的键值；其右子树中所有结点的键值大于等于该结点的键值；其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1： 7 8 6 5 7 10 8 11 输出样例 1： YES 5 7 6 8 11 10 8 输入样例 2： 7 8 10 11 8 6 7 5 输出样例 2： YES 11 8 10 7 5 6 8 输入样例 3： 7 8 6 8 5 10 9 11 输出样例 3： NO #include <bits/stdc++.h> using namespace std; const int N = 1010; int n; int pre[N], in[N], post[N]; bool dfs(int pl, int pr, int il, int ir, bool type) { int root = pre[pl]; int k; if(!type) { for(int i = il, i <= ir; i++) { if(in[i] == root) { k = i; break; } if(k > ir) return false; } } else if(type) { for(int i = ir, i >= il; i--) { if(in[i] == root) { k = i; break; } if(k < il) return false; } } if(!dfs(pl +1, k - il + pl , il, k -1, type)) return false; if(!dfs(k - il + pl + 1, pr, k + 1, ir, type)) return false; post[cnt++] = root; return true; } int main() { cin >> n; for(int i = 0; i < n; i++) cin >> pre[i] , in[i] = pre[i]; sort(in, in + n); if(dfs(0, n - 1, 0, n -1 , 0)) { cout << "YES" << endl; for(int i = 0; i < n; i++) { if(i) cout << " "; cout << post[i]; } } else { reverse(in, in + n); if(dfs(0, n - 1, 0, n -1 , 1)) { cout << "YES" << endl; for(int i = 0; i < n; i++) { if(i) cout << " "; cout << post[i]; } } else cout << "NO"; } }

哈利·波特的考试

分数 25

全屏浏览

切换布局

作者 陈越

单位 浙江大学

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是 haha，将老鼠变成鱼的魔咒是 hehe 等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如 ahah 可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒 lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。

现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念 4 个字符；而如果带猫去，则至少需要念 6 个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:

输入说明：输入第 1 行给出两个正整数 n (≤100)和 m，其中 n 是考试涉及的动物总数，m 是用于直接变形的魔咒条数。为简单起见，我们将动物按 1~$$n编号。随后m行，每行给出了3个正整数，分别是两种动物的编号、以及它们之间变形需要的魔咒的长度(\le 100$$)，数字之间用空格分隔。

输出格式:

输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出 0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例: 6 11 3 4 70 1 2 1 5 4 50 2 6 50 5 6 60 1 3 70 4 6 60 3 6 80 5 1 100 2 4 60 5 2 80 输出样例: 4 70

#include <iostream> #define INF 0x3f3f3f3f //定义INF作为两点之间不相连的标志 using namespace std; int Matrix[101][101]; //定义邻接矩阵 void Floyd(int n){ //弗洛伊德算法求所有点的所有最小路径 for(int u=1; u <= n; u++){ //第一层循环遍历所有点 for(int v=1; v <= n; v++){ //二三层循环遍历邻接矩阵，按照权重找出u到所有点的最小路径 for(int w=1; w <= n; w++){ if(Matrix[v][w] > Matrix[v][u] + Matrix[u][w]){//v->w的距离大于v->u->v Matrix[v][w]= Matrix[v][u] + Matrix[u][w]; // Matrix[w][v]= Matrix[v][u] + Matrix[u][w]; } } } } } void findAnimal(int n){ //找到所需的动物 int needV=0,needMax=INF; //所需点的坐标，所需点的最长路径 for(int u=1; u <= n; u++){ //第一层循环遍历所有点 int maxLen=0; //u的最大路径 for(int v=1; v <= n; v++){ //遍历u到所有点的所有路径，找到最大路径 if(Matrix[v][u] == INF){ //如果图不连通，直接输出0，注意对角线上的点为INF cout<<0<<endl; return; } else if(Matrix[v][u]>maxLen) //找u点的最大路径 maxLen=Matrix[v][u]; } if(maxLen<needMax){ //找到所有点的最大路径中的最小值，并记录该点 needMax=maxLen; needV=u; } } cout << needV << ' ' << needMax << endl; } void iniMatrix(int n, int e){ //初始化邻接矩阵 int x,y,w; while (e--){ cin>>x>>y>>w; Matrix[x][y]=w; Matrix[y][x]=w; } for(int i=1; i <= n; i++){ for(int j=1; j <= n; j++){ if(!Matrix[i][j]&& i!=j) //注意对角线上的点不要设为INF，可以省不少麻烦 Matrix[i][j]=INF; } } } int main(){ int n,e; cin >> n >> e; iniMatrix(n, e); Floyd(n); findAnimal(n); }

 HBU最亮的崽

分数 5

全屏浏览

切换布局

作者 HBU_DS-李振浩-赵润朔

单位 河北大学

HBU的孩子们都有一个梦想，那就是成为学校中中最受欢迎的人。在N(1<=N<=10000)个孩子中，你会得到M(1<=M<=50000)对(A，B)的有序排列，即A认为B是受欢迎的。并且受欢迎是传递的，如果A认为B是受欢迎的，B认为C是受欢迎的，那么A也会认为C是受欢迎的

输入格式:

第一行: 两个正整数N和M

第二行到1+M行: 每行两个正整数A,B,即A认为B是受欢迎的

输出格式:

共一行，即受到所有人欢迎的学生的数量。

输入样例:

在这里给出一组输入。例如：

3 3 1 2 2 1 2 3 输出样例:

在这里给出相应的输出。例如：

1

代码长度限制

16 KB

时间限制

400 ms

内存限制

512 MB

栈限制

#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int n, m; int rd[N]; int cnt; set<int> vet[N]; int main() { cin >> n >> m; while(m--) { int a, b; cin >> a >> b; vet[a].insert(b); } for(int i = 1; i <= n; i++) { if(vet[i].size() >= n - 1) cnt++; } cout << cnt << endl; }

铺设网线

分数 65

全屏浏览

切换布局

作者 HBU_DS-李振浩-刘哲轩

单位 河北大学

阿生想在宿舍连上HBU的VIP专属校园网。不幸的是，他的账号无法通过WIFI连接，所以他需要架设一些连接学校路由器到所在宿舍所需的网线。

学校免费提供N台可用的路由器，编号为1⋯N，位于学校到阿生宿舍之间，它们之间没有网线连接。

此外，学校还提供了P根网线,第i根网线可以连接两个不同的路由器Ai​和Bi​，长度为Li​（1≤Li​≤1000000。1号路由器已连接到校园网，阿生宿舍路由器编号为N。

同时，学校愿意在P根网线中为阿生提供K(0≤K<N)条免费网线。也就是说，阿生需要连到校园网，需要的网线不大于K的话，阿生可以免费连接，否则，他需要支付除去K条网线之外的最长的一个网线的价格，输出该网线对应的长度即可，没有则输出0。

输入格式:

第1行：三个整数：N、P和K

第2行到第P+1:第i+1行包含三个空格分隔的整数：Ai、Bi和Li

输出格式:

共1行：一个整数，阿生可以支付的最低金额。如果无法连接到校园网，请打印-1。

输入样例:

在这里给出一组输入。例如：

5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6 输出样例:

在这里给出相应的输出。例如：

4

#include <iostream> #include <vector> #include <deque> #include <climits> #include <tuple> using namespace std; int main() { int N, P, K; cin >> N >> P >> K; vector<tuple<int, int, int>> edges; int maxL = 0; for (int i = 0; i < P; ++i) { int a, b, l; cin >> a >> b >> l; edges.emplace_back(a, b, l); if (l > maxL) maxL = l; } int left = 0, right = maxL, ans = -1; while (left <= right) { int mid = (left + right) / 2; vector<vector<pair<int, int>>> adj(N + 1); for (const auto& e : edges) { int a = get<0>(e), b = get<1>(e), l = get<2>(e); int w = (l > mid) ? 1 : 0; adj[a].emplace_back(b, w); adj[b].emplace_back(a, w); } deque<int> q; vector<int> dist(N + 1, INT_MAX); dist[1] = 0; q.push_back(1); while (!q.empty()) { int u = q.front(); q.pop_front(); for (const auto& p : adj[u]) { int v = p.first, w = p.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (w == 0) { q.push_front(v); } else { q.push_back(v); } } } } if (dist[N] <= K) { ans = mid; right = mid - 1; } else { left = mid + 1; } } cout << ans << endl; return 0; }

 奇数平方和

分数 10

全屏浏览

切换布局

作者 usx程序设计类课程组

单位 绍兴文理学院

输入一个奇数n，请计算：12+32+52+……+n2。测试数据保证最终结果不会超出263−1。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据输入一个奇数n。

输出格式:

对于每组测试，输出奇数的平方和。

输入样例: 3 输出样例: 10 说明:

请注意：运算的中间结果可能会超出263−1，但不会超出264−1。

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 7e6 + 10; int a[N]; signed main() { for(int i = 1; i <= N; i+= 2) { a[i] = a[i - 2] + i * i; // cout << a[i] << endl; } int n; while(cin >> n) { cout << a[n] << endl; } }