2020牛客暑期多校训练营（第二场）

A. All with Pairs $\looparrowright$

题目描述

Given $n$ strings $s_1, s_2, \cdots, s_n$ . Now define $f(s,t)$ as the maximum $i$ that satisfy $s_{1\cdots i} = t_{|t|-i+1 \cdots |t|}$ , and if such $i$ doesn’t exist, $f(s, t) = 0$ .
The Problem is to calculate:
\sum_{i=1}^{n}\sum_{j=1}^{n}f(s_i, s_j)^2 \pmod{998244353}∑
i=1
n

∑
j=1
n

f(s
i

,s
j

)
2
(mod998244353)
输入描述:
The first line contains one integer n~(1 \leq n \leq 10^5)n (1≤n≤10
5
), denoting the number of given strings.
The following {n}n lines each contains a string s_i~(i = 1, 2, \cdots, n)s
i

(i=1,2,⋯,n).
It’s guaranteed that 1\leq |s_i|, \sum|s_i| \leq 10^61≤∣s
i

∣,∑∣s
i

∣≤10
6
and all strings only contain lowercase letters.
输出描述:
Only one line containing one integer, denoting the answer.
示例1
输入
复制
3
ab
ba
aba
输出
复制
29
说明

So the answer is 4\times 1^2 + 4\times 2^2 + 1\times 3^2 = 294×1
2
+4×2
2
+1×3
2
=29.

分析

计算 $n$ 个字符串的所有后缀的哈希值，用 \text{unordered_map} 存不同后缀的个数， $cnt_x$ 表示哈希值为 $x$ 的后缀的个数。
然后对每个字符串的前缀求哈希值，若某个前缀的哈希值为 $x$ ，那么就有 $cnt_x$ 个后缀与之匹配，而实际上这样的计数方法会产生重复。就拿单个字符串 $\mathrm{aba}$ 来说，会有两个后缀 $\mathrm a$ 和 $\mathrm{aba}$ 在位置 $0$ 和 $2$ 处匹配，而我们要的最长匹配显然是 $aba$ 。也就是说，某个位置 $i$ 的匹配数多了与 $i$ 为结尾的前缀与的后缀的最长匹配长度，这就是 $\text{Next}$ 数组的定义，只需要将位置 $i$ 的匹配后缀数量减去 $\text{Next}$ 数组的值就是真正的贡献了。

代码

#include<iostream>
#include<unordered_map>
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
const ull base=131;
const int N=1000003;
const int mod=998244353;
int n;
string s[N];
int Next[N];
//统计不同后缀个数
unordered_map<ull,int>cnt;
int matched[N];
void get_next(string s)
{
	int i=0,j=-1;
	Next[0]=-1;
	while(i<s.length())
	{
		if(j==-1||s[j]==s[i]) Next[++i]=++j;
		else j=Next[j];
	}
}
void suffix_countment(string s)
{
	ull suffix_hash=0,power=1;
	int i;
	for(i=s.length()-1;i>=0;i--)
	{
		suffix_hash+=power*(s[i]-'a'+1);
		power*=base;
		cnt[suffix_hash]++;
	}
}
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++) 
	{
		cin>>s[i];
		suffix_countment(s[i]);//后缀哈希值
	}
	ull ans=0;
	for(i=1;i<=n;i++)
	{
		ull prefix_hash=0;
		for(j=0;j<s[i].length();j++)//前缀哈希值
		{
			prefix_hash=prefix_hash*base+(s[i][j]-'a'+1);
			matched[j]=cnt[prefix_hash];
		}
		get_next(s[i]);
		//减去重复的
		for(j=0;j<s[i].length();j++) matched[Next[j+1]-1]-=matched[j];
		//匹配数乘长度的平方
		for(j=0;j<s[i].length();j++) ans=(ans+1LL*matched[j]*(j+1)%mod*(j+1)%mod)%mod;
	}
	cout<<ans<<endl;
	return 0;
}

