10.13 正睿做题笔记

T1

大模拟,直接 \(9!\) 枚举然后 \(8\) 倍常数建边,然后在这张图上直接跑 bfs,我们可以首先打表出来可能的最终状态,然后一经过最终态的时候。就停止即可。

代码:

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 4000010
#define M 20
using namespace std;

const int INF=0x3f3f3f3f;
const int mod=2908361;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Min(T a,T b){return a<b?a:b;}

// int table[9][10]={
//     {0,0,0,0,0,0,0,0,0,0},
//     {0,2,7,6,9,5,1,4,3,8},
//     {0,2,9,4,7,5,3,6,1,8},
//     {0,4,3,8,9,5,1,2,7,6},
//     {0,4,9,2,3,5,7,8,1,6},
//     {0,6,1,8,7,5,3,2,9,4},
//     {0,6,7,2,1,5,9,8,3,4},
//     {0,8,1,6,3,5,7,4,9,2},
//     {0,8,3,4,1,5,9,6,7,2}
// };

int t[9]={0,276951438,294753618,438951276,492357816,618753294,672159834,816357492,834159672};
int ta[9];

struct edge{
    int to,next;
    inline void Init(int to_,int ne_){
        to=to_;next=ne_;
    }
}li[N*10];
int head[N],tail;

inline void Add(int from,int to){
    li[++tail].Init(to,head[from]);
    head[from]=tail;
}

struct Hash{
    int head[N],li[N],tot,val[N];
    inline void Insert(int v){
        int ha=v%mod;
        for(int x=head[ha];x;x=li[x]);
        val[++tot]=v;li[tot]=head[ha];head[ha]=tot;
        // printf("v=%d tot=%d\n",v,tot);
    }
    inline int Find(int v){
        int now=v%mod;
        for(int x=head[now];x;x=li[x]){
            // printf("x=%d\n",x);
            if(val[x]==v) return x;
        }
        return -1;
    }
}h;

int a[M],b[N],bt,TenPow[N],T;

inline void PreWork(){
    for(int i=1;i<=9;i++) a[i]=i;
    for(int i=1;i<=362880-1;i++){
        int val=0;
        for(int j=1;j<=9;j++){val*=10;val+=a[j];}
        h.Insert(val);b[++bt]=val;
        next_permutation(a+1,a+9+1);
    }
    int val=0;
    for(int j=1;j<=9;j++){val*=10;val+=a[j];}
    h.Insert(val);b[++bt]=val;
    TenPow[0]=1;
    for(int i=1;i<=9;i++) TenPow[i]=TenPow[i-1]*10;
    for(int i=1;i<=8;i++) ta[i]=h.Find(t[i]);
    // for(int i=1;i<=8;i++){
    //     printf("i=%d ta[i]=%d\n",i,ta[i]);
    // }
}

inline int Get(int x,int i,int j){
    if(i<j) swap(i,j);
    int p1=x/TenPow[i];
    int p2=(x%TenPow[i])/TenPow[i-1];
    int p3=(x%TenPow[i-1])/TenPow[j];
    int p4=(x%TenPow[j])/TenPow[j-1];
    int p5=x%TenPow[j-1];
    // printf("%d %d %d %d %d\n",p1,p2,p3,p4,p5);
    swap(p2,p4);
    return p1*TenPow[i]+p2*TenPow[i-1]+p3*TenPow[j]+p4*TenPow[j-1]+p5;
}

inline void Build(){
    for(int i=1;i<=bt;i++){
        // assert(h.Find(b[i])!=-1);
        // if(h.Find(Get(b[i],9,8))==-1){
        //     printf("b[i]=%d get=%d\n",b[i],Get(b[i],9,8));
        // }
        // assert(h.Find(Get(b[i],9,8))!=-1);
        Add(h.Find(b[i]),h.Find(Get(b[i],9,8)));
        Add(h.Find(b[i]),h.Find(Get(b[i],9,6)));
        Add(h.Find(b[i]),h.Find(Get(b[i],8,5)));
        Add(h.Find(b[i]),h.Find(Get(b[i],8,7)));
        Add(h.Find(b[i]),h.Find(Get(b[i],6,3)));
        Add(h.Find(b[i]),h.Find(Get(b[i],6,5)));
        Add(h.Find(b[i]),h.Find(Get(b[i],5,2)));
        Add(h.Find(b[i]),h.Find(Get(b[i],5,4)));
        Add(h.Find(b[i]),h.Find(Get(b[i],7,4)));
        Add(h.Find(b[i]),h.Find(Get(b[i],4,1)));
        Add(h.Find(b[i]),h.Find(Get(b[i],3,2)));
        Add(h.Find(b[i]),h.Find(Get(b[i],2,1)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],8,9)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],6,9)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],5,8)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],7,8)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],3,6)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],5,6)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],2,5)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],4,5)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],4,7)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],1,4)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],2,3)));
        // Add(h.Find(b[i]),h.Find(Get(b[i],1,2)));
    }
}

