F. 清楚姐姐学树状数组

思路

tag: 树状数组，树的遍历

/*悲观看待成功，乐观看待失败。 author：leimingze 
*/#include
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=131;
#define YES cout<<"YES"<
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
int n,k,q;
int l,m,r;
int sz(int x)//包括x在内的x子树的节点个数 
{return (lowbit(x)<<1)-1;
} 
bool is_left_child(int x)//判断x是否为其父节点的左孩子，lowbit(x)的前一位是0则是 
{return !(x&(lowbit(x)<<1));
}
int fa(int x)//求父亲节点 
{return is_left_child(x)?x+lowbit(x):x-lowbit(x);//如果是左孩子则其父节点是x-lowbit(x),否则x+lowbit(x) 
} 
int lch(int x)//求左孩子,把x的最低位1置0，把x的最低位1的下一位置为1 得到 左孩子 
{return x^lowbit(x)^(lowbit(x)>>1);
} 
int rch(int x)
{return x^(lowbit(x)>>1);//把x的最低位1的下一位置为1 得到右孩子 	
} 
int VLR(int x)
{int rt=n;int pos=1;while(rt!=x){pos++;if(xpos+=sz(lch(rt));rt=rch(rt);}}return pos;
}
int LRD(int x)
{if(x==n)return n;int rt=x;int pos=sz(rt);while(rt!=n){if(rt==rch(fa(rt)))pos+=sz(lch(fa(rt)));rt=fa(rt);}return pos;
}
void solve()
{cin>>k>>q;n=1ll<int x;cin>>x;cout<io;int _;_=1;//cin>>_;while(_--)solve();
}

G. 清楚姐姐逛街(Easy Version)

思路

tag：搜索，暴力
先预处理zngg到达每个点的时间，然后qcjj按照地标走

const int N=1010;
int n,m;
int startx,starty;
int q;
char g[N][N];
int dist[N][N];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
PII get(char c,int x,int y)
{if(c=='L')if(g[x][y-1]!='#')return {x,y-1};if(c=='R')if(g[x][y+1]!='#')return {x,y+1};if(c=='U')if(g[x-1][y]!='#')return {x-1,y};if(c=='D')if(g[x+1][y]!='#')return {x+1,y};return {x,y};
}
void bfs()
{queueq;q.push({startx,starty});dist[startx][starty]=0;while(q.size()){auto t=q.front();q.pop();for(int i=0;i<4;i++){int a=dx[i]+t.x,b=dy[i]+t.y;if(a<0||a>=n||b<0||b>=m)continue;if(g[a][b]=='#')continue;if(dist[a][b]!=0x3f3f3f3f)continue;dist[a][b]=dist[t.x][t.y]+1;q.push({a,b});}}
}
int find(int x,int y)
{int cnt=1;int res=ll_INF;while(cnt<=n*m){auto t=get(g[x][y],x,y);int a=t.x,b=t.y;if(a==x&&b==y){if(dist[a][b]==0x3f3f3f3f)return -1;}if(dist[a][b]<=cnt)res=min(res,max(dist[a][b],cnt));cnt++;x=a,y=b;}return res;
}
void solve()
{cin>>n>>m>>startx>>starty>>q;rep(i,0,n-1)rep(j,0,m-1)cin>>g[i][j],dist[i][j]=0x3f3f3f3f;bfs();while(q--){int x,y;cin>>x>>y;cout<

int va,vb,vc;
void solve()
{cin>>va>>vb>>vc;int a=vb+vc-va;int b=va+vc-vb;int c=va+vb-vc;if(a%2||b%2||c%2)NO;else if(a+b>c&&a+c>b&&b+c>a&&abs(a-b)YES;cout<

const int N=1e5+10;
int a[N];
int n;
void solve()
{cin>>n;a[1]=a[2]=1;a[3]=2;for(int i=4;i<=n;i+=3){a[i]=a[i-3];a[i+1]=a[i-2];a[i+2]=a[i-1];}rep(i,1,n)cout<