B. Boundary $\looparrowright$

题目描述

Given $n$ points in $2\mathrm D$ plane. Considering all circles that the origin point $(0, 0)$ is on their boundries, find the one with the maximum given points on its boundry. Print the maximum number of points.

输入描述

The first line contains one integer $n$ $(1 \leqslant n \leqslant 2000)$ , denoting the number of given points.
Following $n$ lines each contains two integers $x, y$ $(|x|,|y| \leqslant 10000)$ , denoting a given point $(x,y)$ .
It’s guaranteed that the points are pairwise different and no given point is the origin point.

输出描述

Only one line containing one integer, denoting the answer.

示例1

输入

输出

说明

Considering circle $(x-1)^2+(y-1)^2=2$ , we can see that the origin point is on its boundry and that there are $3$ given points $(0,2),(2,0),(2,2)$ on its boundry.

分析

不共线的三点确定一个圆，已知其中一个点为 $(0,0)$ ，可以在 $O(n^2)$ 的时间内枚举得到另外两个点，得到不共线的三点后，可以轻易计算出三点所确定的圆心。
当第一层枚举得到点 $A$ ，那么再枚举一个点即可得到圆心，若第三个点 $B_1$ 或 $B_2$ 同 $A$ 和原点确定的圆心都为 $C$ ，那么 $B_1,B_2,A$ 都被同一个圆的边界覆盖。第一层枚举后，用 $\text{map}$ 记录在 $\odot C$ 边界上的点（第二层枚举得到的点）的个数，取最大即可，因为圆上的点还有第一层枚举得到的点，最大值还要增加 $1$ 。
枚举的方式可保证统计在 $\odot C$ 上的点时，做到不重复不遗漏。对于同一个圆 $\odot C$ ，若枚举点 $i$ ，有 $j_1,j_2,\cdots,j_k$ 都与 $i$ 在 $\odot C$ 上，那么有 $k+1$ 个点在同一个圆上；当下一次枚举到 $j_1$ ，第三层枚举不会涉及到 $i$ ，可以确定的是，会得到有 $j_2,\cdots,j_k$ 与 $j_1$ 在 $\odot C$ 上。

for(i=1;i<=n;i++)
{
	for(j=i+1;j<=n;j++)
	{
		//function
	}
}

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem D
Date: 8/12/2020
Description: Computational Geometry
*******************************************************************/
#include<iostream>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-6;
const int N=2005;
int n;
struct CPoint 
{
	double x;
	double y;
	bool operator<(const CPoint& A)const
	{
		if(x==A.x) return A.y-y>eps;
		else return A.x-x>eps;
	}
}p[N];
map<CPoint,int>cnt;
int main()
{
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	int ans=1;//至少能覆盖一个点
	for(i=1;i<=n;i++)
	{
		cnt.clear();
		for(j=i+1;j<=n;j++)
		{
		//===========================================
		//三点确定圆心模板
			double x1=0,y1=0;
			double x2=p[i].x,y2=p[i].y;
			double x3=p[j].x,y3=p[j].y;
			double a=x1-x2;
			double b=y1-y2;
			double c=x1-x3;
			double d=y1-y3;
			double e=((x1*x1-x2*x2)-(y2*y2-y1*y1))/2;
			double f=((x1*x1-x3*x3)+(y1*y1-y3*y3))/2;
			if(fabs(b*c-a*d)<eps) continue;
			CPoint C;//圆心
			C.x=(b*f-d*e)/(b*c-a*d);
			C.y=(c*e-a*f)/(b*c-a*d);
		//============================================
			cnt[C]++;//j1,j2,...,jk
		}
		//+1 囊括第一层枚举的点
		for(auto v:cnt) ans=max(ans,v.second+1);
	}
	cout<<ans<<endl;
	return 0;
}

D. Duration $\looparrowright$

题目描述

Given two moments on the same day in the form of $HH:MM:SS$ , print the number of seconds between the two moments.

输入描述

