程序员进阶之算法练习（八十八）- CF883
题目1
题目链接 题目大意： 在地面上有n个点，点都在同一条垂直地面的线上面，每个点的高度为a[i]； 每个点有一条绳子，绳子长度为b[i]，一端连着点，一端连着小球（每个点相连的小球是同一个）；
如图
现在想知道，切掉多少条绳子，小球会掉落到地面。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤50). 接下来n行，每行两个整数 𝑎𝑖 and 𝑏𝑖 (1≤𝑎𝑖,𝑏𝑖≤200 )
输出： 每个样例一行，输出最少需要剪断的绳子数量；
Examples input 4 3 4 3 3 1 1 2 4 9 2 5 2 7 7 3 4 5 11 7 5 10 12 9 3 2 1 5 3 5 6 4 5 7 7
output 2 2 3 0
题目解析： 阅读理解题，如果某个点的高度大于绳子的长度，那么需要切断这个绳子。 那么只要遍历每个点，计算a[i]>b[i]的数量。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ans = 0;
while (n--) {
int x, y;
cin >> x >> y;
ans += x > y;
}
cout << ans << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目2
题目链接 题目大意： 在一个3x3的矩形棋盘上，如果有三个相同图案连在一起，则该图案获胜； 现在给出最终的结果，询问最终获胜者；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例3行，表示3x3棋盘最终结果。 "X" 、"O" 、 "+" 是表示不同棋子， "." 表示该位置是空的。
输出： 每个样例，如果有获胜棋子，则输出对应的棋子图案；（"X" 、"O" 、 "+" ） 如果没有获胜者，则输出DRAW；
Examples input 5 +X+ OXO OX. O+. +OX X+O .XO OX. +++ O.+ X.O +.. .++ X.O +..
output X O
DRAW DRAW
题目解析： 代码实现题，横竖斜三种情况分开处理。 这里有个trick，当找到获胜者的时候，可以直接结束，避免后续处理的影响。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
string str[3];
public:
void solve() {
int t;
cin >> t;
while (t--) {
for (int i = 0; i < 3; ++i) cin >> str[i];
char result = '.';
for (int i = 0; i < 3; ++i) {
if (str[i][0] == str[i][1] && str[i][1] == str[i][2] && result == '.') {
result = str[i][0];
}
}
for (int i = 0; i < 3; ++i) {
if (str[0][i] == str[1][i] && str[1][i] == str[2][i] && result == '.') {
result = str[0][i];
}
}
if (str[0][0] == str[1][1] && str[1][1] == str[2][2] && result == '.') {
result = str[0][0];
}
if (str[0][2] == str[1][1] && str[1][1] == str[2][0] && result == '.') {
result = str[0][2];
}
if (result == '.') {
cout << "DRAW" << endl;
}
else {
cout << result << endl;
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目3
题目链接 题目大意： 有n个人参加竞赛，竞赛有m个题目，每个题目需要耗费t[i][j]的时间； 小明是参赛者1号，竞赛总时长为h； 排名规则： 解答题目数多者优先，如果题目相同则耗时少则优先，耗时为每个题目解答时比赛已经进行的时间；
问，最终小明的排名是多少，假设每个参赛者都会用最优解去处理。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例第一行整数𝑛,𝑚,ℎ(1≤𝑛⋅𝑚≤2⋅1e5,1≤ℎ≤1e6) 接下来n行，每行有m个整数，表示𝑡𝑖,𝑗 (1≤𝑡𝑖,𝑗≤1e6 )
输出： 每个样例一行，输出小明最终的排名。
Examples input 5 3 4 2 1 4 5 1 5 1 3 4 6 6 1 2 3 4 2 1 200000 1 200000 2 4 3 9 11
output 11 2.5 34.5 199999.9999975 11.333333
题目解析： 模拟题，首先理解每个选手的最优解，必然是优先做耗时少的题目，再做耗时多题目； 那么对每个选手的题目耗时进行排序，从时间最小开始做题，直到时间消耗完毕或者题目做完；
接下来对n个人的成绩进行排序，这里可以用sort+pair+自定义排序来实现。 最后遍历结果，找到小明题数和耗时所在名次即可。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const lld N = 201010;
vector<lld> a[N];
pair<lld, lld> result[N];
static bool cmp(pair<lld, lld> x, pair<lld, lld> y) {
if (x.first != y.first) return x.first > y.first;
else return x.second < y.second;
}
public:
void solve() {
lld t;
cin >> t;
while (t--) {
lld n, m, h;
cin >> n >> m >> h;
for (lld i = 0; i < n; ++i) {
a[i].clear();
for (lld j = 0; j < m; ++j) {
lld tmp;
cin >> tmp;
a[i].push_back(tmp);
}
sort(a[i].begin(), a[i].end());
}
for (lld i = 0; i < n; ++i) {
lld tmp = 0, cnt = 0, time = 0;
for (lld j = 0; j < m; ++j) {
if (tmp + a[i][j] <= h) {
tmp += a[i][j];
++cnt;
time += tmp;
}
}
result[i] = make_pair(cnt, time);
}
pair<lld, lld> ans = result[0];
lld out = 0;
sort(result, result + n, cmp);
for (lld i = 0; i < n; ++i) {
if (result[i].first == ans.first && result[i].second == ans.second) {
out = i;
cout << out + 1 << endl;
break;
}
}
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目4
题目链接 题目大意： 在一个二维坐标系上面，有若干个三角形；
所有三角形的底为d(平行于x轴)，高为h，被y轴分为完全平分。 现在想知道所有三角形的覆盖面积是多少。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数 𝑛,𝑑,ℎ （1≤𝑛,𝑑,ℎ≤2⋅1e5） 接下来一行是n个整数 𝑦𝑖 ，表示每个三角形底的高度 (1≤𝑦𝑖≤19,𝑦1<𝑦2<...<𝑦𝑛)
输出： 每个样例一行，输出具体覆盖面积，误差小于10^-6；
Examples input 5 3 4 2 1 4 5 1 5 1 3 4 6 6 1 2 3 4 2 1 200000 1 200000 2 4 3 9 11
output 11 2.5 34.5 199999.9999975 11.333333
题目解析： 分情况讨论。 1、完全分开，就是纯三角形面积，ans += d * h / 2; 2、有交集，此时三角形面积有部分三角形被重叠。 假设重叠三角形的底部为y，高为x，这个重叠三角形和整个大三角形相似，可以得知： x/y = h/d x=a[i+1]-a[i]，h和d已知，那么有y=x*h/d，可以求得重叠三角形的面积。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, d, h;
cin >> n >> d >> h;
for (int i = 0; i < n; ++i) cin >> a[i];
double ans = 0;
for (int i = 0; i < n; ++i) {
if (i + 1 < n && a[i + 1] - a[i] < h) {
// 第i个三角形是梯形
int x = h - (a[i + 1] - a[i]);
ans += (1.0 * x * d / h + d) * (a[i + 1] - a[i]) / 2;
}
else {
ans += 1.0 * d * h / 2;
}
}
printf("%.6lf\n", ans);
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目5
题目链接 题目大意： 有一种雪花结构，可以用这样的规则来描述： 1、初始状态只有一个节点； 2、往每一个边的数量小于k的节点，添加k条边以及对应的新节点； 不断重复规则2达到2次以上，则能形成雪花结构：
现在想知道，是否存在一个雪花结构的结点数为n；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行整数𝑛 (1≤𝑛≤1e6 ).
输出： 每个样例，如果无解直接输出NO； 如果有解，则先输出YES；
Examples input 9 1 2 3 6 13 15 255 10101 1000000
output NO NO NO NO YES YES YES YES NO
题目解析： 按照题目的要求，一个雪花的结构可以用 1 + k + k*k + ....来描述； 找到规律，那么可以枚举k，从小到大，再枚举雪花结构重复次数。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
//1 + n + n*n
lld ans = 0, cur = 2;
while (!ans && cur < 1000) {
lld tmp = 1 + cur + cur * cur, pos = cur * cur * cur;
while (tmp + pos <= n) {
tmp += pos;
pos *= cur;
}
if (tmp == n) ans = 1;
++cur;
}
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目6
题目链接 题目大意： 有一种雪花结构，可以用这样的规则来描述： 1、初始状态只有一个节点； 2、往每一个边的数量小于k的节点，添加k条边以及对应的新节点； 不断重复规则2达到2次以上，则能形成雪花结构：
现在想知道，是否存在一个雪花结构的结点数为n；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行整数𝑛 (1≤𝑛≤1e18 ).
输出： 每个样例，如果无解直接输出NO； 如果有解，则先输出YES；
Examples input 9 1 2 3 6 13 15 255 10101 1000000
output NO NO NO NO YES YES YES YES NO
题目解析： 按照题目的要求，一个雪花的结构可以用 1 + k + k*k + ....来描述； 找到规律后，由于n的数据非常大，那么无法直接枚举k来得到结果。
对于重复3次及以上，1 + k + k^2 + k3，k取106是极大值，可以直接枚举。
重点放在重复2次的情况，此时结果表达式为 1 + k + k^2 ，由于平方可以有很多种可能，需要用数学分析； 容易知道最终结果是k * (k + 1) + 1，那么减去1之后进行sqrt开平方，可以得到一个数字q。容易知道q的结果是在n和n+1之间的数字，因为平方后的数字是大于n2，小于(n+1)2。
注意： 1、样例最大的情况，会超过int64。 2、样例很多大数据，特殊情况会超时，可以先提前打表；
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
map<lld, lld> h;
lld cur = 2;
lld total = 1000000000000000000l;
while (cur < 1000000) {
lld pos = cur * cur * cur;
lld tmp = 1 + cur + cur * cur + pos;
while (tmp <= total) {
h[tmp] = 1;
if (total / pos >= cur) {
pos *= cur;
tmp += pos;
}
else break;
}
++cur;
}
while (t--) {
lld n;
cin >> n;
//1 + n + n*n
lld ans = h.find(n) != h.end();
if (!ans) {
lld tmp = sqrt(n - 1);
if (tmp >= 2 && (tmp * tmp + tmp + 1) == n) ans = 1;
}
cout << (ans ? "YES" : "NO") << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目7
题目链接 题目大意： 有n个人，每个人都有一个0~9的序号；这里面有个模仿者，他的序号可能会发生变化。 小明想要找出来模仿者，游戏规则是这样： 1、首先会给出n个整数，表示n个人的序号； 2、小明可以挑选若干个人（可以是0个），如果这些人不包括模仿者，系统会移除选中的人； 3、剩下的人顺序会打乱，此时模仿者的序号可能会变成0~9任意中一个，注意模仿者最多连续两次保持同一个数字；接着进入步骤2； 4、小明在游戏过程中，可以随时指定某个位置的人为模仿者；
如果小明在步骤2挑选到模仿者，则游戏失败； 如果小明在步骤2执行超过5次，则游戏失败； 如果小明在步骤4挑选到正确模仿者，则游戏胜利；如果在步骤4挑选错误，则游戏失败。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例第一行整数𝑛 (1≤𝑛≤200). 接下来一行n个整数 𝑎1 ,𝑎2 ,...,𝑎𝑛 (1≤𝑎𝑖≤9)
输出： 如果小明要执行操作2，则输出-开头，然后输出移除人数m，接下来是m个整数，表示要移除人数的位置；（移除之后，操作3会输出剩下人数的序号） 如果小明要执行操作4，则输出!开头，然后输出模仿者的位置；
Examples input
3
5
1 1 2 2 3
2 1 1 2
2 2 2
2
8
1 2 3 4 3 4 2 1
4 3 4 3 2 2 1 3
2 3 3 2
5 3 2
2 5
15
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 9 5 4 3 2 1output
- 1 5
- 1 3
- 2 1 2
! 1
- 0
- 4 1 3 7 8
- 1 4
- 1 2
! 2
- 0
! 10题目解析： 从操作1给出的初始信息，我们并不能马上确定模仿者； 那么在进行操作2就要慎重，因为有可能选择到模仿者； 我们利用模仿者最多连续2个回合保持相同数字的规则，先按兵不动，直到模仿者改变序号，那么我们遍历数组就可以知道哪个整数增加了，这个整数必然是模仿者所在整数； 如果这个整数只有1个，那么找到模仿者，游戏结束； 如果这个整数有多个，那么就把这个整数之外的数字移除，接着按兵不动，直到模仿者变化出新的数字。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int N = 10;
int a[202];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> cnt(N, 0);
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[a[i]]++;
}
cout << "- 0" << endl; // don't move
do {
int check = 0;
vector<int> change(N, 0);
for (int i = 0; i < n; ++i) {
cin >> a[i];
change[a[i]]++;
}
for (int i = 1; i < N; ++i) {
if (change[i] > cnt[i]) check = i;
}
// 直到变化
if (check) {
if (change[check] == 1) {
for (int i = 0; i < n; ++i) if (a[i] == check) cout << "! " << i + 1 << endl;
break;
}
else {
vector<int> out;
for (int i = 0; i < n; ++i) {
if (a[i] != check) out.push_back(i + 1);
}
cout << "- " << out.size();
for (int i = 0; i < out.size(); ++i) cout << " " << out[i];
cout << endl;
n -= out.size();
}
for (int i = 0; i < N; ++i) if (i != check) cnt[i] = 0;
cnt[check] = change[check];
}
else {
cout << "- 0" << endl; // don't move
}
} while (true);
}
cout.flush();
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}题目8
题目链接 题目大意： 小明生病了，出现了若干症状，现在需要吃药治疗； 所有症状一共有n种，小明的症状可以用由字符0和1组成的字符串s来表示，第i个字符为0表示第i种症状未出现，第i个字符为1表示第i种症状出现； 现在有m种药，每种药可以治疗若干症状，但是也会造成若干副作用的症状，分别用字符0和字符1组成的字符串x和字符串y表示；（规则同上） 已知每种药只能单独吃，并且吃完需要一段时间； 想知道小明消除所有症状需要的时间。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例的第一行整数𝑛,𝑚(1≤𝑛≤10,1≤𝑚≤1000) 第二行是长度为n的字符串s，表示小明已经出现的症状 接下来m · 3行，表示m种药品 第一行，整数𝑑，表示该药吃完需要的时间(1≤𝑑≤1000) 第二行，字符串x，表示该药能治疗的症状 第三行，字符串y，表示该药会产生的副作用症状
输出： 每个样例一行，输出小明消除所有症状需要的时间；如果无解，则输出-1；
Examples input 4 5 4 10011 3 10000 00110 3 00101 00000 3 01010 00100 5 11010 00100 4 1 0000 10 1011 0100 2 2 11 2 10 01 3 01 10 2 3 11 3 01 10 3 10 00 4 10 01
output 8 0 -1 6
题目解析： 假如有一种药，那么小明就只能吃这种药； 假如有两种药A和B，那么小明就会有两个选择，先A后B，先B后A； 有没有可能出现一种药吃两次的情况？不会，因为假如出现某种药吃两次，那么第一次吃的药，效果会被第二次药替代，因为两次吃效用、副作用是一样的。 假如有多种药A/B/C...，此时情况就复杂很多，需要通过搜索法来进行枚举，这样的复杂度是阶乘量级；
考虑到症状数量不多，我们将所有可能的症状梳理出来，发现最多就只有1024种情况（n的最大值为10）； 假如每种情况是一个点，那么每种药可以抽象为从情况a变成情况b的一条边，这样就建立了一张图。 而题目想要的，就是从初始状态的点，走到点0（全部症状为0）的最短路。 这里选用迪杰斯特拉算法来实现。
#include<cstdio>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<sstream>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long lld;
class Solution {
static const int inf = 0x7ffffff;
static const int N = 1030;
int g[N][N];
int strToInt(string s) {
int ret = 0, tmp = 1;
while (s.length()) {
ret += (s[s.length() - 1] - '0') * tmp;
tmp *= 2;
s.pop_back();
}
return ret;
}
string intToString(int t, int n) {
string ret(n, '0');
int tmp = n - 1;
while (t) {
ret[tmp] = '1';
--tmp;
t /= 2;
}
return ret;
}
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int sum = (1 << n);
for (int i = 0; i <= sum; ++i) {
for (int j = 0; j <= sum; ++j)
g[i][j] = inf;
}
string str;
cin >> str;
for (int k = 1; k <= m; ++k) {
int cost;
string x, y;
cin >> cost >> x >> y;
for (int u = 0; u < sum; ++u) {
string s;
for (int j = 0; j < n; ++j) {
if ((1 << j) & u) s.insert(s.begin(), '1');
else s.insert(s.begin(), '0');
}
for (int j = 0; j < n; ++j) {
s[j] = '0' + ((s[j] == '1') && (x[j] == '0'));
}
for (int j = 0; j < n; ++j) {
s[j] = '0' + ((s[j] == '1') || (y[j] == '1'));
}
int v = strToInt(s);
g[u][v] = min(g[u][v], cost);
// cout << u << " to " << v << " cost " << g[u][v] << endl;
}
}
priority_queue<pair<int, int> > q; // dis, u
int u = strToInt(str);
vector<int> dis(N), vis(N);
for (int i = 0; i < N; ++i) dis[i] = inf;
dis[u] = 0;
q.push(make_pair(0, u));
while (!q.empty()) {
pair<int, int> top = q.top();
q.pop();
u = top.second;
if (!vis[u]) {
vis[u] = 1;
// not vis
for (int v = 0; v < sum; ++v) {
if (g[u][v] != inf) {
dis[v] = min(dis[v], dis[u] + g[u][v]);
if (!vis[v]) q.push(make_pair(-dis[v], v));
}
}
}
}
if (dis[0] == inf) {
dis[0] = -1;
}
cout << dis[0] << endl;
}
}
}
ac;
int main(int argc, const char * argv[]) {
// insert code here...
ac.solve();
return 0;
}总结
本次练习是Codeforce883的所有题目，比赛链接。 算法练习的更新，可能到练习一百就结束，专注业务实践；也可能随着职业生涯延续，持续锻炼。 提高思维敏捷度，着重问题的分析过程； 克服畏难心理，把想法付诸实践，保持代码实践能力。