\[\text{NOIP模拟赛-2023.11.8} \]
T1 日本题一
\(n\times m\) 的网格，从 \((1,1)\) 移到 \((n,m)\)
网格间有两种连边（无向边）：一类边 \((i,j)\rightarrow (i+1,j)\)；二类边 \((i,j)\rightarrow (i,j+1)\)。所有边的代价都是 \(1\)，但初始时二类边均不能通过
网络中有 \(k\) 个节点可以变换边的使用权限，将通过的变成不通过，不通过的变成通过，变换一次代价 \(1\)。求最小代价，不能到则输出 \(-1\)
\(2\leq n,m\leq 10^5\)，\(1\leq k\leq 2\times 10^5\)
由于一开始题面有问题所以没写，后来看错了写了递推，最后半小时才开始写
其实就是分层图最短路
code
#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+10,M=5e5+10;
int n,m,k,tor[M],toc[M];
LL ans,f[M<<1];
struct node{int x,y,id,pd;}a[M];
vector <node> r[N],c[N];
vector <pii> g[M];
bool flag1,flag2,vis[M];
bool cmp2(const node &A,const node &B)
{
if(A.y==B.y)
return A.x<B.x;
return A. y<B.y;
}
bool cmp1(const node &A,const node &B)
{
if(A.x==B.x)
return A.y<B.y;
return A.x<B.x;
}
void add1(int x,int y,int z,int pd1,int pd2)
{
g[x].push_back({y,z});
g[y].push_back({x,z});
if(pd1)
g[x+k].push_back({y,z+1});
if(pd2)
g[y+k].push_back({x,z+1});
}
void add2(int x,int y,int z,int pd1,int pd2)
{
// cout<<x<<" "<<y<<" "<<z<<endl;
g[x+k].push_back({y+k,z});
g[y+k].push_back({x+k,z});
if(pd1)
g[x].push_back({y+k,z+1});
if(pd2)
g[y].push_back({x+k,z+1});
}
void dij()
{
priority_queue < pair<LL,int> > q;
q.push({0,a[1].id}); f[a[1].id]=0;
if(a[1].pd)
q.push({1,a[1].id+k}),f[a[1].id+k]=1;
while(q.size())
{
int x=q.top().second; q.pop();
if(vis[x])
continue;
vis[x]=1;
for(auto v:g[x])
{
if(f[v.first]>f[x]+(LL)v.second)
f[v.first]=f[x]+(LL)v.second,q.push({-f[v.first],v.first});
}
}
}
int main()
{
freopen("jpa.in","r",stdin);
freopen("jpa.out","w",stdout);
memset(f,0x3f,sizeof(f));
scanf("%d%d%d",&n,&m,&k);
swap(n,m);
for(int i=1; i<=k; i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
swap(a[i].x,a[i].y);
flag1|=(a[i].x==1&&a[i].y==1);
flag2|=(a[i].x==n&&a[i].y==m);
a[i].pd=1; a[i].id=i;
}
if(!flag1)
a[++k]={1,1,k,0};
if(!flag2)
a[++k]={n,m,k,0};
// for(int i=1; i<=n; i++)
// a[++k]={i,m,k,0};
// for(int i=1; i<=m; i++)
// a[++k]={n,i,k,0};
sort(a+1,a+1+k,cmp2);
for(int i=1; i<=k; i++)
{
if(a[i+1].y==a[i].y)
add1(a[i].id,a[i+1].id,a[i+1].x-a[i].x,(a[i].pd==1||i==1),a[i+1].pd);
}
sort(a+1,a+1+k,cmp1);
for(int i=1; i<=k; i++)
{
if(a[i+1].x==a[i].x)
add2(a[i].id,a[i+1].id,a[i+1].y-a[i].y,a[i].pd,a[i+1].pd);
}
dij();
ans=min(f[a[k].id],f[a[k].id+k]);
if(ans>1e15)
puts("-1");
else
printf("%lld\n",ans);
return 0;
}
T2 毛子题
CF1582F2 Korney Korneevich and XOR (hard version)
easy version 还是比较好搞的，设 \(f_{i,j}\) 表示前 \(i\) 位是否存在异或和为 \(j\) 的上升子序列，枚举 \(j\)，转移即找到一个 \(f_{k,j\oplus a_i}=1\) 的 \(k\) 且 \(a_k<a_i\)，那我们可以记录 \(t_v\) 表示最小的产生异或和为 \(v\) 的上升子序列的结尾元素，枚举时只需判断 \(t_{j\oplus a_i}\) 是否小于 \(a_i\) 即可，并用 \(a_i\) 去更新 \(t_j\)
对于 hard version 来说，原先的 dp 状态转移已经很难再优化，考虑换一个状态。因为其实我们从前往后枚举时并不关心当前的位置，只关心产生异或和的那个上升子序列的结尾元素，所以设 \(f_{j,k}\) 表示是否存在以 \(<j\) 的元素结尾的上升子序列异或和为 \(k\)。对于当前的数 \(a_i\)，枚举 \(k\)，若 \(f_{a_i,k}=1\)，则更新 \(f_{j,k\oplus a_i}\)，其中 \(a_i<j\leq V\)。
实际上，我们并没有必要去更新所有的 \(j\in (a_i,V]\)，因为若我们知道了 \(f_{j,k}=1\) 则所有 \(>j\) 的 \(j'\) 均满足 \(f_{j',k}=1\)。所以记 \(mx_v\) 表示对于 \(j\in(mx_v,V]\) 来说，均有 \(f_{j,v}=1\)。所以下次遇到 \(a_i\oplus k=v\) 时，只需从 \(a_i+1\) 枚举到 \(mx_v\)，然后用 \(a_i\) 更新 \(mx_v\) 即可
我们通过上述操作，优化了更新的复杂度。考虑优化枚举的复杂度。对于同一个 \(a_i\) 的 \(f_{a_i,k}\) 若 \(k\) 枚举过了就没有必要再枚举，\(f_{a_i,k}=0\) 的也没必要枚举。故开一个桶 \(buc_{a_i}\) 表示 \(a_i\) 还没有枚举过且 \(f_{a_i,k}=1\) 的 \(k\)，每次遇到 \(a_i\) 就枚举 \(buc_{a_i}\) 里的数然后更新 \(k\oplus a_i\)，最后把 \(buc_{a_i}\) 清空
时间复杂度 \(\mathcal{O}(n+V^2)\)
code
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,V=8192;
int n,a[N];
int mx[V],vis[V],cnt;
vector <int> buc[V];
int main()
{
freopen("ru.in","r",stdin);
freopen("ru.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
vis[0]=1;
for(int i=0; i<V; i++)
mx[i]=V-1,buc[i].push_back(0);
for(int i=1; i<=n; i++)
{
for(int k:buc[a[i]])
{
int cur=k^a[i];
vis[cur]=1;
while(mx[cur]>a[i])
buc[mx[cur]--].push_back(cur);
}
buc[a[i]].clear();
}
for(int i=0; i<V; i++)
if(vis[i])
cnt++;
printf("%d\n",cnt);
for(int i=0; i<V; i++)
if(vis[i])
printf("%d ",i);
return 0;
}
T3 欧洲小国题
P8313 [COCI2021-2022#4] Izbori
一眼原题，但是树状数组写了调了 2.5h 无果
注意维护三阶前缀和的写法
code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+10,M=4e5+10;
int n,m,a[N],b[N],siz;
LL ans;
vector <int> pos[N];
struct BIT
{
LL c1[M],c2[M],c3[M];
void add(int x,int y)
{
x+=n+3;
for(int i=x; i<=siz; i+=(i&-i))
{
c1[i]+=1LL*y;
c2[i]+=1LL*y*x;
c3[i]+=1LL*y*x*x;;
}
}
LL query(int x)
{
x+=n+3; LL res=0;
for(int i=x; i; i-=(i&-i))
res+=1LL*(x+2)*(x+1)*c1[i]-1LL*(2*x+3)*c2[i]+c3[i];
return res/2;
}
}t;
int main()
{
freopen("eu.in","r",stdin);
freopen("eu.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-(b+1);
for(int i=1; i<=m; i++)
pos[i].push_back(0);
for(int i=1; i<=n; i++)
a[i]=lower_bound(b+1,b+1+m,a[i])-b,pos[a[i]].push_back(i);
for(int i=1; i<=m; i++)
pos[i].push_back(n+1);
siz=2*n+5;
for(int i=1; i<=m; i++)
{
int len=pos[i].size();
for(int j=0; j<len-1; j++)
{
int L=pos[i][j],R=pos[i][j+1]-1;
int x=2*j-L,y=x-(R-L+1)+1; //y<x
if(L>R)
continue;
ans+=t.query(x-1)-t.query(y-2);
t.add(y,1); t.add(x+1,-1);
}
for(int j=0; j<len-1; j++)
{
int L=pos[i][j],R=pos[i][j+1]-1;
int x=2*j-L,y=x-(R-L+1)+1; //y<x
if(L>R)
continue;
t.add(y,-1); t.add(x+1,1);
}
}
printf("%lld\n",ans);
return 0;
}
T4 日本题二
原：https://atcoder.jp/contests/cf16-exhibition/tasks/codefestival_2016_ex_b
其实就是求所有可能的和在十进制下第 \(i\) 的最大值
枚举 \(i\)，由数据范围的限制最多只用枚举到 \(17\)
不难想到背包，在 \(\sum a_i\) 比较小的时候可以直接先做背包再枚举 \(i\)，应该可以获得 \(40\sim 50\) 分
但现在 \(\sum a_i\) 达到了 \(10^{17}\) 级别，所以考虑在模 \(10^i\) 的意义下做背包
但是直接做我们仍然会产生非常多的状态，但其实很多状态是无用的，因为我们只关心第 \(i\) 位的情况，并不关心其它位置。设有三个合法状态 \(x<y<z\) 且 \(z-x\leq 10^{i-1}\) 即 \(z,x\) 的第 \(i\) 位的差 \(\leq 1\)，这时我们就可以说 \(y\) 是无用的。为什么？因为若后面它们同时加上 \(v\)，则 \(x+v,y+v,z+v\) 这三个新状态仍然满足 \((z+v)-(x+v)\leq 10^{i-1}\)，所以 \(y\) 这个状态的第 \(i\) 位肯定和 \(x,z\) 中的一个相同，我们就可以舍弃这个状态。因此每个时刻合法状态的数量都不超过 \(10\) 个
时间复杂度 \(\mathcal{O}(17\times n\times 10\log 10)\)
code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e4+10;
int n,m,tot;
LL a[N],S[N],ans;
int main()
{
freopen("jpb.in","r",stdin);
freopen("jpb.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%lld",&a[i]);
LL pw=1;
for(int i=1; i<=17; i++)
{
LL p=pw*10; S[m=1]=0;
for(int j=1; j<=n; j++)
{
for(int k=1; k<=m; k++)
S[k+m]=(S[k]+a[j])%p;//,cout<<S[k+m]<<" ";
sort(S+1,S+1+2*m);
tot=2;
for(int k=3; k<=2*m; k++)
{
// cout<<S[k]<<" ";
if(S[k]-S[tot-1]<=pw)
S[tot]=S[k];
else
S[++tot]=S[k];
}
// cout<<endl;
m=tot;
}
ans+=S[m]/pw;
// cout<<S[m]<<endl;
pw*=10;
}
printf("%lld\n",ans);
return 0;
}