Input two lines each contains a string in the form of $HH:MM:SS$ $(00 \leqslant$ $ HH \leqslant 23, 00 \leqslant MM,SS \leqslant 59)$, denoting a given moment.

输出描述

Only one line containing one integer, denoting the answer.

示例1

输入

1 2	12:00:00 17:00:00

输出

示例2

输入

1 2	23:59:59 00:00:00

输出

分析

以每天的 $00:00:00$ 作为基准，分别算出两个时刻距离基准的时间间隔 $HH\times 3600+MM\times 60+SS$ ，两个时间间隔差的绝对值即为答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem D
Date: 8/11/2020
Description: Easy Calculation
*******************************************************************/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
	int HH,MM,SS;
	scanf("%d:%d:%d",&HH,&MM,&SS);
	int a=HH*3600+MM*60+SS;
	scanf("%d:%d:%d",&HH,&MM,&SS);
	int b=HH*3600+MM*60+SS;
	cout<<abs(a-b)<<endl;
	return 0;
}

E. Exclusive OR $\looparrowright$

题目描述

Given $n$ integers $A_1, A_2, \cdots, A_n$ . For all $i \in \{1, 2, \cdots, n\}$ , you should determine the maximum value you can get if you repeatedly choose exactly $i$ integers $a_1, a_2, \cdots a_i$ and calculate their XOR sum $a_1 \oplus a_2 \oplus \cdots $.
Please notice that you can choose one integer multiple times for one $i$ in this problem.

输入描述

The first line contains one integer $n$ $(1\leqslant n\leqslant 2\times 10^5)$ , denoting the number of given integers.
The second line contains $n$ integers $A_1, A_2, \cdots, A_n$ $(0\leqslant A_i < 2^{18})$ .

输出描述

One line containing $n$ integers, where $i$ -th integer denotes the maximum value you can get if you repeatedly choose $i$ integers and calculate their XOR sum.

示例1

输入

1
2

4
1 4 5 7

输出

7 6 7 7

说明

${i = 1 : 7 = 7}$
$i = 2 : 7\oplus 1 = 6$
$i = 3 : 7\oplus 1 \oplus 1 = 7$
$i = 4 : 7\oplus 1 \oplus 4 \oplus 5 = 7$

翻译

给出 $n$ 个数，可以重复选择，依次求出选择 $1,2,\cdots n$ 个数字时的最大异或和。

分析

