出题人预估难度：
签到：AJM
简单：CGL
中等：DFH
偏难：BIE
困难：K

A-别叫我那刻夏

题目大意

输入一个正整数 $x$ ，如果为 $315211$ 就输出宁波大学笔画数，否则输出阿那克萨戈拉斯笔画数。

解题思路

纯签到，唯一坑点是子的笔画是 $3$ 笔。宁波大学笔画数为 $24$ 。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll x;
int main(){
    cin>>x;
    if(x==315211)
        cout<<24;
    else
        cout<<55;
}

J-选最好的算法

题目大意

给定一个数 $n$ ，比较 $n!$ 与 $2^n$ 的大小。

解题思路

签到第二题，当 $n\le 3$ ， $n!$ 明显小于 $2^n$ ；当 $n\ge 4$ ， $n!$ 明显大于 $2^n$ 。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll T,n;
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        if(n<=3)
            cout<<1<<'\n';
        else
            cout<<2<<'\n';
    }
}

M-手机里有一款四字游戏

题目大意

根据题目中的段位匹配规则（要求在连续大段位内），判断两名玩家能否一起匹配。（注意玩家的段位只升不降）

解题思路

签到，注意不能直接通过两名玩家的小段位差距来判断，因为像 A1 和 B5，A5 和 C1，前者差了 $9$ 小段，后者差了 $6$ 小段，但前者可以一起匹配后者不行，所以与小段位的差值没有必然联系。

于是本题做法是，先判断大段位只差是不是大于等于 $2$ ，若是，则转化成小段位差，最后输出结果。

参考代码

#include<bits/stdc++.h>
using namespace std;
char Ax, Ay, Bx, By;
int main(){
    cin >> Ax >> Ay >> Bx >> By;
    if (abs(Ax - Bx) >= 2) {
        cout << "NO" << '\n';
        if (Ax <= Bx) {
            cout << (Bx - Ax - 2) * 5 + 6 - (Ay - '0');
        }
        else {
            cout << (Ax - Bx - 2) * 5 + 6 - (By - '0');
        }
    }
    else {
        cout << "YES";
    }
    return 0;
}

C-仿生人不会梦到彩色电子羊

题目大意

给定一个 $n$ 个节点的树，用 $K$ 个颜色对树每个点染色，相邻节点颜色不能相同。

解题思路

假定 $1$ 号节点为根节点，从根往叶子染色，根节点有 $K$ 种染色方法，它的儿子节点不能与它自己颜色相同，由于他们之间不会互相影响，因此这些儿子节点都有 $K-1$ 种染色方法。发现除了根节点的所有节点都有 $K-1$ 种染色方法。

最终得到式子 $K\times (K-1)^{n-1}$ 。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MO 1000000007
using namespace std;
ll n,K,ans;
int main(){
    cin>>n>>K;ans=K;
    for(ll i=1,u,v;i<n;i++)
        cin>>u>>v,ans*=K-1,ans%=MO;
    cout<<ans;
}

G-无路可逃

题目大意

在给定的二维平面，模拟对一个矩形区域进行干扰，注意同一个地方干扰两次会被抵消。

最后输出***扰的面积。

解题思路

直接对每个单位面积进行模拟会超时，于是考虑二维差分。

对于每一个单位的面积，他的干扰次数可以通过差分来做到 $O(1)$ 存储，二维的话可以通过容斥原理来差分。

最后再进行二位前缀和就能统计出答案了，前缀和时间复杂度是 $O(nm)$ 。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int _;
int n,m;
int p[3600][3600];
int x,y,xx,yy;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    cin >> _;
    while (_--) {
        cin >> x >> y >> xx >> yy;
        p[x][y] += 1;
        p[xx + 1][y] -= 1;
        p[x][yy + 1] -= 1;
        p[xx + 1][yy + 1] += 1;
    }
    ll ans = 0;
    for (int i = 1;i <= n;++i) {
        for (int j = 1;j <= m;++j) {
            p[i][j] += p[i][j - 1];
        }
    }
    for (int j = 1;j <= m;++j) {
        for (int i = 1;i <= n;++i) {
            p[i][j] += p[i - 1][j];
        }
    }
    for (int i = 1;i <= n;++i) {
        for (int j = 1;j <= m;++j) {
            if (p[i][j] % 2 == 1) {
                ans += 1;
            }
        }
    }
    cout << ans;
    return 0;
}