int d[N];
queue<int> q;
bool vis[N];
inline int bfs(int s){
    for(int i=1;i<=400000;i++) vis[i]=0;
    while(q.size()) q.pop();
    d[s]=0;q.push(s);vis[s]=1;
    while(q.size()){
        int top=q.front();q.pop();
        // printf("val=%d\n",h.val[top]);
        for(int i=1;i<=8;i++) if(top==ta[i]){
            // printf("top=%d\n",top);
            return d[top];
        }
        for(int x=head[top];x;x=li[x].next){
            int to=li[x].to;
            // printf("id=%d to=%d\n",to,h.val[to]);
            if(vis[to]) continue;
            vis[to]=1;q.push(to);
            d[to]=d[top]+1;
        }
    }
    return -1;
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    PreWork();
    // printf("here\n");
    Build();
    // printf("here\n");
    read(T);
    while(T--){
        int val=0;
        for(int i=1;i<=9;i++){
            read(a[i]);val*=10;val+=a[i];
        }
        // printf("here\n");
        int id=h.Find(val);
        // printf("val=%d\n",val);
        // printf("id=%d\n",id);
        printf("%d\n",bfs(id));
    }
    return 0;
}

T2

比较巧妙地一个想法,说明我的思维量还是不够。

首先异或可以用 01Trie 来做,然后我们考虑如何维护和和或。一下我们考虑或,和同理。

假设我们有一个数组 \(mark_i\) 表示 \(i\) 在二进制下,在当前集合中是否存在一个数的二进制包含 \(i\)。

然后我们从大到小枚举当前数 \(x\) 的每一位,如果为 \(1\) 那么我们不管他,如果为 \(0\),我们考虑令 \(cur\) 与 \(x\) 当前的最优解,我们看 \(mark_{cur|1<<j}\) (设当前到了第 \(j\) 位)是否为 \(1\),如果是,那么我们就可以更新,否则不行。

所以我们只需要维护 \(mark\) 就可以了,容易发现维护的总复杂度可以做到 \(2^{20}\),这是因为如果一个数为 \(1\),那么其子集一定为 \(1\)。

代码:

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 30000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Max(T a,T b){return a<b?b:a;}

struct Trie{
    int ch[N][2],tot;
    inline void Insert(int x){
        int p=0;
        for(int i=20;i>=0;i--){
            int digit=(x>>i)&1;
            if(!ch[p][digit]) ch[p][digit]=++tot;
            p=ch[p][digit];
        }
    }
    inline int Query1(int x){
        int p=0,maxx=0;
        for(int i=20;i>=0;i--){
            int digit=(x>>i)&1;
            if(ch[p][digit^1]){p=ch[p][digit^1];maxx+=(1<<i);}
            else p=ch[p][digit];
        }
        return maxx;
    }
}tr;

int q;
bool vis[N];

inline int Digit(int x){
    int cnt=0;for(;x;x&=(x-1)) cnt++;
    return cnt;
}

inline int lowbit(int x){return x&(-x);}

inline void dfs(int x,int w){
    int now=x;
    for(int i=1;i<=w;i++){
        int val=lowbit(now);now-=val;
        int nowx=x^val;
        if(vis[nowx]) continue;
        vis[nowx]=1;
        dfs(nowx,w-1);
    }
}