因为所有可选择的数字都小于 $2^{18}$ ，所以最大异或和必定小于 $2^{18}$ 。那么就有结论,当取的数字个数 $i>19$ 时,必定有有 $ans_{i}=ans_{i-2}$ 。下面简单证明：首先， $\forall\ i\in\mathbb N^\ast$ ，有 $ans_{i+2}\geqslant ans_{i}$ ，只需要在 $ans_i$ 的基础上随便挑两个相同的数字即可；若 $i>19$ 且 $ans_i>ans_{i-2}$ ，那么异或空间的秩至少为 $i-1$ ，这与秩为 $18$ 矛盾。方便表示，令 $lim=2^{18}$ 。
首先考虑选取两个数字时的答案。对于多项式 $C=c_0+c_1x+c_2x^2+\cdots+c_{lim-1}x^{lim-1}$ , $c_i>1$ 表示异或和为 $i$ 的方案存在，否则为 $0$ 。
首先考虑只取两个数字的情况。设多项式 $A=a_0+a_1x+a_2x^2+\cdots+a_{lim-1}x^{lim-1}$ ， $B=b_0+b_1x+b_2x^2+\cdots+b_{lim-1}x^{lim-1}$ ，初始时，令输入的 $n$ 个数字的位置的系数为 $1$ 。那么令 $C=A\oplus B$ ，即 $c_i=\sum\limits_{j\oplus k}a_j\times b_k$ ，我们遍历所有 $c_i$ ，即可得到能够获得的最大异或和。此时，若 $c_i>0$ ，表示取两项能够获得异或和 $i$ ，我们同时令 $b_i=1$ 。再算一次 $A\oplus B$ ，就能得到取三个数字的最大异或和。迭代 $19$ 次即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场）Problem E
Date: 9/17/2020
Description: FWT
*******************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=(1<<18)+5;
const ll mod=998244353;
const ll inv2=499122177;
const int lim=1<<18;
ll ans[N];
ll A[N],B[N],C[N];
int n;
void FWT_XOR(ll *x,short opt){
	for(register int i=1;i<lim;i<<=1){
		int step=i<<1;
		for(register int j=0;j<lim;j+=step){
			for(register int k=0;k<i;k++){
				const ll u=x[j+k],v=x[j+k+i];
				x[j+k]=u+v;
				x[j+k+i]=u-v;
				x[j+k]=(x[j+k]%mod+mod)%mod;
				x[j+k+i]=(x[j+k+i]%mod+mod)%mod;
				if(opt==-1){
					x[j+k]=x[j+k]*inv2%mod;
					x[j+k+i]=x[j+k+i]*inv2%mod;
				}
			}
		}
	}
}
int main(){
	cin>>n;
	int i,j;
	for(i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		A[x]=B[x]=1;
		ans[1]=max(ans[1],(ll)x);
	}
	FWT_XOR(A,1);
	for(i=2;i<=min(19,n);i++){
		FWT_XOR(B,1);
		for(j=0;j<lim;j++){
			C[j]=A[j]*B[j]%mod;
		}
		FWT_XOR(C,-1);
		for(j=0;j<lim;j++){
			if(C[j]){
				ans[i]=j;
				B[j]=1;
			}else{
				B[j]=0;//一定要初始化！
			}
		}
	}
	for(i=20;i<=n;i++){
		ans[i]=ans[i-2];
	}
	for(i=1;i<=n;i++){
		printf("%lld",ans[i]);
		putchar(i==n?'\n':' ');
	}
	return 0;
}

F. Fake Maxpooling $\looparrowright$

题目描述

Given a matrix of size $n\times m$ and an integer $k$ , where $a_{i,j} = \mathrm{lcm}(i, j)$ , the least common multiple of $i$ and $j$ . You should determine the sum of the maximums among all $k\times k$ submatrices.

输入描述

Only one line containing three integers $n,m,k$ $(1\leqslant n,m \leq 5000, 1 \leqslant k \leqslant $$\min(n, m))$.

输出描述

Only one line containing one integer, denoting the answer.

示例1

输入

3 4 2

输出

说明

The given matrix is: $\begin{pmatrix}1&2&3&4\\2&2&6&4\\3&6&3&12\end{pmatrix}$.
The maximums among all $2\times 2$ submatrices are $2,6,6,6,6,12$ respectively, and their sum is $38$ .

分析

