A - Lacked Number

Code

void solve()
{
    string s;   cin >> s;
    for (int i = 0; i < s.length(); i++)    st[s[i] - '0']++;

    for (int i = 0; i < 10; i++)
        if (!st[i])
        {
            cout << i;
            return 0;
        }
}

B - Slimes

Code

void solve()
{
    int a, b, k;    cin >> a >> b >> k;

    int res = 0;
    while (a < b)
    {
        a *= k;
        res++;
    }

    cout << res << endl;
}

C - Dice Sum(背包方案数)

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = N * N, mod = 998244353;

int n, m, k, f[N][M];  // f[i][j]表示选择i个数字总和为sum的方案数

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)    f[1][i] = 1;  // 初始化

    for (int i = 1; i < n; i++)
        for (int j = 0; j < k; j++)
            for (int k = 1; k <= m; k++)
                f[i + 1][j + k] = (f[i + 1][j + k] + f[i][j]) % mod;

    int res = 0;
    for (int i = 0; i <= k; i++)    res = (res + f[n][i]) % mod;

    cout << res << endl;
    return 0;
}

D - Range Count Query(容器\二分)

题目大意

给定一个数组$a$和$l, r, x$查询区间[l, r]内等于$x$的数的个数

解题思路

对于每个数存储它的坐标，对于每个查询进行l, r位置的二分查找

void solve()
{
    int n;  cin >> n;
    vector<vector<int>> pos(n + 1);

    for (int i = 1; i <= n; i++)  // 坐标从0开始
    {
        int x;  cin >> x;
        pos[x].push_back(i);
    }

    int q;  cin >> q;
    while (q--)
    {
        int l, r, x;    cin >> l >> r >> x;
        cout << lower_bound(pos[x].begin(), pos[x].end(), r + 1) - lower_bound(pos[x].begin(), pos[x].end(), l) << endl;
    }   
}

E - K-colinear Line

题目描述

给定$N$个二维坐标和$K$,问能形成多少个经过$K$个或$K$个以上点的直线

解题思路

当$k = 1$:经过一点可以形成无数条直线
当$k > 1$:可以先确定两个点, 然后对两个点之后的每个点进行枚举，
如果斜率一致，表明在一条直线上。

假设有$3$个点， $P(x, y), A(x_0, y_0), B(x_1, y_1)$
如果三个点在一条直线上, 则满足$(y_1 - y)/(x_1 - x) = (y_0 - y)/(x_0 - x)$
本公式可以转化为$(y_1 - y) * (x_0 - x) = (y_0 - y) * (x_1 - x)$来避免除法

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
const int N = 330;
typedef pair<int, int> PII;

int n, k, flag[N][N];
vector<int> now;
PII p[N];

bool check(int a, int b, int c)  // 判断是否在一直线
{
    int v1 = (p[b].y - p[a].y)*(p[c].x - p[a].x);
    int v2 = (p[b].x - p[a].x)*(p[c].y - p[a].y);
    return (v1 == v2);
}

signed main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;

    if (k == 1) 
    {
        cout << "Infinity" << endl;
        return 0;
    } 

    memset(flag, true, sizeof flag);

    int res = 0, cnt;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (flag[i][j])
            {
                cnt = 2;
                now.clear();
                now.push_back(i);
                now.push_back(j);
                for (int k = j + 1; k < n; k++)  // 向后枚举每个点是否符合
                    if (check(i, j, k))
                    {
                        cnt++;
                        now.push_back(k);
                    }
                for (int k = 0; k < cnt; k++)
                    for (int l = k + 1; l < cnt; l++)
                        flag[now[k]][now[l]] = false;  // 对于符合条件的点所构成的直线标记为使用过。避免重复

                if (cnt >= k)   res++;
            }

    cout << res << endl;
    return 0;
}