A.A Hard Problem（签到）

题意：

给定一个 $n$ ，要求找到最小的集合大小，使得 $T$ 中存在一个数是另一个数的因子,其中 $T$ 为 $\left\{ 1,2,...n \right\}$ 的子集且 $T$ 中元素任意

题解：

找规律题，发现答案为 $\frac{n+1}{2}+1$
证明的话就是鸽巢原理，取 $\frac{n+1}{2} \sim n$ ，其中最小的数为 $\frac{n+1}{2}$ ，最大的数为 $n$ ，而 $\frac{n+1}{2} * 2 = n+1>n$ ，因此不存在任意两个数为倍数关系，再从 $1 \sim \frac{n-1}{2}$ 中取一个数就能满足有一个数为另一个数的倍数，因此答案为 $\frac{n+1}{2}+1$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
    ll n;
    scanf("%lld", &n);
    printf("%lld\n", (n + 1) / 2 + 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Chessboard（组合数学）

题意：

给定一个 $n*m$ 的棋盘。现在每走一步就将该格涂色，求出有多少种遍历方式可以遍历整个棋盘，但是在遍历过程中有限制：任意两个涂色的格子沿着涂色格子的最短路径不能更短（就是涂了当前该点不会影响涂完色格子的最短路径） $(1≤n,m≤10^6)$

题解：

首先，我们可以观察到如下几个不难证明的性质：

两个被染上颜色的格子之间的距离始终为：曼哈顿距离。
一个染色方案是合法的，当且仅当：任何时刻，每行/列被染色的格子要么不存在，要么是连续的一段。
如果当前被染色的区域是个矩形，那么最后一个被染色的点，一定在角上。

因为可以发现如果走出一个凸形的话，走回那个点势必会使左右两点的距离变短，因此只能要么一次增加一行，或者增加一列。于是，可以得出以下结论：

如果当前被染色的区域是个 $r(r \geq 2)$ 行 $c(c \geq 2)$ 列的矩形，那么接下来要么扩充成 $r+1$ 行 $c$ 列的矩阵(扩充行)，要么扩充成 $r$ 行 $c+1$ 列的矩形(扩充列)。并且根据当前状态中最后一个被染色的格子在哪个角上，扩充行/列的方案都是唯一的。
从 $1*1$ 的矩阵，到 $n*m$ 的矩阵，一共要扩充 $n+m-2$ 次，其中有 $n-1$ 次是扩充行，这样的决策有 $C_{n+m-2}^{n-1}$ 种，根据最后一个被染色的格子在哪个角上，方案数为 $4*C_{n+m-2}^{n-1}$
要特判 $n=1$ 和 $m=1$ 的情况

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll fac[maxn];
ll qpow(ll a, ll b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
void init()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++)
        fac[i] = fac[i - 1] * i % mod;
}
ll c(int x, int y)
{
    if (x < y)
        return 0;
    return fac[x] * qpow(fac[y] * fac[x - y] % mod, mod - 2) % mod;
}
void solve()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    if (n == 1)
    {
        if (m == 1)
            puts("1");
        else
            puts("2");
        return;
    }
    if (m == 1)
    {
        if (n == 1)
            puts("1");
        else
            puts("2");
        return;
    }
    printf("%lld\n", 4ll * c(n + m - 2, n - 1) % mod);
}
int main()
{
    init();
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Digital Path（DP）

题意：

给定 $n×m$ 的矩阵，每个格子有个权值，找寻最长路径的数目，其中每条路径长度 $>=4$ ，并且路径中的数值严格增加 $1$ 。

题解：

相邻的两个点如果权值相差为 $1$ ，则从小的向大的连边。然后最终连成的是一个 $DAG$ ，在 $DAG$ 上面按照拓扑序 $DP$ 即可。

$dp$ ：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int head[maxn], nxt[maxn << 2], to[maxn << 2], deg[maxn], tot;
int n, m, a[1005][1005], dp[maxn][5];
void addedge(int u, int v)
{
    deg[v]++;
    to[tot] = v;
    nxt[tot] = head[u];
    head[u] = tot++;
}
int id(int x, int y)
{
    return (x - 1) * m + y;
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(a, 0x3f, sizeof(a));
    memset(head, -1, sizeof(head));
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int x = id(i, j);
            if (a[i + 1][j] == a[i][j] + 1)
                addedge(x, id(i + 1, j));
            if (a[i][j + 1] == a[i][j] + 1)
                addedge(x, id(i, j + 1));
            if (a[i - 1][j] == a[i][j] + 1)
                addedge(x, id(i - 1, j));
            if (a[i][j - 1] == a[i][j] + 1)
                addedge(x, id(i, j - 1));
        }
    queue<int> q;
    for (int i = 1; i <= n * m; i++)
        if (deg[i] == 0)
        {
            q.push(i);
            dp[i][1] = 1;
        }
    ll res = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        bool flag = true;
        for (int i = head[u]; ~i; i = nxt[i])
        {
            int v = to[i];
            dp[v][2] = (dp[v][2] + dp[u][1]) % mod;
            dp[v][3] = (dp[v][3] + dp[u][2]) % mod;
            dp[v][4] = (dp[v][4] + dp[u][3] + dp[u][4]) % mod;
            if (--deg[v] == 0)
                q.push(v);
            flag = false;
        }
        if (flag)
            res = (res + dp[u][4]) % mod;
    }
    printf("%lld\n", res);
    return 0;
}