要求所有边长为 $k$ 的正方形区域内的最值，可以看作将滑动窗口由一维的数轴扩展到了二维矩阵上。
首先对于每一行利用单调队列求出位于 $(i,j)$ 时， $(i,j)\sim (i,j+k-1)$ 区域内的最大值，用 $ans_{i,j}$ 表示。然后，遍历每一列，利用单调队列求出位于 $(i,j)$ 时， $(i,j)\sim (i+k-1,j)$ 区域内 $ans$ 的最大值，用 $ans_{i,j}$ 表示（直接赋值于 $ans_{i,j}$ ）；由于 $ans_{i,j}$ 已经是 $(i,j)\sim (i,j+k-1)$ 的最大值，所以第二次纵向求区间最大值后， $ans_{i,j}$ 已经表示由 $(i,j)$ 为左上角， $(i+k-1,j+k-1)$ 为右下角的正方形区域内的最大值。
至此，求出了所有边长为 $k$ 的正方形区域内的最值。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem F
Date: 8/11/2020
Description: Monotonous Queue
*******************************************************************/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=5003;
int n,m,k;
int ans[N][N];
int a[N][N];
int q[N];
int head,tail;
int main()
{
	int i,j;
	cin>>n>>m>>k;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			a[i][j]=i*j/__gcd(i,j);
		}
	}
	for(i=1;i<=n;i++)
	{
		//第i行区间长度为k的区间最大值
		head=1;
		tail=0;
		for(j=1;j<=m;j++)
		{
			while(head<=tail&&a[i][q[tail]]<=a[i][j]) tail--;
			q[++tail]=j;
			while(head<=tail&&q[head]<=j-k) head++;
			if(j>=k) ans[i][j-k+1]=a[i][q[head]];
		}
	}
	for(j=1;j<=m;j++)
	{
		//考察每一列
		//已经是从i开始的横向长度为k的区间最大值
		//求从第j列开始的纵向长度为k的区间最大值
		//便有从(i,j)开始的区域边长为k的区间最大值
		head=1;
		tail=0;
		for(i=1;i<=n;i++)
		{
			while(head<=tail&&ans[q[tail]][j]<=ans[i][j]) tail--;
			q[++tail]=i;
			while(head<=tail&&q[head]<=i-k) head++;
			if(i>=k) ans[i-k+1][j]=ans[q[head]][j];
		}
	}
	long long tot=0;
	for(i=1;i<=n-k+1;i++)
	{
		for(j=1;j<=m-k+1;j++)
		{
			tot+=ans[i][j];
		}
	}
	cout<<tot<<endl;
	return 0;
}

G. Greater and Greater $\looparrowright$

题目描述

Given a sequence $a$ of size $n$ and a sequence $b$ of size $m$ , determine the number of subintervals called $s$ of size $m$ in $a$ satisfying $\forall i \in \{1, 2, \cdots, m\}$ , $s_i \geqslant b_i$ .

输入描述

The first line contains two integers $n,m$ $(1\leqslant n\leqslant 150000$ , $1\leqslant m\leqslant$ $\min(n, 40000))$ . The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ $(1\leqslant a_i\leqslant 10^9)$ , denoting the sequence $a$ .
The third line contains $m$ integers $b_1, b_2, \cdots, b_n$ $(1\leqslant b_i\leqslant 10^9)$ , denoting the sequence $b$ .

输出描述

Only one line containing one integer, denoting the answer.

示例1

输入

6 3
1 4 2 8 5 7
2 3 3

输出

2

说明

The two subintervals are $[2,8,5],[8,5,7]$ .

分析

