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;
}