A.All with Pairs

题意：

给定个字符串,要求计算，其中表示的前缀和的后缀最大匹配数，

题解：

首先可以用将的后缀数量都记录下来，然后依次遍历每个，对于每个的前缀记录有多少后缀与之匹配，最终答案就是每个每一位长度之和的平方乘上该长度对应的后缀数量。其中要注意的是这样计算的匹配数并不是最大匹配数，例如在对前缀求匹配数时，的答案必然包含了的答案，因此可以想到利用中求数组的方法来完成去重。最终要注意每一步的精度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const ll mod = 998244353;
const ull base = 233;
string s[maxn];
char b[maxm];
ll cnt[maxm];
int nxt[maxm];
unordered_map<ull, ll> mp;
void get_next(int len)
{
    nxt[1] = 0;
    for (int i = 2, j = 0; i <= len; i++)
    {
        while (j > 0 && b[i] != b[j + 1])
            j = nxt[j];
        if (b[i] == b[j + 1])
            j++;
        nxt[i] = j;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i];
        ull hash = 0, cur = 1;
        int len = (int)s[i].size();
        for (int j = len - 1; j >= 0; j--)
        {
            hash = hash + cur * s[i][j];
            cur *= base;
            mp[hash]++;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int len = (int)s[i].size();
        for (int j = 0; j < len; j++)
            b[j + 1] = s[i][j];
        get_next(len);
        ull hash = 0;
        for (int j = 1; j <= len; j++)
        {
            hash = hash * base + b[j];
            if (mp[hash])
                cnt[j] = mp[hash];
            else
                cnt[j] = 0;
            cnt[nxt[j]] -= cnt[j];
        }
        for (int j = 1; j <= len; j++)
            ans = (((1ll * j * j) % mod) * cnt[j] + ans) % mod;
    }
    printf("%lld\n", ans);
}

B.Boundary

题意：

给定个点，要求找到一个经过原点的圆，使得它的边界上存在尽可能多的给定的点

题解：

因为要经过原点，通过三点可以确定一个圆可以通过枚举任意两个点算出每个圆的圆点，求出出现次数最多的那个圆点，为最多的出现次数。注意在枚举两点时要排除共线的情况。

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-10
struct Point
{
    double x, y;
    Point(double x, double y)
    {
        this->x = x;
        this->y = y;
    }
    Point()
    {
        x = y = 0;
    }
};
Point p[5000];
//过三点求圆心坐标
Point waixin(Point a, Point b, Point c)
{
    double a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    double a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    double d = a1 * b2 - a2 * b1;
    return Point(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
}
pair<double, double> m[2222222];
int main()
{
    int n, i, j = 0, k = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lf%lf", &p[i].x, &p[i].y);
    Point z(0, 0);
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (fabs(p[i].x * p[j].y - p[i].y * p[j].x) > eps)//判断是否三点共线
            {
                Point temp = waixin(p[i], p[j], z);
                m[k++] = make_pair(temp.x, temp.y);
            }
        }
    }
    if (k == 0)
    {
        puts("1");
        return 0;
    }
    sort(m, m + k);
    int cnt = 1, mx = 1;
    for (int i = 0; i < k - 1; i++)
    {
        if (fabs(m[i].first - m[i + 1].first) < eps && fabs(m[i].second - m[i + 1].second) < eps)
        {
            cnt++;
            mx = max(mx, cnt);
        }
        else
            cnt = 1;
    }
    for (int i = 1; i <= n; i++)
        if (i * (i - 1) == 2 * mx)
        {
            printf("%d\n", i);
            break;
        }
    return 0;
}

C.Cover the Tree

题意：

给定一个个节点的无根树，要求选出最少的链，使得选出的链能覆盖树上的每一条边，输出一种可行的方案。

题解：

首先可以知道最少的方案数肯定为。
这题觉得官方题解写得挺好，就直接贴过来了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<int> G[maxn];
int deg[maxn], dfn[maxn], id[maxn], cnt;
vector<int> e;
void dfs(int u, int f)
{
    dfn[u] = ++cnt;
    id[cnt] = u;
    if (G[u].size() == 1)
    {
        e.push_back(cnt);
        return;
    }
    for (auto v : G[u])
    {
        if (v == f)
            continue;
        dfs(v, u);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    if (n == 1)
    {
        puts("0");
        return 0;
    }
    if (n == 2)
    {
        puts("1 2");
        return 0;
    }
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] >= 2)
        {
            dfs(i, 0);
            break;
        }
    int sum = (e.size() + 1) / 2;
    printf("%d\n", sum);;
    sort(e.begin(), e.end());
    for (int i = 0; i < sum; i++)
        printf("%d %d\n", id[e[i]], id[e[i + e.size() / 2]]);
    return 0;
}