当初还写了个垃圾模拟：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int mod = 1e9 + 7;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int vis[maxn][maxn];
int mp[maxn][maxn];
ll num[maxn][maxn];
int n, m;
struct node
{
    int step, x, y;
    node(int s0 = 0, int x0 = 0, int y0 = 0) : step(s0), x(x0), y(y0) {}
};
struct Node
{
    int val, x, y;
    Node(int v0 = 0, int x0 = 0, int y0 = 0) : val(v0), x(x0), y(y0) {}
    bool operator<(const Node &C) const
    {
        return val < C.val;
    }
};
bool check(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx <= 0 || tx > n || ty <= 0 || ty > m)
            continue;
        if (mp[tx][ty] == mp[x][y] + 1)
            return false;
    }
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    queue<node> q;
    priority_queue<Node> qq;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &mp[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (check(i, j))
                q.push(node(1, i, j));
    while (!q.empty())
    {
        node now = q.front();
        q.pop();
        int x = now.x;
        int y = now.y;
        if (now.step >= 4)
        {
            if (!num[x][y])
                qq.push(Node(mp[x][y], x, y));
            num[x][y]++;
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (tx <= 0 || tx > n || ty <= 0 || ty > m)
                continue;
            if (mp[tx][ty] == mp[x][y] - 1)
                q.push(node(now.step + 1, tx, ty));
        }
    }
    ll ans = 0;
    while (!qq.empty())
    {
        Node now = qq.top();
        qq.pop();
        int x = now.x;
        int y = now.y;
        if (vis[x][y])
            continue;
        vis[x][y] = 1;
        int flag = 0;
        for (int i = 0; i < 4; i++)
        {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (tx <= 0 || tx > n || ty <= 0 || ty > m)
                continue;
            if (mp[tx][ty] == mp[x][y] - 1)
            {
                num[tx][ty] = (num[tx][ty] + num[x][y]) % mod;
                qq.push(Node(mp[tx][ty], tx, ty));
                flag = 1;
            }
        }
        if (!flag)
            ans = (ans + num[x][y]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

F.Paper Grading（trie树+主席树套树状数组）

题意：

给定 $n$ 组字符串 $s_i$ 和 $m$ 次操作，操作分为两种：

$1$ $i$ $j$ :交换 $s_i$ 和 $s_j$ 的位置

$2$ $q$ $k$ $l$ $r$ :给定一个字符串 $q$ ，询问字符串 $s_l \sim s_r$ 中与字符串 $q$ 的最长公共前缀长度 $\geq k$ 的个数

题解：

首先将字符串都加到Trie中，然后标记 $f[i]$ 为每个字符串的最后一个字符所指定的Trie结点，考虑每次询问，在Trie中向下走 $k$ 次，对于可以找到合法结点的情况，答案就是 $f[l..r]$ 中，属于该合法结点子树的个数。
到这里，先不考虑修改操作，可以把Trie按dfs序建立主席树， $dfn[i]$ 表示第 $i$ 号结点的dfs序，然后对每个 $f[i]$ , 在第 $dfn[f[i]]$ 棵权值线段树的 $i$ 位置的权值 $+1$ ，然后每次查询子树区间中有多少个数字在 $[l,r]$ 的范围内。
加上修改操作，可以利用树状数组维护权值线段树，交换两个字符串的位置，也就是交换了f[i]，直接在权值线段树中修改即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, m;
int f[N];
char s[N];
inline int lowbit(int x) { return x & -x; }
struct PST
{
    int sum[N * 200], ls[N * 200], rs[N * 200];
    int rt[N], tot, maxn;
    void update_SgT(int &rt, int l, int r, int pos, int val)
    {
        if (!rt)
            rt = ++tot;
        sum[rt] += val;
        if (l == r)
            return;
        int mid = l + r >> 1;
        if (pos <= mid)
            update_SgT(ls[rt], l, mid, pos, val);
        else
            update_SgT(rs[rt], mid + 1, r, pos, val);
    }
    void update_BIT(int x, int pos, int v)
    {
        for (; x <= maxn; x += lowbit(x))
            update_SgT(rt[x], 1, n, pos, v);
    }
    int rt1[30][30], rt2[30][30], cnt1, cnt2;
    void locate(int l, int r)
    {
        cnt1 = cnt2 = 0;
        for (int i = l - 1; i; i -= lowbit(i))
            rt1[++cnt1][0] = rt[i];
        for (int i = r; i; i -= lowbit(i))
            rt2[++cnt2][0] = rt[i];
    }
    int query(int dep, int l, int r, int ql, int qr)
    {
        if (ql > qr)
            return 0;
        int res = 0;
        if (l >= ql && r <= qr)
        {
            for (int i = 1; i <= cnt1; i++)
                res -= sum[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                res += sum[rt2[i][dep]];
            return res;
        }
        int mid = l + r >> 1;
        if (ql <= mid)
        {
            for (int i = 1; i <= cnt1; i++)
                rt1[i][dep + 1] = ls[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                rt2[i][dep + 1] = ls[rt2[i][dep]];
            res += query(dep + 1, l, mid, ql, qr);
        }
        if (qr > mid)
        {
            for (int i = 1; i <= cnt1; i++)
                rt1[i][dep + 1] = rs[rt1[i][dep]];
            for (int i = 1; i <= cnt2; i++)
                rt2[i][dep + 1] = rs[rt2[i][dep]];
            res += query(dep + 1, mid + 1, r, ql, qr);
        }
        return res;
    }
} PST;
struct Trie
{
    int ch[N][26], tot;
    int dfn[N], cid[N], out[N], cnt;
    int ins(char *s)
    {
        int p = 1, len = strlen(s);
        for (int i = 0; i < len; i++)
        {
            int c = s[i] - 'a';
            if (!ch[p][c])
                ch[p][c] = ++tot;
            p = ch[p][c];
        }
        return p;
    }
    void dfs(int x)
    {
        dfn[x] = ++cnt, cid[cnt] = x;
        for (int i = 0; i < 26; i++)
        {
            if (ch[x][i])
                dfs(ch[x][i]);
        }
        out[x] = cnt;
    }
    int find(char *s, int k)
    {
        int p = 1;
        for (int i = 0; i < k; i++)
        {
            int c = s[i] - 'a';
            if (!ch[p][c])
                return -1;
            p = ch[p][c];
        }
        return p;
    }
} trie;

int main()
{
    scanf("%d%d", &n, &m);
    trie.tot = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s);
        f[i] = trie.ins(s);
    }
    trie.dfs(1);
    PST.maxn = trie.cnt;
    for (int i = 1; i <= n; i++)
    {
        f[i] = trie.dfn[f[i]];
        PST.update_BIT(f[i], i, 1);
    }
    while (m--)
    {
        int op, l, r, k;
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &l, &r);
            PST.update_BIT(f[l], l, -1);
            PST.update_BIT(f[r], r, -1);
            PST.update_BIT(f[r], l, 1);
            PST.update_BIT(f[l], r, 1);
            swap(f[l], f[r]);
        }
        else
        {
            scanf("%s%d%d%d", s, &k, &l, &r);
            int pos = trie.find(s, k);
            if (pos == -1)
            {
                puts("0");
                continue;
            }
            int x = trie.dfn[pos], y = trie.out[pos];
            PST.locate(x, y);
            printf("%d\n", PST.query(0, 1, n, l, r));
        }
    }
    return 0;
}

H.Prince and Princess

题意：

找到被藏到某个房间的公主。 $a,b,c$ 分别表示说真话的人（一定包括公主），说假话的人，不确定说真话说假话的人。你可以问每个人三个问题：1.你是谁 2.谁待在指定的房间 3.公主在哪个房间判断能不能找到公主，可以找到的话并输出至少需要问几个人才可以确定公主一定在哪个房间。

题解：

每次都问公主在哪个房间，一定要满足 $a>b+c$ ，则可以确定且询问次数为 $(b+c)∗2+1$ ,因此最坏情况就是将所有说假话的人，不确定说真话说假话的人都问过了，并且不确定说真话说假话的人也说了假话，那么问 $(b+c)∗2+1$ 个人，有一个房间肯定会出现 $b+c+1$ 次，那公主肯定在这个房间。注意特殊情况 $1，0，0$ 这个人一定是公主，不需要询问，输出 $0$ 。否则 $a \leq b+c$ 输出 $NO$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a <= b + c)
        puts("NO");
    else
    {
        puts("YES");
        if (a == 1 && b == 0 && c == 0)
            printf("0\n");
        else
            printf("%d\n", (b + c) * 2 + 1);
    }
    return 0;
}

