2019牛客全国多校训练三 题解

A Gragh Games

Unsolved.

B Crazy Binary String

题解：水题，子序列只要统计0和1数量，取最小值然后乘2就是答案；

对于子串：先记录0和1 前缀和的差值，然后找差值相等的距离最远的两个位置即可；

参考代码：

#include<bits/stdc++.h>
#define maxl 100010
using namespace std;
 
int n;
int cnt[2];
int num[maxl*2];
int sum[maxl][2];
char s[maxl];
int ans1,ans2;
 
inline void prework()
{
    scanf("%s",s+1);
    cnt[0]=cnt[1]=0;
    for(int i=1;i<=n;i++)
    {
        cnt[s[i]-'0']++;
        if(s[i]=='0')
        {
            sum[i][0]=sum[i-1][0]+1;
            sum[i][1]=sum[i-1][1];
        }
        else
        {
            sum[i][0]=sum[i-1][0];
            sum[i][1]=sum[i-1][1]+1;   
        }
    }
}
 
inline void mainwork()
{
    for(int i=1;i<2*maxl;i++)
        num[i]=-1;
    num[maxl]=0;
    ans1=0;ans2=min(cnt[0],cnt[1])*2;
    for(int i=1;i<=n;i++)
    {
        int d=sum[i][1]-sum[i][0]+maxl;
        if(num[d]>=0)
            ans1=max(i-num[d],ans1);
        else
            num[d]=i;
    }
}
 
inline void print()
{
    printf("%d %d
",ans1,ans2);
}
 
int main()
{
    int t;
    while(~scanf("%d",&n))
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}
View Code

C Guess ETT

unsolved.

D Big Integer

https://blog.csdn.net/baiyifeifei/article/details/97318024

#include<bits/stdc++.h>
using namespace std;
typedef __int128 LL;
LL quick_pow(LL a,LL b,LL mod)
{
    LL ans=1;
    a=a%mod;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return ans;
}
LL pows(long long f,int s,int m)
{
    LL ans=1;
    int tims=s/m+(s%m!=0);
    while(tims)
    {
        if(tims&1) ans=ans*f;
        f=f*f;
        tims>>=1;
    }
    return ans;
}
vector<LL> fac;
int cnt[50];
int tor[50],tot;
int main()
{
    int t;
    scanf("%d",&t);
    int p,n,m;
    while(t--)
    {
        scanf("%d%d%d",&p,&n,&m);
        if(p%2==0||p%5==0)
        {
            puts("0");
            continue;
        }
        LL phi=6LL*(p-1);
        if(p==3) phi=18;
        LL mod=9LL*p;
        fac.clear();
        for(LL i=1;i*i<=phi;i++)
        {
            if(phi%i!=0) continue;
            fac.push_back(i);
            fac.push_back(phi/i);
        }
        sort(fac.begin(),fac.end());
        LL g=phi;
        for(auto x:fac)
        {
            if(quick_pow(10,x,mod)==1)    {g=x;break;}
        }
        LL tmp=g;
        tot=0;
        for(LL i=2;i*i<=tmp;i++)
        {
            if(g%i==0)
            {
                tor[++tot]=i;cnt[tot]=0;
                do g/=i,cnt[tot]++;
                while(g%i==0) ;
            }
        }
        if(g>1) {tor[++tot]=g;cnt[tot]=1;}
        g=tmp;
        int mx=0;
        for(int i=1;i<=tot;i++) mx=max(mx,cnt[i]);
        LL tg=1;
        long long  ans=0;
        for(LL i=1;i<=min(mx,m);i++)
        {
            tg=1;
            for(int j=1;j<=tot;j++) tg=tg*pows(tor[j],cnt[j],i);
            ans=ans+n/tg;
        }
        ans=ans+max(0,(m-mx))*(n/tg);
        printf("%lld
",ans);
    }
}

E Trees In the Pocket II

unsolved.

F plating tree

 题解：题目意思就是给你你个N*N的矩阵，里面有数字。让你找一个面积最大的子矩阵使得其中所有的数字的差不大于K；

思路：我们以枚举上下边界，然后枚举右边界，用两个单调队列分别维护最大值和最小值来确定左边界，

最大值队列下标增大，值减小，最大值队列下标增大，值增大；

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
typedef long long ll;
const int INF=0x3f3f3f3f;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;    
}

const int maxn=520;
int T,n,k,a[maxn][maxn];
int mx[maxn],mn[maxn],q1[maxn],q2[maxn];

int main()
{
    T=read();
    while(T--)
    {
        n=read();k=read();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) 
                scanf("%d",&a[i][j]);
        int l1,r1,l2,r2,ans=0;
        for(int up=1;up<=n;++up)
        {
            memset(mx,0,sizeof(mx));
            memset(mn,INF,sizeof(mn));
            for(int dn=up;dn<=n;++dn)
            {
                l1=l2=r1=r2=0;
                for(int r=1,l=0;r<=n;++r)
                {
                    mx[r]=max(mx[r],a[dn][r]);mn[r]=min(mn[r],a[dn][r]);
                    while(l1<r1 && mx[q1[r1-1]]<mx[r]) --r1;
                    while(l2<r2 && mn[q2[r2-1]]>mn[r]) --r2;
                    q1[r1++]=r; q2[r2++]=r;
                    
                    while(l1<r1 && l2<r2 && mx[q1[l1]]-mn[q2[l2]]>k)
                    {
                        if(q1[l1]<q2[l2]) l=q1[l1++];    
                        else l=q2[l2++];
                    }
                    
                    ans=max(ans,(dn-up+1)*(r-l));
                }    
            }
        }
        printf("%d
",ans);    
    }
    
    return 0;
}
View Code

G Removing Stone

unsolved.

H Magic Line

题解：只要按照横坐标为第一排序关键字，纵坐标为第二关键字排个序就行了。

然后在中间两个点之间画一条直线并使得他与其他点不想交就行了（斜率取得很大就行了）

参考代码:

#include<bits/stdc++.h>
#define maxl 200010
using namespace std;
 
int n,nn;
struct node
{
    int x,y;
}a[maxl];
vector <int> b[maxl];
int num[maxl];
 
inline void prework()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        num[i]=a[i].x;
    }
    sort(num+1,num+1+n);
    nn=unique(num+1,num+1+n)-num-1;
    for(int i=1;i<=nn;i++)
        b[i].clear();
    for(int i=1;i<=n;i++)
    {  
        a[i].x=lower_bound(num+1,num+1+nn,a[i].x)-num;
        b[a[i].x].push_back(a[i].y);
    }
}
 