D.Duration

题意：

给定两个时间，求它们的时间差

题解：

签到题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
int main()
{
    int h1, m1, s1, h2, m2, s2;
    scanf("%d:%d:%d", &h1, &m1, &s1);
    scanf("%d:%d:%d", &h2, &m2, &s2);
    ll s1 = 1ll * h1 * 3600 + m1 * 60 + s1;
    ll s2 = 1ll * h2 * 3600 + m2 * 60 + s2;
    printf("%lld\n", fabs(s1 - s2));
    return 0;
}

F.Fake Maxpooling

题意：

给定一个的矩阵，其中，给定一个，要求计算出每个规模为的子矩阵中最大元素的和

题解：

两次滑动窗口，第一次滑动窗口求出每行每个元素的最大值，形成一个的新矩阵，再对新矩阵每一列进行一次滑动窗口，求出每的最大值，最大值之和即为最终所求。
可以学习的地方是标程用类似埃筛的方法把的复杂度降到了

for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!a[i][j])
                for (int k = 1; k * i <= n && k * j <= m; ++k)
                    a[k * i][k * j] = i * j * k;

代码：

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 2e6 + 10;
typedef long long ll;
int a[5005][5005];
int mp[5005][5005];
int que[5005];
int main()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!a[i][j])
                for (int k = 1; k * i <= n && k * j <= m; ++k)
                    a[k * i][k * j] = i * j * k;
    for (int j = 1; j <= m; j++)
    {
        int head = 1, tail = 1;
        for (int i = 1; i < k; i++)
        {
            while (tail >= head && a[i][j] > a[que[tail]][j])
                tail--;
            tail++;
            que[tail] = i;
        }
        for (int i = k, z = 1; i <= n; i++, z++)
        {
            while (tail >= head && i - que[head] >= k)
                head++;
            while (tail >= head && a[i][j] > a[que[tail]][j])
                tail--;
            tail++;
            que[tail] = i;
            mp[z][j] = a[que[head]][j];
        }
        for (int i = 1; i <= tail; i++)
            que[i] = 0;
    }
    ll sum = 0;
    for (int i = 1; i <= n - k + 1; i++)
    {
        int head = 1, tail = 1;
        for (int j = 1; j < k; j++)
        {
            while (tail >= head && mp[i][j] > mp[i][que[tail]])
                tail--;
            tail++;
            que[tail] = j;
        }
        for (int j = k; j <= m; j++)
        {
            while (tail >= head && j - que[head] >= k)
                head++;
            while (tail >= head && mp[i][j] > mp[i][que[tail]])
                tail--;
            tail++;
            que[tail] = j;
            sum += mp[i][que[head]];
        }
        for (int j = 1; j <= tail; j++)
            que[j] = 0;
    }
    printf("%lld\n", sum);
    return 0;
}

G.Greater and Greater

题意：

给定一个长度为的序列和一个长度为的序列，要求求出中存在多少个长度为的字串,满足的每一位均大于的对应位

题解：

对于每一个求出一个长度为的，其中表示。
对于样例可以求出

如果对于每个都得遍历一次，那显然复杂度太高了，更好的办法是记录下的位置，然后对进行排序，同时对排序后的B也求出个,排序后的只需在的基础上再在令原先位置上的地方为即可。这样就只需根据在算出，这样就可以算出所有的

观察样例可以发现，只有一列的全部元素都等于，才对答案有贡献，所以问题就是求出所有全为的列数。
可以从第一位开始每次都将上一次的结果右移一位再与当前位的与一下，判断次过后结果的第位是否为，为则说明有贡献，答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 5;
const int inf = 0x3f3f3f3f;
int n, m, ans;
int a[150005], b[maxn], ord[maxn];
bitset<maxn> cur, B[maxn];

int find(int x)
{
    int l = 0, r = m;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (x < b[ord[mid]])
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

bool cmp(int x, int y)
{
    return b[x] < b[y];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i++)
        scanf("%d", &b[i]), ord[i] = i;
    sort(ord, ord + m, cmp);
    for (int i = 1; i <= m; i++)
    {
        B[i] = B[i - 1];
        B[i].set(ord[i - 1]);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        cur >>= 1;
        cur.set(m - 1);
        cur &= B[find(a[i])];
        ans += cur[0];
    }
    printf("%d\n", ans);
    return 0;
}