J.Spy（KM）

题意：

A队有 $n$ 个队，每个队有能力值 $a_i$ 和名声值 $p_i$
B队有 $2n$ 个人现在要组成 $n$ 个小队，每一个队从 $b_n$ 中取一个人， $c_n$ 中取一个人，组成小队，组成的队伍的能力值是两个能力值之和。
现在将A队和B队中的每一队两两PK一轮，如果B队能力值大于A队就获得相应A队的名声值，询问B队所能获得的最大名声值

题解：

将可以发现将 $b_n$ 和 $c_n$ 组合后形成 $d_n$ ，最终答案就是 $\sum_{i=1}^{n}\sum_{j=1}^{n}[d_i>a_j]p_j$ ，而这道题的关键就是如果组成每一队，可以很自然的将问题转化为二分图最大权匹配，那么就是建完图以后套个 $KM$ 模板，但是这道题卡 $O(n^4)$ ，只能用 $O(n^3)$ 的 $bfsKM$ 来做

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 405;
ll n, a[maxn], b[maxn], c[maxn], p[maxn];
ll w[maxn][maxn];
ll lx[maxn], ly[maxn];
ll match[maxn];
ll slack[maxn];
bool vy[maxn];
ll pre[maxn];
void bfs(ll k)
{
    ll x, y = 0, yy = 0, delta;
    memset(pre, 0, sizeof(pre));
    for (ll i = 1; i <= n; i++)
        slack[i] = inf;
    match[y] = k;
    while (1)
    {
        x = match[y];
        delta = inf;
        vy[y] = true;
        for (ll i = 1; i <= n; i++)
        {
            if (!vy[i])
            {
                if (slack[i] > lx[x] + ly[i] - w[x][i])
                {
                    slack[i] = lx[x] + ly[i] - w[x][i];
                    pre[i] = y;
                }
                if (slack[i] < delta)
                    delta = slack[i], yy = i;
            }
        }
        for (ll i = 0; i <= n; i++)
        {
            if (vy[i])
                lx[match[i]] -= delta, ly[i] += delta;
            else
                slack[i] -= delta;
        }
        y = yy;
        if (match[y] == -1)
            break;
    }
    while (y)
        match[y] = match[pre[y]], y = pre[y];
}