inline void Signed(int x){
    // printf("x=%d\n",x);
    if(vis[x]) return;vis[x]=1;
    dfs(x,Digit(x));
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(q);
    for(int i=1;i<=q;i++){
        int op,a;read(op);read(a);
        if(op==1){
            tr.Insert(a);Signed(a);
        }
        else if(op==2){
            int ans1=0,ans2=0,ans3=tr.Query1(a);
            for(int i=20;i>=0;i--){
                if(((a>>i)&1)==0) continue;
                else{
                    if(vis[ans1|(1<<i)]){
                        ans1|=(1<<i);
                    }
                }
            }
            ans1&=a;
            for(int i=20;i>=0;i--){
                if((a>>i)&1) continue;
                else{
                    if(vis[ans2|(1<<i)]){
                        ans2|=(1<<i);
                    }
                }
            }
            // printf("ans2=%d\n",ans2);
            ans2|=a;
            printf("%d %d %d\n",ans3,ans1,ans2);
        }
        else if(op==3){
            printf("%d\n",tr.Query1(a));
        }
    }
}
/*
1026909 201744 1032061
879724 984162 1048062
655316 682376 1043962
649621 683464 1048571
926039 85160 1011199
*/

T3

这个题其实比较简单,考试的时候快要想出来了,但是因为时间不够还是作罢,下次要加快打程序的速度,一定要细心。首先考虑如果只是一棵树,其根节点为黑色,可以通过简单的树形 dp 来做,两个节点为黑色的话我们不妨可以二分两个黑点之间的路径,把整颗树分为两颗树来做,容易发现答案的单调性,我们可以首先找到满足 \(f_a\le f_b\) 且 \(f_a\) 最大的 \(mid\),然后考虑 \(mid,mid+1\) 两个答案。

注意边界与细节,以及 \(ans\) 的初始值。

代码:

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 300010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Max(T a,T b){return a<b?b:a;}
template<typename T> inline T Min(T a,T b){return a<b?a:b;}

struct edge{
    int to,next,from;
    inline void Init(int fr_,int to_,int ne_){
        to=to_;next=ne_;from=fr_;
    }
}li[N<<1];
int head[N],tail=1;

inline void Add(int from,int to){
    li[++tail].Init(from,to,head[from]);
    head[from]=tail;
}

int a,b,n,Pre[N],Pass[N],ct,tag,f[N],g[N],gt;
bool op=1;

typedef pair<int,int> P;

inline void Init(){
    read(n);read(a);read(b);
    for(int i=1;i<=n-1;i++){
        int from,to;read(from);read(to);
        Add(from,to);Add(to,from);
    }
}

inline void dfs(int k,int fa){
    if(k==b){op=0;return;}
    for(int x=head[k];x&&op;x=li[x].next){
        int to=li[x].to;
        if(to==fa) continue;
        Pre[to]=x;
        dfs(to,k);
    }
}

inline void Connect(){
    dfs(a,0);int now=b;
    while(li[Pre[now]].from!=a){Pass[++ct]=Pre[now];now=li[Pre[now]].from;}
    Pass[++ct]=Pre[now];reverse(Pass+1,Pass+1+ct);
}

inline bool Check(P a){
    if(a.first<=a.second) return 1;
    else return 0;
}

inline bool cmp(int a,int b){return a>b;}

inline void Dp(int k,int fa){
    f[k]=0;
    for(int x=head[k];x;x=li[x].next){
        if(x==tag||x==(tag^1)) continue;
        int to=li[x].to;
        if(to==fa) continue;
        Dp(to,k);
    }
    gt=0;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to;if(to==fa||x==tag||x==(tag^1)) continue;
        g[++gt]=f[to];
    }
    if(!gt) return;
    sort(g+1,g+gt+1,cmp);
    for(int i=1;i<=gt;i++){
        f[k]=Max(f[k],g[i]+i);
    }
}

inline P Solve(int mid){
    tag=Pass[mid];Dp(a,0);Dp(b,0);
    return make_pair(f[a],f[b]);
}

inline int Binary(){
    int l=1,r=ct,ans=l;
    while(l<=r){
        int mid=(l+r)>>1;
        if(Check(Solve(mid))){l=mid+1;ans=mid;}
        else r=mid-1;
    }
    // printf("ans=%d\n",ans);
    P ans1=Solve(ans),ans2=make_pair(-INF,INF);
    if(ans+1<=ct) ans2=Solve(ans+1);
    return Min(Max(ans1.first,ans1.second),Max(ans2.first,ans2.second));
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Connect();
    printf("%d\n",Binary());
    return 0;
}

T4

调了蛮久的,但其实没有想象中的那么难。

首先考虑把询问离线,然后按照电压排序,这样每次的连通块只会变大不会变小,但每次找新的点还是一个比较难实现的事情,怎么办?

