游记及总结在逼乎。
所有题目已更新。
A. 期望逆序对
题目描述
有$n$个独立的随机变量，其中$x_i$的值是一个从$[l_i,r_i]$中随机选取的整数，即对于$[l_i,r_i]$中的任何一个整数$j$，$x_i=j$的概率都是$(r_i−l_i+1)^{−1}$。
现在你需要给出一个长度为$n$的排列$p$，那么可以得到一个长度为$n$的随机变量序列。你的目标是让结果序列的逆序对个数的期望尽可能少。
求逆序对个数的期望的最小值。
题目分析
贪心，按照中点从小到大排序，然后枚举两两区间计算形成逆序对的概率即可。
计算逆序对概率的时候要分三种情况讨论，推推公式就可以了。
这么简单居然考试没做。（恼）
代码
1 |
|
B. 密码学
题目描述
考虑一种加密方式，它需要一个任意长度的原文$m$和秘钥$key$，其中要求原文和秘钥只包含大写和小写的英文字符。
首先定义字符之间的加密，用字符$a$去加密字符$b$的结果是：
- 首先把$a$和$b$转成数字$x$和$y$。转换的规则是，小写字母$a$到$z$依次对应$0$到$25$，大写字母依次对应$26$到$51$。
- 计算$x$和$y$的和$z$，对$52$取模，即计算$(x+y)\mod52$。
- 返回数字$z$对应的字符。
现在来讲如何用秘钥 key 来加密原文$m$：
- 如果秘钥的 key 的长度小于$m$，那么不停重复 key 直到长度不小于$m$为止。举例来说，如果原文是 beijing，秘钥是 PKUSAA，那么秘钥需要被重复称 PKUSAAPKUSAA。
- 假设原文的长度是$n$，那么对于每一个$[1,n]$的数字$i$，都用 key 的第$i$个字符去加密$m$的第$i$个字符。
- 返回结果。
那么用 PKUSAA 去加密 beijing 的结果就是：QOcbINV。
现在火山哥有$n$个字符串，$s_1$到$s_n$，他对这些字符串做了$m$次加密操作：第$i$次加密操作用第$s_{x_i}$去加密$s_{y_i}$，并把$s_{y_i}$替换成加密结果。
现在依次给出$m$次加密操作，以及加密操作结束后每一个字符串的模样，你可以还原出这$n$个字符串原来的模样吗？
题目分析
倒序模拟即可。
代码
1 |
|
C. 染色图
题目描述
定义一张无向图$G=⟨V,E⟩$是$k$可染色的当且仅当存在函数$f:V↦\{1,2,⋯,k\}$满足对于$G$中的任何一条边$(u,v)$，都有$f(u)\neq f(v)$。
定义函数$g(n,k)$的值为所有包含$n$个点的无自环、无重边的$k$可染色无向图中的边数最大值。举例来说，$g(3,1)=0,g(3,2)=2,g(3,3)=3$。
现在给出三个整数$n,l,r$，你需要求解：$(\sum_{i=l}^rg(n,i))\mod 998244353$
题目分析
设第$i$种颜色的点有$x_i$个，那么为了获得最大的边数，我们应在不同颜色点间都连边，最大边数即为：
由于$f(x)=g(n,m)$的对称性，将$n$尽量平均地分给所有$x_i$，可以让$g(n,m)$最大。此时有$n\bmod m$种颜色有$\lceil\frac nm\rceil$个点，剩下的$m-n\bmod m$个颜色只有$\lfloor\frac nm\rfloor$个点。
根据恒等式$\lceil\frac nm\rceil=\lfloor\frac {n-1}m\rfloor+1,n\bmod m=n-m\lfloor\frac nm\rfloor$化简得到：
于是使用数论分块就可以在$\sqrt n$的时间内得出每组数据的解了。
这种解法有一个$2$的常数，本题还可以考虑使用$n$个数的平方和公式求解，就可以省去这个常数，下方附上队友yk的代码。
代码
常数$2$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
typedef long long LL;
const int p=998244353;
LL n,L,R;
LL get(LL L,LL R) {return (L+R)*(R-L+1)/2%p;} //等差数列求和
LL C2(LL x) {return x*(x-1)/2%p;}
LL g(LL n,LL l,LL r) {
LL Down=n/l,Up=(n-1)/l+1,len=r-l+1;
LL tmp=Down*get(l,r)%p;
LL val1=(len*n%p-tmp+p)%p*C2(Up)%p,val2=(get(l,r)-n*len%p+tmp+p)%p*C2(Down)%p;
return (val1+val2)%p;
}
int main() {
int t=Get_Int();
while(t--) {
n=Get_Int();
L=Get_Int();
R=Get_Int();
int Next=1;
LL ans=0;
for(int i=L; i<=min(R,n-1); i=Next+1) {
Next=min(R,min(n/(n/i),(n-1)/((n-1)/i)));
ans=(ans+g(n,i,Next))%p;
}
printf("%lld\n",(C2(n)*(R-L+1)%p-ans+p)%p);
}
return 0;
}
yk的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=100007;
const ll inf=1<<29;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int mod=998244353;
ll sum(ll l,ll r){
return (r-l+1)*(l+r)/2%mod;
}
ll solve(ll N,ll L,ll R){
ll ans=0;
for(ll l=L,r;l<=R;l=r+1){
r=min(R,N/(N/l));ll y=N/l;
// cout<<y<<endl;
ans+=(mod-sum(l,r)*(((y*y)%mod+y)%mod))%mod+(2*y+1)%mod*N%mod*(r-l+1)%mod;
ans%=mod;
}
// cout<<ans<<endl;
return (N*N%mod*(R-L+1)%mod+mod-ans)%mod*(mod+1)/2%mod;
}
int main(){
int t=read();
while(t--){
ll n=read(),L=read(),R=read();
printf("%lld\n",solve(n,L,R)%mod);
}
return 0;
}
D. 生成树
题目描述
首先给出一些简单的概念：
- 对于一张 无向图$G=⟨V,E⟩$，树$T=⟨V,E′⟩$是$G$的生成树当且仅当$E′$是$E$的子集。
- 两棵$G$的生成树$T_1=⟨V,E_1⟩,T_2=⟨V,E_2⟩$是不同的当且仅当它们使用的边集不同。
- 集合$\mathcal{T}(G)$表示图$G$所有不同的生成树形成的集合。
- 函数$s(G,T)$来衡量树$T$和图$G$的相似度，它的值等于同时出现在$T$和$G$中的边的数量。
现在给出两张$n$个点的无向图$G_1,G_2$，你需要求：$\sum_{T\in \mathcal{T}(G_1)}s(G_2,T)$
题目分析
这题需要用到矩阵树定理与基尔霍夫矩阵。
矩阵树定理告诉我们可以使用基尔霍夫矩阵求生成树的个数。
然而这有扩展版，带权的基尔霍夫矩阵可以求一些奇奇怪怪的东西。
如果定义一棵生成树的权值是其所有边权相乘，那么构造带权的基尔霍夫矩阵：
- $\forall1\le i\le n,A_{i,i}$为与$i$相连的所有边的权值和。
- $\forall1\le i\neq j\le n,A_{i,j}$为$(i,j)$边权的相反数。
删去矩阵第$n$行第$n$列，得到的矩阵行列式即为所有生成树权值的和。
那么对于这道题来说，我们需要构建一个更奇怪的图来将原来的两个图的边合并起来。
我们定义只在$G_1$中的边在新图$G_3$中边权为$1$，而在$G_1,G_2$中都存在的边边权为$x$，那么$G_3$生成的基尔霍夫矩阵$A$中每一个元素都是一个关于$x$的多项式，其行列式是一个$n-1$阶的多项式：$\left|A\right|=f(x)=\sum_{i=0}^{n-1}a_ix^i$，考虑$a_i$的意义，即为有$a_i$个生成树有$i$条公共边，因此答案就是$\sum i\times a_i=f’(1)$。
行列式$\left|A(x)\right|$求导可以用公式：
如果继续用行列式的展开化简我们可以得到：
取$x=1$，用高斯消元算逆矩阵和行列式就可以了。
代码
1 |
|
E. 树与路径
题目描述
在一棵有根树$T$上，任何两点间的最短路径都能够分为两个阶段：
- 从起点出发，沿着向根的方向走若干条边。
- 向着终点，沿着离开根的方向走若干条边。
定义一条路径的权值为向上走的边数乘上向下走的边数。特殊地，当起点等于终点的时候，两阶段的边数都是$0$；当起点是终点的祖先的时候，第一阶段的边数是$0$；当终点是起点的祖先的时候，第二阶段的边数是 0———这三种情况下，路径的权值都是$0$。
现在给出一棵$n$个节点的无根树$T$和$m$条路径$(a_i,b_i)$。对于每一个$r\in[1,n]$，你需要计算当$r$是根节点的时候，所有路径的权值和是多少。
题目分析
考试的时候傻了，觉得这个转移必定不可维护，理由是中间点没法考虑，但是如果考虑贡献作差的话就可以维护了。
假设$A_x$是以$x$为根的答案（假设当$1$为根时，$x$的父亲是$f_x$），那么$A_1$很容易求出来，现在我们考虑换根求$A_x$，那么只需要考虑$A_x-A_{f_x}$：
- 如果一条路径不同时经过$x$与$f_x$，则他们对$A_x,A_{f_x}$的贡献相同。
- 如果路径同时经过$x,f_x$，设路径长度为$len$，向上段路径长度是$l$，那么路径对$A_x$的贡献是$l(len-l)$，而它对$A_{f_x}$的贡献是$(l+1)(len-l-1)$，贡献差为$2l+1-len$。
因此我们需要对树上所有的结点$i$，统计同时经过$i,f_i$的路径的$2l+1-len$的和，这样我们就可以通过换根求出$A_i$，问题转化为如何对于每一个$i$求出$2l+1-len$的和。
考虑对于一条路径$[u,v]$，它对$u$产生了$1-len$的贡献，它对$f_u$产生了$3-len$的贡献，依次类推，它对每一个路径$[u,lca)$上的点$i$产生了$1-len+2dep_u-2dep_i$的贡献。这是一个等差数列，第$i$个点获得的贡献可以转化为一个关于$dep_i$的一次函数：$a_idep_i+b_i$。
每一条路径的贡献可以通过树上差分处理，然后从下往上统计所有的$a_i,b_i$，就可以求出贡献差$A_x-A_{f_x}$了，然后换根即可。
代码
1 |
|
F. 乘法
题目描述
给出一个长度为$n$的数列和一个长度为$m$的数列 ，可以构造得到一个$n\times m$的矩阵$C$，其中$C_{i,j}=A_i\times B_j$。
给出整数$K$，你需要求出$C$中第$K$大的数的值。
题目分析
这道题的难点在于有负数和$0$，可以分成六个表用二分+双指针（难调），也可以二分+lowerbound（但也要特殊处理$0$）。
这道题我们调了3个小时，可以说是day1演了的罪魁祸首，主要问题出在配合上，一开始写的是lowerbound，因为$0$的问题出锅，讨论后发现双指针不需要特殊处理，于是重新写双指针，结果更难调，3个小时后又换回lowerbound处理0才过。
代码
队友的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
const int maxn = 1e5+5;
const double eps = 1e-7;
long double a[maxn],b[maxn],rb[maxn];
long long n,m,k;
bool check(long long mid) {
long long cnt = 0;
for (int i=0;i<n;i++) {
if (a[i] == 0) continue;
if (a[i] > 0) {
cnt += b + m - upper_bound(b,b+m,(long double)mid / a[i] + eps);
}
else if (a[i]< 0) {
cnt += rb + m - upper_bound(rb,rb+m,-((long double)mid/a[i]) + eps);
}
}
long long zero=0;
for(int i=0; i<n; i++)if(a[i]==0)zero++;
if(mid<0) cnt+=zero*m;
//printf("mid=%lld cnt=%lld\n",mid,cnt);
return cnt <= k;
}
long long work(long long _k) {
k = _k - 1;
long long l = -1e13, r = 1e13;
long long ans = 0x8000000000000000;
while (l <= r) {
long long mid = (l + r) >> 1;
if (check(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ans;
}
void debug() {
vector <long long> res;
for (int i=0;i<n;i++) for (int j=0;j<m;j++) res.push_back(a[i] * b[j]);
sort(res.begin(),res.end());
reverse(res.begin(),res.end());
printf("-----DEBUG BEGIN-----\n");
for (auto x:res) printf("%lld\n",x);
printf("-----DEBUG END -----\n");
}
int main() {
long long _k;
scanf("%lld%lld%lld",&n,&m,&_k);
for (int i=0;i<n;i++) scanf("%Lf",&a[i]);
for (int i=0;i<m;i++) scanf("%Lf",&b[i]);
for (int i=0;i<m;i++) rb[i] = -b[i];
//debug();
sort(a,a+n);
sort(b,b+m);
sort(rb,rb+m);
//k = _k - 1;
printf("%lld\n",work(_k));
//for (int mid=-10;mid<=10;mid++) printf("debug mid=%d %lld\n",mid,check(mid));
//for (long long _k=1;_k<=n*m;_k++) printf("debug k=%lld %lld\n",_k,work(_k));
return 0;
}
G. 圆凸包
题目描述
给出$n$个点求他们的凸包是一个经典问题，所以出了一道稍微难一点的题。
给出平面上$n$个圆，第$i$个圆的圆心是$(x_i,y_i)$，半径是$r_i$。定义这$n$个点的凸包为所有满足以下条件的点$P$形成的区域：存在点$A,B$和常数$\alpha\in[0,1]$满足$A,B$都在某个圆的内部（所在的圆可以不同）且$P=\alpha A+(1−\alpha)B$。换句话说，这$n$个点的凸包等于这$n$个圆内部的所有点形成的凸包。
现在给出这$n$个圆，试求这$n$个圆形成的凸包的周长。
给出整数$K$，你需要求出$C$中第$K$大的数的值。
题目分析
很容易想到凸包上存在的只可能是圆弧或者公切线。
而一个点要成为凸包上的点也必须满足条件：
- 它是两个圆的外切点
- 它不被任何圆覆盖
处理公切线部分的凸包很容易想，主要问题在于如何判断凸包点集中的相邻两点连接它们的是线段还是圆弧。
这里吉老师给出了一个性质：如果这两个点在一个圆上，连接它们的是圆弧，否则是线段。
接下来就贴板子就可以了。
代码
没有，不想写了。（有一定概率会回来补）
H. 最大公约数
题目描述
有三个人，$A,B,C$，其中$A$和$B$共享了一个神秘的数字$k$，已知$1\le k\le n$。
现在$A$和$C$说：“$k$的值等于$x$”。
$C$不太信任$A$，于是想向$B$确认一下$k$是否真的等于$x$。$B$虽然不想直接把$k$的值告诉$C$，但是$B$允许$C$给出一个正整数$y$（注意$y$可以大于$n$），然后$B$会回答$gcd(k,y)$。
现在给出$k,n$，你需要帮助$C$决定这样的$y$的取值，使得$C$一定可以通过$B$的回答来判断$A$有没有撒谎。如果这样的$y$有多个，你需要输出最小的那个。
题目分析
- $y$必须是$k$的倍数，否则无法区分$gcd(y,k)$和$k$。
- 对于$[1,\lfloor\frac nk\rfloor]$的每一个质数$p$，$\frac yk$必须是$p$的倍数，否则无法区分$k$和$pk$。
- 答案就是$k\prod p_i$，需要用高精度。
代码
队友的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int maxn=100007;
const ll inf=1<<29;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
int vis[1007];
int a[1007][1007];
struct bignum{
int shu[300];int len;
bignum(){
memset(shu,0,sizeof(shu));
}
bignum operator = (int a){
char b[30];sprintf(b+1,"%d",a);
return *this=b;
}
bool operator < (bignum a) const {
if(len!=a.len) return len<a.len;
for(int i=a.len;i;i--) if(shu[i]!=a.shu[i]) return shu[i]<a.shu[i];
return false;
}
bool operator == (bignum a) const{
if(len!=a.len) return false;
for(int i=a.len;i;i--) if(shu[i]!=a.shu[i]) return false;
return true;
}
bignum operator = (char *a){
len=strlen(a+1);for(int i=1;a[i]=='0';i++) len--;
for(int i=1;i<=len;i++) shu[i]=a[len-i+1]-'0';
return *this;
}
bool operator > (bignum a) const{
return a<*this;
}
void move(){
for(int i=1;i<=len;i++){
if(shu[i]>9){
if(i==len){
shu[++len]=shu[i]/10;
shu[i]%=10;
}
else shu[i+1]+=shu[i]/10,shu[i]%=10;
}
}
}
bignum operator + (bignum a){
int lm=max(len,a.len);bignum new1;
for(int i=1;i<=lm;i++){
new1.shu[i]=shu[i]+a.shu[i];
}
new1.len=lm;
new1.move();
return new1;
}
bignum operator * (bignum a){
bignum new1;
for(int i=1;i<=len;i++)
for(int k=1;k<=a.len;k++)
new1.shu[i+k-1]+=shu[i]*a.shu[k];
new1.len=len+a.len-1;
new1.move();
return new1;
}
void print(){
for(int i=len;i;i--) printf("%d",shu[i]);
printf("\n");
}
};
int main(){
for(int i=2;i<=1000;i++)
for(int k=2*i;k<=1000;k+=i)\
vis[k]=1;
int t=read();
while(t--){
int n=read(),m=read();
int x=m;bignum tot;tot=1;
for(int i=2;i<=n;i++){
bignum now;now=i;
if(!vis[i]){
if(x%i==0){
while(x%i==0) x/=i,tot=tot*now;
if(m*i<=n) tot=tot*now;
}
else if(m*i<=n) tot=tot*now;
}
}
tot.print();
}
return 0;
}
I. K小数查询
题目描述
热爱学习刻苦奋斗的九条可怜最近做了很多数据结构题，接触到了$K$小数查询这一系列的问题以及线段树的重磅打击这一套理论，她觉得这两样东西都很厉害，所以想要出一道题。
给出一个长度为$n$的数列$A$，接下来有$m$次操作，操作有两种：
- $1\,l\,r\,x$，表示对$i\in[l,r]$，令$A_i=min(A_i,x)$
- $2\,l\,r\,k$，表示询问区间$[l,r]$中第$k$小的数。
这个问题对可怜来说有点难，你能帮帮她吗。
题目分析
线段树套权值线段树，内部权值线段树需要可持久化处理。
也就是，对区间$[1,n]$建立线段树，对于每一个区间$[l,r]$建立一棵权值线段树保存每种权值出现了多少次。
这样询问可以转化为在$\log n$棵权值线段树上二分，询问可以在$O(\log^2n)$的时间内处理结束。
修改时，线段树先定位到一些结点区间$[l,r]$（这些区间的定位用到吉老师线段树定位,外部线段树的定位还是$\log n$的时间），将其内部权值线段树中$\ge x$的所有数并入$x$处，考虑暴力修改，可以转化为$t+1$次单点修改，$t$是被并入的结点个数，修改完权值线段树后，这$t+1$次修改需要向上维护，每一个父亲结点的权值线段树都需要重新合并，在可持久化后，这一段的时间复杂度是$O(t\log^2n)$。
接着在$[l,r]$这个区间打上已经取$\min$的标记，在标记下传时将比$x$更大的结点并入$x$。
时间复杂度的瓶颈在于$O(t\log^2n)$，每一次操作后内层线段树的叶子结点都会减少$t$，而$t$最多减少$n\log n$，所以$t\le n\log n$，本题时间复杂度为$O(n\log^3 n)$。
但是这道题卡时间卡空间烦死了，到处要回收内存（所以写了两个merge）。
代码
1 |
|
J. 德州扑克
题目描述
略
题目分析
枚举减枝，算了算了。
