两次考试-白红宇

两次考试

阅读量：5231 次

发布时间：2019-06-14

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

11.6

super_gcd

还是要抓紧复习一下板子...

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int LEN=1006;int t[LEN],he;int cm;struct bign{    int s[LEN],len;    bign(){mem(s,0);len=1;}    void read()    {        int i;        he=0; char q=getchar();        while(q<'0'||q>'9') q=getchar();        while(q>='0'&&q<='9') t[++he]=q-'0',q=getchar();        for(i=he;i;--i) s[he-i+1]=t[i];        len=he;    }    bool operator < (const bign &c) const    {        bign x=*this;        if(x.len==c.len)        {            int i;            for(i=x.len;i;--i)            {                if(x.s[i]==c.s[i]) continue;                return x.s[i]
           
            1&&x.s[x.len]==0) --x.len; return x; } void out() { int i; for(i=len;i;--i) printf("%d",s[i]); puts(""); }};int T;bign A,B;int gcd(){ while( !(A.len==1&&A.s[1]==0)&&!(B.len==1&&B.s[1]==0) ) { if(A

考试什么都想不出来...

考虑补集转化，用总方案数减去0、1、2各自不合法的方案数

因为每个区间只会有一个数超过一半，所以不用容斥

枚举0、1、2

把跟它相等的数看做1，不相等的看做-1

这样统计前缀和中比当前低的位置即可

$O(n)$

其实$O(nlogn)$的很好想

$$pre_r-pre_{l-1}>\frac{r-l+1}{2}$$

$$2*pre_r-r>2*pre_{l-1}-l+1$$

直接树状数组就行了

真是菜...

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    char q=getchar();    while(q<'0'||q>'9') q=getchar();    x=q-'0';}const int N=5000006;int n;int cm;int aee=5000000;int cnt[N<<1],v[N];ll ans;ll get(){    rint i; int tt; ll ans=0,now=aee,ccc=0;    mem(cnt,0); ++cnt[aee];    for(i=1;i<=n;++i)    {        if(v[i]==cm) ccc+=cnt[now],++now;        else --now,ccc-=cnt[now];        ++cnt[now];        ans+=ccc;    }    return ans;}int main(){        //freopen("ex1.in","r",stdin);        rint i;        scanf("%d",&n);    for(i=1;i<=n;++i) read(v[i]);        /*printf("\n");    for(i=1;i<=n;++i)        printf("%d",v[i]);    printf("\n");*/        ans=1LL*n*(n+1)/2;    for(i=0;i<3;++i)        cm=i,ans-=get();    printf("%lld\n",ans);}

$O(n^3)$的dp很简单，但是我根本没想...

考试打了用堆来贪心取，骗了40

70分还可以打网络流

建图就S向豆干和干脆面连流量为给出个数费用为0的边

豆干和干脆面在向每只猫连一条$1/p_i$ 一条$1/0$ 的边

正解是wqs二分套wqs二分

二分两个cost，分别表示选豆干和干脆面各会需要额外的花费

每次dp记录最优的猫的个数和用掉的豆干和干脆面的个数

这样一直二分到第一个大于等于给出个数的值

而且二分出的值不一定可以使得dp结果正好是给出的个数

就像陈立杰那个黑白树一样(毕竟重打了7遍呢，记忆比较深刻...)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define eps 0.00000001#define dd double#define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int N=100006;const ll Inf=1e10;int n,A,B;int now,pr;dd p[N],q[N];dd f[2];int ga[2],gb[2];void check(dd xp,dd xq){    rint i,j;    now=0;    f[0]=0; ga[0]=gb[0]=0;    for(i=1;i<=n;++i)    {        now^=1; pr=now^1;        f[now]=-Inf; ga[now]=gb[now]=0;        if(f[now]
           
            n) A=n; if(B>n) B=n; printf("%.3f\n",work()); }}

11.7

T一定可以分解成$S*B^{a}+n1*A*B^{a-1}+n2*A*B^{a-2}...$的形式

其中n1,n2是系数，可以为0

这样的话，直接枚举a，在贪心取就行了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}int S,T,A,B;int maxk;ll P[106];int main(){        //freopen("T1.in","r",stdin);    //freopen("T1hh.out","w",stdout);        //freopen("a.in","r",stdin);    //freopen("a.out","w",stdout);        rint i,j; ll tt,t1; int con,ans=1e9;        read(S); read(T); read(A); read(B);        if(S>T)    {        puts("-1");        return 0;    }        tt=S; maxk=0;    while(tt<=T&&maxk<=32) tt*=B,++maxk;    --maxk; tt/=B;        P[0]=1;    for(i=1;i<=maxk;++i)        P[i]=P[i-1]*B;        for(i=maxk;~i;--i)    {        tt=S*P[i]; con=i;        for(j=i;~j;--j)        {            t1=(1LL*T-tt)/(1LL*A*P[j]);            con+=t1; tt+=1LL*t1*A*P[j];        }        if(tt==T&&ans>con) ans=con;    }    if(ans==1000000000)        ans=-1;    printf("%d\n",ans);}

算法1(考试骗分) 90

先考虑二分ans

然后二分点对的左端点距离选择的边的左端点的最大值

然后对右端点做区间交

$O(nlog^2n)$

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int N=100006;int n,m;int u[N],v[N],len[N];int check60(int maxd){    rint i,j; int mn,mx,t1,t2;    for(i=1;i<=n;++i)    {        mn=1000000; mx=1;        for(j=1;j<=m;++j)            if(len[j]>maxd)            {                t1=u[j]-i; if(t1<0) t1=-t1;                if(t1>maxd)                {                    mn=1; mx=1000000;                    break;                }                t2=maxd-t1;                if(mn>v[j]+t2) mn=v[j]+t2;                if(mx
           
            >1; //printf("l=%d r=%d mid=%d\n",l,r,mid); if(check60(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int check100(int maxd){ int l=0,r=maxd,mid; int mn,mx,t1,t2,tt,l1=n,r1=1; rint i,j; while(l<=r) { mid=(l+r)>>1; //printf("l2=%d r2=%d mid2=%d\n",l,r,mid); mn=n; mx=1; for(i=1;i<=m;++i) if(len[i]>maxd) { if(mx
            
             u[i]+mid) mn=u[i]+mid; } //printf("mn=%d mx=%d\n",mn,mx); if(mx>mn) l=mid+1; else { l1=mx,r1=mn,r=mid-1; /*if(l1>mx) l1=mx; if(r1
             
              r1) return 0; //printf("l1=%d r1=%d mid=%d\n",l1,r1,mid); for(i=l1;i<=r1;++i) { t1=n; t2=1; for(j=1;j<=m;++j) if(len[j]>maxd) { tt=u[j]-i; if(tt<0) tt=-tt; tt=maxd-tt; if(t2
              
               v[j]+tt) t1=v[j]+tt; } //printf("asdsd:: %d %d\n",t2,t1); if(t2<=t1) return 1; } return 0;}int work100(){ int l=0,r=n,mid,ans=n; while(l<=r) { mid=(l+r)>>1; //printf("l=%d r=%d mid=%d\n",l,r,mid); if(check100(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int main(){ //freopen("T2.in","r",stdin); //freopen("T2.out","w",stdout); //freopen("b.in","r",stdin); //freopen("b.out","w",stdout); rint i; read(n); read(m); for(i=1;i<=m;++i) read(u[i]),read(v[i]),len[i]=v[i]-u[i]; if(n<=5000) printf("%d\n",work60()); else printf("%d\n",work100());}

