buctoj-寒假集训进阶训练赛（二十二）

问题 A: Stones

题目描述
由于自行车状态错误，森普尔开始每天早上从东到西走，每天晚上走回去。走路可能会有点累，所以森普这次总是玩一些游戏。
路上有很多石头，当他遇到一块石头时，如果是他遇到的奇数石头，他会尽可能把它扔到前面，如果是偶数石头，他会把它留在原地。现在给你一些关于路上石头的信息，你要告诉我从起点到森普尔走过后最远的石头的距离。请注意，如果两颗或两颗以上的石头停留在同一位置，您将首先遇到较大的一颗（Di最小的那颗，如输入中所述）。
输入
在第一行中，有一个整数 T（1<=T<=10），这意味着输入文件中的测试用例。然后是 T 测试用例。
对于每个测试用例，我会在第一行给你一个整数 N（0<N<=100，000），这意味着路上的石头数量。然后跟着N条线，行中有两个整数Pi（0<=Pi<=100，000）和Di（0<=Di<=1，000），这意味着第i块石头的位置以及Sempr可以将其扔多远。
输出
只需为一个测试用例输出一行，如 Desc翻录中所述。
样例输入

2
2
1 5
2 4
2
1 5
6 6

样例输出

11
12

思路：首先题里面的奇数往前扔，偶数不动是需要的石子是第几个的奇偶，不是石子位置的奇偶，需要单开一个变量去存。这道题麻烦在于往前扔的石头加入队列也需要跟着一起排序，所以用一个堆去实现。

