多校冲刺 noip 11.10
仍然是不太行，又挂分了，不爽
T1 开挂
最后的数字集合是一定的
直接用\(set\)维护数字集合，尽量找最近的匹配，可以让小的变化大些
我考场上怕被卡常，还写了一个链表版的
set
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
const int N=1e6+5;
int n,a[N],b[N],c[N],add[N];
set<int> st;
unsigned long long ans;
signed main(){
freopen("openhook.in","r",stdin);
freopen("openhook.out","w",stdout);
n=read();
fo(i,1,n)a[i]=read();
fo(i,1,n)b[i]=read();
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int now=0;
fo(i,1,n){
if(a[i]>now){
now=a[i];
st.insert(now);
}
else {
now+=1;
st.insert(now);
}
}
fu(i,n,1){
set<int>::iterator it=st.lower_bound(a[i]);
add[i]=*it-a[i];st.erase(it);
}
sort(add+1,add+n+1,greater<int>());
fo(i,1,n)ans=ans+1ull*add[i]*(1ull*b[i]);
printf("%llu",ans);
return 0;
}
链表
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
const int N=1e6+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,a[N],b[N],c[N],add[N];
int bg[N],ed[N],nt[N],hd,rp;
unsigned long long ans;
signed main(){
freopen("openhook.in","r",stdin);
freopen("openhook.out","w",stdout);
n=read();
fo(i,1,n)a[i]=read();
fo(i,1,n)b[i]=read();
sort(a+1,a+n+1);a[n+1]=inf;
sort(b+1,b+n+1);
fu(i,n,1){
if(a[i]!=a[i+1]){
add[i]=0;
bg[++rp]=a[i]+1;
ed[rp]=a[i+1]-1;
if(bg[rp]>ed[rp])continue;
nt[rp]=hd;hd=rp;
}
else {
add[i]=bg[hd]-a[i];
bg[hd]++;
if(bg[hd]>ed[hd])hd=nt[hd];
}
}
sort(add+1,add+n+1,greater<int>());
fo(i,1,n)ans=ans+1ull*add[i]*(1ull*b[i]);
printf("%llu",ans);
return 0;
}
T2 叁仟柒佰万
看性质，发现每一个区间的\(mex\)都是大区间的\(mex\)
所以我们直接\(\mathcal{O(n)}\)找到\(mex\)
直接判断数字集合，转移就完事了，考场上多开了一个数组，认为内存不太够，只有\(90pts\)
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
const int N=3.7e7+5;
const int mod=1e9+7;
int T,n,a[N],mex;
bool vis[N];
int buc[N],cnt,nxt;
int dp[N];
signed main(){
freopen("clods.in","r",stdin);
freopen("clods.out","w",stdout);
//cout<<(sizeof(dp)*3+sizeof(vis)>>20)<<endl;
T=read();
while(T--){
n=read();int x,y;
if(n==37000000)x=read(),y=read();
fo(i,0,n){
vis[i]=false;
buc[i]=dp[i]=0;
}mex=0;cnt=0;nxt=n+1;
dp[n+1]=0;
fo(i,1,n){
if(n==37000000){
if(i==1)a[i]=0;
else a[i]=(1ll*a[i-1]*x+y+i)&262143;
}
else a[i]=read();
if(a[i]<=n)vis[a[i]]=true;
}
fo(i,0,n)if(!vis[i]){mex=i;break;}
fo(i,1,n){
if(a[i]<=mex){
buc[a[i]]++;
if(buc[a[i]]==1)cnt++;
if(cnt==mex){nxt=i;break;}
}
}
if(nxt==n+1)nxt=1;
int it=nxt;dp[nxt]=1;
fo(i,1,n){
if(a[i]<=mex){
buc[a[i]]--;
if(!buc[a[i]]){
cnt--;int las=it;
for(int j=it+1;j<=n;j++){
if(a[j]<=mex||mex==0){
buc[a[j]]++;
if(buc[a[j]]==1)cnt++;
if(cnt==mex){
it=j;
break;
}
}
}
if(it==las){
fo(j,i,n){
dp[j]=(dp[j]+dp[j-1]);
dp[j]=dp[j]>=mod?dp[j]-mod:dp[j];
}
break;
}
}
}
it=max(it,i+1);
dp[i]=(dp[i]+dp[i-1]);
dp[i]=dp[i]>=mod?dp[i]-mod:dp[i];
dp[it]=(dp[it]+dp[i]);
dp[it]=dp[it]>=mod?dp[it]-mod:dp[it];
}
printf("%d\n",dp[n]);
}
return 0;
}
T3 超级加倍
确实学过单调栈和笛卡尔树在序列上的应用
考场上可以想到将笛卡尔树应用到树上，但是我不会用啊
原来是\(Kruskal\)重构树，我学到了
所以建一个小的，建一个大的，互相是祖先就直接用树状数组判断就好了
AC_code
#include<bits/stdc++.h>
using namespace std;
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=2e6+5;
int n,fa[N];long long ans;
int too[N*2],nt[N*2],hd[N],rp;
void add_edg(int x,int y){
too[++rp]=y;
nt[rp]=hd[x];
hd[x]=rp;
}
struct kcgs{
int to[N],nxt[N],head[N],rp;
int fai[N],pot[N];
int find(int x){return fai[x]==x?x:fai[x]=find(fai[x]);}
void add(int x,int y){
to[++rp]=y;
nxt[rp]=head[x];
head[x]=rp;
}
void rebuild1(){
fo(i,1,n)fai[i]=i;
fo(i,1,n){
int x=pot[i];
for(int j=hd[x];j;j=nt[j]){
int y=too[j];
if(y>x)continue;
int fx=find(x),fy=find(y);
if(fx==fy)continue;
fai[fy]=fx;add(fx,fy);
}
}
}
void rebuild2(){
fo(i,1,n)fai[i]=i;
fo(i,1,n){
int x=pot[i];
for(int j=hd[x];j;j=nt[j]){
int y=too[j];
if(y<x)continue;
int fx=find(x),fy=find(y);
if(fx==fy)continue;
fai[fy]=fx;add(fx,fy);
}
}
}
}t1,t2;
int dfn[N],cnt,dfm[N];
void dfs_t1(int x){
dfn[x]=++cnt;
for(int i=t1.head[x];i;i=t1.nxt[i]){
int y=t1.to[i];
dfs_t1(y);
}
dfm[x]=cnt;
}
int tr[N];
void ins(int x,int v){
for(int i=x;i<=n;i+=(i&-i))
tr[i]+=v;
}
int query(int x){
int ret=0;
for(int i=x;i;i-=(i&-i))
ret+=tr[i];
return ret;
}
void dfs_t2(int x){
// cerr<<x<<" "<<dfn[x]<<" "<<dfm[x]<<" "<<query(dfm[x])<<" "<<query(dfn[x]-1)<<endl;
ans+=query(dfm[x])-query(dfn[x]-1);
ins(dfn[x],1);
for(int i=t2.head[x];i;i=t2.nxt[i]){
int y=t2.to[i];
dfs_t2(y);
}
ins(dfn[x],-1);
}
signed main(){
freopen("charity.in","r",stdin);
freopen("charity.out","w",stdout);
scanf("%d",&n);
fo(i,1,n){
scanf("%d",&fa[i]);
if(i==1)continue;
add_edg(fa[i],i);
add_edg(i,fa[i]);
}
fo(i,1,n)t1.pot[i]=i;t1.rebuild1();
fo(i,1,n)t2.pot[i]=n+1-i;t2.rebuild2();
dfs_t1(n);dfs_t2(1);
printf("%lld",ans);
}
T4 欢乐豆
更改的边很少，考虑导出子图
边数很少，我们可以用线段树模拟\(dijstra\)
我想了想，这线段树是依赖边数的，无法直接替换原本的\(dijstra\)
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e5+5;
const int M=3e3+5;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,a[N],ans;
vector<pair<int,int> > e[N];
struct DSU{
int fa[N],siz[N];
void init(){fo(i,1,n)fa[i]=i,siz[i]=1;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
fa[fx]=fy;siz[fy]+=siz[fx];
}
}dsu;
int ltkcnt,which[N];
vector<int> ltk[N];
multiset<int> st;
int pos_in_xds[N],xds_siz;
int dis[N];
struct XDS{
#define ls x<<1
#define rs x<<1|1
int val[M*4],who[M*4],tag[M*4];
bool bji[M*4];
void pushup(int x){
val[x]=min(val[ls],val[rs]);
if(val[x]==val[ls]&&!bji[ls])who[x]=who[ls];
else who[x]=who[rs];
bji[x]=bji[ls]&bji[rs];
}
void pushdown(int x){
if(!bji[ls])val[ls]=min(val[ls],tag[x]),tag[ls]=min(tag[ls],tag[x]);
if(!bji[rs])val[rs]=min(val[rs],tag[x]),tag[rs]=min(tag[rs],tag[x]);
tag[x]=inf;return ;
}
void build(int x,int l,int r){
tag[x]=inf;bji[x]=0;
if(l==r)return who[x]=l,val[x]=inf,void();
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
pushup(x);return ;
}
void huimieba(int x,int l,int r,int pos){
if(l==r)return bji[x]=true,val[x]=inf,void();
if(tag[x]!=inf)pushdown(x);
int mid=l+r>>1;
if(pos<=mid)huimieba(ls,l,mid,pos);
else huimieba(rs,mid+1,r,pos);
pushup(x);return ;
}
void ins(int x,int l,int r,int ql,int qr,int v){
if(ql>qr)return ;
if(bji[x])return ;
if(ql<=l&&r<=qr){
tag[x]=min(tag[x],v);
val[x]=min(val[x],v);
return ;
}
if(tag[x]!=inf)pushdown(x);
int mid=l+r>>1;
if(ql<=mid)ins(ls,l,mid,ql,qr,v);
if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
pushup(x);return ;
}
#undef ls
#undef rs
}xds;
signed main(){
freopen("happybean.in","r",stdin);
freopen("happybean.out","w",stdout);
scanf("%lld%lld",&n,&m);
fo(i,1,n)scanf("%lld",&a[i]),st.insert(a[i]);
dsu.init();
fo(i,1,m){
int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
e[x].push_back(make_pair(y,z));dsu.merge(x,y);
}
fo(i,1,n)sort(e[i].begin(),e[i].end());
fo(i,1,n){
if(dsu.siz[dsu.find(i)]==1)continue;
if(dsu.fa[i]==i)which[i]=++ltkcnt;
}
fo(i,1,n){
if(dsu.siz[dsu.find(i)]==1){
ans+=(n-1)*a[i];
continue;
}
ltk[which[dsu.find(i)]].push_back(i);
}
fo(i,1,ltkcnt){
for(int x:ltk[i])st.erase(a[x]);
int minn=*st.begin();
if(st.begin()==st.end())minn=inf;
xds_siz=ltk[i].size();
fo(j,0,xds_siz-1)pos_in_xds[ltk[i][j]]=j+1;
for(int u:ltk[i]){
xds.build(1,1,xds_siz);
xds.ins(1,1,xds_siz,pos_in_xds[u],pos_in_xds[u],0);
dis[pos_in_xds[u]]=0;
while(xds.val[1]!=inf){
int x=xds.who[1];
dis[x]=xds.val[1];
xds.huimieba(1,1,xds_siz,x);
int bas=dis[x],las=1;
x=ltk[i][x-1];
for(auto j:e[x]){
xds.ins(1,1,xds_siz,las,pos_in_xds[j.first]-1,bas+a[x]);
xds.ins(1,1,xds_siz,pos_in_xds[j.first],pos_in_xds[j.first],bas+j.second);
las=pos_in_xds[j.first]+1;
}
xds.ins(1,1,xds_siz,las,xds_siz,bas+a[x]);
}
fo(j,1,xds_siz)ans+=min(dis[j],a[u]+minn);
int mn=inf;
fo(j,1,xds_siz)mn=min(mn,dis[j]+a[ltk[i][j-1]]);
ans+=mn*(n-xds_siz);
}
for(int x:ltk[i])st.insert(a[x]);
}
printf("%lld",ans);
}