A n-th

题意

已知公式$\pi ={\sum }_{k=0}^{\infty }\frac{1}{16^k}(\frac{4}{8k+1}-\frac{2}{8k+4}-\frac{1}{8k+5}-\frac{1}{8k+6})$

请你求出$\pi$的十六进制的小数点后的第$n$位。

思路

如何将一个十进制小数转换为十六进制小数？

以3.1415926为例 , 转换为小数为3.243f69a25b094

我们需要做的是取小数部分0.1415926，乘以16后，此时会得到一个数$num$（$0\le num<16$ ）， 0.1415926 * 16 = 2.2654816 , 那么2就是$3.1415926$ 的十六进制小数部分的第一位

之后我们再取小数部分乘以16，0.2654816* 16 = 4.2477056 , 于是就求出了十六进制的小数点后第二位为4

以此类推，我们就可以将一个十进制小数转换为十六进制小数。

---

因此我们要计算十六进制下$\pi$ 的第n位，也就是计算$16^n\pi$ 的整数部分。

$16^d\pi =4\ast (16^d\ast {\sum }_{k=0}^{\infty }\frac{1}{8k+1})-2\ast (16^d\ast {\sum }_{k=0}^{\infty }\frac{1}{8k+4})-(16^d\ast {\sum }_{k=0}^{\infty }\frac{1}{8k+5})-(16^d\ast {\sum }_{k=0}^{\infty }\frac{1}{8k+6})$

其中$$\begin{gathered} 16^d{\sum }_{k=0}^{\infty }\frac{1}{16^k(8k+1)} \\ ={\sum }_{k=0}^d\frac{16^{d-k}}{8k+1}+{\sum }_{k=d+1}^{\infty }\frac{16^{d-k}}{8k+1} \\ ={\sum }_{k=0}^d\frac{16^{d-k}}{8k+1}+{\sum }_{k=d+1}^{\infty }\frac{16^{d-k}}{8k+1} \end{gathered}$$

因为我们只要最终的小数位

对于第二项${\sum }_{k=d+1}^{\infty }\frac{16^{d-k}}{8k+1}$,因为$d<k$ ,所以这一项一定是小于1的

对于第一项，他的小数部分为每项的小数相加，即${\sum }_{k=0}^d\frac{16^{d-k}mod(8k+1)}{8k+1}$

因此对于第一部分$(16^d\ast {\sum }_{k=0}^{\infty }\frac{1}{8k+1})$，我们就得到了${\sum }_{k=0}^d\frac{16^{d-k}mod(8k+1)}{8k+1}+{\sum }_{k=d+1}^{\infty }\frac{16^{d-k}}{8k+1}$ 。

（其余三部分按照同样方法处理即可。）

