T1

对于一个矩形我们只要统计固定当前的点，然后就找它的主对角线结点。
通过枚举发现规律：
0 0 0 0
0 0 0 0
0 0 0 0
对于这个3 x 4的格点图来讲只有2 x 3的格点对答案产生了影响
我们发现这个影响自上而下为
6 4 2
3 2 1
以此，我们推论n x m的规律为：
cout << ((((n - 1) * n) / 2) % mod) * ((((m - 1) * m) / 2) % mod) % mod;

T2

典型贪心题目
假设我们没有加和为s的限制我们很容易得到：
若ai < bi那么我们当前值为ai
否则就取bi。
这样我们就可以保证它一定是最小答案，但是由于增加了s的限制，我们发现对于每个数来讲，
加减产生的影响其实是一样的所以我们只需要判断当前值可否移动即可，若最后移动完加和
仍不满足条件 = s，即没有答案。
//分割线
code:
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;

const int MAXN = 2e5 + 17;

int n;
long long a[MAXN],b[MAXN],c[MAXN],S,mo,sum,w;

int main()
{
    cin >> n >> S;
    for(int i = 1;i <= n;i += 1)
        cin >> a[i];
    for(int i = 1;i <= n;i += 1)
        cin >> b[i];
    for(int i = 1;i <= n;i += 1)
    {
        if(a[i] >= b[i])c[i] = b[i];
        else c[i] = a[i];
        sum += c[i];
    }
    mo = S - sum;
    if(mo > 0)
    {
        for(int i = 1;i <= n;i += 1)
        {
            w = a[i] - c[i];
            if(w <= mo)
            {
                mo -= w;
                c[i] = a[i];
            }
            else {
                c[i] += mo;
                mo = 0;
            }
            if(mo == 0)break;
        }
        if(mo > 0){
            cout << -1 << endl;
            return 0;
        }
    }
    if(mo < 0)
    {
        for(int i = 1;i <= n;i += 1)
        {
            w = 0 - c[i];
            if(w >= mo)
            {
                mo -= w;
                c[i] = 0;
            }
            else {
                c[i] += mo;
                mo = 0;
            }
            if(mo == 0)break;
        }
        if(mo < 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    long long ans = 0;
    for(int i = 1;i <= n;i += 1)
        ans += abs(c[i] - b[i]);
    cout << ans << endl;
    for(int i = 1;i <= n;i += 1)
        cout << c[i] << ' ';
    cout << endl;
    return 0;
}

T3

对于所有洪水点何时联通，我们发现对于一个点到另一个点所需时间为(x + y)/2，并且对
于每个点都可以向外连边，所以问题就转化成了最小生成树问题，对于我们的答案就是最小
生成树中的最大边的值。由于并不是特别能存的下边所以我们考虑prim算法（甚至可以
不需要优化，不过貌似这题优化也没啥太大作用qwq）
//挂题原因
对于kruskal来讲，我们处理的时候是默认至少2个点的所以需要特判一个点的情况
而prim的初始值就是ans = 0；
//分割线
code:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

const int INF = 1e9 + 17;
const int MAXN = 2e4 + 17;

int W,H,n,x[MAXN],y[MAXN],d[MAXN],res,ans;
bool vis[MAXN];

int main()
{
    cin >> W >> H >> n;
    for(int i = 1;i <= n;i += 1)
        cin >> x[i] >> y[i];
    memset(vis,0,sizeof(vis));
    d[1] = 0;
    vis[1] = 1;
    for(int i = 2;i <= n;i += 1)
        d[i] = (abs(x[1] - x[i]) + abs(y[1] - y[i]))/2;
    int k;
    for(int i = 2;i <= n;i += 1)
    {
        res = INF;
        for(int j = 1;j <= n;j += 1)
            if(!vis[j] && d[j] < res)
            {
                k = j;
                res = d[j];
            }
        ans = max(ans,res);
        vis[k] = 1;
        for(int j = 1;j <= n;j += 1)
        {
            int w = (abs(x[k] - x[j]) + abs(y[k] - y[j]))/2;
            if(!vis[j] && d[j] > w)d[j] = w;
        }
    }
    cout << ans << endl;
    return 0;
}

T4

我们发现1 / 7 和3 / 7的循环节答案贡献一样只是移动了一位，是因为10 % 7 = 3,而这个找
循环节都是哪些数的循环节的过程其实就是我们一开始推出当前数的循环节的过程。所以我们
的算法复杂度也是大大减小。
我们只需要查找当前数有无循环节，如果没有，就将它求出并将这个循环节的影响传递下去
//分割线
code:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 1e6 + 17;
const int mod =  998244353;

int tot,p;
long long r[MAXN],a[MAXN],ans;
bool vis[MAXN];

void getp(int u)
{
    tot++;
    r[tot] = 1;
    int x = u,num = 0;
    while(1)
    {
        num++;
        vis[x] = 1;
        r[tot] = r[tot] * a[x*10/p] % mod;
        x = x * 10 % p;
        if(x == u)break;

    }
    r[tot] = r[tot] * num % mod;
    ans = (ans + r[tot]) % mod;
}

int main()
{
    cin >> p;
    for(int i = 0;i <= 9;i += 1)
        cin >> a[i];
    for(int i = 1;i < p;i += 1)
        if(!vis[i])getp(i);
    cout << ans << endl;
    return 0;
}