题目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 1
output
- 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的所有题目，比赛链接。
算法练习的更新，可能到练习一百就结束，专注业务实践；也可能随着职业生涯延续，持续锻炼。
提高思维敏捷度，着重问题的分析过程；
克服畏难心理，把想法付诸实践，保持代码实践能力。
网友评论