本场比赛由我校MercurySurfer、enterdawn和Raksasa命题，div4难度。
补题链接：https://codeforces.com/contestInvitation/4db715ea54f1286ef034e1950050e138c668fb8b

A.上学的路

题目定位：二分答案

题目答案具有明显二分性，二分答案即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;

int a[N], x[N];
int n, m, b;

bool check(int mid)
{
    for(int i = 1, base = mid;i <= n + 1;i ++)
    {
        int dis = a[i] - a[i - 1];
        if(base < dis) return false;
        base = min(m, base - dis + x[i]);
    }
    return true;
}

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &b);
    for(int i = 1;i <= n;i ++) scanf("%lld", &a[i]);
    for(int i = 1;i <= n;i ++) scanf("%lld", &x[i]);
    a[n + 1] = b;

    int l = 1, r = m + 1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(r == m + 1) printf("-1\n");
    else printf("%lld\n", r);
    return 0;
}

且该题有线性做法：从后向前反推维护当前点所需最小电量即可得出正确答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int a[N], x[N];

signed main()
{
    int n, m, b; cin>>n>>m>>b;
    for(int i = 1;i <= n;i ++) cin>>a[i];
    for(int i = 1;i <= n;i ++) cin>>x[i];
    a[n + 1] = b;

    int base = 0;
    for(int i = n;i >= 0;i --)
    {
        int dis = a[i + 1] - a[i];
        if(base + dis > m)
        {
            cout<<-1<<endl;
            return 0;
        }
        base = max(0, base + dis - x[i]);
    }
    cout<<base<<endl;
    return 0;
}

B.军训

题目定位：签到题

排列的所有可能数为$(n^2)!$
当$n^2 \geq p$时，$(n^2)!$为$p$的倍数所以模$p$意义下结果为0
否则$n^2<p$直接算阶乘即可不会超出时间限制

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int n, p; scanf("%lld%lld", &n, &p);
    if(p <= n * n) printf("0\n");
    else
    {
        int res = 1;
        for(int i = 1;i <= n * n;i ++)
            res = res * i % p;
        printf("%lld\n", res);
    }
    return 0;
}

C.美丽的神话

计算几何入门题，甚至不能被叫做计算几何。
我们观察参数方程，发现我们可以将它转换成极坐标方程的形式：
$$r=2a(1-cost) $$
发现该弧线为心形曲线，不过不知道也没关系。由于直线是过原点的直线，我们也能很容易的将直线转换为极坐标形式：
$$θ=atan(b)$$
易知第一个角为atanb。
因为是直线，我们给第一个角加上$π$，如果加完之后大于$2π$就减掉$2π$使其小于$2π$，最后将两个代入极坐标方程即可。
注意事项1：无论scanf还是cin，读入浮点数都非常慢，容易超时，所以我们能读整数尽量读整数。
注意事项2：用平面直角坐标系去算不仅麻烦，还容易损失精度，造成精度不足。

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <tuple>
#define ll long long
#define pi acos(-1)
#define hu(x) x*pi/180.0
#define mod 998244353
#define linf 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
using namespace std;
struct node {
    int l, r, i;
    bool operator < (node a) {
        return l < a.l;
    }
    node(int _l, int _r, int _i) : i(_i), l(_l), r(_r) {};
};
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b;
        scanf("%d%d", &a, &b);
        double re1 = 2* a * (1 - cos(atan(b)));
        double c = atan(b)+pi;
        if (fabs(c - 2 * pi) <= 0.0000001) c -= 2 * pi;
        double re2 = 2* a * (1 - cos(c));
        printf("%.9lf %.9lf\n", min(re1, re2), max(re1, re2));
    }
    return 0;
}

D.瑄的01数

题目定位：枚举预处理 + 二分查找

先预处理枚举$[1, 1e9]$区间所有合法的$01$数，共$512$个。

每次查询 二分查找左右端点的位置统计个数即可。

(该题数据弱，导致暴力枚举左右端点也能通过，正解为二分查找左右端点)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int MAX = 1e9;

int a[N], cnt;

void dfs(int num)
{
    if(num > MAX) return;
    a[++ cnt] = num;
    dfs(num * 10);
    dfs(num * 10 + 1);
}