将每部分都计算之后，就会得到一个小于1的数，对这个数再乘上16，那么整数部分就是我们要求的pi的第n位了。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int QuickPow(int x,int n,int mod = INF){
    int ans = 1;
    while (n != 0){
        if ((n & 1) != 0) ans = ans * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ans;
}
double Calculate16dSj(int d, int j){
    double part1 = 0;
    double part2 = 0;

    // 精度按 d ~ d + 10 
    int accuracy = d + 10;

    for (int k = 0; k <= d; k++)
    {
        part1 += QuickPow(16, d - k, 8 * k + j) * 1.0 / (8 * k + j);
    }

    for (int k = d + 1; k < accuracy; k++)
    {
        part2 += QuickPow(16, d - k) / (8 * k + j);
    }

    return part1 + part2;
}
double Calculate16dPI(int d)
{
    double rlt = 4 * Calculate16dSj(d, 1) - 2 * Calculate16dSj(d, 4) - Calculate16dSj(d, 5) - Calculate16dSj(d, 6);
    // 只需要小数部分,所以减去整数部分
    rlt -= (int)rlt;
    // 因为在计算 16^d * Sj 的第一部分时用到了取模, 所以可能计算结果是负数, 需要加 1
    if (rlt < 0) rlt += 1;
    return rlt;
}
signed main(){
    int n;
    cin>>n;
    int ans = (int)(Calculate16dPI(n-1) * 16);
    char c;
    if(ans <= 9) c = '0' + ans;
    else c = 'A' + ans - 10;
    cout<<c<<endl;
    return 0;
}

B a的b次方

题意

给你一个算式，让你在算式左边插入一个幂次符号来分割，并使得等式成立。

如123=1728 , 即$12^3=1728$

约定等式右边的数不大于$10^9$

思路

本题考查题意模拟。

我们设等号左边的部分为A，右边的部分为B,算式表示为$x^n=b$。

由于算式太长，我们无法将A和B直接转换为数字，而应该先处理特殊情况：

**情况一：**如果这个算式以0=1结尾，此时$n=0$, 那么一定有$x^0=1$ ， 我们输出$YES$即可。

情况二：如果A以1结尾，此时$n=1$ , 并且A的除最后一个字符外构成的子串与B相等，那么就会出现$x^1=x$ 的情况。此时也应该输出$YES$

**情况三：**如果A[0] == '1' 并且A[1] != '0' 并且B == "1"，那么就有$1^n=1$ 的情况，输出$YES$。

**情况四：**如果不满足上述三种情况，那么若想使得$x^n=b$ ,就有 $x,n\ge 2$ , 而我们知道$x\le \sqrt{b}\le \sqrt{10^9}$ 因此x的位数不会超过5位。于是我们可以直接判断当A字符串的长度大于$6$ 时, 不存在一种构造方法，输出$NO$

在上述四种情况都判断以后，我们就可以进行字符串转数值的操作了，在转换完之后，我们枚举A的分界点，就可以找出所有情况。

代码

    #include<bits/stdc++.h>
    using namespace std;
    #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define int long long
    #define rep(i,l,r) for(int i = l;i<=r;i++)
    #define per(i,r,l) for(int i = r;i>=l;i--)
    const int INF = 0x3f3f3f3f3f3f3f3f;
    typedef pair<int,int> PII;
    void solve(){
        string s;
        cin>>s;
        if(s.substr(s.size()-3) == "0=1") {
            cout<<"YES"<<endl;return ;
        }
        int p = 0;
        while(p<s.size() && s[p] !='=') p ++;
        string A = s.substr(0,p);
        string B = s.substr(p+1);
        if(A.back() == '1' && A.substr(0,A.size()-1) == B){
            cout<<"YES"<<endl;return ;
        } 
        if(A[0] == '1' && A[1]!='0' && B == "1"){
            cout<<"YES"<<endl;return ;
        }
        if(A.size() >= 12) {
            cout<<"NO"<<endl;return ;
        } 
        int b = stoll(B);
        for(int i = 1;i<A.size();i++){
            if(A[i] == '0') continue;
            int x = stoll(A.substr(0,i));
            int n = stoll(A.substr(i));
            if(pow(x,n) == b) {
                cout<<"YES"<<endl;return ;
            }
        }
        cout<<"NO"<<endl;
        return ;
    }
    signed main(){
        int T = 1;
        // cin>>T;
        while(T--){
            solve();
        }
        return 0;
    }

C a^b

题意

给你一个数n($n>2)$ , 你需要找到一个长度大于1的区间$[L,R]$ 使得$XO{R}_{i=L}^{R}i=n$

思路

异或和公式：

对于任意的正整数$x$, 有KaTeX parse error: Unknown column alignment: * at position 52: … \begin{array}{*̲*lr**} …

很容易证明该式子是成立的。

我们列举从1开始开始的一些异或和：

x	1	2	3	4	5	6	7	8
$XO{R}_{i=1}^x$	1	3	0	4	1	7	0	8

可以发现

若$nmod4=3$ ,那么我们令L = 1,R = n-1

若$nmod4=0$ 那么令L = 1,R = n 即可。

然而对于另外两种情况，我们无法直接由前缀异或得出。

我们发现每次出现两个数，又有两个数无法构造出来。于是我们想到，如果不异或1 ，那么就会让最终的答案加1或者减1, 利用这个特性就可以构造出剩下的$n$

x	1	2	3	4	5	6	7	8
$XO{R}_{i=2}^x$		2	1	5	0	6	1	9

若$nmod4=1$ ,那么令L=2,R = n-1

若$nmod4=2$ ,那么令L=2,R = n

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int n;cin>>n;
    if(n % 4 == 3) {cout<<"1 "<<n-1<<endl;}
    if(n % 4 == 0) {cout<<"1 "<<n<<endl;}
    if(n % 4 == 1) {cout<<"2 "<<n-1<<endl;}
    if(n % 4 == 2) {cout<<"2 "<<n<<endl;}
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D b个a相乘

题意

给出$n(1\le n\le 10^5)$个数组成的元组A， 令这个$A$进行$b(1\le b\le 10^{18})$次幂乘法，规定本题中，元组的乘法运算$mul(A,B)$ 为A和B中两两相乘，得到的新的元组。

最终得到$n^b$ 个数，对这$n^b$ 个数进行取余100操作后，统计答案中0~99各自出现的次数, 最终的次数对$998244353$取模。

---

乘法运算示例：

$ (1,4,16)^2 \ =(1,4,16)(1,4,16) \ = (11,14,116,41,44,416,161,164,1616) \ =(1,4,16,4,16,64,16,64,256)$

思路

本题考查记忆化搜索与快速幂的结合应用。

首先我们知道取余运算有如下公式：$(A\ast B)\%P=((A\%P)\ast (B\%P))\%P$ , 在本题中$P=100$ , 因为在计算过程中，我们只需要知道这个数在取余100后的值即可。

于是我们就可以如下设计dp数组：$dp[i][j]$表示$A^i$ 时，$j(0\le j\le 99)$出现的次数。

而$mul(A^x,A^y)=A^{x+y}$ (这里的$mul$为本题定义的乘法运算) 。我们已知$A^x$ 中存在$dp[x][i]$ 个值为$i$ 的项，$A^y$ 中存在$dp[y][j]$ 个值为$i$ 的项，那么二者会为$A^{x+y}$中提供$dp[x][i]\ast dp[y][j]$ 个值为$(i+j)\%100$ 的项。

在递推式中体现为$dp[x+y][(i+j)\%100]=(dp[x+y][(i+j)\%100]+dp[x][i]\ast dp[x][j])\%998244353$

但是由于b的取值为$1\le b\le 10^{18}$ ，我们无法一项一项地推出$A^b$的值，联想到快速幂的过程，我们可以得到如下递推式：

KaTeX parse error: Unknown column alignment: * at position 44: … \begin{array}{*̲*lr**} …

根据递推式，我们可以用记忆化搜索来处理这个过程。

由于dp的第一维范围过大（与b的范围相同，为$1\le b\le 10^{18}$), 因此我们不能以数组的方式存储$dp[i][j]$ ，第一项的大小是不允许的。