L-人有五名，代价有三个

题目大意

求一个字符串中， $a5b3c$ 形式的子串个数。

题目要求相当于寻找所有包含子序列 "53" （即 "5" 的位置小于 "3" 的位置）的子串个数。

解题思路

枚举每个左端点。

对于所有左端点相同的子串，从左往右枚举右端点，用 $vis5,vis53$ 变量记录是否出现 "5" 与是否出现 "53" 子序列，初始值为 $0$ 。如果出现 "5"，那么 $vis5=1$ ；如果出现 "3" ，并且 $vis5==1$ ，说明有 "53" 子序列，那么 $vis53=1$ 。判断完后如果 $vis53==1$ ，说明当前子串是 $53$ 句式。

时间复杂度是 $O(n^2)$ 。

（存在时间复杂度 $O(n)$ 的算法。）

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,ans;
string s;
int main(){
    cin>>s;
    n=s.length();
    s='@'+s;
    for(ll i=1,vis5,vis53;i<=n;i++){
        vis5=vis53=0;
        for(ll j=i;j<=n;j++){
            if(s[j]=='5')
                vis5=1;//找到子序列"5"
            else if(vis5&&s[j]=='3')
                vis53=1;//找到子序列"53"
            if(vis53) ans++;
        }
    }
    cout<<ans;
}

D-神秘小游戏

题目大意

模拟地图中每个玩家的数值 $power$ 。

地图最多容纳 $k$ 个玩家。

玩家的 $power$ 值会在下列情况发生变化：

当玩家进入地图时，全员的 $power$ 值加一，而他自己的 $power$ 值变为 $0$ 。
当玩家重生时， $power$ 值小于他的人全员加一，大于他的人不变，而他自己的 $power$ 值变为 $0$ 。
当玩家离开地图时， $power$ 值小于他的人不变，大于他的人全员减一，而他自己的 $power$ 值被移除。

我们需要维护所有玩家的 $power$ 值，并对每一种指令做出对应的回应。输出描述看题目，就不累赘了。

解题思路

$power$ 值是唯一的。

用一个字符串数组维护每个 $power$ 值对应的玩家。

然后 $power$ 值变化时，按要求对这个数组中的玩家进行换位即可。

