• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

10.14 正睿做题笔记

开发技术 开发技术 5小时前 2次浏览

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

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("%lfn",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("%dn",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]=%dn",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]=%dn",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;
}

程序员灯塔
转载请注明原文链接:10.14 正睿做题笔记
喜欢 (0)