今天考的不是联考的试题，而是ZZ_zuozhe的题，题目质量好高！！！
第一题，想到了用bitset做，然后发现枚举的有用的只有是1的位，于是想到用set，但是复杂度瓶颈在于转移时的赋值操作，没想到可以用主席树
第二题，妈呀想着是阶乘然后就写成没阶乘了......
第三题，写了个背包，于是只有35分
T1 最短路
发现增加一条路就是将一段连续的1变成0,前面加个1,可以用线段树二分
转移就是直接赋值，这里用dij的时候，用set当堆，这样比较函数比较好写参数可以改
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--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*t;
}
const int N=1e5+5;
const int M=2e5+1e3;
const int mod=1e9+7;
int ksm(int x,int y){
int ret=1;
while(y){
if(y&1)ret=1ll*ret*x%mod;
x=1ll*x*x%mod;y>>=1;
}return ret;
}
int mo(int x){return x>=mod?x-mod:x;}
int fro[M];int all(int l,int r){if(l==0)return fro[r];return mo(fro[r]-fro[l-1]+mod);}
struct ZXS{
struct POT{int ls,rs,sum;}tr[M*100];
int seg;
int newpot(int x){tr[++seg]=tr[x];return seg;}
void pushup(int x){
//if(!tr[x].ls&&!tr[x].rs)return ;
tr[x].sum=mo(tr[tr[x].ls].sum+tr[tr[x].rs].sum);
}
void ins(int &x,int px,int l,int r,int ql,int qr,int v){
x=newpot(px);if(ql>qr)return ;
if(ql<=l&&r<=qr){
tr[x].ls=tr[x].rs=0;
if(v)tr[x].sum=all(l,r);
else tr[x].sum=0;
return ;
}
int mid=l+r>>1;
if(ql<=mid)ins(tr[x].ls,tr[px].ls,l,mid,ql,qr,v);
if(qr>mid)ins(tr[x].rs,tr[px].rs,mid+1,r,ql,qr,v);
pushup(x);return ;
}
int query_mxlen(int x,int l,int r,int ql){
if(ql<=l){
if(tr[x].sum==all(l,r))return r;
if(l==r||!tr[x].sum)return l-1;
int mid=l+r>>1;
if(tr[tr[x].ls].sum==all(l,mid))return query_mxlen(tr[x].rs,mid+1,r,ql);
else return query_mxlen(tr[x].ls,l,mid,ql);
}
if(tr[x].sum==all(l,r))return r;
if(!tr[x].sum)return ql-1;
int mid=l+r>>1,ret=0;
if(ql<=mid)ret=query_mxlen(tr[x].ls,l,mid,ql);
if(ret==mid||ql>mid)return query_mxlen(tr[x].rs,mid+1,r,ql);
else return ret;
}
bool comp(int x,int y,int l,int r){//x<y true
if(tr[x].sum==tr[y].sum)return false;
if(tr[x].sum==all(l,r))return false;
if(!tr[x].sum)return true;
if(tr[y].sum==all(l,r))return true;
if(!tr[y].sum)return false;
if(l==r)return tr[x].sum<tr[y].sum;
int mid=l+r>>1;
if(tr[tr[x].rs].sum==tr[tr[y].rs].sum)return comp(tr[x].ls,tr[y].ls,l,mid);
else return comp(tr[x].rs,tr[y].rs,mid+1,r);
}
}zxs;
int rt[N];
int n,m,R=2e5+20,s,t;
bool vis[N],ist[N];
struct node{
int x;
bool operator < (node a)const{
if(zxs.tr[rt[x]].sum==zxs.tr[rt[a.x]].sum)return x<a.x;
return zxs.comp(rt[x],rt[a.x],1,R);
}
};
set<node> st;
struct E{int to,nxt,val;}e[M*2];
int head[N],rp;
void add_edg(int x,int y,int z){
e[++rp].to=y;e[rp].nxt=head[x];
e[rp].val=z;head[x]=rp;
}
signed main(){
freopen("hellagur.in","r",stdin);
freopen("hellagur.out","w",stdout);
n=read();m=read();
fro[0]=1;fo(i,1,R)fro[i]=(fro[i-1]+ksm(2,i))%mod;
fo(i,1,m){
int x=read(),y=read(),z=read();
add_edg(x,y,z);add_edg(y,x,z);
//if(z==0)cerr<<"SB"<<endl;
}
s=read();t=read();rt[s]=++zxs.seg;
fo(i,1,n)if(i!=s)zxs.ins(rt[i],rt[s],1,R,1,R,1);
st.insert(node{s});ist[s]=true;
while(st.size()){
int x=st.begin()->x;st.erase(st.begin());
if(vis[x])continue;
vis[x]=true;ist[x]=false;
for(int i=head[x];i;i=e[i].nxt){
int y=e[i].to,tmp,r,l=e[i].val;
if(vis[y])continue;
r=zxs.query_mxlen(rt[x],1,R,l);
zxs.ins(tmp,rt[x],1,R,l,r,0);
zxs.ins(tmp,tmp,1,R,r+1,r+1,1);
if(zxs.comp(tmp,rt[y],1,R)){
if(ist[y])st.erase(node{y});
ist[y]=true;rt[y]=tmp;
st.insert(node{y});
}
}
}
if(zxs.tr[rt[t]].sum==all(1,R))printf("-1");
else printf("%d",zxs.tr[rt[t]].sum);
}
T2 集合
发现有可能的大小是n,n-1,n-2
奇数的话，还有n-3,用异或hash表示
AC_code
#include<bits/stdc++.h>
using namespace std;
#define ll 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--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*t;
}
const ll inf=1e18;
random_device pyt;
mt19937 you(pyt());
ll rd(ll l,ll r){
return rand()%inf;
uniform_int_distribution<> ee(l,r);
return ee(you)*ee(you);
}
const int N=1e6+5;
int n;
unordered_map<ll,int> mp;
ll vl[100005],val[N],tmp;
int p[100005],cnt,mn[N];
bool vis[N];
void init_p(){
fo(i,2,n){
if(!vis[i]){
p[++cnt]=i;
vl[cnt]=rd(1,inf);
mn[i]=cnt;
}
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=true;mn[i*p[j]]=j;
if(i%p[j]==0)break;
}
}
}
int ck2(int n){tmp=0;
fo(i,1,n)tmp^=val[i];
fo(i,1,n)if(mp.find(tmp^val[i])!=mp.end()&&mp[tmp^val[i]]!=i)return i;
return false;
}
int ck1(int n){tmp=0;
fo(i,1,n)tmp^=val[i];
fo(i,1,n)if((tmp^val[i])==0)return i;
return false;
}
bool ck0(int n){tmp=0;
fo(i,1,n)tmp^=val[i];
return !tmp;
}
signed main(){
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
n=read();int res;srand(time(0));
init_p();
fo(i,1,n){int now=i;ll hs=0;
while(now!=1)hs^=vl[mn[now]],now/=p[mn[now]];
val[i]=val[i-1]^hs;mp[val[i]]=i;
}
if(n&1)n--;
if(ck0(n)){
printf("%d\n",n);
fo(i,1,n)printf("%d ",i);
return 0;
}
if(res=ck1(n)){
printf("%d\n",n-1);
fo(i,1,n)if(i!=res)printf("%d ",i);
return 0;
}
if(res=ck2(n)){
printf("%d\n",n-2);int sm=0;
fo(i,1,n)if(i!=res&&i!=mp[tmp^val[res]])printf("%d ",i);
return 0;
}
mp.erase(val[n--]);res=ck2(n);
printf("%d\n",n-2);//mp.erase(val[n]);
fo(i,1,n)if(i!=res&&i!=mp[tmp^val[res]])printf("%d ",i);
return 0;
}
T3 食材
这个不可改，根本看不懂题解诶......