时间复杂度是 $O(20mk)$ （ $20$ 是名字的最大长度）。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MXN 1002
using namespace std;
ll m,k,num;
string hook[MXN];
int main(){
    cin>>m>>k;
    while(m--){
        string op,name;
        ll power,x;
        cin>>op;
        if(op=="find"){//找power值对应的玩家
            x=0;
            cin>>power;
            cout<<hook[power]<<'\n';
        }else{
            cin>>name;
            if(op=="join"){{//玩家加入
                x=0;
                if(num<k){
                    for(ll i=num;i;i--)
                        hook[i]=hook[i-1];
                    hook[0]=name;
                    num++;
                    cout<<"joined\n";
                }else{
                    cout<<"full\n";
                }
            }else if(op=="exit"){{//玩家退出
                for(ll i=0;i<num;i++)
                    if(hook[i]==name) x=i;
                for(ll i=x;i<num-1;i++)
                    hook[i]=hook[i+1];
                num--;
                cout<<"exited\n";
            }else if(op=="kill"){//玩家重生
                for(ll i=0;i<num;i++)
                    if(hook[i]==name) x=i;
                for(ll i=x;i;i--)
                    hook[i]=hook[i-1];
                hook[0]=name;
                cout<<"killed\n";
            }else{//找玩家对应的power值
                for(ll i=0;i<num;i++)
                    if(hook[i]==name) x=i;
                cout<<x<<'\n';
            }
        }
    }
}

F-崩环：星球轨道

题目大意

有 $n$ 环轨道，所有轨道的圆心在 $x$ 轴上，所有轨道在同一个二维平面上。

问有多少数对 $\{i,j\}(i<j)$ ，满足第 $i$ 个轨道与第 $j$ 个轨道相切或相交。

解题思路

$i$ 轨道与 $j$ 轨道相交，那么 $j$ 轨道与 $i$ 轨道相交。如果不限制数对 $\{i,j\}$ 的 $i,j$ 大小关系，那么每个 $\{i,j\}(i<j)$ 对应一个 $\{j,i\}(i<j)$ 这样的数量恰好是要求的答案 $ans$ 乘上 $2$ 。也就是说，轨道的顺序不重要，我们对轨道换位也不影响最终结果。

我们求出每个轨道的左右端点 $[l,r]$ 。

我们对轨道按左端点 $l$ 从小到大排序，如果左端点 $l$ 相同，右端点 $r$ 小的在前。

对于排序后第 $i$ 个轨道 $[l_i,r_i]$ ，如果排在它前面的第 $j(j<i)$ 个轨道 $[l_j,r_j]$ ，满足 $l_i<=r_j<=r_i$ ，那么这两个轨道相交。

我们只需要对每个轨道，求出在排序后序号更小的轨道中，有多少个轨道，它的 $r$ 值在当前轨道范围内，这样的排序方式保证了不会重复或者漏算。

使用数据结构（参考代码是线段树）维护区间和，具体维护区间有多少个轨道的 $r$ 值在区间中。

时间复杂度是 $O(nlogn)$ 。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MXN 100002
using namespace std;
struct XD_tree{
    ll pl,pr,sum;//左右子树与区间和
}tr[MXN*8];//线段树
ll trt,rt;//线段树节点数与根
struct huan{
    ll l,r;//轨道左右端点
}a[MXN];//轨道
ll n,m=400002,x[MXN],r[MXN],ans;//轨道覆盖的范围大小能到400000
bool cmp(huan i,huan j){
    return i.r==j.r?i.l<j.l:i.r<j.r;
}
void ptup(ll p){//以下为线段树基本操作
    tr[p].sum=tr[tr[p].pl].sum+tr[tr[p].pr].sum;
}
void chg(ll &p,ll l,ll r,ll x,ll k){
    if(!p) p=++trt;//因为懒没写线段树的建树，而直接开点。
    if(l==r){
        tr[p].sum+=k;
        return;
    }
    ll mid=l+r>>1;
    if(x<=mid) chg(tr[p].pl,l,mid,x,k);
    else chg(tr[p].pr,mid+1,r,x,k);
    ptup(p);
}
ll ask(ll p,ll l,ll r,ll x,ll y){
    if(!p) return 0;
    if(x<=l&&r<=y) return tr[p].sum;
    ll mid=l+r>>1,ans=0;
    if(x<=mid) ans+=ask(tr[p].pl,l,mid,x,y);
    if(y>mid) ans+=ask(tr[p].pr,mid+1,r,x,y);
    return ans;
}//以上为线段树基本操作
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>x[i];
    for(ll i=1;i<=n;i++)
        cin>>r[i];
    for(ll i=1;i<=n;i++)
        a[i]={x[i]-r[i],x[i]+r[i]};
    sort(a+1,a+n+1,cmp);
    for(ll i=1;i<=n;i++){
        ans+=ask(rt,1,m,1,a[i].l+m/2);
        chg(rt,1,m,a[i].l+m/2,1);
        chg(rt,1,m,a[i].r+1+m/2,-1);
    }
    cout<<ans<<'\n';
}

H-阿基维利的列车

题目大意

给定 $n,k$ ，构造一个长度为 $n$ 的数列 $\{a_1,a_2,\dots,a_n\}$ 。使得下列条件成立。

相邻两个数互质。
相隔 $k$ 个数的两个数非互质。
所有的值互不相同，且范围为 $[1,10^{18}]$ 。

解题思路

一、思路引导：

$1$ 无法与其他数满足非互质，我们不考虑 $1$ 。

尝试先满足相邻互质，按顺序的数 $\{2,3,4,5\dots\}$ 虽然满足，但是在普遍情况下无法满足非互质。

尝试用质数数列， $\{2,3,5,7,11\dots\}$ 全部互质，也无法满足非互质。

为了形象化，将每 $k+1$ 个数作为一行，比如当 $n=8,k=2$ ，列成下面形式：

$\{a_1,a_2,a_3,$
$a_4,a_5,a_6,$
$a_7,a_8\}$

那么每一列需要非互质。

如果按 $\{2,3,5,7,11\dots\}$ ，那么所有数之间都互质，非互质最简单的满足方法便是给这整列乘上同一个数，比如给第 $1$ 列乘上 $2$ 。

$\{2a_1,a_2,a_3,$
$2a_4,a_5,a_6,$
$2a_7,a_8\}$

既然如此那我们给第 $2$ 列乘上 $3$ ；但是第 $3$ 列不能乘上 $4$ ，会与第 $1$ 列非互质，那么给第 $3$ 列乘上 $5$ 。

$\{2a_1,3a_2,5a_3,$
$2a_4,3a_5,5a_6,$
$2a_7,3a_8\}$

因此，为了仍然满足相邻互质，将每列乘上不同的质数，而且这个质数最好不出现在其他列的数的因子中。

二、构造方法：

尝试使用质数数列 $\{2,3,5,7,11\dots\}$ 初步作为 $\{a_1,a_2,\dots,a_n\}$ ，给第 $i(1\le i\le k+1)$ 列的数乘上 $a_i$ ，既保证了每列非互质，又因为质数 $a_i$ 是独一的，不同列之间也不会存在大于 $1$ 的公因数，即满足相邻互质。不难发现这样的数列每个数不相同。满足题目要求。

因此 $n=8,k=2$ 能构造出下面数列：

$\{2\times2,3\times3,5\times5,$
$2\times7,3\times11,5\times13,$
$2\times17,3\times19\}$

（构造方法不唯一，存在许多构造方法。~~甚至有随机数的~~）

参考代码

参考代码为了取模偷点懒，数组从下标0开始

#include<bits/stdc++.h>
#define ll long long
#define MXM 3000002
#define MXN 220002
using namespace std;
ll n,k;
ll p[MXN],tt;
bool vis[MXM];
int main(){
    for(ll i=2;i<MXM;i++)//埃氏筛
        if(!vis[i]){
            p[tt++]=i;
            for(ll j=i*2;j<MXM;j+=i)
                vis[j]=1;
        }
    cin>>n>>k;
    for(ll i=n-1;i>=0;i--)
        p[i]*=p[i%(k+1)];
    for(ll i=0;i<n;i++)
        cout<<p[i]<<' ';
}

B-阳光跑

题目大意

给定一个有向图，每次询问求 Bezime 从一个节点 $x$ 出发，行走恰好 $k$ 条边后，可能会出现在哪些节点，输出节点个数并从小到大输出这些节点的编号。

解题思路

~~题目很板，有原题。~~

行走的距离很大，而且也不像无向图那样可以分奇偶解决。

由于距离很大，又没什么好的贪心方法，联想到快速幂。

注意到题目给的节点个数 $n$ 比较小，边数 $m$ 比较大，可以考虑直接写出 $n^2$ 的邻接矩阵。

邻接矩阵能表示每个点走 $1$ 步能到的点，想到邻接矩阵自乘得到的矩阵是每个点走 $2$ 步能到的点，继续自乘则是 $4$ 步、 $8$ 步，以此类推。

如此，便能设置初始矩阵为单位矩阵，用矩阵快速幂求出每个点走 $k$ 步能到的点。但每次询问的时间复杂度为 $O(n^3logn)$ ，总时间复杂度为 $O(Tn^3logn)$ 。

初步写出下面代码， $f$ 初始是 $n\times n$ 邻接矩阵, $a$ 初始是 $n\times n$ 单位矩阵。

while(k){
    if(k&1) a=mul(a,f);
    f=mul(f,f);
    k>>=1;
}

考虑优化，想到每次询问时，矩阵快速幂内部都要算一遍邻接矩阵的自乘 $O(n^3)$ ，因此可以预处理邻接矩阵的自乘。但是在初始矩阵的累乘 $O(n^3)$ 中还是很慢，由于我们每次询问只问一个点，因此初始矩阵可以设为 $1\times n$ 的矩阵，表示初始点 $x$ 能到的点，单次矩阵乘法时间复杂度降为 $O(n^2)$ 。

预处理时间复杂度为 $O(n^3logn)$ ，矩阵快速幂时间复杂度为 $O(Tn^2logn)$ ，总时间复杂度为 $O((T+n)n^2logn)$ 。

（本题没打算塞 $bitset$ 优化，因此 $bitset$ 优化爆搜找循环也能过本题。）

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MX 2000000000
#define MXN 102
#define LG 31
using namespace std;
ll n,m,T;
bool a[MXN],f[LG][MXN][MXN];
void mul1(bool x[MXN][MXN],bool y[MXN][MXN],bool z[MXN][MXN]){//将y*z赋值到n*n矩阵x
    ll ans[MXN][MXN]={};
    for(ll k=1;k<=n;++k)
        for(ll i=1;i<=n;++i)
            for(ll j=1;j<=n;++j)
                ans[i][j]|=y[i][k]&z[k][j];
    for(ll i=1;i<=n;++i)
        for(ll j=1;j<=n;++j)
            x[i][j]=ans[i][j];
}
void mul2(bool x[MXN],bool y[MXN],bool z[MXN][MXN]){//将y*z赋值到1*n矩阵x
    ll ans[MXN]={};
    for(ll k=1;k<=n;++k)
        for(ll j=1;j<=n;++j)
            ans[j]|=y[k]&z[k][j];
    for(ll j=1;j<=n;++j)
        x[j]=ans[j];
}
int main(){
    cin>>n>>m>>T;
    for(ll i=1,u,v;i<=m;++i)
        cin>>u>>v,f[0][u][v]=1;
    for(ll l=1;l<LG;++l)
        mul1(f[l],f[l-1],f[l-1]);//预处理行走2的幂次距离的矩阵
    while(T--){
        ll x,k,j=0,num=0;
        cin>>x>>k;
        for(ll i=1;i<=n;++i)
            a[i]=0;
        a[x]=1;//初始化为行走0步能到的点
        while(k){
            if(k&1) mul2(a,a,f[j]);
            k>>=1;
            ++j;
        }
        for(ll i=1;i<=n;++i)
            num+=a[i];
        cout<<num<<' ';
        for(ll i=1;i<=n;++i)
            if(a[i]) cout<<i<<' ';
        cout<<'\n';
    }
}

I-你的头怎么尖尖的

题目大意

给定一个长度为 $n$ 的数组 $\left \{ h_1,h_2,\dots,h_n \right \}$ 。每次操作可以给 $h_i$ 增减 $1$ 。问最少要多少次操作，才能让所有的 $i(1<i<n)$ ，均不满足 $h_{i-1}<h_i>h_{i+1}$ 。

解题思路

我们约定 $h_{i-1}<h_i>h_{i+1}$ 的位置 $i$ 为峰， $i-1,i+1$ 为山脚，发现山脚不能为峰，因此峰与峰之间不相邻。

贪心部分：

看到这种题，思考能不能贪心。

如果 $h_i$ 值需要增加，那么 $i-1$ 或 $i+1$ 为峰；如果 $h_i$ 值需要减少，那么 $i$ 为峰。贪心使得消去后的峰大小关系为 $h_{i-1}=h_i\ge h_{i+1}$ 或者 $h_{i-1}\le h_i=h_{i+1}$ ，并且也不会产生新的峰。

我们先尝试贪心将所有的峰值减小，减至两山脚的最大值。

如果这时我们将一个被减过的峰值回退一个减少 $1$ 的操作，将最大的山脚增加 $1$ ，此时总操作次数不变，但是山脚增加了 $1$ 。不难发现，一个峰只有山脚会影响其他的峰，而这个山脚增加，只会利于其他峰的消去，毕竟其他峰的山脚增加，那么消去这个峰所需操作次数可能减少。

因此只增山脚不减峰的修改方式优于其他的方案。

dp 部分:

这时发现可能能 $dp$ ，因为只有山脚增加，并且增加只会到峰值，也就是说每个位置只有 $3$ 个可能的最终值：

$i$ 山脚变化为 $i-1$ 峰值的大小；
$i$ 山脚不变；
$i$ 山脚变化为 $i+1$ 峰值的大小。

考虑线性 $dp$ 求从下标 $1$ 开始所需的最小操作次数。

给 $dp_i$ 设定 $2$ 个状态（ $i$ 山脚增加至 $i+1$ 峰值的状态，被优化进 $i$ 峰值不变的状态中了），存的值均为从下标 $1$ 开始所需的最小操作次数：

$dp_{i,0}$ 表示第 $i$ 个位置 $h_i$ 暂时不发生变化，即不变为 $h_{i-1}$ （可能在后面的状态转移中变为 $h_{i+1}$ ）。
$dp_{i,1}$ 表示第 $i$ 个位置 $h_i$ 增加至峰值 $h_{i-1}$ ，如果 $i-1$ 不是峰，那么给 $dp_{i,1}=10^{18}$ ，表示 $h_i$ 不需要增加。

对于 $i+1$ 位置求状态转移：

如果 $i$ 为峰，那么有两种方式消去:
- $h_{i+1}$ 不变，将 $h_{i-1}$ 增加到 $h_i$ ，考虑 $h_{i-1}$ 是否增加过（增加的状态中 $h_{i-1}$ 为 $h_{i-2}$ ），两个状态取最小的操作方法，
  对应转移方程： $dp_{i+1,0}=min\{dp_{i-1,0}+h_i-h_{i-1},dp_{i-1,1}+max\{0,h_i-h_{i-2}\}\}$ ；
- 或者将 $h_{i+1}$ 增加到 $h_i$ ，
  对应转移方程： $dp_{i+1,1}=dp_{i,0}+h_i-h_{i+1}$ 。
如果 $i$ 不为峰，那么 $h_{i+1}$ 值必然不会发生变化，
对应转移方程： $dp_{i+1,0}=min\{dp_{i,0},dp_{i,1}\},dp_{i+1,1}=10^{18}$ 。

最终状态转移方程：

dp_{i+1,0}=\begin{cases} min\{dp_{i-1,0}+h_i-h_{i-1},dp_{i-1,1}+max\{0,h_i-h_{i-2}\}\} ,& i为峰 \\ min\{dp_{i,0},dp_{i,1}\} ,& i不为峰 \end{cases}

dp_{i+1,1}=\begin{cases} dp_{i,0}+h_i-h_{i+1} ,& i为峰 \\ 10^{18} ,& i不为峰 \end{cases}

时间复杂度为 $O(n)$ 。

（其他做法合理均可。）

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MX 1000000000000000000ll
using namespace std;
ll n,h[200002],f[200002][2];
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++)
        cin>>h[i];
    f[1][1]=f[2][1]=MX;//0和1位置不可能为峰，因此1和2位置1状态赋值为MX。
    for(ll i=2;i<n;i++){
        if(h[i-1]<h[i]&&h[i]>h[i+1]){
            f[i+1][0]=min(f[i-1][0]+h[i]-h[i-1],f[i-1][1]+max(0ll,h[i]-h[i-2]));
            f[i+1][1]=f[i][0]+h[i]-h[i+1];
        }else f[i+1][0]=min(f[i][0],f[i][1]),f[i+1][1]=MX;
    }
    cout<<min(f[n][0],f[n][1]);
}

