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);elsenum[d]=i;}
}inline void print()
{printf("%d %d\n",ans1,ans2);
}int main()
{int t;while(~scanf("%d",&n)){prework();mainwork();print();}return 0;
}

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\n",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\n",ans);    }return 0;
}

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\n",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;
}

I Median

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

#include<bits/stdc++.h>
#define maxl 100010
using namespace std;

int n;
int b[maxl];
int v[maxl][3],f[maxl][3][3],pre[maxl][3][3];
bool flag;
int ans[maxl];

inline void prework()
{
    scanf("%d",&n);
    for(int i=3;i<=n;i++)
        scanf("%d",&b[i]);
    b[2]=b[1]=b[3];
    b[n+1]=b[n+2]=b[n];
    v[1][0]=v[1][1]=v[1][2]=b[1];
    for(int i=2;i<=n;i++)
        v[i][0]=b[i],v[i][1]=b[i+1],v[i][2]=b[i+2];
    for(int i=1;i<=n;i++)
        sort(v[i],v[i]+2);
}

inline int sorta(int a,int b,int c)
{
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(b>c) swap(b,c);
    return b;
}

inline void mainwork()
{
    for(int i=1;i<=n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                f[i][j][k]=0,pre[i][j][k]=0;
    for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
            f[2][j][k]=1;
    for(int i=3;i<=n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                if(f[i-1][k][l])
                {
                    if(sorta(v[i-2][l],v[i-1][k],v[i][j])==b[i])
                    {
                        f[i][j][k]=1;pre[i][j][k]=l;
                        break;
                    }
                }
    flag=false;int jj,kk,l;
    for(int j=0;j<3 && !flag;j++)
        for(int k=0;k<3;k++)
        if(f[n][j][k])
        {
            jj=j;kk=k;
            flag=true;
            break;
        }
    if(!flag) return;
    for(int i=n;i>=2;i--)
    {
        ans[i]=v[i][jj];
        l=pre[i][jj][kk];
        jj=kk;kk=l;
    }
    ans[1]=b[1];
}

inline void print()
{
    if(!flag)
        puts("-1");
    else
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i],(i==n)?'\n':' ');
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}

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\n",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]];}elseans=val[q[i].s];}if(ans==-100)puts("Invalid");elseprintf("%d\n",ans);}}
}int main()
{int t;scanf("%d",&t);for(int i=1;i<=t;i++){prework();mainwork();}return 0;
}

---

后面题解慢慢更新~