A.活动投票
主元素问题，用摩尔投票
#include<bits/stdc++.h>
using namespace std;
int n,a=-1,acnt,x;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&x);
if(acnt==0){
a=x;
acnt++;
}
else if(a==x){
acnt++;
}
else{
acnt--;
if(acnt==0) a=-1;
}
}
printf("%d",a);
}
B.序列
mei ting dong
C.Legacy
赛时打的时候想可能是 DIJ 会假，结果 DIJ 没假，但是建图意料之中的 T 了.
这道题的建图非常有特色，区间建图的话，虽然不知道怎么建，但是确实是应该想到线段树.
考虑建分层图，然后把目标区间用线段树拆成节点，因为目标区间可以是出边也可以是入边，所以分两层，然后在每层叶节点连边权为零的边，这样建图复杂度只有 \(log\). 然后在树上跑 DIJ 就行了
关于 SPFA
- 它死了
D.DP搬运工1
题解里说了，考虑设一个 \(f_{i,j,k}\) 做 DP
但是我觉得题解里的说法不是很清楚，我对这个 DP 的理解是，假设我们现在有一堆格子需要填，用 \(i\) 来表示已经填入的数字数量，\(j\) 来表示目前的空缺总数（注意这里的 “空缺”，一个空格组成的联通块称作一个 “空缺”，这么定义是因为比较好转移），\(k\) 用来表示当前填入数字后的 \(\max\) 总和
我们考虑以下情况（用 \(S\) 表示一个空缺，\(x,y\) 分别表示数字）
xSy
在我们将 \(S\) 填上的时候，假设我们每次都填一个更大的值，显然，填上之前的和是 \(a+b\)，之后的和是 \(2k\)，显然这么做会很麻烦，因为我们在填的时候还要考虑先把 \(a+b\) 减掉. 因此我们可以想到，与其先加上 \(a+b\) 再减掉，还不如直接不统计这个 \(a+b\) 了，因此我们直接在最后填上的时候再加上边界的贡献，这样就会比较简单.
因此，枚举五种情况：填在外面并合并，填在外面并新建连通块，填在里面并左右合并，填在里面并左或右合并，填在里面并新建联通块. 可以分别得到连通块贡献 \(0,1,-1,0,1\)，\(\max\) 求和贡献 \(i,0,2i,i,0\)，并且注意情况 \(1,2,4\) 是左右均可的合并方式，方案数贡献需要乘二
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
int f[51][51][2501];
int n,kk;
signed main(){
cin>>n>>kk;
f[1][0][0]=1;
for(int i=2;i<=n;++i){
for(int j=0;j<=n-i+1;++j){
for(int k=0;k<=kk;++k){
if(!f[i-1][j][k]) continue;
if(j){
f[i][j][k+i]+=2*f[i-1][j][k]*j%p;
f[i][j+1][k]+=f[i-1][j][k]*j%p;
f[i][j-1][k+2*i]+=f[i-1][j][k]*j%p;
}
f[i][j][k+i]+=2*f[i-1][j][k]%p;
f[i][j+1][k]+=2*f[i-1][j][k]%p;
}
}
}
int ans=0;
for(int i=0;i<=kk;++i){
ans+=f[n][0][i];
ans%=p;
}
cout<<ans;
}