牛客周赛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 rint 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 dred 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;
}