于是我们可以将dp数组的第一维离散化处理（或使用map来记录）。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
const int mod = 998244353;
vector<PII> mul[100];
int n,b;
map<int,array<int,100> > dp;
void dfs(int now){
    if(dp.find(now) != dp.end()) return ;
    array<int,100> dp1,dp2;
    if(now & 1){
        dp1 = dp[1];
        if(dp.find(now-1) == dp.end()) dfs(now-1);
        dp2 = dp[now-1];
    }else{
        if(dp.find(now/2) == dp.end()) dfs(now/2);
        dp1 = dp[now/2];
        dp2 = dp[now/2];
    }
    array<int,100> dpnow;
    for(int i = 0;i<=99;i++) dpnow[i] = 0;
    for(int i = 0;i<=99;i++){
        for(auto [l,r] : mul[i]){
            dpnow[i] = (dpnow[i] + dp1[l]*dp2[r]%mod)%mod;
        }
    }
    dp[now] = dpnow;
    return ;
}
void solve(){
    for(int i = 0;i<=99;i++){
        for(int j = 0;j<=99;j++){
            mul[i*j%100].push_back({i,j});
        }
    }
    cin>>n>>b;
    array<int,100> tmp;
    for(int i = 0;i<=99;i++) tmp[i] = 0;
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        tmp[x%100] ++;
    }
    dp[1] = tmp;
    dfs(b);
    array<int,100> ans = dp[b];
    for(int i = 0;i<=99;i++){
        cout<<ans[i]<<' ';
    }
}
int qpow(int x,int n){
    int ans = 1;
    while(n){
        if(n&1){
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n>>=1;
    }
    return ans;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E 小猪吃蛋糕

题意

一共有n天，你每天可以赚$a_i$ 个金币

有两种商品：

• 商品一售价$x$ ，价值$u$
• 商品二售价$y$ ,价值$v$

问如何购物才能有最大的价值。

（保证$lcm(x,y)|{\sum }_{i=1}^n{a}_i$）

注：小猪可以选择将没花完的钱留在之后使用。

思路

—本题不是背包问题！—

因为小猪可以把钱留在之后花，所以完全可以留在最后一天再购物。

并且因为题目保证了$lcm(x,y)|{\sum }_{i=1}^n{a}_i$ ，因此最终无论买哪个商品都是不会有钱没花掉。

于是我们选择性价比最高的商品来买就好了：

设小猪总共的钱为$sum={\sum }_{i=1}^n{a}_i$,最终答案即为$max(\frac{sum}{x}\ast u,\frac{sum}{y}\ast v)$

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
    int x,y,u,v;
    cin>>x>>u>>y>>v;
    int n;
    cin>>n;
    int sum = 0 ;
    for(int i =1;i<=n;i++){
        int x;cin>>x;sum += x;
    }
    cout<<max(sum/x*u,sum/y*v);
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F 猫猫虫配对

题意

给$2N(1\le N\le 8)$ 个数，以及一个你需要两两配对， 若$i,j$ 进行配对， 会产生$A_{i,j}$ 的价值

问这N个价值的异或和，最大是多少。

思路

本题考查dfs搜索。

可以求得总的方案数量为$\frac{C_{2N}^2\ast C_{2N-2}^2\ast ...\ast C_2^2}{N!}=\frac{(2N)!}{N!2^N}$ ， 当N最大时，方案数为 $\frac{16!}{8!2^8}=2,027,025$ 。在程序的容忍度之内。

因此我们使用dfs枚举所有的方案，找其中的最大值即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
#define N 21
int vis[N];
vector<int>v;
int ar[21][21];
int n;
int res=0;
int ans=0;
void dfs(int x,int sum){
	if(x==n){
		res++;
		ans=max(ans,sum);
		return;
	}
	if(vis[x]){
		dfs(x+1,sum);
		return;
	}
	for(int i=x+1;i<=n;++i){
		if(!vis[i]){
			vis[i]=1;
			dfs(x+1,sum^ar[x][i]);
			vis[i]=0;
		}
	}
	
}
void solve() {
	cin>>n;
	n*=2;
	for(int i=1;i<n;++i){
		for(int j=i+1;j<=n;++j){
			cin>>ar[i][j];
			ar[j][i]=ar[i][j];
		}
	}
	dfs(1,0);
	cout<<ans<<endl;
}
signed main(){
    IO;
	int T = 1;
    // cin>>T;
	while(T--){
		solve();
	}
	return 0;
    return 0;
}

G 排队(easy)

题意

有$m$个柜台可以并行处理任务，有$n$个任务要按顺序进行，每个任务所需要的时间为$a_1,a_2,...,a_n$ 。你是第n+1个任务，问什么时候能轮到你的任务，并且你需要去哪个柜台。

（如果有多个柜台同时空闲，此时你需要去标号最小的那个柜台）

easy版本中$1\le m\le 10$

思路

因为柜台数量很少，所以我们可以设置一个长度为$m$的数组$server$ , 其中$ser[i]$表示第$i$个柜台会在什么时候重新开放。

于是初始时，$server$数组全为0。

当第$i$个任务到来时，我们按顺序枚举所有的柜台，找到值最小的柜台，代表他是最先开放的。然后我们让他的值加上$a[i]$ ，表示这个柜台在处理完当前任务后，时间会过去$a[i]$

我们处理所有的1-n 个任务，这样就可以知道轮到我们时的柜台的状态了。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int server[15];
void solve(){
    int n,m;cin>>n>>m;
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        int minp = 1; // 时间最小的那个柜台的标号
        for(int i= 2;i<=m;i++){
            if(server[i] < server[minp]){ // 这里不能写成<=,因为有多个最小值时选择小标号
                minp = i;
            }
        }
        server[minp] += x;
    }
    int minp = 1;
    for(int i = 2;i<=m;i++){
        if(server[i] < server[minp]){
            minp = i;
        }
    }
    cout<<server[minp]<<" "<<minp<<endl; 
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

H 排队(hard)

题意

有$m$个柜台可以并行处理任务，有$n$个任务要按顺序进行，每个任务所需要的时间为$a_1,a_2,...,a_n$ 。你是第n+1个任务，问什么时候能轮到你的任务，并且你需要去哪个柜台。

（如果有多个柜台同时空闲，此时你需要去标号最小的那个柜台）

hard版本中$1\le m\le 10^5$

思路

我们观察简单版本的思路，会发现我们每次要找的就是$server$中最小的那个值，但是如果暴力枚举的话，时间复杂度是$O(nm)$是不被允许的，于是我们想到了堆(也就是优先队列，是一种能够在$logm$的复杂度下进行删除和插入元素的数据结构) 。

因为要依赖时间和柜台标号两个键进行排序，因此推荐创建一个类，并重载比较函数来规定排序规则。

对于$server[x]=server[x]+a[i]$ 操作，我们可以等价换做使原先的元素出队，然后入队一个值为 $server[x]+a[i]$，下标和出队元素下标相同的元素。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
struct node{
    int time,id;
    bool operator < (const node& a) const{ // 重载排序函数
        if(time != a.time) return time > a.time;
        return id > a.id;
    }
};
void solve(){
    priority_queue<node> pq;
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        pq.push({0,i});
    }
    for(int i = 1;i<=n;i++){
        int x;cin>>x;
        node t = pq.top();pq.pop();
        pq.push({t.time+x,t.id});
    }
    cout<<pq.top().time<<' '<<pq.top().id;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

I 近距猎兵型

题意

给定$n,m$ 。 表示为有n个圆心在原点的同心圆，半径为$1,2,3,...,n-1,n$ ，以及m个角度相等的过圆心的直线。

较易得知，直线将每个圆划分为$2m$个等长的弧线。形成了$2m$个交点。

问：交点之间两两最短路径的和是多少？（答案向下取整）

（只要两点相同即被认为是相同的点对，即若有交点A B , 那么点对(A,B)与(B,A)应当被认为是同一个点对）

最短路径表示为从一个交点出发，沿着圆或直线到达另一个交点，所走过的路径的最短距离。

（$1\le n,m\le 500$）

思路

我们先计算单位圆被切割为$2m$ 个交点后，这些交点产生的贡献。

假设要计算点$i$ 与点$j$ 的路径，那么有两种路径可以选择：

1. 绕着圆的半径到达，路径长度为点$i$和点$j$之间的弧度。
2. 先沿直线到达圆心，再沿着直线到达另一个点,路径长度为2。

于是我们得知当弧度小于等于2时，选择方案一更近，弧度大于2时选择方案二更近。

根据m的大小，便可以得出当$i$和$j$之间相差超过多少时，弧度会大于2。我们设这个值为$lim$

那么可以得到如下公式：$lim=\lfloor \frac{2\ast m}{\pi }\rfloor$ 。 其中$\lfloor x \rfloor $表示对$x$向下取整。

对于圆上的一个点，有$2\ast lim$ 个点与它的角度距离小于$2$ ，该点到这些点之间的距离的和为

$di{s}_1^{\prime }=2\ast (\frac{lim\ast (lim+1)}{2}\ast (\frac{2\pi }{2m})\ast 1)=\frac{lim\ast (lim+1)\ast \pi }{m}$

对于其余的$2\ast m-2\ast lim-1$ 个点，距离均为2 ,所以距离和为

$di{s}_1^{\prime \prime }=4\ast m-4\ast lim-2$

因此单位圆上的一个点到其他点的距离和即为$di{s}_1=di{s}_1^{\prime }+di{s}_1^{\prime \prime }=\frac{lim\ast (lim+1)\ast \pi }{m}+(4\ast m-4\ast lim-2)$

---

由此拓展到半径为$i$ 的圆上，该圆上的一个交点与同一个圆上的其他交点的距离的和为$di{s}_i=i\ast di{s}_1$ 。

于是可得半径为$i$的圆上两两点产生的距离的和为：$su{m}_i^{\prime }=m\ast di{s}_i$

---

假设有半径为$i$的圆上的交点$a$, 那么它到半径为$j$的圆上的所有的交点距离的和为$di{s}_j+2\ast m\ast |i-j|$ 。

于是对于所有$j<i$的点，他们与点$a$的距离的和为$con{t}_i={\sum }_{j=1}^{i-1}(di{s}_j+2\ast m\ast (i-j))={\sum }_{j=1}^{i-1}di{s}_j+2\ast m\ast i\ast (i-1)-2\ast m\ast {\sum }_{j=1}^{i-1}j$

化简可得$con{t}_i={\sum }_{j=1}^{i-1}di{s}_j+2\ast m\ast (i-1)\ast i-2\ast m\ast \frac{i\ast (i-1)}{2}={\sum }_{j=1}^{i-1}di{s}_j+m\ast (i^2-i)$

其中第一项${\sum }_{j=1}^{i-1}di{s}_j$可以由${\sum }_{j=1}^{i-2}di{s}_j+di{s}_{i-1}$递推得来。

那么对于所有的半径为$i$的圆上的点，到所有半径为$j(j<i)$ 的距离的和为

$su{m}_i^{\prime \prime }=2\ast m\ast con{t}_i$

---

由上式可得所有圆上的交点两两之间的距离和为$ans={\sum }_{i=1}^n(su{m}_i^{\prime }+su{m}_i^{\prime \prime })$

---

需要注意的是，如果$m>1$ ,那么多条直线会在原点形成一个额外的交点，需要额外计算它与其他点的距离的和：

$ans=ans+n\ast m\ast (n+1)$

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define uint unsigned long long
#define ld long double
#define pii pair<int,int>
#define complex complex<ld>
#define rand mt19937_64
#define endl '\n'
#define PI (ld)(3.141592653589793)
#define INF (int)(1e8+1)
#define MOD (int)(1e9+7)
#define eps (ld)(1e-9)
#define mpair(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define lowbit(x) (x&-x)
rand rnd(clock());

int n, m;

void solve() {
    cin >> n >> m;
    ld lim = floor(2.0 * m / PI);
    ld dis1 = lim*(lim+1)*PI/m + (4*m-4*lim-2);
    ld ans = 0;
    ld z = 0;
    ld dis = 0; // 从1到i的dis的和
    for (int i = 1;i <= n;++i) {
        ld cont = dis + m * (i*i-i);
        ld sum1 = m * dis1 * i;
        dis += i * dis1;
        ld sum2 = 2 * m * cont;
        ans += sum1+sum2;
    }
    if(m>1){
        ans += n * m * (n + 1);
    }
    cout<<((int)ans)<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // freopen("test.err", "w", stderr);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

J 闪蝶

题意

给你一个长度为$n$的数组$a$ , （$a_1,a_2,...,a_n$) 保证$1\le a_i\le m$

进行q次询问，每次询问给出区间$[l,r]$ 。

你需要求出数组a的区间$[l,r]$内每种数出现的次数$c_1,c_2,...,c_m$ ， 输出$c_1^2+c_2^2+...+c_m^2$

($1\le n,m,q\le 10^5$)

思路

本题考查莫队算法，如果你没了解过该算法，请移步https://oi-wiki.org/misc/mo-algo/

---

我们发现本题要求的值是满足莫队的性质的，即可以在$O(1)$的时间复杂度内将$[l,r]$的结果扩展到$[l-1,r],[l+1,r],[l,r-1],[l,r+1]$ ，具体为：

我们将区间向外扩展一个数字$a_i$，会让$c_{a_i}$ 的值加一，于是答案增加$(c_{a_i}+1{)}^2-c_{a_i}^2=2\ast c_{a_i}+1$ 。

对于将区间向内收缩一个数字$a_i$ ，同理可得答案会减少$2\ast c_{a_i}-1$

于是我们按照莫队算法的求解过程，我们将这q组询问进行排序后，不断扩展收缩，并得出答案即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define lowbit(x) (x&-x)
#define endl '\n'
#define INF 1e14
#define MOD 998244353
#define lc p<<1
#define rc p<<1|1

const int N = 2e5 + 5;
int n, m, k;
int a[N];
int seg;
int ans[N];

typedef struct {
    int l, r;
    int id;
}Query;
Query q[N];
bool cmp(Query a, Query b) {
    if (a.l / seg != b.l / seg) return a.l < b.l;
    return a.r < b.r;
}

int res, cnt[N];

void add(int v) {
    res += 2 * (cnt[v]++) + 1;
}

void del(int v) {
    res += -2 * (cnt[v]--) + 1;
}

void solve() {
    cin >> n >> k;
    seg = pow(n, 0.5);
    for (int i = 1;i <= n;++i)
        cin >> a[i];
    cin >> m;
    for (int i = 1;i <= m;++i) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    sort(q + 1, q + m + 1, cmp);

    for (int i = 1, l = 1, r = 0;i <= m;++i) {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        ans[q[i].id] = res;
    }

    for (int i = 1;i <= m;++i)
        cout << ans[i] << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

K 奶龙摇花手

题意

有n个城市，他们之间两两互通，城市之间的距离由矩阵$D$ 表示，即$D_{i,j}$表示从$i$到$j$的距离的权重。

你需要从城市1到达城市n，并且给定了整数$A,B,C$ 。

从城市$i$到城市$j$有两种方案：

方案一：花费$D_{i,j}\ast A$的时间从城市$i$到达城市$j$。

方案二：花费$D_{i,j}\ast B+C$的时间从城市$i$到达城市$j$。

但有如下限制：一旦你开始使用方案二，那么在此之后都只能使用方案二来移动，无法切换到方案一。（相反，可以随时从方案一切换到方案二）

问最少需要多少时间能从城市$1$到达城市$n$？

思路

注意本题使用floyd算法会导致超时！

本题中的两种方案可以当作图中的两个边来看待，我们可以用dijstra来找到图的起点到终点的最短路。

由于有限制当使用过方案二后，之后只能使用方案二。因此我们在记录节点状态时，除了要记录已经花费的时间$tim$ 和当前的节点编号$id$ ,还要记录当前是否使用过方案二$op$ 。

起点的状态为(0,1,0) , 然后执行dijstra（优先队列BFS），在节点转移时根据op的状态来决定能否使用方案一来转移，以及转移后的状态，当我们第一次到达终点时，此时的时间就是所花费的最少的时间。

---

注意我们用vis数组来记录某个节点是否到达过时，同样需要二维，分别表示$id$和$op$的值。

L 抽象数组

题意

有两个长度为$n$的数组$a_1,a_2,...,a_n$ 和$b_1,b_2,...,b_n$ 。我们称他们的抽象程度为${\sum }_{i=1}^n(|a_i-b_i|)$ , 其中$|x|$ 表示$x$的绝对值。

你可以进行最多一次如下操作，来使得抽象程度尽可能地大：

1. 选择两个索引$i,j(1\le i<j\le n)$
2. 交换$b_i$ 与$b_j$的值。

请问最终的抽象程度最大为多少。

思路

我们可以把$(a_i,b_i)$ 视为数轴上的一段线段。这个线段的两端为$a_i,b_i$ 。

那么本题中的抽象值，即为所有线段的长度的和。

如果我们想要通过交换$b_i,b_j$ 来使得这个值变大，那么就需要保证 两个线段在交换前没有交集。

可以发现交换能够使得贡献增加$2\ast (|a_j-b_i|)$ 。通过画图可以发现，对于其他不相交线段的情况，交换后同样会使得贡献增加中间区间的长度的两倍。

于是我们便不需要关心$a_i,b_i$ 的大小关系， 只需要关心区间的左右端点即可，令$l[i]=min(a_i,b_i),r[i]=max(a_i,b_i)$ 。

如果我们交换区间$[l_i,r_i]$和$[l_j,r_j]$ 那么就会增加$2\ast (l_j-r_i)$ 的贡献， 于是我们找到最大的$l_i$ 以及最小的$r_j$ ，便可以得出答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+5);
	vector<int> b(n+5);
	rep(i,1,n) cin>>a[i];
	rep(i,1,n) cin>>b[i];
	int ans = 0;
	rep(i,1,n){
		ans = ans + abs(a[i]-b[i]);
	}
	int mxl = 0;
	for(int i = 1;i<=n;i++){
		int l = min(a[i],b[i]);
		mxl = max(mxl,l);
	}
	int mnr = INF;
	for(int i = 1;i<=n;i++){
		int r = max(a[i],b[i]);
		mnr = min(mnr,r);
	}
	if(mxl > mnr) ans += 2 * (mxl - mnr);
	cout<<ans<<endl;
}
signed main(){
	int T = 1;
	// cin>>T;
	while(T--){
		solve();
	}
	return 0;
}