牛客周赛63

https://ac.nowcoder.com/acm/contest/91592

好数

简单的判断两位数，且十位等于个位

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

void solve() 
{
    int x;cin>>x;
    if(x>=10&&x<=99)
    {
        int xx=x%10;
        x=x/10;
        if(xx==x)
        {
            cout<<"Yes"<<'\n';
            return;
        }
    }
    cout<<"No"<<'\n';
}
signed main() 
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    IOS;

    int _ = 1; //cin >> _;
    while (_--) solve();
    return 0;
}

小红的好数组

1<n,k<1000

暴力最多进行 (n-k+1)*k次

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int n,k,a[N];

int chang(deque<int>de)
{
    int ans=0;
    while(de.size())
    {
        auto x=de.front(),y=de.back();
        if(x!=y) ans++;
        if(de.size()) de.pop_back();
        if(de.size()) de.pop_front();
    }
    if(ans==1) return 1;
    return 0;
}

void solve() 
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    deque<int>de;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        de.push_back(a[i]);
        while(de.size()>k) de.pop_front();
        if(de.size()==k)
        ans+=chang(de);
        //if(chang(de)) cout<<i<<"\n";
    }
    cout<<ans<<'\n';
}
signed main() 
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    IOS;

    int _ = 1; //cin >> _;
    while (_--) solve();
    return 0;
}

小红的矩阵行走

正常bfs走，当当前位置与（1，1）一样时才能走

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int N = 200 + 10;
const int mod = 1e9 + 7;
int a[N][N];
int n,m;
int p=0;
int dx[]={0,1};
int dy[]={1,0};
void dfs(int x,int y)
{
    //cout<<"(x,y)"<<"("<<x<<","<<y<<")"<<'\n';
    if(x==n&&y==m)
    {
        p=1;
        return;
    }
    for(int i=0;i<2;i++)
    {
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==a[x][y])
        {
            dfs(xx,yy);
        }
    }
}
void solve() 
{
    p=0;
    cin>>n>>m;
    //vector<int>a(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
    int k=a[1][1];
    dfs(1,1);
    if(p) cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
}
signed main() 
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    IOS;

    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

小红的行列式构造

如果时0的话就构造

1 1 1
1 1 1
1 1 1

反之

-x x -x
2 1 1
1 1 2

即可

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

void solve() 
{
    int x;cin>>x;
    if(x==0)
    {
        cout<<"1 1 1\n1 1 1\n1 1 1\n"<<'\n';
        return ;
    }
    cout<<-x<<" "<<-x<<" "<<-x<<"\n";
    cout<<2<<" "<<1<<' '<<1<<'\n';
    cout<<1<<" "<<1<<" "<<2<<"\n";
}
signed main() 
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    IOS;

    int _ = 1; //cin >> _;
    while (_--) solve();
    return 0;
}

小红的 red 计数

red 长度只有3 用线段树维护 r,e,d,re,rd,ed,red,ew,de,dr,der。
搜索 l r是只需要搜 0~l-1 l~r r+1,n
反转l~r,然后将三个区间合并。
总体时间越nlogn

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
#define kl (k<<1)
#define kr (k<<1|1)

struct node
{
    int ll,rr;
    int r,e,d;//d e r
    int re,rd,ed;
    int er,dr,de;
    int red,der;
}tre[N<<2];
string s;
int n,m;

void pushup(node& op1,node& op2,node& op3)
{
    op1.r=op2.r+op3.r;
    op1.e=op2.e+op3.e;
    op1.d=op2.d+op3.d;

    op1.re=op2.re+op3.re+op2.r*op3.e;
    op1.rd=op2.rd+op3.rd+op2.r*op3.d;
    op1.ed=op2.ed+op3.ed+op2.e*op3.d;

    op1.er=op2.er+op3.er+op2.e*op3.r;
    op1.dr=op2.dr+op3.dr+op2.d*op3.r;
    op1.de=op2.de+op3.de+op2.d*op3.e;

    op1.red=op2.red+op3.red+op2.r*op3.ed+op2.re*op3.d;
    op1.der=op2.der+op3.der+op2.d*op3.er+op2.de*op3.r;
}



void build(int k,int l,int r)
{
    //tre[k].l=l;tre[k].r=r;
    tre[k]={l,r,0,0,0,0,0,0,0,0,0,0,0};
    if(l==r)
    {
        tre[k].r=(s[l]=='r');
        tre[k].e=(s[l]=='e');
        tre[k].d=(s[l]=='d');
        return;
    }
    int mid=(l+r)>>1;
    build(kl,l,mid);
    build(kr,mid+1,r);
    pushup(tre[k],tre[kl],tre[kr]);
}


node query(int k,int l,int r)
{
    if(l<=tre[k].ll&&tre[k].rr<=r) return tre[k];
    int mid=(tre[k].ll+tre[k].rr)>>1;

    node op1={0},op2={0},op3={0};
    int oop2=0,oop3=0;
    if(l<=mid) op2=query(kl,l,r),oop2=1;
    if(r>mid) op3=query(kr,l,r),oop3=1;
    if(oop2&&oop3) 
    {
        pushup(op1,op2,op3);
        return op1;
    }
    if(oop2) return op2;
    return op3;
}



void print_op(node op)
{
    cout<<"r "<<op.r<<"\n";
    cout<<"e "<<op.e<<'\n';
    cout<<"d "<<op.d<<'\n';
    cout<<"re "<<op.re<<'\n';
    cout<<"rd "<<op.rd<<'\n';
    cout<<"ed "<<op.ed<<'\n';
    cout<<"red "<<op.red<<'\n';
    cout<<"der "<<op.der<<'\n';
}

void solve() 
{
    cin>>n>>m;
    cin>>s;s=' '+s;
    build(1,1,n);
  //  print_op(tre[1]);cout<<'\n';
    while(m--)
    {
        int l,r;cin>>l>>r;
        node op1={0},op2={0},op3={0};
        op1=query(1,1,l-1);
        op2=query(1,l,r);
        op3=query(1,r+1,n);

        swap(op2.re,op2.er);
        swap(op2.rd,op2.dr);
        swap(op2.ed,op2.de);
        swap(op2.red,op2.der);

        node op12,op123;
        pushup(op12,op1,op2);
        pushup(op123,op12,op3);

    //    print_op(op1);
        
    
    //    print_op(op2);


     //   print_op(op3);


        cout<<op123.red<<'\n';
        //cout<<"\n\n\n";
    }
}

/*

r e d

red der red
r    e    d







*/
signed main() 
{
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    IOS;

    int _ = 1; //cin >> _;
    while (_--) solve();
    return 0;
}