10.14 正睿做题笔记

10.14 正睿做题笔记

连续两场掉分，心情非常不爽。

T1

水题，直接拿 bitset 优化转移就可以过掉这道题。

代码：

#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 26
#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;
}

bitset<25> bit[N];

int n,m,f[1<<N],cnt[N*N+100];

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

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    // dd d1=clock();
    read(n);read(m);
    for(int i=1;i<=m;i++){
        int from,to;read(from);read(to);
        from--;to--;
        bit[from][to]=1;bit[to][from]=1;
    }
    int maxx=(1<<n)-1;
    for(int s=1;s<=(1<<n)-1;s++){
        int now=Lowbit(s);
        int t=s-now;
        int w=log2(now);
        bitset<25> nowt(t);
        nowt&=bit[w];
        f[s]=f[t]+nowt.count();
        assert(f[s]<=m);
        cnt[f[s]]++;
    }
    cnt[f[0]]++;
    for(int i=0;i<=m;i++) printf("%d ",cnt[i]);puts("");
    // dd d2=clock();
    // printf("%lf
",d2-d1);
    return 0;
}

T2

有一定技巧性，属于那种没见过做不出来的题。真的非常巧妙。

首先是一个莫比乌斯反演转化，利用莫比乌斯反演，每个询问可以做成这样：(sum_{d|x}mu(d)sum_{i=l}^r[d|a_i])。

我们考虑维护后面这个东西，不难发现可以把询问分成两块，这样我们所有的询问都变成了这样：(sum_{d|x}mu(d)sum_{i=1}^r[d|a_i])。

然后我们考虑做上面这个东西。首先我们可以把询问离线下来，然后按照 (r) 排序。

然后我们用双指针去做这个东西，当可以回答询问的时候，我们就回答询问。然后没遇到一个 (a) 或者是查询一个 (x)，我们用 (sqrt n) 的时间复杂度去枚举其因数。这样总复杂度可以做到 (O(n sqrt n))。

代码：

#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 100010
#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;}

int Prime[N],tail,Mu[N],n,a[N],Q,qcnt,ans[N],c[N];
bool NotPrime[N];

struct Ques{
    int r,x,type,id;
    inline Ques(){}
    inline Ques(int r,int x,int type,int id) : r(r),x(x),type(type),id(id) {}
    inline bool operator < (const Ques &b)const{return r<b.r;}
}ques[N<<1];

inline void GetMu(int n){
    NotPrime[1]=1;Mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!NotPrime[i]) Prime[++tail]=i,Mu[i]=-1;
        for(int j=1;j<=tail&&Prime[j]*i<=n;j++){
            NotPrime[i*Prime[j]]=1;
            if(i%Prime[j]==0) break;
            else Mu[i*Prime[j]]=-Mu[i];
        }
    }
}

inline void Init(){
    read(n);read(Q);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=Q;i++){
        int l,r,x;read(l);read(r);read(x);
        if(l-1>0) ques[++qcnt]=Ques(l-1,x,-1,i);
        ques[++qcnt]=Ques(r,x,1,i);
    }
    sort(ques+1,ques+qcnt+1);
}

inline void Insert(int x){
    int i;for(i=1;i*i<x;i++) if(x%i==0){c[i]++;c[x/i]++;}if(i*i==x) c[i]++;
}

inline int Query(int x){
    int i,nowans=0;
    for(i=1;i*i<x;i++) if(x%i==0){nowans+=Mu[i]*c[i];nowans+=Mu[x/i]*c[x/i];}if(i*i==x) nowans+=Mu[i]*c[i];
    return nowans;
}

inline void Solve(){
    for(int i=1,j=0;i<=n;i++){
        Insert(a[i]);
        while(j+1<=qcnt&&ques[j+1].r<=i){j++;ans[ques[j].id]+=Query(ques[j].x)*ques[j].type;}
    }
    for(int i=1;i<=Q;i++) printf("%d
",ans[i]);
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    GetMu(100000);
    Init();Solve();
}

T3

这个题已经把暴力想出来了，但是放弃了进一步优化，这是我的问题，当时在 BC 之间抉择的时候，应该优先选择优化 dp 的。这样起码还有些盼头。

暴力 dp 很好想，设 (f_{l,r,k}) 表示区间 (l,r) 内 (k) 是否有可能赢。那么我们在左边枚举一个能够被 (k) 打败的数 (a)，右边枚举一个能被 (k) 打败的数 (b)，然后转移就可以。

稍微想一下可以枚举到 (n^4)，就是我们关注的是左边有没有，右边有没有，所以不用枚举数对。

然后我们考虑如何优化到 (n^3)，考虑第 (3) 维实际上并没有什么用处，这是因为：(f_{l,r,k}=f_{l,k,k}and f_{k,r,k})。然后我们直接可以省掉第 (3) 维，把 dp 变成 (f_{l,r,0/1}) 其中 (0) 表示原来的 (f_{l,r,l}) ，(1) 表示原来的 (f_{l,r,r})。

因为 dp 值为 bool，所以我们考虑用 bitset 优化，具体来说，就是用 bit1[l] 来存 (f_{l,k,0})，用 bit2[r] 来存 (f_{k,r,1})，然后因为需要保证能够打败，所以我们转移的时候在 and 上一个 beat[k] 表示能被 (k) 打败的集合即可。

注意我们最好做完一阶段 dp，在去更新两个帮助转移的 bitset。

代码：

#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 2010
#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;
}

