A. To My Critics 题意 签到题,问输入的三个数里较大两数之和是否大于等于10
思路 存进数组然后排序,取较大的两个数相加和10比较
代码 #include <bits/stdc++.h> using namespace std;int main () { int t; cin >> t; while (t -- ) { int a[3 ]; cin >> a[0 ] >> a[1 ] >> a[2 ]; sort (a, a + 3 ); if (a[1 ] + a[2 ] >= 10 ) cout << "YES\n" ; else cout << "NO\n" ; } }
B. Ten Words of Wisdom 题意 每组输入两个数,判断在第一个数小于等于10的情况下,最大的第二个数的序号
思路 用vector<pari<int, int>>
存数据,first存第二个输入的数,second存输入序号,当第一个数小于等于10时就将其存入,然后对vector排序,输出最大的第二个数的编号
代码 #include <bits/stdc++.h> using namespace std;typedef pair<int , int > PII;int main () { int t; cin >> t; while (t -- ) { int n; cin >> n; vector<PII> a; for (int i = 0 ; i < n; i ++ ) { int x; int y; cin >> x >> y; if (x <= 10 ) a.push_back (make_pair (y, i)); } sort (a.begin (), a.end ()); cout << a[a.size () - 1 ].second + 1 << endl; } }
C. Word on the Paper 题意 8x8的矩阵中,输出所有竖着排列的字符串
思路 遍历整个矩阵,遇到非.
时就将其和下方的所有非.
元素输出
代码 #include <bits/stdc++.h> using namespace std;const int N = 8010 ;char grid[N][8 ];bool st[8 ];int main () { int t; cin >> t; while (t -- ) { memset (st, false , sizeof st); for (int j = 0 ; j < 8 ; j ++ ) for (int k = 0 ; k < 8 ; k ++ ) cin >> grid[j][k]; for (int i = 0 ; i < 8 ; i ++ ) for (int j = 0 ; j < 8 ; j ++ ) if (grid[i][j] != '.' && !st[j]) { int h = i; st[j] = true ; while (h < 8 ) { if (grid[h][j] != '.' ) cout << grid[h][j]; h ++ ; } cout << '\n' ; } } }
D. Balanced Round 题意 给出一串数字,可以任意交换他们的位置,要求删掉最小个数的数字,让连续的两个数字差值小于给定的 k
思路 先从大到小排序,用dp做,f[i][j]
表示在前 i 个数字内能选择的最大个数,j 表示第 i 个数有没有选,1表示选了,0表示没选,从前往后更新f[i][j]
,f[n][1]
和f[n][0]
的较大值为能选择的最大数字个数,用总个数减去最大个数就是删去的最小个数
代码 #include <bits/stdc++.h> using namespace std;const int N = 200010 ;int f[N][2 ];int main () { int t; cin >> t; while (t -- ) { int n, k; cin >> n >> k; vector<int > a (n) ; for (int i = 0 ; i < n; i ++ ) cin >> a[i]; sort (a.begin (), a.end ()); f[0 ][0 ] = 0 ; f[0 ][1 ] = 1 ; for (int i = 1 ; i < n; i ++ ) { if (a[i] - a[i - 1 ] <= k) { f[i][1 ] = f[i - 1 ][1 ] + 1 ; f[i][0 ] = max (f[i - 1 ][0 ], f[i - 1 ][1 ]); } else { f[i][1 ] = 1 ; f[i][0 ] = max (f[i - 1 ][0 ], f[i - 1 ][1 ]); } } int ans = max (f[n - 1 ][1 ], f[n - 1 ][0 ]); cout << n - ans << '\n' ; } }
E. Cardboard for Pictures 题意 有一组已知边长的正方形,现在要将每个正方形的边长加上同一个w,问w是多少能满足所有新正方形的面积等于给定值c
思路 一开始路走歪了…不知道怎么就去解一元二次方程去了,然后因为double的误差wa了 实际很简单~ 二分就可以啦~ 首先利用倍增思想,把每个正方形边长都加上 2^j^,求出最小的 j 使总面积第一次大于 c 然后就在1到 j 之间二分求出 w
代码 #include <bits/stdc++.h> using namespace std;using i64 = unsigned long long ;int main () { ios::sync_with_stdio (false ); cin.tie (0 ); cout.tie (0 ); int t; cin >> t; while (t -- ) { i64 n, sum; cin >> n >> sum; vector<i64> a (n) ; for (int i = 0 ; i < n; i ++ ) cin >> a[i]; i64 l = 0 , r = 1 ; while (1 ) { i64 res = 0 ; for (int i = 0 ; i < n; i ++ ) res += (a[i] + 2 * r) * (a[i] + 2 * r); if (res >= sum) break ; r *= 2 ; } while (l < r) { i64 mid = l + r >> 1 ; i64 res = 0 ; for (int i = 0 ; i < n; i ++ ) res += (a[i] + 2 * mid) * (a[i] + 2 * mid); if (res >= sum) r = mid; else l = mid + 1 ; } cout << r << '\n' ; } }
F. We Were Both Children 题意 每个青蛙都可以跳到它弹跳能力的整数倍上,人能到达的最远距离是青蛙的个数,现在人要待在一个位置逮青蛙,问待在那个位置逮到的青蛙最多
思路 先标记每个青蛙第一次跳到的位置,之后从后往前更新每个青蛙能跳到的小于 n 的位置,选择有最多青蛙能跳到的位置输出
代码 #include <bits/stdc++.h> using namespace std;const int N = 200010 ;int main () { int t; cin >> t; while (t -- ) { int n; cin >> n; vector<int > a (n) ; vector<int > cnt (n + 1 ) ; for (int i = 0 ; i < n; i ++ ) { cin >> a[i]; if (a[i] <= n) cnt[a[i]] ++ ; } for (int i = n; i >= 1 ; i -- ) for (int j = i * 2 ; j <= n; j += i) cnt[j] += cnt[i]; cout << *max_element (cnt.begin (), cnt.end ()) << '\n' ; } }
G. The Morning Star 题意 从所有给的坐标里面选择两个坐标,一个放a,一个放b,这两个坐标要在同一条直线上
思路 遍历给定的坐标,只要这个坐标同一行 / 同一列 / 对角线 / 反对角线上有坐标,这个坐标就是可以选的,所以只要判断上面列举的四种情况有没有对应的坐标,有就加上,之后再更新遍历到的这个点 最后不要忘记*2,因为ab可以交换
代码 #include <bits/stdc++.h> using namespace std;using i64 = long long ;typedef pair<int , int > PII;int main () { int t; cin >> t; while (t -- ) { int n; cin >> n; map<i64, int > a; map<i64, int > b; map<i64, int > c; map<i64, int > d; i64 ans = 0 ; for (int i = 0 ; i < n; i ++ ) { i64 x, y; cin >> x >> y; ans += a[x] + b[y] + c[x - y] + d[x + y]; a[x] ++ ; b[y] ++ ; c[x - y] ++ ; d[x + y] ++ ; } cout << ans * 2 << '\n' ; } }
H. The Third Letter 题意 给定士兵个数和信息条数,每条信息告诉两个士兵的相对位置,判断所有的信息是否矛盾
思路 把和每个点有关的信息存到vector>里面,存完后逐个士兵dfs判断是否矛盾
代码 #include <bits/stdc++.h> using namespace std;const int N = 200010 ;using i64 = long long ;typedef pair<int , int > PII;int main () { ios::sync_with_stdio (false ); cin.tie (0 ); cout.tie (0 ); int t; cin >> t; while (t -- ) { int n, q; cin >> n >> q; vector<i64> d (n + 1 ) ; vector<bool > st (n + 1 ) ; bool flag = true ; vector<vector<PII>> g (n + 1 ); while (q -- ) { int a, b, c; cin >> a >> b >> c; g[a].push_back (make_pair (b, c)); g[b].push_back (make_pair (a, -c)); } function<void (int )> dfs = [&](int u) { st[u] = true ; for (int i = 0 ; i < g[u].size (); i ++ ) { int j = g[u][i].first; int w = g[u][i].second; if (!st[j]) { d[j] = d[u] + w; dfs (j); } else if (d[j] != d[u] + w) flag = false ; } }; for (int i = 1 ; i <= n; i ++ ) if (!st[i]) dfs (i); if (!flag) cout << "NO\n" ; else cout << "YES\n" ; } }