H.Happy Triangle

题意：

给定次询问，一共有三种操作：

1. 插入一个数
2. 删除一个数
3. 能否找到两条边与构成一个三角形

题解：

这题的关键是解决第三个操作，首先知道满足和(其中)就可以构成一个三角形。因此如果存在，找到一个，那么为的前驱时一定符合条件，所以只需要维护和前驱的差值，每次找到，之后的数都可以作为选取，因此每次只需选取中差值最小和判断大小即可。关于的选取，，先判断和的前驱之和是否大于，如果是则这个数为，否则取的后继作为。可以用权值线段树来维护相邻两个数的差值，考虑到要在线操作，因此用动态权值线段树来维护即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int tr[maxn*40],ls[maxn*40],rs[maxn*40],cnt,now;
map<int,int>mp;
void update(int &rt,int l,int r,int pos,int val)
{
    if(!rt)rt=++cnt;
    if(l==r)
    {
        tr[rt]=val;
        return;
    }
    int mid = l+r >>1;
    if(pos<=mid)update(ls[rt],l,mid,pos,val);
    else update(rs[rt],mid+1,r,pos,val);
    int ans = INF;
    if(ls[rt]) ans = min(ans, tr[ls[rt]]);
    if(rs[rt]) ans = min(ans, tr[rs[rt]]);
    tr[rt] = ans;
}
int query(int rt,int l,int r,int L,int R)
{
    if(r<l||!rt)return INF;
    if(L<=l&&r<=R)return tr[rt];
    int mid = l+r >>1;
    int ans = INF;
    if(L<=mid)ans=min(ans,query(ls[rt],l,mid,L,R));
    if(R>mid)ans=min(ans,query(rs[rt],mid+1,r,L,R));
    return ans;
}
void add(int x)
{
    mp[x]++;
    if(mp[x]==1)
    {
        auto it = mp.lower_bound(x);
        if(++it != mp.end()&&it->second==1)
            update(now,0,1e9,it->first,it->first-x);
        if(--it!=mp.begin())
            update(now,0,1e9,x,x-(--it)->first);
    }
    else if(mp[x]==2)update(now,0,1e9,x,0);
}
void del(int x)
{
    auto it = mp.lower_bound(x);
    mp[x]--;
    int l=-1e9;
    if(it!=mp.begin()){
        l=(--it)->first;
        ++it;
    }
    if(mp[x]==0){
        if((++it)!=mp.end() && it->second==1)
            update(now,0,1e9,it->first,it->first-l);
        update(now,0,1e9,x,INF);
        mp.erase(x);
    }
    else if(mp[x]==1)update(now,0,1e9,x,x-l);
}

int ask(int x)
{
    auto it = mp.lower_bound(x/2+1);
    if(it == mp.end()) return INF;
    if(it->second > 1) return it->first;
    if(it != mp.begin()){
        auto l = it; --l;
        if(l -> first + it -> first > x) return it->first;
    }
    if((++it) != mp.end()) return it->first;
    return INF;
}