signed main()
{
    dfs(1);
    sort(a + 1, a + cnt + 1);

    int t; scanf("%lld", &t);
    for(int i = 1;i <= t;i ++)
    {
        int l, r; scanf("%lld%lld", &l, &r);
        printf("%d\n", upper_bound(a + 1, a + cnt + 1, r) - upper_bound(a + 1, a + cnt + 1, l - 1));
    }
    return 0;
}

E.井字棋

题意很明显，涂满所有黑块的最小操作数，就是让你把所有情况都算一遍，直接写就行了。

但是如何写比较方便呢？

我们可以考虑DFS和位运算模拟。手打所有情况当然也可以。

位运算比较直观，所以本题解采用位运算模拟选择。

#define ll long long
char c[N][N];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n,m;
        scanf("%lld",&n);
        ll x1,x2,y1,y2;
        scanf("%lld%lld%lld%lld",&x1,&x2,&y1,&y2);
        for(int i=1; i<=n; i++)
        {
            scanf("%s",c[i]+1);
        }
        ll sum=0,sumx1=0,sumx2=0,sumy1=0,sumy2=0;
        for(int i=1; i<=n; i++) sumx1+=(c[x1][i]=='W');
        for(int i=1; i<=n; i++) sumx2+=(c[x2][i]=='W');
        for(int i=1; i<=n; i++) sumy1+=(c[i][y1]=='W');
        for(int i=1; i<=n; i++) sumy2+=(c[i][y2]=='W');
        sum+=sumx1+sumx2+sumy1+sumy2-(c[x1][y1]=='W')-(c[x1][y2]=='W')-(c[x2][y1]=='W')-(c[x2][y2]=='W');
        //计算所有要涂黑的块有多少个
        ll calc[4]= {sumx1,sumx2,sumy1,sumy2};
        bool bl[4];
        //标记是否涂过
        ll ans=inf;
        //位运算，模拟选择，例如：1011 就是选y2,y1,x1三条边涂
        //1为选，0位不选,为什么是倒着选，因为是从最后一位开始算的
        for(int i=0; i<=15; i++)
        {
            ll x=i;
            ll num=0;
            ll cnt=0;//记录操作数
            memset(bl,0,sizeof(bl));
            for(int j=0; j<4; j++)
            {
                if(x&1)//最后一位为1运行
                {
                    cnt++;
                    num+=calc[j];
                    bl[j]=1;
                }
                x/=2;
            }
            if(bl[0]&&bl[2]) num-=(c[x1][y1]=='W');
            if(bl[0]&&bl[3]) num-=(c[x1][y2]=='W');
            if(bl[1]&&bl[2]) num-=(c[x2][y1]=='W');
            if(bl[1]&&bl[3]) num-=(c[x2][y2]=='W');
            //删除涂了两次的块
            if(num==sum)
            {
                ans=min(cnt,ans);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

F.回家的路

题目定位：$dp$，解法不唯一，下面介绍一种$dp$方法：

$dp[i][j]$ 代表到达第$i$个充电桩时还有$j$电量的最小花费

转移方程：$dp[i][j] = min(dp[i – 1][j + dis] , dp[i][j – 1] + x_i)$

注意根据本题数据范围规定 $a_i$可能大于$b$

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int inf = 0x3f3f3f3f;

int a[N], x[N];
int f[N][N];

signed main()
{
    int n, m, b, s; scanf("%d%d%d%d", &n, &m, &b, &s);
    for(int i = 1;i <= n;i ++) scanf("%d", &a[i]);
    for(int i = 1;i <= n;i ++) scanf("%d", &x[i]);

    memset(f, 0x3f, sizeof f);
    f[0][s] = 0;
    for(int i = 1;i <= n;i ++)
    {
        int dis = a[i] - a[i - 1];
        for(int j = 0;j + dis <= m;j ++)
            f[i][j] = min(f[i][j], f[i - 1][j + dis]);
        for(int j = 1;j <= m;j ++)
            f[i][j] = min(f[i][j], f[i][j - 1] + x[i]);
    }

    int res = inf;
    for(int i = 0;i <= n && a[i] <= b;i ++)
        for(int j = b - a[i];j <= m;j ++)
            res = min(res, f[i][j]);

    if(res == inf) printf("-1\n");
    else printf("%d\n", res);
    return 0;
}

G.瑄与洛的SOLO赛

题目定位：贪心 + 枚举

贪心思路：在瑄可用英雄中最高熟练度小于洛可用英雄中最高熟练度时，无需考虑瑄对各个英雄的熟练度，每次$ban$英雄必须$ban$洛当前可用英雄中熟练度最高的英雄，否则没有意义。因为洛一定会选这个他熟练度最高的英雄参加比赛。

现将瑄与洛的赢输熟练度非升序排序，但要记录排序前的编号(即英雄编号)，

然后从前向后(从大到小)枚举$ban$掉洛的熟练度最高的前$k$个英雄，每次比较瑄当前可用英雄中熟练度最高的是否不小于洛当前可用英雄中熟练度最高的，若是则输出”Yes”,若枚举完最后都无法满足则输出”No”。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;

pair<int, int> a[N], b[N];
bool vis[N];

signed main()
{
    int n, k; scanf("%lld%lld", &n, &k);

    for(int i = 1;i <= n;i ++)
    {
        int x; scanf("%lld", &x);
        a[i] = make_pair(x, i);
    }
    for(int i = 1;i <= n;i ++)
    {
        int x; scanf("%lld", &x);
        b[i] = make_pair(x, i);
    }

    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    sort(b + 1, b + n + 1, greater<pair<int, int>>());

    int i = 1, j = 1;
    for(;i <= k + 1;i ++)
    {
        while(j <= n && vis[a[j].second]) j ++;
        if(a[j].first >= b[i].first)
        {
            printf("Yes\n");
            return 0;
        }
        vis[b[i].second] = true;
    }

    printf("No\n");
    return 0;
}

H.博弈游戏

由于是任意取一个数，所以在有数的可操作的情况下Alice必赢，没有数的时候Bob赢。

I.瑄的期末考试

签到题，按要求输出即可。

J.瑄的浪漫星空

题目定位：小学数学

因为自身到自身的距离为$0$，为计算方便，可将原式等同于下式

$$ \sum{_ {j = 1, j ≠ i}^n}(x_i – x_j)^2 + (y_i – y_j)^2 $$

$$ =\sum{_ {j = 1}^n}(x_i – x_j)^2 + (y_i – y_j)^2 $$

$$ =\sum{_ {j = 1}^n}(x_i – x_j)^2 + \sum{_{j = 1}^n}(y_i – y_j)^2 $$

$$ =\sum{_ {j = 1}^n}({x_i}^2 – 2x_ix_j + {x_j}^2) + \sum{_{j = 1}^n}({y_i}^2 – 2y_iy_j + {y_j}^2) $$

$$=n{x_i}^2 – 2x_i\sum{_ {j = 1}^n}x_j + \sum{_ {j = 1}^n}{x_ j}^2 + n{y_i}^2 – 2y_i\sum{_ {j = 1}^n}y_j + \sum{_{j = 1}^n}{y_j}^2 $$

预处理得到$\sum{_ {j = 1}^n}x_j$、$\sum{_ {j = 1}^n}{x_ j}^2$、$\sum{_ {j = 1}^n}y_j$ 和 $\sum{_ {j = 1}^n}{y_j}^2$四个数然后逐一枚举计算即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;

int x[N], y[N];

signed main()
{
    int n; scanf("%lld", &n);
    for(int i = 1;i <= n;i ++) scanf("%lld %lld", &x[i], &y[i]);
    int sumx1 = 0, sumx2 = 0, sumy1 = 0, sumy2 = 0;
    for(int i = 1;i <= n;i ++)
        sumx1 += x[i], sumx2 += x[i] * x[i], sumy1 += y[i], sumy2 += y[i] * y[i];
    for(int i = 1;i <= n;i ++)
        cout<< n * x[i] * x[i] - x[i] * 2 * sumx1 + sumx2 + n * y[i] * y[i] - y[i] * 2 * sumy1 + sumy2<<" ";
    cout<<endl;
    return 0;
}