11.5 正睿停课训练 Day16-白红宇

11.5 正睿停课训练 Day16

阅读量：4926 次

发布时间：2019-06-11

本文共 6913 字，大约阅读时间需要 23 分钟。

2018.11.5 正睿停课训练 Day16

时间：3.5h

期望得分：80~100+40+60

实际得分：80+60+60

好菜啊QAQ

A 道路规划(思路)

题意：有一张\(n\)个点的图。给定任意两点之间的最短距离，求最多可以删掉多少条边，并保证任意两点间的最短距离不变。

\(n\leq 300\)。

\(i,j\)之间的边可以删除当且仅当存在一条路径，满足\(i\)到\(j\)的最短距离为\(dis[i][j]\)。

这个路径一定是\(i\)走最短路到某个点\(k\)，再从\(k\)走最短路到\(j\)。枚举一下有没有合法的\(k\)就行了啊。

//15ms  1120kb#include 
    
     #include 
     
      #include 
      
       //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=305;int dis[N][N];char IN[MAXIN],*SS=IN,*TT=IN;inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}int main(){    int n=read(),ans=n*(n-1)>>1;    for(int i=1; i<=n; ++i)        for(int j=1; j<=n; ++j) dis[i][j]=read();    for(int i=1; i<=n; ++i)        for(int j=i+1; j<=n; ++j)            for(int k=1; k<=n; ++k)                if(k!=i&&k!=j&&dis[i][k]+dis[k][j]==dis[i][j])                    {--ans; break;}    printf("%d\n",ans);    return 0;}

B 逻辑判断(枚举位运算/DP 高维前缀和)

原题：。

dalao位运算用的太神了orz。

\(2^n\)枚举哪t位相同，然后我们要求，能区分这t位，且其余n-t位任意的所有集合的f值。

&1就可以保证这一位保持不变了（\(0\&1=0\ 1\&1=1\)），\(\&0\)就可以保证这一位任意（\(1/0\&1=0\)）。所以\(2^n\)枚举所有集合\(s\)，用\(f[s]\)更新\(g[s\&t]\)就可以了。

然后\(2^n\)枚举要求的\(x\)，如果\(g[x\&t]\)合法（所有都相等，且等于\(f[x]\)），就可以用\(t\)更新\(Ans[x]\)了。

于是就可以\(O(4^n)\)水过。

正解是\(O(n*3^n)\)的。以下是瞎说，可最好忽略。

用三进制表示状态，\(0/1\)表示这一位作为\(t\)位中的一位（确定），且等于\(0/1\)，\(2\)表示这一位可以任意。

然后用\(n*3^n\)的DP，用\(g(s,i)\)（当前集合为\(s\)，前\(i-1\)位已考虑过），推出\(f(s)\)（满足\(s\)集合的状态有多少个）。

然后再\(n*3^n\)的DP反推出答案。

这个DP就是高维前缀和。

以后再说。。

//1675ms    692kb#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define gc() getchar()const int N=17000;int Ans[N],f[N],g[N];inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}int main(){    int n=read(); const int all=(1<

C 区间(贪心/树状数组)

题意：给定\(n\)个区间\([l_i,r_i]\)。你可以选出任意一些区间，设选出的区间个数是\(s\)，\(l,r\)是这些区间的交，求\(\min(s,r-l+1)\)的最大值。

\(n\leq3\times10^5\)。

要最大化\(\min(s,r-l+1\))（\(s\)是当前区间数，\(l,r\)是区间交）。

考虑按左端点从小到大依次枚举并加入一个区间\(x\)。那么\(l\)就是\(l_x\)，而\(r\)是当前选中的所有区间中最小的\(r_i\)，拿个小根堆就可以维护了。

每次加入一个区间\(x\)后，若此时\(s<r-l+1\)，则可以继续加入区间；若\(s>r-l+1\)，可以删掉一些区间。然后更新一下答案。

删区间的时候，每次一定是删掉\(r\)最小的一个区间，把堆顶pop掉就行了。

复杂度\(O(n\log n)\)。

把右端点的删除标记放到点上，然后用一个不断右移的指针\(R\)（右端点小于当前右指针的区间就不需要考虑了），就可以代替堆做到\(O(n)\)了。

其它做法：

二分+树状数组：对每个左端点二分区间长度，显然啊怎么就没想到啊QAQ。常数小能跑过。

不二分的树状数组：右端点位置是单调的，所以把最初做法的\(R\)用指针+树状数组维护（\(s<r-l+1\ \to\ s-Query(R-1)<R-l+1\)），保证\(R\)单调就可以了。

//195ms 4176kb#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define gc() getchar()#define MAXIN 300000//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=3e5+5;    std::priority_queue
         
          
           ,std::greater
           
             > q;char IN[MAXIN],*SS=IN,*TT=IN;struct Node{ int l,r; bool operator <(const Node &x)const { return l==x.l?r>x.r:l
            
             q.top()-A[i].l+1) q.pop(); ans=std::max(ans,std::min((int)q.size(),q.top()-A[i].l+1)); } printf("%d\n",ans); return 0;}

