NOI2022
[NOI2022] 众数
首先看到题面第一句话发现这玩意跟摩尔投票一样。然后我们知道摩尔投票有结合律。于是我们如果不考虑前两个操作，那每个序列开个动态开点线段树维护一下摩尔投票，然后合并可以线段树合并，查询直接查每个序列摩尔投票的和，然后再统计一下这个答案在所有序列里的出现次数是否合法即可。
对于前两个操作，可以开个什么东西动态地维护序列，然后合并可以启发式合并。
然后是坑：首先这题赛时爆了一车零，因为 1e6 个 deque 会 MLE。需要 list。
然后是这题赛时一车人挂了 0-30 不等，因为查询的序列可能相同，因此统计次数要开 long long。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <list>
using namespace std;
int n,q;
list<int>v[1000010];
struct data{
int val;
long long cnt;
data operator+(data s){
if(val==s.val)return {val,cnt+s.cnt};
else{
if(cnt>s.cnt)return {val,cnt-s.cnt};
else return {s.val,s.cnt-cnt};
}
}
};
struct node{
#define lson tree[rt].ls
#define rson tree[rt].rs
int ls,rs;
data val;
}tree[1000010<<5];
int t,rt[1000010];
void pushup(int rt){
tree[rt].val=tree[lson].val+tree[rson].val;
}
void update(int &rt,int L,int R,int pos,int val){
if(!rt)rt=++t;
if(L==R){
tree[rt].val.val=pos;
tree[rt].val.cnt+=val;
return;
}
int mid=(L+R)>>1;
if(pos<=mid)update(lson,L,mid,pos,val);
else update(rson,mid+1,R,pos,val);
pushup(rt);
}
int query(int rt,int L,int R,int pos){
if(!rt)return 0;
if(L==R)return tree[rt].val.cnt;
int mid=(L+R)>>1;
if(pos<=mid)return query(lson,L,mid,pos);
else return query(rson,mid+1,R,pos);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x|y;
if(l==r){
tree[x].val.cnt+=tree[y].val.cnt;
return x;
}
int mid=(l+r)>>1;
tree[x].ls=merge(tree[x].ls,tree[y].ls,l,mid);
tree[x].rs=merge(tree[x].rs,tree[y].rs,mid+1,r);
pushup(x);
return x;
}
int main(){
scanf("%d%d",&n,&q);int lim=n+q;
for(int i=1;i<=n;i++){
int l;scanf("%d",&l);
while(l--){
int x;scanf("%d",&x);
v[i].push_back(x);update(rt[i],1,lim,x,1);
}
}
while(q--){
int od;scanf("%d",&od);
if(od==1){
int x,y;scanf("%d%d",&x,&y);
v[x].push_back(y);
update(rt[x],1,lim,y,1);
}
else if(od==2){
int x;scanf("%d",&x);
int y=v[x].back();v[x].pop_back();
update(rt[x],1,lim,y,-1);
}
else if(od==3){
data val={0,0};
int m;scanf("%d",&m);
long long cnt=0,sum=0;
static int tmp[500010];
for(int i=1;i<=m;i++){
scanf("%d",&tmp[i]);
val=val+tree[rt[tmp[i]]].val;
sum+=v[tmp[i]].size();
}
for(int i=1;i<=m;i++)cnt+=query(rt[tmp[i]],1,lim,val.val);
if((cnt<<1)<=sum)puts("-1");
else printf("%d\n",val.val);
}
else{
int x1,x2,x3;scanf("%d%d%d",&x1,&x2,&x3);
rt[x1]=merge(rt[x1],rt[x2],1,lim);rt[x3]=rt[x1];
if(v[x1].size()<v[x2].size()){
while(!v[x1].empty())v[x2].push_front(v[x1].back()),v[x1].pop_back();
swap(v[x2],v[x3]);
}
else{
while(!v[x2].empty())v[x1].push_back(v[x2].front()),v[x2].pop_front();
swap(v[x1],v[x3]);
}
}
}
return 0;
}
[NOI2022] 移除石子
一道玄学的题目。
首先考虑如何判定。先看 \(k=0,l=r\) 的部分，即给定一个序列如何判定是否有解。
观察到操作 \(2\) 只会有 \(3,4,5\) 长度的而且不会重复。
设 \(dp_{i,j,k}\) 为到 \(i\)，钦定有 \(j\) 个 \(i\) 之前的段延长到 \(i\)，必须有 \(k\) 个延伸到 \(i+1\) 是否合法。转移考虑初值 \(dp_{1,0,0}=1\)，从 \(i\) 转移到 \(i+1\) 时枚举从 \(i\) 开始的操作个数 \(l\)，若 \(a_i-j-k-l\) 小于 \(0\) 或等于 \(1\) 则不合法，否则选出 \(p\in[k,k+j]\) 个钦定延伸到 \(i+1\)，并使 \(dp_{i+1,p,l}=1\)，答案即 \(dp_{n+1,0,0}\)。复杂分析或者打个大表一直拍可以得到 \(j,k\) 只取到 \([0,2]\) 一共九种状态。
考虑 \(k>0\) 的判断。容易发现大部分情况下 \(k\) 合法则 \(>k\) 的数也合法，特例是 \(k=1\) 且全 \(0\) 或 \(k=1,n=3\) 且三个都是 \(1\)。于是设 \(f_{i,j,k}\) 为使 \(dp_{i,j,k}=1\) 至少添加的石子个数，转移同样枚举 \(l\) 和 \(p\)，容易得到至少在 \(i\) 出添加多少个石子。检查是否 \(f_{n+1,0,0}\le k\) 即可。
然后是关于计数。先对 \(k=0\) 计数：由于 \(j,k,l\le 2\)，因此 \(\ge 8\) 的所有 \(a_i\) 都是等价的。打个大表一直拍可以把这个界减到 \(6\)。于是只要枚举 \([0,6]\)。考虑 dp 套 dp：先暴力搜出 \(a_i\) 为某个数时一种状态会转移到哪种状态。转移枚举状态 \(s\) 和 \(a_i\)，对于 \(a_i<6\) 那么只要 \(l_i\le a_i\le r_i\) 就有一倍贡献，\(a_i\ge 6\) 时则每个 \(a_i\) 都有贡献，转移很简单。
把两个东西拼起来，\(k\) 是 \(100\) 所以 \(g\) 的值域是 \([0,101]\)，看起来状态数是 \(102^9\)。但是搜一下会发现实际上 \(8000\) 多种，直接跑就行了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
const int mod=1000000007;
int n,k,num,ans,trans[10010][7],dp[2][10010],l[1010],r[1010];
map<vector<int>,int>mp;
int dfs(vector<int>g){
if(mp.find(g)!=mp.end())return mp[g];
mp[g]=num++;int id=mp[g];
for(int i=0;i<7;i++){
vector<int>tmp;
for(int j=0;j<9;j++)tmp.push_back(101);
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
if(g[3*j+k]==101)continue;
for(int x=0;x<3;x++){
int val=i-j-k-x;
if(val<0)val=-val;
else val=val==1;
for(int l=k;l<=min(2,j+k);l++)tmp[3*l+x]=min(tmp[3*l+x],g[3*j+k]+val);
}
}
}
trans[id][i]=dfs(tmp);
}
return id;
}
int main(){
int tim;scanf("%d",&tim);
dfs({0,101,101,101,101,101,101,101,101});
while(tim--){
scanf("%d%d",&n,&k);ans=0;
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
memset(dp,0,sizeof(dp));dp[0][0]=1;
int cur=0;
for(int i=1;i<=n;i++){
cur^=1;
memset(dp[cur],0,sizeof(dp[cur]));
for(int j=0;j<num;j++){
if(!dp[cur^1][j])continue;
for(int k=0;k<7;k++){
int ret=0;
if(k<6)ret=l[i]<=k&&k<=r[i];
else if(r[i]>=6)ret=r[i]-max(l[i],6)+1;
dp[cur][trans[j][k]]=(dp[cur][trans[j][k]]+1ll*ret*dp[cur^1][j])%mod;
}
}
}
for(pair<vector<int>,int>p:mp)if(p.first[0]<=k)ans=(ans+dp[cur][p.second])%mod;
if(k==1){
bool jud=true;
for(int i=1;i<=n;i++)if(l[i]!=0){
jud=false;break;
}
if(jud)ans=(ans-1+mod)%mod;
if(n==3&&l[1]<=1&&r[1]>=1&&l[2]<=1&&r[2]>=1&&l[3]<=1&&r[3]>=1)ans=(ans-1+mod)%mod;
}
printf("%d\n",ans);
}
return 0;
}
[NOI2022] 树上邻域数点
不会 Top Tree。
[NOI2022] 挑战 NPC Ⅱ
看到 \(k\) 比较小，于是来个暴力一点的方法。
我们顺序搜两棵树，然后哈希值相同的直接匹配显然是最优的，哈希值不同的可以 \(O(k!)\) 暴力枚举哪对之间匹配然后暴力搜下去。
然后还需要加上一些玄学剪枝：首先如果 \(G\) 的儿子个数 / 子树大小小于 \(H\) 的儿子个数 / 子树大小显然不合法。然后如果子树大小相同直接返回哈希值相同。好像还有别的剪枝，不过不加也没什么关系，反正能过。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int n1,n2;
ull nxt(ull x){
x^=x<<13;x^=x>>7;x^=x<<17;
return x;
}
ull hs[100010][2];
vector<int>g[100010][2];
bool cmp1(int a,int b){
return hs[a][0]<hs[b][0];
}
bool cmp2(int a,int b){
return hs[a][1]<hs[b][1];
}
int size[100010][2];
void dfs1(int x,int id){
hs[x][id]=size[x][id]=1;
for(int v:g[x][id]){
dfs1(v,id);
hs[x][id]+=nxt(hs[v][id]);
size[x][id]+=size[v][id];
}
if(id==0)sort(g[x][id].begin(),g[x][id].end(),cmp1);
else sort(g[x][id].begin(),g[x][id].end(),cmp2);
}
bool dfs(int x,int y){
if(g[x][0].size()<g[y][1].size())return false;
if(size[x][0]<size[y][1])return false;
if(size[x][0]==size[y][1])return hs[x][0]==hs[y][1];
vector<int>A,B;
int a=0,b=0;
while(a<g[x][0].size()&&b<g[y][1].size()){
if(hs[g[x][0][a]][0]==hs[g[y][1][b]][1])a++,b++;
else if(hs[g[x][0][a]][0]<hs[g[y][1][b]][1])A.push_back(g[x][0][a]),a++;
else B.push_back(g[y][1][b]),b++;
}
while(a<g[x][0].size())A.push_back(g[x][0][a]),a++;
while(b<g[y][1].size())B.push_back(g[y][1][b]),b++;
vector<int>p;
for(int i=0;i<A.size();i++)p.push_back(i);
do{
bool jud=true;
for(int i=0;i<B.size();i++){
if(size[A[p[i]]][0]<size[B[i]][1]){
jud=false;break;
}
}
if(!jud)continue;
for(int i=0;i<B.size();i++){
if(!dfs(A[p[i]],B[i])){
jud=false;break;
}
}
if(jud)return true;
}while(next_permutation(p.begin(),p.end()));
return false;
}
int main(){
int tim;scanf("%*d%d%*d",&tim);
while(tim--){
scanf("%d",&n1);
int rt1,rt2;
for(int i=1;i<=n1;i++){
int f;scanf("%d",&f);
if(f==-1)rt1=i;
else g[f][0].push_back(i);
}
scanf("%d",&n2);
for(int i=1;i<=n2;i++){
int f;scanf("%d",&f);
if(f==-1)rt2=i;
else g[f][1].push_back(i);
}
dfs1(rt1,0);dfs1(rt2,1);
if(dfs(rt1,rt2))puts("Yes");
else puts("No");
for(int i=1;i<=n1;i++)g[i][0].clear();
for(int i=1;i<=n2;i++)g[i][1].clear();
}
}
[NOI2022] 冒泡排序
首先显然可以让所有数只取到给定的 \(V\) 中的数。于是先离散化一下。然后最小化逆序对个数。
先看 B 部分分。确定了一堆单点，那么开个区间加查最小值的线段树随便扫一扫就行了。
然后是 C。容易发现把区间的最小值放在开头一定最优，于是变成了确定一堆单点，每个位置 \(\ge\) 某个数。也是线段树扫一扫就行了。
最后是比较困难的 A。根据上边的性质，我们必须把 \(1\) 铺满。然后看剩下的 \(0\) 的区间，它就变成了 C 部分。在开头安上然后线段树扫一扫就行了。
于是正解就十分显然了：我们把 \(V\) 从大到小排序，每次扫所有 \(\ge V\) 且没扫过的位置（可以用并查集记录扫没扫），在开头确定为最小值，然后给剩下的位置打个 \(\ge\) 这个最小值的标记。确定的部分可以树状数组扫一遍统计，不确定的线段树扫一扫。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m,lsh[1000010];
long long ans;
struct ques{
int l,r,val;
}q[1000010];
vector<pair<int,int> >v[1000010];
struct BIT{
int c[1000010];
#define lowbit(x) (x&-x)
void update(int x){
while(x)c[x]++,x-=lowbit(x);
}
int query(int x){
int sum=0;
while(x<=m)sum+=c[x],x+=lowbit(x);
return sum;
}
}c;
int fa[1000010];
int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
struct node{
#define lson rt<<1
#define rson rt<<1|1
int mn,pos,lz;
}tree[4000010];
void pushup(int rt){
tree[rt].mn=min(tree[lson].mn,tree[rson].mn);
if(tree[rt].mn==tree[lson].mn)tree[rt].pos=tree[lson].pos;
else tree[rt].pos=tree[rson].pos;
}
void pushtag(int rt,int val){
tree[rt].mn+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);
pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void build(int rt,int l,int r){
tree[rt].mn=tree[rt].lz=0;tree[rt].pos=l;
if(l==r)return;
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
pair<int,int> query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return make_pair(tree[rt].mn,tree[rt].pos);
pushdown(rt);
int mid=(L+R)>>1;
pair<int,int>val=make_pair(0x3f3f3f3f,0x3f3f3f3f);
if(l<=mid)val=min(val,query(lson,L,mid,l,r));
if(mid<r)val=min(val,query(rson,mid+1,R,l,r));
return val;
}
int val[1000010],mn[1000010];
void solve(){
scanf("%d%d",&n,&m);ans=0;
for(int i=1;i<=n+1;i++)fa[i]=i,val[i]=mn[i]=0;
for(int i=1;i<=m;i++)c.c[i]=0,v[i].clear();
for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].val),lsh[i]=q[i].val;
sort(lsh+1,lsh+m+1);
for(int i=1;i<=m;i++){
q[i].val=lower_bound(lsh+1,lsh+m+1,q[i].val)-lsh;
v[q[i].val].push_back(make_pair(q[i].l,q[i].r));
}
for(int i=m;i>=0;i--){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end());
int pre=n+1;
for(int j=v[i].size()-1;j>=0;j--){
if(v[i][j].second<pre){
int pos=find(v[i][j].first);
if(pos>v[i][j].second){
puts("-1");return;
}
val[pos]=i;pre=pos;
}
}
for(pair<int,int>p:v[i]){
for(int j=find(p.first);j<=p.second;j=find(j))mn[j]=i,fa[j]=j+1;
}
}
build(1,0,m+1);
for(int i=1;i<=n;i++){
if(val[i]){
ans+=c.query(val[i]+1);
c.update(val[i]);
update(1,0,m+1,val[i]+1,m+1,1);
}
}
for(int i=1;i<=n;i++){
if(val[i]){
update(1,0,m+1,val[i]+1,m+1,-1);
update(1,0,m+1,0,val[i]-1,1);
}
else{
pair<int,int>p=query(1,0,m+1,mn[i],m+1);
ans+=p.first;
if(p.second)update(1,0,m+1,0,p.second-1,1);
}
}
printf("%lld\n",ans);
}
int main(){
int tim;scanf("%d",&tim);
while(tim--)solve();
return 0;
}
[NOI2022] 二次整数规划问题
（原先是 10 个，由于要放假了于是加 10 个）
快踩