inline void mainwork()
{
    int l,sum=0,h;bool flag;
    for(int i=1;i<=nn;i++)
    {
        sort(b[i].begin(),b[i].end());
        l=b[i].size();
        for(int j=0;j<l;j++)
        {
            sum++;
            if(sum==n/2)
            {
                h=b[i][j];
                break;
            }
        }
        if(sum==n/2)
        {
            int y1=h+8*1e8,y2=h-8*1e8;
            y2++;
            printf("%d %d %d %d
",num[i]-1,y1,num[i]+1,y2);
            return;
        }
    }
}
 
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
//      print();
    }
    return 0;
}
View Code

I Median

题解：https://blog.csdn.net/liufengwei1/article/details/97392482

 1 #include<bits/stdc++.h>
 2 #define maxl 100010
 3 using namespace std;
 4 
 5 int n;
 6 int b[maxl];
 7 int v[maxl][3],f[maxl][3][3],pre[maxl][3][3];
 8 bool flag;
 9 int ans[maxl];
10 
11 inline void prework()
12 {
13     scanf("%d",&n);
14     for(int i=3;i<=n;i++)
15         scanf("%d",&b[i]);
16     b[2]=b[1]=b[3];
17     b[n+1]=b[n+2]=b[n];
18     v[1][0]=v[1][1]=v[1][2]=b[1];
19     for(int i=2;i<=n;i++)
20         v[i][0]=b[i],v[i][1]=b[i+1],v[i][2]=b[i+2];
21     for(int i=1;i<=n;i++)
22         sort(v[i],v[i]+2);
23 }
24 
25 inline int sorta(int a,int b,int c)
26 {
27     if(a>b) swap(a,b);
28     if(a>c) swap(a,c);
29     if(b>c) swap(b,c);
30     return b;
31 }
32 
33 inline void mainwork()
34 {
35     for(int i=1;i<=n;i++)
36         for(int j=0;j<3;j++)
37             for(int k=0;k<3;k++)
38                 f[i][j][k]=0,pre[i][j][k]=0;
39     for(int j=0;j<3;j++)
40         for(int k=0;k<3;k++)
41             f[2][j][k]=1;
42     for(int i=3;i<=n;i++)
43         for(int j=0;j<3;j++)
44             for(int k=0;k<3;k++)
45                 for(int l=0;l<3;l++)
46                 if(f[i-1][k][l])
47                 {
48                     if(sorta(v[i-2][l],v[i-1][k],v[i][j])==b[i])
49                     {
50                         f[i][j][k]=1;pre[i][j][k]=l;
51                         break;
52                     }
53                 }
54     flag=false;int jj,kk,l;
55     for(int j=0;j<3 && !flag;j++)
56         for(int k=0;k<3;k++)
57         if(f[n][j][k])
58         {
59             jj=j;kk=k;
60             flag=true;
61             break;
62         }
63     if(!flag) return;
64     for(int i=n;i>=2;i--)
65     {
66         ans[i]=v[i][jj];
67         l=pre[i][jj][kk];
68         jj=kk;kk=l;
69     }
70     ans[1]=b[1];
71 }
72 
73 inline void print()
74 {
75     if(!flag)
76         puts("-1");
77     else
78         for(int i=1;i<=n;i++)
79             printf("%d%c",ans[i],(i==n)?'
':' ');
80 }
81 
82 int main()
83 {
84     int t;
85     scanf("%d",&t);
86     for(int i=1;i<=t;i++)
87     {
88         prework();
89         mainwork();
90         print();
91     }
92     return 0;
93 }
View Code

J LRU management

参考代码：

#include<bits/stdc++.h>
#define maxl 500010
using namespace std;
  
int n,m,tot,nn,cnt;
int tr[maxl*11][11],num[maxl*11];
int nxt[maxl],pre[maxl],val[maxl];
struct qu
{
    int op,s,v;
}q[maxl];
char s[11];
bool in[maxl];
  
inline int insert(char s[])
{
    int len=strlen(s),u=0,c;
    for(int i=0;i<len;i++)
    {
        c=s[i]-'0';
        if(tr[u][c]==0)
            tr[u][c]=++tot;
        u=tr[u][c];
    }
    if(num[u]==0)
        num[u]=++cnt;
    return num[u];
}
  
inline void prework()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=tot;i++)
    {
        num[i]=0;
        memset(tr[i],0,sizeof(tr[i]));
    }
    tot=0;cnt=0;
    for(int i=1;i<=n;i++)
    { 
        scanf("%d%s%d",&q[i].op,s,&q[i].v);
        q[i].s=insert(s);
    }
}
  