E-密码生成

题目大意

输入 $a,b,c$ ，计算题目中算式的结果。

解题思路

显然直接计算是不行的，通过打表找规律可以发现答案是 $a * b \% c$ 。

下面来证明这个结果：

由于 $[gcd(i,j)=1]$ 代表了既约关系，考虑构造一个二维平面来理解，下面举一个特殊情形 $a = 6, b = 5$ 。

首先我们将所有 $[gcd(i,j)=1]$ 的点标出，并写上他们乘的值 $\min\left(\left\lfloor\frac{a}{i}\right\rfloor,\left\lfloor\frac{b}{j}\right\rfloor\right)$ 。

alt

对于值不为1的点，我们把他与原点连线。

alt

将直线经过的整点标注出来，这时我们可以发现，网格已经恰好被填满了，并且直线上面的整点数，与首个经过的整点上的值一致。

在这个提示下，接下来我们倒着思考问题，先考虑对于网格中的经过 $(0,0)$ , $(x,y)$ 的直线，这一直线经过的第一个整点是什么？应该是 $(\frac{x}{gcd(x,y)},\frac{y}{gcd(x,y)})$ 。不妨设这个点是 $(i,j)$ ，再考虑这个直线经过了多少个整点，对于 $a * b$ 的网格，其经过的整点个数应该是 $\min\left(\left\lfloor\frac{a}{i}\right\rfloor,\left\lfloor\frac{b}{j}\right\rfloor\right)$ 。