考试代码

A

暴力Dij，果然还是成功挂掉了。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mp std::make_pair#define pr std::pair
         
          //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=305,M=90009;int dis[N][N],Enum,H[N],nxt[M],to[M],len[M];bool ok[M];char IN[MAXIN],*SS=IN,*TT=IN;struct Node{ int u,v,ds; bool operator <(const Node &x)const { return ds
          
            q; memset(vis,0,sizeof vis); memset(dis,0x3f,(n+2)<<2); dis[s]=0, q.push(mp(0,s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=H[x],v; i; i=nxt[i]) if(dis[v=to[i]]>dis[x]+len[i]) q.push(mp(-(dis[v]=dis[x]+len[i]),v)); }}void Dijkstra2(int s,int n){ static bool vis[N]; static int dis[N],pre[N]; static std::priority_queue
           
             q; memset(vis,0,(n+2)<<2); memset(pre,0,(n+2)<<2); memset(dis,0x3f,(n+2)<<2); dis[s]=0, q.push(mp(0,s)); while(!q.empty()) { int x=q.top().second; q.pop(); if(vis[x]) continue; vis[x]=1; for(int i=H[x],v; i; i=nxt[i]) if(dis[v=to[i]]>dis[x]+len[i]) pre[v]=i, q.push(mp(-(dis[v]=dis[x]+len[i]),v)); } for(int i=1; i<=n; ++i) ok[pre[i]]=ok[pre[i]^1]=1;}int main(){// freopen("ex_road3.in","r",stdin);// freopen(".out","w",stdout); int n=read(),cnt=0; Enum=1; for(int i=1; i<=n; ++i) { for(int j=1; j<=i; ++j) read(); for(int j=i+1; j<=n; ++j) A[++cnt]=(Node){i,j,read()}; } std::sort(A+1,A+1+cnt); int ans=0; for(int i=1,u,v; i<=cnt; ++i) { u=A[i].u, v=A[i].v, Dijkstra(dis[u],u,n); if(dis[u][v]!=A[i].ds) AE(u,v,A[i].ds), ++ans; } if(n<=100) { for(int i=1; i<=n; ++i) Dijkstra2(i,n); for(int i=2; i<=Enum; i+=2) if(!ok[i]) --ans; } printf("%d\n",ans); return 0;}

B

#include 
    
     #include 
     
      #include 
      
       #define gc() getchar()typedef long long LL;const int N=17000;int n,Ans,A[36],bit[36],fx,X;char f[N];int DFS0(int x,int s,int now){    if(x==-1) return f[now]-'0';    if(s>>x&1) return DFS0(x-1,s,now|(bit[x]<
       
        =Ans) return;    if(x==-1)    {        DFS0(::n-1,s,0)==fx&&(Ans=std::min(Ans,sum));        return;    }    DFS(x-1,s,sum), DFS(x-1,s|(1<
        
         >=1);    std::random_shuffle(A,A+n);    Ans=n, DFS(n-1,0,0);    return Ans;}int main(){//  freopen("ex_logic3.in","r",stdin);//  freopen(".out","w",stdout);    int n; scanf("%d%s",&n,f); ::n=n;    const int all=(1<

C

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define gc() getchar()#define MAXIN 300000//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)typedef long long LL;const int N=3e5+5,INF=1e9;int n,L[N],R[N],sum[N<<1],ref[N<<1],Ans;bool ban[N];char IN[MAXIN],*SS=IN,*TT=IN;struct Node{    int l,r,id;}A[N],B[N];struct Segment_Tree{    #define ls rt<<1    #define rs rt<<1|1    #define lson l,m,ls    #define rson m+1,r,rs    #define S N<<2//  int sum[S],len[S],ans[S];    #undef S};inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}void DFS(int x,int t){    static int sum2[33];    if(!x)    {        int tot=0;        memcpy(sum2,sum,sizeof sum2);        for(int i=1; i<=n; ++i) tot+=((sum2[i]+=sum2[i-1])==t);        Ans=std::max(Ans,std::min(t,tot));        return;    }    DFS(x-1,t), ++sum[L[x]], --sum[R[x]+1], DFS(x-1,t+1), --sum[L[x]], ++sum[R[x]+1];}inline int Find(int x,int r){    int l=1,mid;    while(l
        
         >1]
         
          2000) return Solve(n),0; int ans=std::min(1,n),now=1; for(int i=1; i<=n; ++i) { while(B[now].r

转载于:https://www.cnblogs.com/SovietPower/p/9911729.html

你可能感兴趣的文章

A 道路规划(思路)

B 逻辑判断(枚举 位运算/DP 高维前缀和)

C 区间(贪心/树状数组)

考试代码

A

B

C

B 逻辑判断(枚举位运算/DP 高维前缀和)