数字之和

题意

给abc三个数，任选两个数字，和大于等于10，输出YES，否则NO。

题解

枚举所有情况，判断即可。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t, a, b, c;
    cin >> t;
    while(t--) {
        cin >> a >> b >> c;
        puts(a + b >= 10 || c + b >= 10 || a + c >= 10 ? "YES" : "NO");
    }
    return 0;
}

智慧格言

题意

n个回答，每个回答有长度和质量两个属性，输出长度不超过10并且质量最高的回答。

题解

遍历所有回答，如果长度超过10，不处理；否则比较当前回答，更新当前质量最高的回答及其下标。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int mx = 0, id = 0;
        for(int i = 1; i <= n; i++) {
            int a, b;
            cin >> a >> b;
            if(a <= 10 && mx < b) {
                mx = b;
                id = i;
            }
        }
        cout << id << "\n";
    }
    return 0;
}

英文单词

题意

8*8字符矩阵，输出一列单词。

题解

方法1：遍历矩阵，一旦找到一个字母，就向下迭代，直到得到整个单词。

方法2（更快）：在输入字符时处理，如果不是点就输出它。

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--) {
        string s = "";
        for(int i = 0; i < 8; i++) {
            for(int j = 0; j < 8; j++) {
                char c;
                cin >> c;
                if(c != '.')
                    s += c;
            }
        }
        cout << s << endl;
    }
    return 0;
}

均衡题目

题意

n个数，每个数代表难度，求删除最少的数，排列剩余的数，任意两个相邻的数的差的绝对值小于等于k。

题解

先排序，问题为寻找最大（连续数字最多）的子数组使得$a_i−a_{i−1}≤k$

。因此，我们可以维护当前子数组中元素数量，设为count变量，并从左到右遍历数组元素。如果现在$a_i−a_{i−1}>k$，则count设为1。因为我们知道一个新的子数组开始了，否则，我们就把count加1。答案是n减去count计数得到的最大值。

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, k;
        cin >> n >> k;
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int count = 1, ans = 0;
        sort(a, a + n);
        for(int i = 0; i < n - 1; i++) {
            if(a[i + 1] - a[i] <= k) {
                count++;
            } else {
                count = 1;
            }
            ans = max(ans, count);
        }
        ans = max(ans, count);
        cout << n - ans << endl;
    }
    return 0;
}

图片与纸板

题意

n张图片，边长分别为s_i。一个纸板，纸板面积为c，刚好能把每一张图片覆盖且每张图片四周留有w的边框。问w的值。

题解

1.二分答案w，对于每个答案，验证使用的纸板面积与c的比较。接着更新二分区间。 2.数值解，解一元二次方程。详情见代码。 二分代码：

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
#define int long long
void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    int l = 1, r = 1e9;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        int sumall = 0;
        for(int i = 0; i < n; ++i) {
            sumall += (a[i] + 2 * mid) * (a[i] + 2 * mid);
            if(sumall > c) break;
        }
        if(sumall == c) {
            cout << mid << "\n";
            return;
        }
        if(sumall > c) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
}
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

数值解代码：

#include<bits/stdc++.h>
using namespace std;
long long a[200005];
int main() {
    ios_base::sync_with_stdio(0);
    int t ;
    cin >> t ;
    while(t--) {
        long long int n, k;
        cin >> n >> k;
        long long p = 0, u = 0;
        for(long long i = 0; i < n; i++) {
            cin >> a[i];
            k -= (a[i] * a[i]);
            p += a[i];
        }
        u = p / n;
        cout << ((int)sqrt(u * u + k / n) - u) / 2 << endl;
    }
    return 0;
}

跳跃的青蛙

题意

n个青蛙，每个跳跃距离为a_i，开始都在坐标0。你可以在1-n选择一个位置放一个陷阱，问掉进陷阱的青蛙数量最多是多少。

题解

统计1-n每个位置有多少青蛙经过，输出最多青蛙经过的位置。具体看代码。

#include<bits/stdc++.h>
using namespace std;
int t;
void solve() {
    int n, res = 0;
    cin >> n;
    vector<int> cnt(n + 1, 0), maxx(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if(x <= n) cnt[x]++;
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) maxx[j] += cnt[i];
    }
    for(int i = 1; i <= n; i++) {
        res = max(res, maxx[i]);
    }
    cout << res << endl;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

指南针

题意

如果星辰在指南针的8个方向上，则指南针正常工作。给你n个点，可以放置一个指南针和一个星辰，问有多少种放置方式，指南针可以正常工作。

题解

统计在同一行，同一列，或同一对角线的点的数量，具体见代码。因为还未教学map容器，因此数据范围缩小了，数组也能做。把map<int, int> up, side, diag1, diag2;改为数组up[],side[],diag1[],diag2[]即可。

map版本

#include <bits/stdc++.h>
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define int long long
void solve() {
    int n;
    cin >> n;
    map<int, int> up, side, diag1, diag2;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        up[x]++;
        side[y]++;
        diag1[x - y]++;
        diag2[x + y]++;
    }
    for(auto x : up) {
        ans += x.second * (x.second - 1);
    }
    for(auto x : side) {
        ans += x.second * (x.second - 1);
    }
    for(auto x : diag1) {
        ans += x.second * (x.second - 1);
    }
    for(auto x : diag2) {
        ans += x.second * (x.second - 1);
    }
    cout << ans << endl;
}
int32_t main() {
    startt
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}