从这两个结论我们可以发现，网格 $a * b$ 恰好可以表示成算式： $\left( \sum_{i=1}^a \sum_{j=1}^b \left[ \gcd(i,j)=1 \right] \cdot \min \left( \left\lfloor \frac{a}{i} \right\rfloor, \left\lfloor \frac{b}{j} \right\rfloor \right) \right)$ 。可以理解成非互质的点被存入互质点的值了，从而填满了网格。

于是，题目结论得证。

参考代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c;
int main(){
    cin>>a>>b>>c;
    cout<<a*b%c;
    return 0;
}

K-鲁珀特帝国机械齿轮

题目大意

有 $n$ 个房间，玩家进入房间 $i$ 时，会变化 $a_i$ 个宇宙碎片，不会低于 $0$ ；玩家离开房间 $i$ 时，宇宙碎片超过 $b_i$ 的部分会失去。

有 $m$ 次操作。

操作一可以修改一个房间的 $a_i$ 。

操作二可以修改一个房间的 $b_i$ 。

操作三需要回答初始有一些宇宙碎片，然后从某个房间进入，到某个房间出来，最终剩下多少宇宙碎片。

解题思路

使用线段树维护区间信息。

将一个房间看作一个函数：（ $w_i$ 为进入第 $i$ 个房间前的宇宙碎片数量）