bitset<N> bit1[N],bit2[N],Beat[N];
int f[N][N][2],n;
char s[N];

inline void Init(){
    read(n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++) if(s[j]=='1') Beat[i][j]=1;
    }   
}

inline void Dp(){
    for(int i=1;i<=n;i++){
        f[i][i][0]=f[i][i][1]=1;
        bit1[i][i]=bit2[i][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            int l=j,r=j+i-1;
            f[l][r][0]=(Beat[l]&bit1[l+1]&bit2[r]).any();
            f[l][r][1]=(Beat[r]&bit1[l]&bit2[r-1]).any();
            // printf("f[%d][%d][0]=%d f[%d][%d][1]=%d
",l,r,f[l][r][0],l,r,f[l][r][1]);
        }
        for(int j=1;j<=n-i+1;j++){
            int l=j,r=j+i-1;
            if(f[l][r][0]) bit2[r][l]=1;
            if(f[l][r][1]) bit1[l][r]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(f[1][i][1]&&f[i][n][0]) printf("%d ",i);
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Dp();
    return 0;
}

T4

非常巧妙的一个转化。首先我们考虑这个题并不是简单的，边不在树边上，我们就可以随便走的题目，这是因为我们题目中的主人公不具有预见性，这个题目实际上是一个博弈模型，想像和你做博弈的人，每当你走到一个点时，就会考虑是否删掉相邻的一个边，且其删边的机会只有一次，他的目标是把你的路径权值和最大化，你的目标是最小化权值和。

以下设 (s) 为最短路树根节点。

我们考虑设 (val_i) 表示在最短路树上去掉 (i) 与其父亲的边之后走到根的最短路。(f_i) 表示节点 (i) 的答案，那么我们考虑如何计算。

显然，如果对手打算在我们走到这个节点的时候删边，那么其一定删最短路上与 (i) 相连的父边，这样答案就是 (val_i)，否则，我们可以走到某个节点 (j)，然后这个时候状态变成了 (f_j)，所以我们有转移 (f_i=max(val_i,minlimits_{(j,i)in E}(f_j+w(i,j)))。

现在我们有两个问题需要解决：

• 如何计算 (val)。
• 以什么顺序转移 (f)。

我们首先考虑第二个问题。

首先 (f_s=0)，其次，不难发现，如果 (f_i) 最终选择从 (f_j) 转移过来，那么一定有 (f_i>f_j)，如果从 (val_i) 转移过来，那么一定要么节点 (i) 没有任何出边，要么 (val_i) 最大。

上述性质标明，这个转移一定没有环，换句话说，我们一定能够找到一个转移方式。

不难发现，如果我们每次找当前 (f) 值最小的还没有被扩展的节点，那么一定不存在其余节点能够更新它。

所以我们可以通过迪杰斯特拉的方式来更新，因为满足贪心性质，所以正确性显然。

然后我们考虑如何计算 (val_x)。

首先一个性质是它一定只走了一条非树边，如果走了两条的话，不满足最短路树的性质，这个容易证明。且这个非树边的两个节点在树上之间的路径一定经过这个节点 (x)，这个画图不难证明，否则的话不满足是一棵树。当然前提得是走这个边是最优边。

我们发现这个最优边一定是从 (x) 往深走，走到某个节点，然后通过一条非树边，走到另一颗子树，然后走到根节点。

我们考虑设 ((a,b,w)) 为这个非树边。那么 (val_x=dis_a+dis_b+w+dis_x)，其中 (dis) 为最短路树上节点到根的距离。

暴力的想法是枚举这个最右边，不过这样复杂度爆炸。

我们不如把所有的非树边拿出来，按照 (dis_a+dis_b+w) 进行排序，然后对于一个非树边 ((a,b,w))，覆盖这两个点到 (lca(a,b)) 的所有点的 (val)，当然不覆盖 (lca)，我们用并查集维护覆盖的点，具体来说，当一个点被覆盖，我们就把它和它的父亲合并，这样我们查询的时候会直接跳到其父亲。

#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 2010
#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;
}

bitset<N> bit1[N],bit2[N],Beat[N];
int f[N][N][2],n;
char s[N];

inline void Init(){
    read(n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++) if(s[j]=='1') Beat[i][j]=1;
    }   
}

inline void Dp(){
    for(int i=1;i<=n;i++){
        f[i][i][0]=f[i][i][1]=1;
        bit1[i][i]=bit2[i][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n-i+1;j++){
            int l=j,r=j+i-1;
            f[l][r][0]=(Beat[l]&bit1[l+1]&bit2[r]).any();
            f[l][r][1]=(Beat[r]&bit1[l]&bit2[r-1]).any();
            // printf("f[%d][%d][0]=%d f[%d][%d][1]=%d
",l,r,f[l][r][0],l,r,f[l][r][1]);
        }
        for(int j=1;j<=n-i+1;j++){
            int l=j,r=j+i-1;
            if(f[l][r][0]) bit2[r][l]=1;
            if(f[l][r][1]) bit1[l][r]=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(f[1][i][1]&&f[i][n][0]) printf("%d ",i);
    }
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Dp();
    return 0;
}

---

update 2021.10.15

我被 hack 了，注意到我们上面的代码在标记树边时遍历树边的方案是只要满足最短路性质即可，但比如说 (k) 到 (u) 一共有两条路径，且权值和相等，那么这两条路径都会被错误的标记为树边。

解决方案是在记一个 visit 数组，保证每个点不被遍历两次。

代码：

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

const int INF=1e17;

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 Node{
    int id,dis;
    inline Node(){}
    inline Node(int id,int dis) : id(id),dis(dis) {}
    inline bool operator < (const Node &b)const{return dis>b.dis;}
};
priority_queue<Node> q;

struct edge{
    int from,to,next,w,val;bool tag;
    inline void Init(int fr_,int to_,int ne_,int w_){
        from=fr_;to=to_;next=ne_;w=w_;
    }
    inline bool operator < (const edge &b)const{return val<b.val;}
}li[M<<1],li2[M<<1];
int head[N],tail,t2;

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

int n,m,d[N],u,fath[N],Deep[N],fa[N],f[N],val[N];
bool vis[N],visit[N];

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

inline void Init(){
    read(n);read(m);read(u);
    for(int i=1;i<=m;i++){
        int from,to,w;read(from);read(to);read(w);
        Add(from,to,w);Add(to,from,w);
    }
}

inline void Dij(int s){
    fill(d+1,d+n+1,INF);
    q.push(Node(s,0));d[s]=0;
    while(q.size()){
        Node top=q.top();q.pop();
        if(vis[top.id]) continue;
        vis[top.id]=1;
        for(int x=head[top.id];x;x=li[x].next){
            int to=li[x].to,w=li[x].w;
            if(d[to]>d[top.id]+w){d[to]=d[top.id]+w;q.push(Node(to,d[to]));}
        }
    }
}

inline void dfs(int k,int father){
    visit[k]=1;
    fath[k]=father;Deep[k]=Deep[father]+1;
    for(int x=head[k];x;x=li[x].next){
        int to=li[x].to,w=li[x].w;
        if(visit[to]||to==father||d[to]!=d[k]+w) continue;
        li[x].tag=1;dfs(to,k);
    }
}

inline void Signed(int from,int to,int w){
    if(!Deep[from]||!Deep[to]) return;
    int a=Find(from),b=Find(to);
    while(a!=b){
        if(Deep[a]<Deep[b]) swap(a,b);
        val[a]=w;fa[a]=fath[a];a=Find(a);
    }
}

inline void GetF(int s){
    fill(f+1,f+n+1,INF);fill(vis+1,vis+n+1,0);
    q.push(Node(s,0));f[s]=0;
    while(q.size()){
        Node top=q.top();q.pop();
        // printf("top.id=%lld
",top.id);
        if(vis[top.id]) continue;
        vis[top.id]=1;
        for(int x=head[top.id];x;x=li[x].next){
            int to=li[x].to,w=li[x].w;
            // printf("to=%lld
",to);
            if(!vis[to]&&f[to]>Max(val[to],f[top.id]+w)){
                f[to]=Max(val[to],f[top.id]+w);
                q.push(Node(to,f[to]));
            }
        }
    }
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    Init();Dij(u);dfs(u,0);
    for(int i=1;i<=tail;i+=2){
        if(li[i].tag||li[i+1].tag) continue;
        li2[++t2]=li[i];li2[t2].val=d[li[i].to]+d[li[i+1].to]+li[i].w;
    }
    sort(li2+1,li2+t2+1);for(int i=1;i<=n;i++) fa[i]=i;
    // printf("t2=%lld
",t2);
    // for(int i=1;i<=t2;i++) printf("from=%lld to=%lld val=%lld
",li2[i].from,li2[i].to,li2[i].val);
    fill(val+1,val+n+1,INF);
    for(int i=1;i<=t2;i++) Signed(li2[i].from,li2[i].to,li2[i].val);
    for(int i=1;i<=n;i++) val[i]-=d[i];GetF(u);
    for(int i=1;i<=n;i++){
        if(f[i]>INF/10) printf("-1 ");
        else printf("%lld ",f[i]);
    }
    // puts("");
    // for(int i=1;i<=n;i++) printf("val[%lld]=%lld
",i,val[i]);
    return 0;
}