牛客小白月赛20(A(斐波那契性质+矩阵快速幂),B水,D(DFS),E（线段树维护等差数列）,F水,G(权值线段树维护LIS),H水,I(BFS水题),J(数位DP+容斥))

题目链接

官方题解链接

A.斐波那契

这题官方题解写的挺好的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+20;
const ll mod=1e9+7;
int MAXN=2;

struct Martix
{
    ll m[3][3];
    Martix operator *(Martix const &o)const
    {
        Martix res;
        memset(res.m,0,sizeof(res.m));
        for(int i=0;i<MAXN;++i)
        for(int j=0;j<MAXN;++j)
        for(int k=0;k<MAXN;++k)
        res.m[i][j]=(res.m[i][j]+m[i][k]*o.m[k][j]%mod)%mod;
        return res;

    }
};
Martix base,fi;
Martix powmod(Martix a,ll n)
{
    Martix res;
    memset(res.m,0,sizeof(res.m));
    for(int i=0;i<MAXN;++i) res.m[i][i]=1;
    for(;n;n>>=1)
    {
        if(n&1) res=res*base;
        base=base*base;
    }
    return res;
}

int main()
{
    base.m[0][0]=1;
    base.m[0][1]=1;
    base.m[1][0]=1;

    fi.m[0][0]=1;
    fi.m[0][1]=1;
    ll n;
    cin>>n;
    //Martix ans=powmod(base,n)*fi;
    Martix ans1=powmod(base,n)*fi;
    printf("%lld/n",ans1.m[0][0]*ans1.m[1][0]%mod);
}

B水题

D 3的倍数

n只有15  dfs一下即可

#include<bits/stdc++.h>
using namespace std;
const int N=30;
int vis[N][30],n,tmp[N];
int ans=0;
string s;
void dfs(int id,int t,int a[])
{
    if(id>=n){
        for(int i=0;i<26;++i) if(a[i]!=0) return ;
        ans=max(ans,t);
        return ;
    }
    int newa[N];
    for(int i=0;i<26;++i) newa[i]=(a[i]+vis[id][i])%3;

    dfs(id+1,t+1,newa);
    dfs(id+1,t,a);
}
int main()
{
    scanf("%d",&n);
    for(int j=1;j<=n;++j){
        cin>>s;
        for(int i=0;i<s.size();++i){
            vis[j][s[i]-'A']=(vis[j][s[i]-'A']+1)%3;
        }
        //for(int k=0;k<26;++k) printf("%d ",vis[j][k]);
    }

    dfs(1,0,tmp);
    printf("%d/n",ans);
}

E-区区区间

线段树基本操作，线段树维护等差数列，

O1 维护左端点值（懒人标志），O1维护等差数列 求和即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m;
ll sum[4*N],val[4*N],lazy[4*N];
void pushup(int id)
{
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
void build(int id,int l,int r)
{
    if(l==r){
        scanf("%lld",&sum[id]);
        return ;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    pushup(id);
}
void pushdown(int id,int l,int r)
{

    if(lazy[id]){
        //printf("%d来pushdown lazy:%lld/n",id,lazy[id]);
        int mid=l+r>>1;
        lazy[id<<1]=lazy[id];
        lazy[id<<1|1]=lazy[id]+mid-l+1;

        ll n=mid-l+1;
        sum[id<<1]=n*lazy[id<<1]+n*(n-1)/2;

        n=r-mid;
        sum[id<<1|1]=n*lazy[id<<1|1]+n*(n-1)/2;

        lazy[id]=0;
    }
}
void up(int id,int l,int r,int ql,int qr,ll k)
{
    //printf("id:%d l:%d r:%d/n",id,l,r);
    if(ql<=l&&r<=qr)
    {
        ll n=r-l+1;
        ll val=k+l-ql;
        sum[id]=n*val+n*(n-1)/2;
        lazy[id]=val;
        return ;
    }
    pushdown(id,l,r);
    int f=0;
    int mid=l+r>>1;

    if(ql<=mid) up(id<<1,l,mid,ql,qr,k);
    if(qr>mid)  up(id<<1|1,mid+1,r,ql,qr,k);
    pushup(id);
}

ll qu(int id,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr) return sum[id];
    int mid=l+r>>1;
    ll res=0;
    pushdown(id,l,r);
    if(ql<=mid) res+=qu(id<<1,l,mid,ql,qr);
    if(qr>mid)  res+=qu(id<<1|1,mid+1,r,ql,qr);
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        int ty,l,r;
        scanf("%d%d%d",&ty,&l,&r);
        if(ty==1){
            ll k;scanf("%lld",&k);
            up(1,1,n,l,r,k);
        }
        else{
            printf("%lld/n",qu(1,1,n,l,r));
        }
    }
}
/*
5 100
1 1 1 1 1
1 1 5 1
1 1 3 3
2 4 4

*/

F-进制转换，水题

G-快乐风男