算法2 100

其实左端点并不具有二分性质，而是一个横坐标为左端点pos，竖坐标为ans的下凹函数

那么可以三分套二分

$O(nlog^2n)$

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int N=100006;int n,m;int u[N],v[N],len[N];int check2(int pos,int maxd){    rint i; int l1=1,r1=n,t1;    for(i=1;i<=m;++i)        if(len[i]>maxd)        {            t1=u[i]-pos; if(t1<0) t1=-t1;            if(t1>maxd) return 0;        }    for(i=1;i<=m;++i)        if(len[i]>maxd)        {            t1=u[i]-pos; if(t1<0) t1=-t1;            t1=maxd-t1;            if(l1
           
            v[i]+t1) r1=v[i]+t1; } if(l1<=r1) return 1; return 0;}int check(int pos){ rint i; int l=0,r=n,mid,ans=n; while(l<=r) { mid=(l+r)>>1; if(check2(pos,mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int work(){ int l=1,r=n,mid,midmid,midv,midmidv,ans=n,i; while(l<=r-10) { mid=l+(r-l)/3; midmid=r-(r-l)/3; midv=check(mid); midmidv=check(midmid); if(midv>midmidv) { if(ans>midmidv) ans=midmidv; l=mid; } else { if(ans>midv) ans=midv; r=midmid; } } for(i=l;i<=r;++i) { midv=check(i); if(ans>midv) ans=midv; } return ans;}int main(){ //freopen("T2.in","r",stdin); rint i; read(n); read(m); for(i=1;i<=m;++i) read(u[i]),read(v[i]),len[i]=v[i]-u[i]; printf("%d\n",work());}

算法3 100

二分ans

对于每一个点对，发现合法的区间映射到二维平面是其实是一个个倾斜45度的正方形

用$(x+y,x-y)$把正方形旋转成水平的(旋转过程大小会变，但是相对位置不会)

这样矩形求交就行了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int N=100006;const int Inf=1e9;int n,m;int u[N],v[N],len[N];int check(int maxd){    rint i;    int l=-Inf,r=Inf,xi=-Inf,sh=Inf;    int t1,t2;    int sha,xia,zuo,you;    for(i=1;i<=m;++i)        if(len[i]>maxd)        {            sha=-Inf; xia=Inf; zuo=Inf; you=-Inf;            t1=u[i]-maxd+v[i]; t2=u[i]-maxd-v[i];            if(sha
           
            t2) xia=t2; if(you
            
             t1) zuo=t1; t1=u[i]+maxd+v[i]; t2=u[i]+maxd-v[i]; if(sha
             
              t2) xia=t2; if(you
              
               t1) zuo=t1; t1=u[i]+v[i]-maxd; t2=u[i]-(v[i]-maxd); if(sha
               
                t2) xia=t2; if(you
                
                 t1) zuo=t1; t1=u[i]+v[i]+maxd; t2=u[i]-(v[i]+maxd); if(sha
                 
                  t2) xia=t2; if(you
                  
                   t1) zuo=t1; if(l
                   
                    you) r=you; if(xi
                    
                     sha) sh=sha; } if(xi<=sh&&l<=r) return 1; return 0;}int work(){ int l=0,r=n,mid,ans=n; while(l<=r) { mid=(l+r)>>1; //printf("l=%d r=%d mid=%d\n",l,r,mid); if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int main(){ //freopen("T2.in","r",stdin); //freopen("T2.out","w",stdout); rint i; read(n); read(m); for(i=1;i<=m;++i) read(u[i]),read(v[i]),len[i]=v[i]-u[i]; printf("%d\n",work());}

算法4 100

其实算法3的check就是求曼哈顿距离可否满足maxd

那么把曼哈顿距离转化成切比雪夫距离

这样横纵坐标就独立起来了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int Inf=1e9;const int N=100006;int n,m;int u[N],v[N],len[N];int check(int maxd){    rint i; int l=-Inf,r=Inf;    for(i=1;i<=m;++i)        if(len[i]>maxd)        {            if(l
           
            u[i]+v[i]+maxd) r=u[i]+v[i]+maxd; } //printf("l1=%d r1=%d\n",l,r); if(l>r) return 0; l=-Inf; r=Inf; for(i=1;i<=m;++i) if(len[i]>maxd) { if(l
            
             u[i]-v[i]+maxd) r=u[i]-v[i]+maxd; } //printf("l2=%d r2=%d\n",l,r); if(l>r) return 0; return 1;}int work(){ int l=0,r=n,mid,ans=n; while(l<=r) { mid=(l+r)>>1; //printf("l=%d r=%d mid=%d\n",l,r,mid); if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int main(){ // freopen("T2.in","r",stdin); rint i; read(n); read(m); for(i=1;i<=m;++i) read(u[i]),read(v[i]),len[i]=v[i]-u[i]; printf("%d\n",work());}

结论：

不管对手怎么动，只要预先知道了他的行动

就可以对应的进行行动，总有一种方案使得最后得到结果

二分即可

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long long#define mem(a,b) memset(a,b,sizeof(a))#define rint register intusing namespace std;inline void read(int &x){    x=0; int ff=1; char q=getchar();    while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }    while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();    x*=ff;}const int N=300006;int first[N],nt[N<<1],ver[N<<1],e;void addb(int u,int v){    ver[e]=v;    nt[e]=first[u];    first[u]=e++;}int n,alln;int v[N],t[N],pos[N];int x[N<<1],y[N<<1];int dfn[N],low[N],tim,zhan[N],he,sun[N],sum;bool flag[N];void tarjan(int x){    dfn[x]=low[x]=++tim;    zhan[++he]=x; flag[x]=1;    int i;    for(i=first[x];i!=-1;i=nt[i])    {        if(dfn[ver[i]]==-1)        {            tarjan(ver[i]);            if(low[x]>low[ver[i]])                low[x]=low[ver[i]];        }        else            if(flag[ver[i]]&&low[x]>dfn[ver[i]])                low[x]=dfn[ver[i]];    }    if(dfn[x]==low[x])    {        i=-1; ++sum;        while(i!=x)            i=zhan[he--],flag[i]=0,++sun[sum];    }}int check(int arr){    rint i; int tt;    for(i=0;i
           
            >1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } return ans;}int main(){ //freopen("T3.in","r",stdin); rint i; read(n); alln=n<<1; for(i=0;i