我们考虑把节点按照电压排序,这样我们枚举点,然后把电压小于其电压的询问回答掉,然后再把这个点插入连通块,就可以完成上面的事情。

具体来说,我们用并查集维护连通块,用权值线段树来维护每个连通块的 \(b\) 值出现次数,每次我们把节点编号往前推移,像上面所说的那样回答询问,然后枚举其所有连边,合并连通块,注意我们可以以并查集是否初始化来判断某个点是否被激活。回答询问的时候要注意,我们首先维护一个 \(multiset\) ,然后去掉包含坏节点的连通块,回答询问,然后再把连通块插入回去即可。

代码:

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
//l+r 可能会超LongLong
#define uint unsigned int
#define ull unsigned long long
#define M 800010
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

vector<int> e[M];

struct Node{
    int a,b,id;
    inline Node(){}
    inline Node(int a,int b,int id) : a(a),b(b),id(id) {}
    inline bool operator < (const Node &b)const{return a<b.a;}
}p[M];

struct Ques{
    int V,p,id;vector<int> s;
    inline bool operator < (const Ques &b)const{return V<b.V;}
}ques[M];

int n,m,K,Q;
int fa[M],tot,limit=(1ll<<31)-1,ans[M],cnt[M<<5],sum[M<<5];;
multiset<int> S;
bool vis[M];

inline int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}

ll root[M],ls[M<<5],rs[M<<5];

inline int NewNode(){return ++tot;}
inline void PushUp(int k){sum[k]=sum[ls[k]]+sum[rs[k]];}

inline void Add(ll &k,int l,int r,int w,int x){
    if(!k) k=++tot;
    if(l==r){
        sum[k]=(((cnt[k]+=x)%=K)==0);
        return;
    }
    int mid=(l+r)>>1;
    if(w<=mid) Add(ls[k],l,mid,w,x);
    else Add(rs[k],mid+1,r,w,x);PushUp(k);
}

inline void Merge(ll &x,int y,int l,int r){
    if(!x||!y){x|=y;return;}
    if(l==r){
        sum[x]=(((cnt[x]+=cnt[y])%=K)==0);
        return;
    }
    int mid=(l+r)>>1;
    Merge(ls[x],ls[y],l,mid);Merge(rs[x],rs[y],mid+1,r);
    PushUp(x);
}

inline void Init(){
    read(n);read(m);read(K);
    for(int i=1;i<=n;i++){read(p[i].a);p[i].id=i;}
    for(int i=1;i<=n;i++) read(p[i].b);
    for(int i=1;i<=m;i++){
        int from,to;read(from);read(to);
        e[from].push_back(to);e[to].push_back(from);
    }
    read(Q);
    for(int i=1;i<=Q;i++){
        read(ques[i].V);read(ques[i].p);ques[i].id=i;
        for(int j=1;j<=ques[i].p;j++){int x;read(x);ques[i].s.push_back(x);}
    }
    sort(ques+1,ques+Q+1);sort(p+1,p+n+1);
    // printf("Complete Initing.\n");
}

inline void Solve(){
    for(int i=1,j=1;i<=n+1;i++){
        // printf("i=%d\n",i);
        int now=-1;
        while(j<=Q&&(i==n+1||p[i].a>ques[j].V)){
            for(int k:ques[j].s)
                if(fa[k]&&!vis[now=Find(k)]) S.erase(S.find(-sum[root[now]])),vis[now]=1;
            ans[ques[j].id]=-*S.begin();
            for(int k:ques[j].s)
                if(fa[k]&&vis[now=Find(k)]) S.insert(-sum[root[now]]),vis[now]=0;
            j++;
        }
        if(i==n+1) break;
        int id=p[i].id;fa[id]=id;
        Add(root[id],1,limit,p[i].b,1);S.insert(-sum[root[id]]);
        for(int to:e[id]){
            if(!fa[to]) continue;
            int u=Find(id),v=Find(to);if(u==v) continue;
            S.erase(S.find(-sum[root[u]]));S.erase(S.find(-sum[root[v]]));
            fa[v]=u;
            Merge(root[u],root[v],1,limit);
            S.insert(-sum[root[u]]);
        }
    }
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();
    Solve();
    return 0;
}
/*
5 4 2
3 7 2 5 4
1 3 3 2 2
1 3
1 2
1 4
1 5
5
4 0
4 1 3
1 0
5 0
10 0
*/
上一篇:NOIp-75


下一篇:macOS软件安装常见问题