一道利用 $\text{bitset}$ 的神题。
对每一个 $b_i$ 求一个长度为 $n$ 的二进制串 $x$ ， $x_j=1$ 当且仅当 $a_j\geqslant b_i$ 。
对于样例，可以构造三个二进制串：$\begin{aligned}&a_1\ a_2\ a_3\ a_4\ a_5\ a_6\\b_1=2\ \ \ \ &\ 0\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\\b_2=3\ \ \ \ &\ 0\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 1\ \ \ 1\\b_3=3\ \ \ \ &\ 0\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 1\ \ \ 1\end{aligned}$。设置一个 $\text{bitset}\ cur$ 来代替二进制串，由于 $\text{bitset}$ 由低位向高位存储，需要将上述二进制串镜像翻转，即 $\begin{aligned}&a_6\ a_5\ a_4\ a_3\ a_2\ a_1\\b_1=2\ \ \ \ &\ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\\b_2=3\ \ \ \ &\ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 0\\b_3=3\ \ \ \ &\ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 0\end{aligned}$；比如， $a_2\geqslant b_1$ ， $cur_2=1$ 。对于一个合法区间，设其起点为 $k$ ，则 $a_k\geqslant b_1,a_{k+1}\geqslant b_2,\cdots,a_{k+m-1}\geqslant b_m$ ；不妨将上述二进制串的向右平移，得到 $\begin{aligned}b_1=2\ \ \ \ &\ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\\b_2=3\ \ \ \ &\ \ \ \ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 0\\b_3=3\ \ \ \ &\ \ \ \ \ \ \ \ \ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ 0\end{aligned}$；对于同一列，为 $a_k$ 与 $b_1$ 至 $a_{k+m-1}$ 与 $b_m$ 的对应大小关系，当且仅当一列有 $m$ 个 $1$ 时，存在一个长度为 $m$ 的合法区间。也就是说，将移动后的 $m$ 个 $\text{bitset}$ 进行与运算，最后得到的结果中 $1$ 的个数即为答案；其中，第 $i$ 个串右移 $i-1$ 位。
最暴力枚举获得 $m$ 个 $\text{bitset}$ 的时间复杂度为 $O(mn)$ ，显然是不可行的。不妨用 pair<int,int> 记录 $a,b$ ， $\text{first}$ 为数值， $\text{second}$ 为元素在原序列中的位置，接着对 $a,b$ 按数值降序排列。定义两个 $\text{bitset}$ ，用 $ans$ 记录与运算的最后结果（初始化为全 $1$ ）；用 $cur$ 记录 a[j].first>=b[i].first 时， $a_j$ 在原序列中的位置。接下来提到的 $a,b$ 中的元素，都为排序后的序列中元素。枚举 $b_i$ ，接着枚举 $a_j$ ，若 a[j].first>=b[i].first，那么令 cur.set(a[j].second)；得到 $cur$ 后，将 $cur$ 右移 b[i].second-1 位，同 $ans$ 进行与运算；多次迭代后，ans.count()即为答案。事实上，经过排序后的序列，不必每次都从 $1$ 开始枚举 $a_j$ ；当枚举 $b_i$ 时， $b_{i-1}$ 的数值必然比 $b_i$ 的数值大，若 a[j].first>=b[i-1].first，必定有 a[j].first>=b[i].first；也就是说，若满足a[j].first>=b[i-1].first的最大的 $j$ 为 $x$ ，考察 $b_i$ 时，直接从 $a_{x+1}$ 开始枚举即可，上一次得到的 $cur$ 中的 $1$ ，在此次的考察中一定是正确的，对于 $a_1\sim a_x$ ，也是不遗漏的。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem G
Date: 8/5/2020
Description: To use bitset
*******************************************************************/
#include<iostream>
#include<bitset>
#include<utility>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=150004;
pair<int,int>a[N],b[N];
int n,m;
bitset<N>ans,cur;
int main()
{
	cin>>n>>m;
	int i,j;
	for(i=1;i<=n;i++) 
	{
		int x;
		scanf("%d",&x);
		a[i]=make_pair(x,i);
	}
	for(i=1;i<=m;i++)
	{
		int x;
		scanf("%d",&x);
		b[i]=make_pair(x,i);
	}
	//按数值降序
	sort(a+1,a+1+n,[](const pair<int,int>& x,const pair<int,int>& y){return x.first>y.first;});
	sort(b+1,b+1+m,[](const pair<int,int>& x,const pair<int,int>& y){return x.first>y.first;});
	//初始化
	ans.set();
	cur.reset();
	//枚举 b
	for(i=1,j=1;i<=m;i++)
	{
		//枚举 a
		//利用上次信息
		while(j<=n&&b[i].first<=a[j].first)
		{
			cur.set(a[j].second);
			j++;
		}
		//与运算
		ans&=cur>>b[i].second-1;
	}
	cout<<ans.count()<<endl;
	return 0;
}

K. Keyboard Free $\looparrowright$

题目描述

Given three concentric circles whose radiuses are $r_1, r_2, r_3$ respectively, and $A,B,C$ are the moving points on the given three circles respectively. Determine the expected area of $\triangle ABC$ .

输入描述

The first line contains one integer $T$ $(1 \leqslant T \leqslant 1000)$ , denoting the number of test cases.
For each test case, one line containing three integers $r_1, r_2, r_3$ $(1\leqslant r_1,r_2,r_3 \leqslant 100)$ , denoting the radiuses of three given concentric circles.

输出描述

