24暑集训Week1
夜行的人，若你不唱歌的话，不惊醒这黑夜的话，就永远也走不出呼蓝别斯了。 这重重的森林，这崎岖纤细的山路，这孤独疲惫的心。 亲爱的，哪怕后来去到了城市，$$走$$夜路时也要大声地唱歌，像喝醉酒的人一样无所顾忌。 大声地唱啊，让远方的大棕熊也听到了，也静静起身，为你在遥远的地方让路。 ——李娟《走夜路请放声歌唱》
【2024.07.22】NOIP2024暑假集训模拟赛（1）
A
- 分数规划模板题，见 我的这篇博客.
B
- 抽 \(n\) 次卡, 连续 \(i\) 次没有抽中时, 第 \(i+1\) 次抽中的概率是 \(p_i\), 规定\(p_k=1\), 求期望抽中次数.
- 标签：矩阵加速递推, 动态规划.
- 暴力: 记 \(f[i][j]\) 表示已经抽了 \(i\) 次, 目前连续 \(j\) 次不中的期望抽中次数,有转移:
-
时间复杂度 \(O(NK)\).
-
优化:矩阵加速递推
- \[\begin{bmatrix} p_0 & p_1 & p_2 & \cdots & p_k & 0 \\ 1-p_0 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1-p_1& 0 &\cdots & 0 & 0 \\ 0 & 0 & 1-p_2&\cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & 1-p_{k-1} & 0 & 0\\ 0 & 0 & \cdots & 0 & 0 & 0 \\ p_0 & p_1 & p_2 & \cdots & p_k & 1 \\ \end{bmatrix} \times \begin{bmatrix} f_{0} \\ f_{1} \\ f_{2} \\ \vdots \\ f_{k} \\ res \\ \end{bmatrix} \]
-
记矩阵为 \(A\)(一个 边长为 \(k+2\) 的方阵), 列向量为 \(F_0\)(其中 \(f_i=1,f_{1 \sim k}=0\))
-
先用矩阵快速幂求出 \(A^n \times F_0\), 答案就是 \(res\)
-
时间复杂度:本来是\(O(K^3 \times log_2^N)\), 但有一个小优化是每次
y&1=1的时候不要另开一个单位矩阵存答案, 直接累计到那个行向量里面,这样时间复杂度会有一个 \(\frac{1}{2}\) 的常数, 会快一倍
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
using namespace std;
using ll = long long;
const int mod=998244353;
int a[205],b[205],p[205];
int n,k;
struct matrix{
int a[205][205];
void init(int val=0){
memset(a,0,sizeof(a));
F(i,0,k+1) a[i][i]=val;
}
}v;
matrix operator $ (matrix A,matrix B){
matrix C; C.init(0);
F(i,0,k+1) F(j,0,k+1) F(z,0,k+1) C.a[i][z]=(C.a[i][z]+1ll$A.a[i][j]$B.a[j][z]%mod)%mod;
return C;
}
void ksm(matrix A,int b){
int f[205],g[205];
memset(f,0,sizeof(f));
f[0]=1;
while(b){
if(b&1){
memset(g,0,sizeof(g));
F(i,0,k+1) F(j,0,k+1) g[i]=(g[i]+1ll$A.a[i][j]$f[j])%mod;//优化在这里,单次变成K^2
memcpy(f,g,sizeof(f));
}
A=A$A;
b>>=1;
}
cout<<(f[k+1]%mod+mod)%mod;
}
int quickmod(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll$res$x%mod;
x=1ll$x$x%mod;
y>>=1;
} return res;
}
signed main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>k;
F(i,0,k-1){
cin>>a[i]>>b[i];
p[i]=1ll$a[i]$quickmod(b[i],mod-2)%mod;
} p[k]=1;
v.init(0);
F(i,0,k) v.a[0][i]=v.a[k+1][i]=p[i];
F(i,1,k) v.a[i][i-1]=1-p[i-1];
v.a[k+1][k+1]=1;
ksm(v,n);
return 0;
}
C
- 线性基
D
- 点分治
【2024.07.24】NOIP2024暑假集训模拟赛（2）
A
-
一句话题意：给定 \(n,T,s_i\) , 询问有多少个四元组 \((a,b,c,d)\) 满足 \(\lfloor \frac{s_a}{s_b} \rfloor + \lfloor \frac{s_c}{s_d} \rfloor = T\), \(n,s_i,T \le 1e6\).
-
先枚举分母是整除分块,时间复杂度 \(O(N\sqrt N)\)
据说drz卡过去了; 先枚举分子是调和级数, 时间复杂度 \(O(Nlog N)\).
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
using namespace std;
using ll = long long;
const int N=1e6+3;
const int mod=998244353;
char buf[100],$p1=buf,$p2=buf;
inline int gc(){return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1==p2)?EOF:$p1++;}
inline int rd(){
int x=0; char ch;
while(!isdigit(ch=gc()));
do x=(x<<3)+(x<<1)+(ch^48); while(isdigit(ch=gc()));
return x;
}
int n,x,m=0,ans=0;
int a[N],num[N],sum[N],t[N];
signed main(){
freopen("floor.in","r",stdin);
freopen("floor.out","w",stdout);
n=rd(),x=rd();
F(i,1,n) num[a[i]=rd()]++;
F(i,1,1000000) sum[i]=sum[i-1]+num[i];
// a/b=0
F(i,1,1000000) t[0]=(t[0]+1ll$sum[i-1]$num[i])%mod;
// a/i = j
F(i,1,1000000){
for(int j=1;j$i<=1000000;++j){
t[j] = (1ll$t[j]+(1ll$sum[min(1000000,i$(j+1)-1)]-sum[i$j-1]) $ num[i]%mod)%mod;
}
}
F(i,0,x) ans=(ans+1ll$t[i]$t[x-i]%mod)%mod;
printf("%d",(ans+mod)%mod);
return 0;
}
B
- 异或
C
- 线段树,滑动窗口
D
- CDQ分治, 线段树
【2024.07.26】NOIP2024暑假集训模拟赛（3）
A
- 考虑什么样的操作合法：
- k 一定是 \(mex(a)\).
- 所有值为 \(mex(a)+1\) 的位置必须被覆盖。
- 对于所有 \(i\in[0,mex(a)−1]\) 的位置不能全被覆盖。
如果 \(a\) 中没有 \(m\)\(e\)\(x\)(\(a\))+1，那只要\(mex(a)\) 不为 \(n\) 就总能找到一个不用的位置赋值。
否则，我们记录值为 \(mex(a)+1\) 的最靠前和最靠后的位置，覆盖，然后判断是否符合 \(3\) 即可。
\(B\)
- 记每个位置的权值为 \(i \times a_i\) , 记总和为 \(S\), 1操作不会使 \(S\) 改变, 每次2操作 \(S+1\).
- 所以只有那个唯一使用 2操作的 \(S\) 不同, \(\Delta S\) 即为 2操作次数.
#include<bits/stdc++.h>
#define F(i,l,r) for(int i(l);i<=r;++i)
#define G(i,r,l) for(int i(r);i>=l;--i)
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define eb emplace_back
#define int long long
using namespace std;
using ll = long long;
int T,m,n;
signed main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>T; while(T--){
cin>>m>>n;
int ws1=-1,ws2=-1,num1=0,num2=0,ps1=-1,ps2=-1,x;
F(i,1,m){
int ws=0;
F(j,1,n) cin>>x,ws+=j*x;
if(ws1==-1) ws1=ws,num1=1,ps1=i;
else if(ws1==ws) ++num1;
else if(ws2==-1) ws2=ws,num2=1,ps2=i;
else if(ws2==ws) ++num2;
}
if(num1>1) cout<<ps2<<" "<<ws2-ws1<<"\n";
else cout<<ps1<<" "<<ws1-ws2<<"\n";
}
return 0;
}
C
-
给定 \(n\) 个点，每个点上有一个长为 \(m\) 的字符串（仅包含字母 \(Y\) 和 \(N\) ），两个点之间的边权为两个字符串不同元素个数，求最小生成树边权和。
-
用2进制预处理所有的字符串, 记 \(f[i][j]\) 表示到 \(i\) 距离为 \(j\) 的一个点(任一个点都可以,因为每次搜索完当前位, \(f[i][j]\) 都会更新(见代码), 同样优的点会在前面被用到(大概是这样吧), 所以任记录一个就行)
-
折半搜索, 每次枚举一对 \((a,b)\) 使 $dis(a,i) = j , dis(b,i) = j , dis(a,b)=1 $, 即枚举一条权值为 \(1\) 的边.
D
- 线段树
【2024.07.27】NOIP2024暑假集训模拟赛（4）
B
- 字符串模拟
C
D
- 线段树,dp