int main()
{
    int q;
    scanf("%d", &q);
    while(q--){
        int op, x;
        scanf("%d%d", &op, &x);
        if(op == 1) add(x);
        if(op == 2) del(x);
        if(op == 3)
        {
            if(query(1, 0, 1e9, ask(x), 1e9) < x) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

I.Interval

题意：

给定一个区间，初始时为，每次操作可以将区间变为下面的其中之一：

现在给出次限制，每次限制给定一个区间，禁止操作，花费为。表示当区间为可以通过花费来使得区间无法对进行操作。现在要使得，要求最少的花费为多少

题解：

首先把问题转化为二维的网格图，对变为点，其中源点定为，汇点定为，对的操作，从向连一条费用为的边，对的操作，从向连一条费用为的边，其余边的费用均为，最终答案即对这个图跑一遍最大流即可，如果最大流不为，则最大流即为最少花费，否则输出。但是观察到，最大可能有个点，跑最大流会超时，因此想到将平面图转化为对偶图，原先的最大流就是对偶图中的最短路，因此只需要对对偶图跑一遍最短路即可。这题与狼抓兔子类似，可以参考狼抓兔子戳我~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
int n, m, S, T;
int head[maxn * maxn], cnt;
struct Edge
{
    int to, nex;
    ll w;
} e[maxn * maxn * 4];
void addedge(int u, int v, ll w)
{
    e[++cnt] = (Edge){v, head[u], w};
    head[u] = cnt;
}

struct node
{
    int u;
    ll d;
    bool operator<(const node &C) const
    {
        return d >= C.d;
    }
};
ll dis[maxn * maxn];
bool vis[maxn * maxn];
void dijkstra()
{
    priority_queue<node> q;
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    q.push((node){S, 0});
    while (!q.empty())
    {
        node t = q.top();
        q.pop();
        int u = t.u;
        ll d = t.d;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = e[i].nex)
        {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w)
            {
                dis[v] = dis[u] + e[i].w;
                q.push((node){v, dis[v]});
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n * n + 1;
    ll sum = 0;
    for (int i = 1; i <= m; i++)
    {
        char c;
        int l, r, x, y;
        ll w;
        scanf("%d%d %c %lld", &l, &r, &c, &w);
        sum += w;
        x = (l - 1) * n + r;
        if (c == 'L')
            y = ((r == n) ? T : x + 1);
        else
            y = max(S, x - n);
        addedge(x, y, w);
        addedge(y, x, w);
    }
    dijkstra();
    if (dis[T] > sum)
        printf("-1");
    else
        printf("%lld", dis[T]);
}

J.Just Shuffle

题意：

给定张牌，初始顺序为，现在将它进行置换。给出经过次置换后的顺序，求经过次置换后的顺序

题解：

可以发现整个序列会形成这么多的环，每个环的长度为，对于每个环只需要置换次就可以回到原来位置，因此也就意味着。理解了这个，那么不妨将经过次置换后的序列看成一个整体，那么只需要求出，因此需要对序列再经过次置换就能得到置换次的序列。将上式中的除到右边就得到了，因此就为的逆元。所以只需要找出每一个环，求出环长度的逆元即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], used[maxn], ans[maxn], tmp[maxn];
vector<int> seq;
int n, m;
ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    else
    {
        ll r = ex_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}
ll inv(ll a, ll p) //a在模p意义下的逆元若gcd(a,p)!=1,逆元不存在
{
    ll x, y;
    ex_gcd(a, p, x, y);
    x = (x % p + p) % p;
    return x;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++)
    {
        if (!used[i])
        {
            seq.clear();
            int now = i;
            while (!used[now])
            {
                seq.push_back(now);
                used[now] = 1;
                now = a[now];
            }
            int k = inv(m % seq.size(), seq.size());
            for (int j = 0; j < seq.size(); j++)
                tmp[j] = seq[(j + k) % seq.size()];
            for (int j = 0; j < seq.size(); j++)
                ans[seq[j]] = tmp[j];
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    return 0;
}

K.Keyboard Free

题意：

给定三个半径为的同心圆，分别在其圆上取一点，询问组成的三角形面积期望

题解：

可以参考这篇博客。戳我~

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-7
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1);
int r[3];
double f(double x)
{
    if (x == 0)
        return 0;
    double sinx = sin(x), cosx = cos(x);
    double t1 = r[1] * r[1] * sinx * sinx + (r[1] * cosx - r[0]) * (r[1] * cosx - r[0]);
    double ang1 = atan(r[1] * sinx / (r[1] * cosx - r[0]));
    double ang2 = asin(r[0] * sin(ang1) / r[2]);
    double t2 = 4 * r[2] * (ang2 * sin(ang2) + cos(ang2));
    return t2 * sqrt(t1);
}

double SimpleSimpson(double a, double b) // 辛普森求积公式
{
    return (b - a) / 6.0 * (f(a) + f(b) + 4 * f((a + b) / 2.0));
}

double Simpson(double l, double r, double ans) // 方法: 自适应辛普森
{
    double mid = (l + r) / 2;
    double ansl = SimpleSimpson(l, mid);
    double ansr = SimpleSimpson(mid, r);
    if (fabs(ansl + ansr - ans) <= eps)
        return ans;
    return Simpson(l, mid, ansl) + Simpson(mid, r, ansr);
}

void solve()
{
    for (int i = 0; i < 3; i++)
        scanf("%d", &r[i]);
    sort(r, r + 3);
    printf("%.1f\n", Simpson(0, 2 * PI, SimpleSimpson(0, 2 * PI)) / (2 * PI * 2 * PI * 2));
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

官方题解