Print $T$ lines each containing one real number with one decimal places after the decimal point, denoting the answer to corresponding test case.
It’s guaranteed that the second decimal place after the decimal point is neither $4$ nor $5$ .

示例1

输入

2
1 1 1
2 3 5

输出

0.5
5.5

说明

For the first text case, the accurate answer is $\frac{3}{2\pi}=0.47746482927568600730665129011754\cdots$ .

分析

由于 $S_{\triangle ABC}$ 只与 $A,B,C$ 三点的相对位置有关，可以将 $A$ 视作顶点， $B,C$ 为动点。不妨以同心圆的圆心作为原点建立平面直角坐标系，令 $A(r_1,0)$ ， $B(r_2\cos\alpha,r_2\sin\alpha)$ ， $C(r_3\cos\beta,r_3\sin\beta)$ ； $\alpha,\beta\in\mathbb R$ ，且 $0\leqslant\alpha,\beta\leqslant 2\pi$ 。
利用向量的叉积计算面积

$S(\alpha,\beta)=\frac{1}{2}|\overrightarrow{AB}\times\overrightarrow{AC}|=\frac{1}{2}|(r_2\cos\alpha-r_1)r_3\sin\beta-(r_3\cos\beta-r_1)r_2\sin\alpha|$

设出现极角 $\alpha,\beta$ 的概率为 $f(\alpha,\beta)$ ，则 $S_{\triangle ABC}$ 的期望为

$E= \int_0^{2\pi}\int_0^{2\pi}S(\alpha,\beta)f(\alpha,\beta)d\alpha d\beta$

此题精度要求较低，不妨将 $2\pi$ 分成 $t$ 份，每份的角度为 $\frac{2\pi}{t}$ ，那么 $f(\alpha,\beta)=\frac{1}{t^2}$ 。可直接用矩形法求积分的近似数值解，设置步长为 $\frac{2\pi}{t}$ ，枚举 $[0,2\pi]$ 内的所有角度即可。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第二场） Problem K
Date: 8/4/2020
Description: Expectation and Integral
*******************************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int t=400;
const double pi=acos(-1);
double _sin[t+1],_cos[t+1];
int main()
{
	int i,j,_;
	const double step=2*pi/t;
	double theta=0;
	for(i=1;i<=t;i++)
	{
		_sin[i]=sin(theta);
		_cos[i]=cos(theta);
		theta+=step;
	}
	for(cin>>_;_;_--)
	{
		double r1,r2,r3;
		scanf("%lf%lf%lf",&r1,&r2,&r3);
		//=====================
		//排序
		if(r1>r2) swap(r1,r2);
		if(r2>r3) swap(r2,r3);
		if(r1>r3) swap(r1,r3);
		//=====================
		//矩形法 
		//枚举 t*t 个角度组合
		double ans=0;
		for(i=1;i<=t;i++)
		{
			for(j=1;j<=t;j++)
			{
				ans+=fabs((r2*_cos[i]-r1)*r3*_sin[j]-(r3*_cos[j]-r1)*r2*_sin[i]);
			}
		}
		printf("%.1lf\n",ans/2/t/t);
	}
	return 0;
}

A. All with Pairs ↬\looparrowright↬

题目描述

分析

代码

B. Boundary ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

说明

分析

代码

D. Duration ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

示例2

输入

输出

分析

代码

E. Exclusive OR ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

说明

翻译

分析

代码

F. Fake Maxpooling ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

说明

分析

代码

G. Greater and Greater ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

说明

分析

代码

K. Keyboard Free ↬\looparrowright↬

题目描述

输入描述

输出描述

示例1

输入

输出

说明

分析

代码

A. All with Pairs $\looparrowright$

B. Boundary $\looparrowright$

D. Duration $\looparrowright$

E. Exclusive OR $\looparrowright$

F. Fake Maxpooling $\looparrowright$

G. Greater and Greater $\looparrowright$

K. Keyboard Free $\looparrowright$