ll KM()
{
    memset(lx, 0, sizeof(lx));
    memset(ly, 0, sizeof(ly));
    memset(match, -1, sizeof(match));
    for (ll i = 1; i <= n; i++)
    {
        memset(vy, false, sizeof(vy));
        bfs(i);
    }
    ll res = 0;
    for (ll i = 1; i <= n; i++)
        if (match[i] != -1)
            res += w[match[i]][i];
    return res;
}

int main()
{
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &p[i]);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &b[i]);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &c[i]);
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = 1; j <= n; j++)
        {
            ll s = 0;
            for (ll k = 1; k <= n; k++)
            {
                if (b[i] + c[j] > a[k])
                    s += p[k];
            }
            w[i][j] = s;
        }
    }
    printf("%lld\n", KM());
    return 0;
}

K.Triangle（计算几何）

题意：

给定一个三角形和一个点 $p$ ，如果该点不在三角形边上直接输出 $−1$ ，否则在三角形上找一点 $q$ ，使得线段 $pq$ 平分三角形面积，输出 $q$ 点坐标。

题解：

首先可以确定要分成三种情况：①该点不在三角形边上②该点为端点③该点在边上且不是端点，①和②可以直接解决。对于③令 $p$ 在 $bc$ 边上，由于 $o$ 为中点，所以 $S_{aob}=S_{aoc}$ ，因此若点 $p$ 在 $ob$ 上，则所求点 $q$ 在 $ac$ 上，同理可得若点 $p$ 在 $oc$ 上，则所求点 $q$ 在 $ab$ 上。因此可由 $S\triangle=\frac{ab*ac*sin\angle{bac}}{2}$ 得，当点在 $ob$ 上时， $cp*cq=\frac{ca*cb}{2}$ ，当点 $p$ 在 $oc$ 上时， $bp*bq=\frac{ba*bc}{2}$ .由此我们可以顺利求出点坐标, $p$ 在其余两边同理可求。具体可以结合代码理解图片说明
同时二分也可以做，可以参考这篇博客戳我~

