继续。仍然按照谷题号。
[省选联考 2020 A/B 卷] 冰火战士
简单题。
离散化一下，温度显然取到某个战士的温度。对于一个温度我们要知道温度小于等于它的冰系战士的能量和和大于等于它的火系战士的能量和。容易发现冰系战士能量随温度升高单调不降，火系单调不升。那么一定有一个交点。两个树状数组分别维护冰系和火系的区间和，如果二分的话是 \(O(n\log^2n)\) 的，换成倍增就是 \(O(n\log n)\)了。决策点最多两个：交点前和交点后。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,cnt,sum,lsh[2000010];
struct BIT{
int c[2000010];
#define lowbit(x) (x&-x)
void update(int x,int val){
while(x<=cnt)c[x]+=val,x+=lowbit(x);
}
int query(int x){
int sum=0;while(x)sum+=c[x],x-=lowbit(x);return sum;
}
}c1,c2;
struct ques{
int od,t,x,y;
}q[2000010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&q[i].od,&q[i].t);
if(q[i].od==1)scanf("%d%d",&q[i].x,&q[i].y),lsh[++lsh[0]]=q[i].x;
}
sort(lsh+1,lsh+n+1);
cnt=unique(lsh+1,lsh+n+1)-lsh-1;
for(int i=1;i<=n;i++){
if(q[i].od==1)q[i].x=lower_bound(lsh+1,lsh+cnt+1,q[i].x)-lsh;
}
for(int i=1;i<=n;i++){
if(q[i].od==1){
if(q[i].t==0)c1.update(q[i].x,q[i].y);
else c2.update(q[i].x+1,q[i].y),sum+=q[i].y;
}
else{
int p=q[i].t;
if(q[p].t==0)c1.update(q[p].x,-q[p].y);
else c2.update(q[p].x+1,-q[p].y),sum-=q[p].y;
}
int pos1=0,sum1=0,sum2=sum;
for(int i=20;i>=0;i--){
if(pos1+(1<<i)<=cnt){
if(sum1+c1.c[pos1+(1<<i)]<sum2-c2.c[pos1+(1<<i)]){
pos1+=1<<i;
sum1+=c1.c[pos1],sum2-=c2.c[pos1];
}
}
}
int ans1=sum1;
int pos2=0;sum1=0,sum2=sum;
int ans2=min(c1.query(pos1+1),sum2-c2.query(pos1+1));
for(int i=20;i>=0;i--){
if(pos2+(1<<i)<=cnt){
if(sum1+c1.c[pos2+(1<<i)]<sum2-c2.c[pos2+(1<<i)]){
pos2+=1<<i;
sum1+=c1.c[pos2],sum2-=c2.c[pos2];
}
else if(min(sum1+c1.c[pos2+(1<<i)],sum2-c2.c[pos2+(1<<i)])==ans2){
pos2+=1<<i;
sum1+=c1.c[pos2],sum2-=c2.c[pos2];
}
}
}
if(!ans1&&!ans2)puts("Peace");
else if(ans1<=ans2)printf("%d %d\n",lsh[pos2],ans2<<1);
else printf("%d %d\n",lsh[pos1],ans1<<1);
}
return 0;
}
[省选联考 2020 A 卷] 组合数问题
简单题。
套路下降幂：设 \(f(x)=\sum_{i=0}^ma_ix^{\underline i}\)。下降幂和组合数相乘有个性质：
\[\binom nmm^{\underline k}=\binom{n-k}{m-k}n^{\underline k}
\]
其实就是某个广为人知的组合数恒等式两边乘个 \(k!\)。
那么答案是
\[\begin{aligned}
&\sum_{k=0}^nf(k)x^k\binom nk\\
=&\sum_{k=0}^n\binom nkx^k\sum_{i=0}^ma_ik^{\underline i}\\
=&\sum_{i=0}^ma_in^{\underline i}\sum_{k=0}^n\binom{n-i}{k-i}x^k\\
=&\sum_{i=0}^ma_in^{\underline i}x^i(x+1)^{n-i}
\end{aligned}
\]
暴力递推斯特林数算一下下降幂就行了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m,x,mod,ans,stiring[1010][1010],a[1010],b[1010];
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return ans;
}
int main(){
scanf("%d%d%d%d",&n,&x,&mod,&m);
for(int i=0;i<=m;i++)scanf("%d",&a[i]);
for(int i=0;i<=m;i++){
stiring[i][0]=(i==0);
for(int j=1;j<=i;j++)stiring[i][j]=(1ll*j*stiring[i-1][j]+stiring[i-1][j-1])%mod;
}
for(int i=0;i<=m;i++){
for(int j=i;j<=m;j++){
b[i]=(b[i]+1ll*stiring[j][i]*a[j])%mod;
}
}
int ret=1;
for(int i=0;i<=m;i++){
ans=(ans+1ll*ret*b[i]%mod*qpow(x,i)%mod*qpow(x+1,n-i))%mod;
ret=1ll*ret*(n-i)%mod;
}
printf("%d\n",ans);
return 0;
}
[省选联考 2020 A 卷] 魔法商店
保序回归，不会。
[省选联考 2020 A/B 卷] 信号传递
困难题。
\(m\le 23\)，算一下复杂度 \(O(m2^m)\)，于是想状压。
两个思路：从 \(1-m\) 位置从左到右填信号站，或者从小到大安排每个信号站的位置。经过一些不可描述第二个是挂的，于是考虑第一个。第一个的 dp 过程也比较简单：考虑新加一个 \(x\) 的贡献，设 \(e_{x,y}\) 为 \(x\to y\) 的传递次数。那么显然有
\[f_S=f_{S-x}+|S|\sum_{i\in S-x}ke_{x,i}+e_{i,x}+|S|\sum_{i\notin S}ke_{i,x}-e_{x,i}
\]
暴力做复杂度 \(O(m^22^m)\)。然而可以枚举 \(S\) 然后递推后边的那一堆东西，这样时空复杂度就都是 \(O(m2^m)\) 的。
做完了？没有。你发现这个空间是爆炸的。卡空间就各凭本事了，大体上还是折半。因为卡空间没写。
[省选联考 2020 A 卷] 树
建议作为新时代 trie 板子。相当于子树加 \(1\)，子树异或和，子树合并。把 oiwiki 上的所有操作套上去就行了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n,cnt,v[530000],trie[530000*22][2],rt[530000],val[530000*22],size[530000*22];
long long ans;
struct node{
int v,next;
}edge[530000];
int t,head[530000];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
void pushup(int x){
size[x]=val[x]=0;
if(trie[x][0]){
size[x]+=size[trie[x][0]];
val[x]^=val[trie[x][0]]<<1;
}
if(trie[x][1]){
size[x]+=size[trie[x][1]];
val[x]^=val[trie[x][1]]<<1|(size[trie[x][1]]&1);
}
size[x]&=1;
}
void ins(int &rt,int x,int d){
if(!rt)rt=++cnt;
if(!d){
size[rt]++;return;
}
ins(trie[rt][x&1],x>>1,d-1);
pushup(rt);
}
int merge(int x,int y){
if(!x||!y)return x|y;
size[x]+=size[y];val[x]^=val[y];
trie[x][0]=merge(trie[x][0],trie[y][0]);
trie[x][1]=merge(trie[x][1],trie[y][1]);
return x;
}
void update(int x){
swap(trie[x][0],trie[x][1]);
if(trie[x][0])update(trie[x][0]);
pushup(x);
}
void dfs(int x){
for(int i=head[x];i;i=edge[i].next){
dfs(edge[i].v);rt[x]=merge(rt[x],rt[edge[i].v]);
}
update(rt[x]);
ins(rt[x],v[x],22);
ans+=val[rt[x]];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=2;i<=n;i++){
int f;scanf("%d",&f);add(f,i);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
[省选联考 2020 A 卷] 作业题
有点智慧的题。
首先套路反演一下答案是
\[\sum_{d=1}^{mx}\varphi(d)\sum_{d|w_e}T
\]
于是问题就变成所有边权整除 \(d\) 的生成树边权和。但是矩阵树定理是算乘积的。
人类智慧方法是把每条边权都变成 \(1+w_ix\) 的形式，然后跑矩阵树，最后行列式的一次项就是答案。
[省选联考 2020 B 卷] 消息传递
一眼淀粉质。询问挂到树上乱跑就行了。
[省选联考 2020 B 卷] 丁香之路
Yazid 神秘题。
首先枚举终点，最后就是求必须经过若干边的欧拉路。给起点和终点的度数 \(+1\) 就变成了欧拉回路。
欧拉回路的条件是所有点度数都为偶数。因此我们把每条必经边连一下，然后对于度数为奇数的点，把它和它的下一个点连边，这样是最优的。
但是一个问题是可能不连通。所以跑最小生成树，连通的代价就是最小生成树的二倍（走过去再走回来）。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,s;
struct node{
int u,v,w;
bool operator<(const node&s)const{
return w<s.w;
}
}edge[6500010];
int fa[2510],d[2510],sum,belong[2510],tmp[2510];
int find(int x){
return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(y)]=find(x);
}
int solve(int t){
for(int i=1;i<=n;i++)fa[i]=i,d[i]=tmp[i];
d[s]++;d[t]++;merge(belong[s],belong[t]);
int ans=sum;
for(int i=1;i<=n;i++){
if(d[i]&1){
merge(belong[i],belong[i+1]);
d[i]++;d[i+1]++;ans++;
}
}
int cnt=0,pos=0;
for(int i=1;i<=n;i++){
if(d[i]){
if(pos&&find(belong[i])!=find(belong[pos]))edge[++cnt]={belong[i],belong[pos],i-pos};
pos=i;
}
}
sort(edge+1,edge+cnt+1);
for(int i=1;i<=cnt;i++){
if(find(edge[i].u)!=find(edge[i].v)){
ans+=edge[i].w<<1;
merge(edge[i].u,edge[i].v);
}
}
return ans;
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
d[u]++;d[v]++;sum+=abs(u-v);
merge(u,v);
}
for(int i=1;i<=n;i++)belong[i]=find(i),tmp[i]=d[i];
for(int i=1;i<=n;i++)printf("%d ",solve(i));puts("");
return 0;
}