#include<bits/stdc++.h>
using namespace std;
#define int long longstruct PII{int first;int second;//重新定义 < ,用于堆的排序 //让位置小的，同位置重量大的在前面 friend bool operator<(PII a, PII b){if(a.first == b.first) return a.second > b.second;return a.first > b.first;}
};signed main()
{int t;cin >> t;while(t --){priority_queue<PII> q;int n;cin >> n;for(int i = 0; i < n; i ++ ){int p, d;cin >> p >> d;q.push({p, d});}int cnt = 1;//用于记录当前遇到石子的序号，奇数往前扔PII tmp;while(q.size()){tmp = q.top();q.pop();if(cnt & 1){tmp.first += tmp.second;q.push(tmp);}cnt ++;}cout << tmp.first << endl;}return 0;} 

问题 B: Expedition

题目描述
一群母牛抓住卡车，冒险进入从林深处。不幸的是，司机跑过一块岩石时，卡车的油箱被刺穿。现在，卡车每行驶一段距离，就会泄漏1单位燃油。要修理卡车，母牛需要沿着一条蜿蜓曲折的道路驶向最近的城镇(相距不超过 1000000 单位)。在这条道路上，在城镇和卡车的当前位置之间，有N个(1≤N≤10000）加油站，卡车可以停下来获取更多的燃料（每站1~100 单位)。
从林对人类来说是一个危险的地方，对母牛来说更为危险。因此，母牛希望在前往小镇的途中尽可能少地停下加油。幸运的是，卡车上的油箱容量很大，以至于可以容纳的燃油量实际上没有限制。卡车目前离镇区L单位，有P单位燃料 （1≤P≤1000000）。
确定到达城镇，或者母牛根本无法到达城镇所需的最少停靠站数。
输入
第1行：一个整数N。
第2~N+1行：每行包含两个以空格分隔的整数，用于描述加油站：第一个整数是从城镇到停靠站的距离；第二个整数是该站的可用燃料量。
第N+2行：两个以空格分隔的整数L和P。
输出
第一行：一个整数，给出到达城镇所需的最少燃料停止数量。如果无法到达城镇，则输出-1。
样例输入

4
4 4
5 2
11 5
15 10
25 10

样例输出

2

ssn：感觉应该是英文直接翻译的，读原本外文的题目都是别别扭扭的。
思路：注意所给的加油站的距离是到终点的距离，为了思考方便我转成了到起点的距离。由于到终点的距离是从小到大给的，反过来之后顺序就颠倒了，排一遍序之后是我按顺序遇到的加油站。
把目前油量能到的加油站加入堆，把目前的油量用完还没有到终点就选一个我能到的并且能加油最多量的加油站，以此类推直到到达终点，如果当目前油量耗完没有到达终点并且堆里没有加油站可用了，则就无法到达终点。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 10010;
PII s[N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++){int d, p;cin >> d >> p;s[i] = {d, p};}int L, P;cin >> L >> P;for(int i = 1; i <= n; i ++ ) s[i].first = L - s[i].first;sort(s + 1, s + 1 + n);priority_queue<int> q;int ans = 0, pos = 0, p = P;s[n + 1].first = L;for(int i = 1; i <= n + 1; i ++ ){int dis = s[i].first - pos;while(p - dis < 0){if(q.empty()){puts("-1");return 0;}p += q.top();q.pop();ans ++;}p -= dis;pos = s[i].first;q.push(s[i].second);}cout << ans << endl;return 0;
}

问题 C: Rescue

题目描述
安琪儿被魔族抓住了！他被莫利吉关进了监狱。监狱被描述为N * M（N，M <= 200）矩阵。监狱里有墙、道路和警卫。

安吉尔的朋友想救安吉尔。他们的任务是：接近安吉尔。我们假设“接近安琪儿”是为了到达安琪儿停留的位置。当网格中有警卫时，我们必须杀死他（或她？）才能进入网格。我们假设我们向上、向下、向右、向左移动需要 1 个单位的时间，杀死一个警卫也需要 1 个单位的时间。我们足够强大，可以杀死所有的警卫。

你必须计算接近安吉尔的最短时间。（当然，我们只能向上、向下、向左和向右移动到边界内的相邻网格。
输入
第一行包含两个整数代表 N 和 M.
然后是 N 行，每行都有 M 个字符。“.”代表道路，“a”代表天使，“r”代表安吉尔的每个朋友。（ssn：猜测那x就代表警卫呗）
处理到文件末尾。
输出
对于每个测试用例，程序应输出一个整数，代表所需的最短时间。如果这样的数字不存在，你应该输出一行包含“Poor ANGEL has to stay in the prison all his life.”。

样例输入

7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........

样例输出

13

思路：这种矩阵图应该是典型的广搜题，但还是比较麻烦的，警卫问题还有长度更新问题不知道怎么解决，所以深搜试试，如果爆了再写广搜。
可以看出来不只有一个朋友去救他，但起初我们并不知道从哪个朋友走可以到达终点最短，需要遍历每一个朋友，也就是我从终点出发到达不同顶点的最短距离。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210;
int n, m;
LL minl;
bool st[N][N];
char a[N][N];void dfs(int x, int y, LL len)
{//return条件：越界，访问过，走到了墙里面，外加如果现在len已经比我上一个记录的min大了就不用遍历这条路了 if(x < 0 || x >= n || y < 0 || y >= m || st[x][y] || a[x][y] == '#' || len >= minl) return;if(a[x][y] == 'r'){minl = min(minl, len);return;}if(a[x][y] == 'x') len ++;st[x][y] = true;dfs(x + 1, y, len + 1);dfs(x - 1, y, len + 1);dfs(x, y + 1, len + 1);dfs(x, y - 1, len + 1);st[x][y] = false;}
int main()
{cin >> n >> m;int beginx, beginy;for(int i = 0; i < n; i ++ ){scanf("%s", a[i]);for(int j = 0; j < m; j ++ )if(a[i][j] == 'a') beginx = i, beginy = j;           }LL len = 0;minl = 1e9;dfs(beginx, beginy, len);if(minl == 1e9) cout << "Poor ANGEL has to stay in the prison all his life.";else cout << minl;return 0;
}

问题 D: Oil Deposits

buctoj-2023寒假集训-进阶训练赛（十六）问题E

问题 E: [蓝桥杯2017初赛]分巧克力

题目描述
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

1. 形状是正方形，边长是整数
2. 大小相同
   例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
   当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。

输出
输出切出的正方形巧克力最大可能的边长。

样例输入

2 10
6 5
5 6

样例输出

2

思路：二分，初始设左右分别是切成 1 × 1 和 max × max。如果切成的块数大于等于所需要的k，那就说明还能尝试再切大点，反之就是切的太大了不够分，边长要减少。
补充：对于 left 和 right 更新 +1还是 -1，mid为什么还要再加1的问题属于二分的边界问题，可以搜一下二分这个知识点理解一下，什么时候会出现死循环，理解不了：“if(check(mid))若更新 r = mid,则l = mid + 1;若更新l = mid,则r = mid - 1，同时mid + 1再除2” 背过

#include<bits/stdc++.h>
using namespace std;
#define long long int
typedef pair<int, int> PII;signed main()
{int n, k, d = 0;cin >> n >> k;PII p[n + 1];for(int i = 1; i <= n; i ++ ){int h, w;cin >> h >> w;d = max(d, max(h, w));p[i] = {h, w};}int l = 1, r = d, mid;while(l < r){mid = l + r + 1 >> 1;int cnt = 0;for(int i = 1; i <= n; i ++ )//遍历每一块巧克力能分成多少半径为 mid 的正方形cnt += (p[i].first / mid) * (p[i].second / mid);if(cnt >= k) l = mid;else r = mid - 1;}cout << l;return 0;
}

问题 F: [蓝桥杯2017初赛]购物单

题目描述
小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。
老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。
小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。
你的任务是计算出，小明最少需要取多少现金。

输入
本题无输入，购物单如下，物品名称被隐藏了。

****     180.90       88折
****      10.25       65折
****      56.14        9折
****     104.65        9折
****     100.30       88折
****     297.15        半价
****      26.75       65折
****     130.62        半价
****     240.28       58折
****     270.62        8折
****     115.87       88折
****     247.34       95折
****      73.21        9折
****     101.00        半价
****      79.54        半价
****     278.44        7折
****     199.26        半价
****      12.97        9折
****     166.30       78折
****     125.50       58折
****      84.98        9折
****     113.35       68折
****     166.57        半价
****      42.56        9折
****      81.90       95折
****     131.78        8折
****     255.89       78折
****     109.17        9折
****     146.69       68折
****     139.33       65折
****     141.16       78折
****     154.74        8折
****      59.42        8折
****      85.44       68折
****     293.70       88折
****     261.79       65折
****      11.30       88折
****     268.27       58折
****     128.29       88折
****     251.03        8折
****     208.39       75折
****     128.88       75折
****      62.06        9折
****     225.87       75折
****      12.89       75折
****      34.28       75折
****      62.16       58折
****     129.12        半价
****     218.37        半价
****     289.69        8折

需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。

输出
输出一个整数表示小明要从取款机上提取的金额，单位是元。
思路：用的笨方法手动输入，输入的时候自己把几折换成小数。输出sum自己看一下，然后再手动补成要求的数。

#include<bits/stdc++.h>
using namespace std;int main()
{
//	double sum = 0, a, b;
//	while(cin >> a >> b){
//		sum += a * b;
//	}
//	cout << sum;cout << 5200;return 0;
}

问题 G: 三角函数最优拟合

题目描述
我们称一个数列 {an}\left\{ a_n \right\}{an​} 是"整三角数列" , 当且仅当它符合通项公式:
$a_i=A\cos \left(\pi \cdot i\right)+B\left(A,BϵR,A\ne 0\right)$
现在给出一个数列{bn}\left\{ b_n \right\}{bn​} ,在一次操作内,你可以选择一个数 i,（1 ≤ bi ≤ n）,任意更改 bi 的值.
请你求出将 {bn}\left\{ b_n \right\}{bn​} 改成"整三角数列"的最小操作数.
输入
第一行,输入一个整数 n （2 ≤ n ≤ 10^5，n为偶数）
第二行,输入 n 个整数,代表b1，b2，……，bn（1 ≤ bi ≤ 10^5）
输出
输出一行,一个整数,代表最小操作数
样例输入

4
1 1 2 2

样例输出

2

提示
两次操作，将数列改为{1，2，1，2},此时符合通项公式 $b_i=\frac{1}{2}\cos \left(\pi i\right)+\frac{3}{2}$
思路：（乍一看这题已经点开matlab了）仔细看题，$\cos \left(\pi i\right)$也就是说它只能是 -1 或者 1 。遍历整个数组统计出出现次数最多和第二多的数，用这两个数拟合我们的三角函数。由于A ≠ 0，所以不能是整个数组都相等。但还有一种情况是出现最多和第二多的数都同在奇数位或者偶数位，目前我除了和99998取min（最少就是选两个数拟合函数，其他的都变）也没有别的方法了，倒是稀里糊涂的也能过。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int cnt[N];signed main()
{int n;cin >> n;for(int i = 1; i <= n; i ++ ){scanf("%d", &a[i]);cnt[a[i]] ++;}int m = 0, idx1, idx2;for(int i = 1; i < N; i ++){if(m < cnt[i]){m = cnt[i];idx1 = i;}}cnt[idx1] = 0;m = 0;for(int i = 1; i < N; i ++ ){if(m < cnt[i]){m = cnt[i];idx2 = i;}}int cnt1 = 0, cnt2 = 0;for(int i = 1; i <= n; i ++ ){if((i & 1) && a[i] != idx1){cnt1 ++;}else if(!(i & 1) && a[i] != idx2) cnt1 ++;if((i & 1) && a[i] != idx2) cnt2 ++;else if(!(i & 1) && a[i] != idx1) cnt2 ++;}m = min(cnt1, cnt2);cout << min(m, 99998);return 0;
}

问题 I: 简单的大背包

题目描述
你有一个容积为 $n$ 的背包。现有两种物品：
物品1: 价值为 $1000$ , 体积为 $500$
物品2: 价值为 $5$ ,体积为 $5$

每种物品的数量是不限的,请问你的背包可以装到物品价值的总和最大是多少?
输入
输入一个整数 $n$,代表背包容积 (0 ≤ $n$ ≤ 10^9)
输出
输出一个整数,代表可以取得的最大价值
样例输入

2022

样例输出

4020

提示
样例解释：物品1拿4个，物品2拿4个。
思路：显然物品1性价比更高，在能放下物品1的基础上装满物品1，其余装物品2，注意背包容量可能无法装满。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010;
int g[N][N];int main()
{int v;cin >> v;cout << (LL)(v / 500) * 1000 + (v % 500 / 5) * 5; return 0;} 

问题 J: 秋风清 秋月明

题目描述
秋风清，秋月明，
落叶聚还散，寒鸦栖复惊。
相思相见知何日？此时此夜难为情！
这诗叫啥啊 有没有认识的
三五七言！
请问 $n$ 以内有多少个只由3 5 7构成的数呢？
3 5 7都要至少出现一遍哦！
输入
输入一个整数
输出
输出一个整数，代表符合条件数字的个数
样例输入

575

样例输出

4

提示
符合条件并小于575的有四个数 分别是357 375 537 573
思路：这个n的范围从357到n遍历一遍肯定会TLE了。但是3 5 7数应该不多，换个思路直接遍历小于等于n的所有3 5 7数。dfs处理所有由 3,5，7组成的0~n之间的数，然后再判断一下是否3 5 7三个数都出现了。但这样会有一个重复的问题，比如说我我的n是四位数，（假设四条dfs语句编号为1 2 3 4）我从1->2->3->4和2->3->4->1都是357，（相当于0357和3570,0不显示）。所以用set保证我每个数只被我加了一次。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int len, n;
//不需要集合排序 
unordered_set <int> v;bool check(int n){int f1 = 0, f2 = 0, f3 = 0;while(n){int t = n % 10;if(t == 3) f1 = 1;else if(t == 5) f2 = 1;else if(t == 7) f3 = 1;else break;n /= 10; }if(f1 && f2 && f3) return true;return false;
}//递归深度就是我n的位数 
void dfs(int cur,int num)
{if(num > n) return;//保证所统计的数都小于等于n if(cur == len) {if(check(num)) v.insert(num);return;}dfs(cur + 1, num);dfs(cur + 1, num * 10 + 3);dfs(cur + 1, num * 10 + 5);dfs(cur + 1, num * 10 + 7);
} int main()
{cin >> n;int nn = n;while(nn){len ++;nn /= 10;}dfs(0, 0);cout << v.size();return 0;
}

问题 K: 简单的旅行商

题目描述
我们知道,旅行商问题是一个 NP-Hard 问题,研究的是图中无重复访问点的最短路径。
我们给定一个周长为 C 的圆,在圆上有 n 个节点.
从圆上某一点开始,沿着一个方向行走,在行走距离 ai 后有一个节点 i 你可以沿着圆周,从任意方向行走,这样我们就得到一个环状的无向图。
请你在图中找到一条路径,使得每个节点恰好访问一次,且路径长度最短.
请你输出这个最短路径的长度
输入
输入第一行,两个整数,C, n,分别代表圆的周长以及节点个数.
输入第二行,n个递增的整数 ai ,代表每个节点在圆上的相对位置.
(2 <= C <= 10^6, 2 <= n <= 2*10^5)
(0 <= a1 < a2 < … < an < C)
输出
输出一个整数,代表最短路径长度
样例输入

20 3
5 10 15

样例输出

10

提示

样例中三点的位置关系如图，最短的路径是 1->2->3 长度为10

思路：把每条路分段，段最长的那条不走，其他的路走个环

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;int main()
{int C, n;cin >> C >> n;int a[n + 1];a[0] = 0;int m = 0, t;for(int i = 1; i <= n; i ++ ){cin >> a[i];t = a[i] - a[i - 1];m = max(m, t);}m = max(m, C- a[n] + a[1]);cout << C - m; return 0;
}

问题 L: 简单的基环树

样例输入

5 2 4

样例输出

5
4
1
0

ssn：懒得敲题目了

#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
int n, x, y;int main()
{cin >> n >> x >> y;//遍历每个点到自己后面的点的距离for(int i = 1; i < n; i ++ )for(int j = i + 1; j <= n; j ++ ){int d = abs(i - x) + abs(j - y);int m = min(j - i, d + 1);mp[m] ++; }for(int i = 1; i < n; i ++ ) cout << mp[i] << endl;return 0;
}