w_{i+1}=\begin{cases} 0 ,& w_i+a_i<0 \\ w_i+a_i ,& 0\le w_i+a_i\le b_i \\ b_i ,& w_i+a_i>b_i \end{cases}

而对于范围 $0\le w_i+a_i\le b_i$ ， $w_{i+1}=w_i+a_i$ ，在范围外的都会限制在边界处。

如果自变量 $w_i$ 取值范围（定义域）为： $[l_i,r_i]$ 。

那么因变量 $w_{i+1}$ 取值范围（值域）能通过一系列分类讨论求得，并将 $w_i$ 取值范围在 $0\le w_i+a_i\le b_i$ 之外的取值都舍去。

接着用 $w_{i+1}$ 取值范围，能够求出 $w_{i+2}$ 取值范围。

因此能从 $w_i$ 的取值范围求得 $w_{i+2}$ 的取值范围，以此类推。

形象化的，我们把取值范围的变化画成下面的平行四边形。

alt

这样的平行四边形合并满足结合律，我们可以对平行四边形的合并进行分治，即线段树维护。

我们维护区间 $[l,r]$ 这种平行四边形的信息， $l$ 的下端点， $r$ 的下端点，与平行四边形的长。

能够从 $w_l$ 轻易计算出 $w_{r+1}$ 的值，如图所示：