inline void mainwork()
{
    for(int i=1;i<=cnt;i++)
        nxt[i]=0,pre[i]=0,in[i]=false,val[i]=0;
    int head=0,tail=0;int ans,sz=0,l,r;
    for(int i=1;i<=n;i++)
    {
        ans=0;
        if(q[i].op==0)
        {
            if(!in[q[i].s])
            {
                in[q[i].s]=true;
                if(head==0)
                {
                    tail=head=q[i].s;
                    pre[q[i].s]=nxt[q[i].s]=0;
                    val[q[i].s]=q[i].v;
                    sz++;
                }
                else
                {
                    sz++;val[q[i].s]=q[i].v;
                    in[q[i].s]=true;
                    pre[q[i].s]=tail;nxt[q[i].s]=0;
                    nxt[tail]=q[i].s;
                    tail=q[i].s;
                }
            }
            else
            {
                if(sz>1 && tail!=q[i].s)
                {
                    l=pre[q[i].s];r=nxt[q[i].s];
                    if(l>0)
                        nxt[l]=r;
                    if(r>0)
                        pre[r]=l;
                    if(q[i].s==head)
                        head=r,pre[r]=0;
                    nxt[tail]=q[i].s;
                    nxt[q[i].s]=0;
                    pre[q[i].s]=tail;
                    tail=q[i].s;
                }
            }
            if(sz>m)
            {
                sz--;
                in[head]=false;val[head]=0;
                r=nxt[head];
                pre[head]=0;nxt[head]=0;
                pre[r]=0;
                head=r;
            }
            ans=val[q[i].s];
            printf("%d
",ans);
        }
        else
        {
            ans=-100;
            if(in[q[i].s])
            {
                if(q[i].v==1)
                {
                    if(nxt[q[i].s]>0 && in[nxt[q[i].s]])
                        ans=val[nxt[q[i].s]];
                }
                else if(q[i].v==-1)
                {
                    if(pre[q[i].s]>0 && in[pre[q[i].s]])
                        ans=val[pre[q[i].s]];
                }
                else
                    ans=val[q[i].s];
            }
            if(ans==-100)
                puts("Invalid");
            else
                printf("%d
",ans);
        }
    }
}
  
int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
    }
    return 0;
}
View Code

后面题解慢慢更新~

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/csushl/p/11246847.html