权值线段树维护字典序最小 的LIS（最长递增子序列）

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],n;
int dp[N];
struct node
{
    int id,mx;
}tr[4*N];
node MAX(node a,node b)
{
    if(a.mx>b.mx) return a;
    else if(a.mx<b.mx) return b;
    else if(a.id<b.id) return a;
    return b;
}
node qu(int id,int l,int r,int ql,int qr)
{
    if(qr<ql) return {0,0};
    if(ql<=l&&r<=qr){
        return tr[id];
    }
    node t={0,0};
    int mid=l+r>>1;
    if(ql<=mid) t=MAX(t,qu(id<<1,l,mid,ql,qr));
    if(qr>mid) t=MAX(t,qu(id<<1|1,mid+1,r,ql,qr));
    return t;
}
void up(int id,int l,int r,int pos,int mx,int val)
{

    if(l==r){
        if(mx>tr[id].mx)
        tr[id]={val,mx};
        else if(val<tr[id].id){
            tr[id]={val,mx};
        }
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) up(id<<1,l,mid,pos,mx,val);
    else up(id<<1|1,mid+1,r,pos,mx,val);
    tr[id]=MAX(tr[id<<1],tr[id<<1|1]);

}
int main()
{
    scanf("%d",&n);
    int m=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        m=max(m,a[i]);
    }
    int last=0,lastid=0;
    for(int i=1;i<=n;++i){

        node t=qu(1,1,m,1,a[i]-1);
        up(1,1,m,a[i],t.mx+1,i);

        dp[i]=t.id;
        //printf("i:%d mx:%d/n",i,t.mx+1);
        if(t.mx+1>last) lastid=i,last=t.mx+1;
    }

    vector<int>ans;
    while(lastid){
        ans.push_back(lastid);
        lastid=dp[lastid];
    }
    printf("%d/n",ans.size());
    for(int i=ans.size()-1;i>=0;--i) printf("%d ",ans[i]);
    return 0;
}
/*
5
1 2 2 2 3

*/

H-好点

pair方式排下序，O1从后面往前扫即可

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int inf=1e9+10;
int X[N],Y[N];
int l1,l2,n;
vector<pair<int,int> >G;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        G.push_back(make_pair(x,y));
    }
    sort(G.begin(),G.end());
    int x=-1,y=-1;
    vector<pair<int,int> >ans;
    for(int i=G.size()-1;i>=0;--i){
        if(x==-1&&y==-1){
            ans.push_back(make_pair(G[i].first,G[i].second));
            x=G[i].first,y=G[i].second;
            continue;
        }
        if(G[i].first<=x&&G[i].second<=y) continue;
        ans.push_back(make_pair(G[i].first,G[i].second));
        x=G[i].first,y=G[i].second;
    }
    sort(ans.begin(),ans.end());
    for(auto now:ans) printf("%d %d/n",now.first,now.second);
}

I-小小小马

BFS水题

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+10;
int vis[N][N];
int n,m;
int dir[8][2]={1,2,2,1,-1,2,2,-1,1,-2,-2,1,-1,-2,-2,-1};
bool bfs(int x,int y)
{
    queue<pair<int,int> >que;
    que.push(make_pair(1,1));
    vis[1][1]=1;
    int t=0;
    while(que.size())
    {
        pair<int,int> now=que.front();que.pop();
        //printf("x:%d y:%d/n",now.first,now.second);

        t++;
        for(int i=0;i<8;++i){
            int x=now.first+dir[i][0];
            int y=now.second+dir[i][1];
            //printf("x:%d y:%d/n",x,y);

            if(x<1||y<1||x>n||y>m) continue;
            if(vis[x][y]) continue;
            vis[x][y]=1;
            que.push(make_pair(x,y));
        }
    }
    //printf("t:%d/n",t);
    return t>=n*m;
}
int main()
{
    cin>>n>>m;
    if(bfs(1,1)) printf("Yes/n");
    else puts("No");
}

J-dh的帽子

数位dp板子题

三位只有0 1 1,1 1 0,1 0 1是不合法的位置点

结合下容斥原理：

 printf("%lld/n",cal(r,r,r)-3ll*cal(l-1,r,r)+3ll*cal(l-1,l-1,r)-cal(l-1,l-1,l-1));

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=32;
ll dp[N][2][2][2];
int a[N],b[N],c[N];
int l,r;

ll dfs(int pos,int l1,int l2,int l3)
{
    if(pos==-1) return 1;
    if(dp[pos][l1][l2][l3]!=-1)  return dp[pos][l1][l2][l3];
    int up1=l1?a[pos]:1;
    int up2=l2?b[pos]:1;
    int up3=l3?c[pos]:1;
    ll ans=0;
    for(int i=0;i<=up1;++i)
    for(int j=0;j<=up2;++j)
    for(int k=0;k<=up3;++k)
    {
        if(i==0&&j!=0&&k!=0) continue;
        if(i!=0&&j==0&&k!=0) continue;
        if(i!=0&&j!=0&&k==0) continue;
        ans+=dfs(pos-1,l1&&(i==up1),l2&&(j==up2),l3&&(k==up3));
    }
    dp[pos][l1][l2][l3]=ans;
    return ans;
}
ll cal(int x,int y,int z)
{
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;++i) a[i]=b[i]=c[i]=0;
    int len=-1;
    while(x){
        a[++len]=x%2;
        x=x/2;
    }
    len=-1;
    while(y){
        b[++len]=y%2;
        y/=2;
    }
    len=-1;
    while(z){
        c[++len]=z%2;
        z/=2;
    }
    return dfs(30,1,1,1);
}
int main()
{
    scanf("%d%d",&l,&r);
    printf("%lld/n",cal(r,r,r)-3ll*cal(l-1,r,r)+3ll*cal(l-1,l-1,r)-cal(l-1,l-1,l-1));
    return 0;
}