alt

参考代码

#include<bits/stdc++.h>
#define ll long long
#define MX 2000000000
#define MXN 100002
using namespace std;
struct edge{//平行四边形
    ll x,y,len;//x为l边界的下端点，y为r边界的下端点，len为平行四边形的长。
};
struct bzm{
    ll pl,pr;//左右子树
    edge ans;//区间的平行四边形
}tr[MXN*2];//线段树
ll rt,trt;//线段树根与节点数
ll n,m,a[MXN],b[MXN];
inline ll mge(ll x,edge b){//将x值代入平行四边形b求得的值
    if(x<b.x) return b.y;
    if(x>b.x+b.len) return b.y+b.len;
    return b.y+x-b.x;
}
inline edge mge(edge a,edge b){//合并两个平行四边形a,b，返回合并的平行四边形
    ll midl=max(a.y,b.x),midr=min(a.y+a.len,b.x+b.len);
    if(midr<midl)
        if(a.y<b.x) midr=midl;
        else midl=midr;
    edge ans={midl+a.x-a.y,midl-b.x+b.y,midr-midl};
    return ans;
}
inline void ptup(ll p){//合并左右区间的平行四边形
    tr[p].ans=mge(tr[tr[p].pl].ans,tr[tr[p].pr].ans);
}
inline void doit(ll p,ll a,ll b){//将房间的信息转化为平行四边形
    if(a<0) tr[p].ans={-a,0,b};
    else tr[p].ans={0,min(b,a),max(0ll,b-a)};
}
void bd(ll &p,ll l,ll r){//建树
    p=++trt;
    if(l==r){
        doit(p,a[l],b[l]);
        return;
    }
    ll mid=l+r>>1;
    bd(tr[p].pl,l,mid);
    bd(tr[p].pr,mid+1,r);
    ptup(p);
}
void chg(ll p,ll l,ll r,ll x,ll ka,ll kb){//单房间修改
    if(l==r){
        a[l]=ka,b[l]=kb;
        doit(p,ka,kb);
        return;
    }
    ll mid=l+r>>1;
    if(x<=mid) chg(tr[p].pl,l,mid,x,ka,kb);
    else chg(tr[p].pr,mid+1,r,x,ka,kb);
    ptup(p);
}
edge ask(ll p,ll l,ll r,ll x,ll y){//查询区间的平行四边形
    if(x<=l&&r<=y) return tr[p].ans;
    ll mid=l+r>>1;
    edge ans={0,0,MX};
    if(x<=mid) ans=mge(ans,ask(tr[p].pl,l,mid,x,y));
    if(y>mid) ans=mge(ans,ask(tr[p].pr,mid+1,r,x,y));
    return ans;
}
int main(){
    cin>>n>>m;
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    for(ll i=1;i<=n;i++)
        cin>>b[i];
    bd(rt,1,n);
    while(m--){
        ll op,i,x,y,w;
        edge ans;
        cin>>op;
        if(op==1){//修改房间的a值
            cin>>i>>x;
            chg(rt,1,n,i,x,b[i]);
        }else if(op==2){//修改房间的b值
            cin>>i>>y;
            chg(rt,1,n,i,a[i],y);
        }else{//利用平行四边形求得最终结果
            cin>>x>>y>>w;
            cout<<mge(w,ask(rt,1,n,x,y))<<'\n';
        }
    }
}

出题人题解

A-别叫我那刻夏

题目大意

解题思路

参考代码

J-选最好的算法

题目大意

解题思路

参考代码

M-手机里有一款四字游戏

题目大意

解题思路

参考代码

C-仿生人不会梦到彩色电子羊

题目大意

解题思路

参考代码

G-无路可逃

题目大意

解题思路

参考代码

L-人有五名，代价有三个

题目大意

解题思路

参考代码

D-神秘小游戏

题目大意

解题思路

参考代码

F-崩环：星球轨道

题目大意

解题思路

参考代码

H-阿基维利的列车

题目大意

解题思路

一、思路引导：

二、构造方法：

参考代码

B-阳光跑

题目大意

解题思路

参考代码

I-你的头怎么尖尖的

题目大意

解题思路

贪心部分：

dp 部分:

参考代码

E-密码生成

题目大意

解题思路

参考代码

K-鲁珀特帝国机械齿轮

题目大意

解题思路

参考代码