Ysmmm的快乐小屋

A. 树 并查集 + dfs + 离线1234567891011121314151617181920212223242526272829303132333435363738394041const int N=1e5+2;char s[N][2];int x,y,a[N],b[N],fa[N],f[N];int n,m,cnt,hd[N],to[N],nxt[N],ans[N];void add(int x,int y){ to[++cnt]=y; nxt[cnt]=hd[x]; hd[x]=cnt;}void dfs(int x,int fat){ if(b[x])f[x]=x; else f[x]=f[fat]; fa[x]=fat; for(int i=hd[x];i;i=nxt[i]) dfs(to[i],x);}int find(int x){ return x==f[x]?x:f[x]=find(f[x]);}int main(){ scanf("%d%d",&n,&m ...

A. 闹市 在树上做差分， 求lca 最后再跑一遍dfs1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465const int N = 1e6+10;int n,k;struct{ int to,nex;}edge[N<<1];int head[N<<1],edge_num;inline void add(int x,int y){ edge[++edge_num].to = y; edge[edge_num].nex = head[x]; head[x] = edge_num;}int fa[N][25],dep[N];inline void dfs(int now,int fu){ fa[now][0] = fu; dep[now] = dep[fu]+1; for(int i=1;(1<<i)<=dep ...

A. 拆盒子 贪心贪过去就好了123456789101112131415signed main() { IOS; string s; cin >> s; int len = s.size(); int sum = 0; for (int i = 0; i < len; i++) { if (s[i] == '(') sum++; else if(s[i] == ')') sum--; else break; } cout << sum << endl; return 0;} B. 数组调整 枚举最小值，算最大值就好了123456789101112131415161718192021signed main() { IOS; int n; cin >> n; vector<int> v(n); for (int ...

A. 苹果树2 用线段树去维护dfs序的连续性1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include<bits/stdc++.h>#define M 200001using namespace std;int n,m,tot;int A[M],to[M];int L[M],R[M];vector<int>Q[M];class { public: int l,r,v;} tree[M<<2];void dfs(int x,int q) { L[x]=++tot,to[tot]=x; for(int i=0; i<Q[x].size(); ++i) { int y=Q[x][i]; if(y==q)continue; dfs(y,x); } R[x]=to ...

A. 俄罗斯国旗 直接模拟就好了12345678910111213141516171819202122232425262728293031#define MAX 55int W[MAX], B[MAX], R[MAX];string mp[MAX];signed main() { IOS; int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> mp[i]; mp[i] = ' ' + mp[i]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { W[i] += mp[i][j] != 'W'; B[i] += mp[i][j] != 'B'; R[i] += mp[i][j] != 'R'; } W[i] += W[i - ...

123456789101112void tarjan(int u,int eid) { dfn[u]=low[u]=++indx; stk[++tp]=u; for(int i=head[u]; ~i; i=edge[i].nxt) { int v=edge[i].to; if(dfn[v]==0) { tarjan(v,i); low[u]=min(low[u],low[v]); } if(i!=(eid^1)) low[u]=min(low[u],dfn[v]); }} A. 桥（割边）- 1234567891011121314151617181920212223242526272829303132333435363738const int N=3e4+10;int n,m,a,b;vector<pair<int,int> >g[N];int dfn[N],low[N],cnt,ans;void DFS(int u,int bef){ dfn[u]=low[u]=++cn ...

A. 三人三数 比一下就好了1234567891011121314151617181920212223signed main() { IOS; int ans = 0; int n, a, b, c, d, e, f; cin >> n >> a >> b >> c >> d >> e >> f; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= n; k++) {#define ch(x, y) min(abs(x - y), n - abs(x - y)) if (ch(a, i) <= 2 && ch(b, j) <= 2 && ch(c, k) <= 2) { ...

A. 搬草啦12345678910111213141516171819202122signed main() { IOS; int n; cin >> n; vector<int> v(n + 1); int sum = 0; for (int i = 1; i <= n; i++) { cin >> v[i]; sum += v[i]; } int tmp = sum / n; int res = 0; for (int i = 1; i <= n; i++) { if (v[i] < tmp) { res += tmp - v[i]; } } cout << res << endl; return 0;} B. 电泳技术 直接模拟写就好了123456789101112 ...

A. 文本校对 暴力HASH就好了1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495const int N = 1e6 + 5, base = 19260817, mod = 998244353;int n, m, h[N], pw[N], inv[N], now[N];string s;ll qpow(int x, int y){ ll res = 0; while (y) { if (y & 1) res = res * x % mod; x = x * x % mod; y >>= 1; } return res;}voi ...

A. 青蛙跳 根号分治去解决12345678910111213141516171819202122232425#define M 100005using namespace std;int A[M],sum[340][M];int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&A[i]); int S=sqrt(n); for(int i=n;i>=1;i--) for(int j=1;j<=S;j++) sum[j][i]=sum[j][i+j]+A[i]; for(int i=1;i<=m;i++){ int a,b; scanf("%d %d",&a,&b); if(b<=S){ printf("%d\n",sum[b][a]); }else{ int r ...