#include <bits/stdc++.h>
using namespace std;
int x[3], y[3], a, b;
int at[3];
double a1, b1;
//用于判断点(a,b)是否在以(x1,y1)和(x2,y2)的线段上
int atline(int x1, int y1, int x2, int y2, int a, int b)
{
    return ((a - x1) * (y2 - y1) == (b - y1) * (x2 - x1) && (a - x1) * (a - x2) + (b - y1) * (b - y2) <= 0) ? 1 : 0;
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, j;
    cin >> n;
    while (n--)
    {
        for (int i = 0; i < 3; i++)
            cin >> x[i] >> y[i];
        cin >> a >> b;
        for (int i = 0; i < 3; i++)
        {
            int i1 = (i + 1) % 3;
            int i2 = (i + 2) % 3;
            at[i] = atline(x[i1], y[i1], x[i2], y[i2], a, b);
        }
        int cnt = at[0] + at[1] + at[2]; // 所在线段数
        if (cnt == 0)
        { //该点不在三角形边上直接输出-1
            cout << "-1\n";
            continue;
        }
        if (cnt == 2)
        { //说明该点为端点
            j = find(at, at + 3, 0) - at;
            int j1 = (j + 1) % 3;
            int j2 = (j + 2) % 3;
            cout << fixed << setprecision(12) << (x[j1] + x[j2]) / 2.0 << ' ' << (y[j1] + y[j2]) / 2.0 << endl;
        }
        else
        { // cnt == 1
            j = find(at, at + 3, 1) - at;
            int j0 = (j + 1) % 3; // j0为基点
            int jj = (j + 2) % 3;
            // 计算 j0--jj线段上(a,b)的位置比例k1
            double k1 = x[j0] == x[jj] ? (double)(b - y[j0]) / (y[jj] - y[j0]) : (double)(a - x[j0]) / (x[jj] - x[j0]);
            if (k1 < 0.5)
            { // 换基点，保证k1 >= 0.5
                j0 = jj;
                k1 = 1 - k1;
            }
            double k2 = 0.5 / k1;
            // 在j0--j线段上按位置比例k2取点

            a1 = 1.0 * x[j0] + k2 * (x[j] - x[j0]);
            b1 = 1.0 * y[j0] + k2 * (y[j] - y[j0]);
            cout << fixed << setprecision(12) << a1 << ' ' << b1 << endl;
        }
    }
    return 0;
}

2019 ICPC Asia Nanjing Regional