CSP-S 模拟 19/10/07

CSP-S 模拟 19/10/07

​​梦回幼儿园​​​

#include#define N 10000050using namespace std;namespace IO{ inline char gc(){ static const int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; } inline int read(){return get();}}using namespace IO;int n, a[N], x;int main(){ n = read(); for(int i = 1; i <= n; i++) a[i] = read(), x ^= a[i]; int p = 0; for(;p < 31; p++) if((1 << p) & x) break; p = 1 << p; int A = 0, B = 0; for(int i = 1; i <= n; i++) if(a[i] & p) A ^= a[i]; x ^= A; B = x; if(A > B) swap(A, B); cout << A << " " << B; return 0;}

​​树的问题​​​

#include#define N 2050using namespace std;int read(){ int x = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x + (x << 2) << 1) + (ch ^ 48), ch = getchar(); return x;}void Mx(int &a, int b){ if(a < b) a = b; }int n, k;vector v[N];int f[N]; // longest_dis int l1[N], l2[N], l3[N]; int t1[N], t2[N]; // fromint s1[N], s2[N];int ans;void dfs(int u, int fa){ f[u] = l1[u] = l2[u] = l3[u] = t1[u] = t2[u] = s1[u] = s2[u] = 0; for(int i = 0; i < v[u].size(); i++){ int t = v[u][i]; if(t == fa) continue; dfs(t, u); Mx(f[u], f[t]); if(f[t] > f[s1[u]]) s2[u] = s1[u], s1[u] = t; else if(f[t] > f[s2[u]]) s2[u] = t; int l = l1[t] + 1; if(l > l1[u]){ l3[u] = l2[u], l2[u] = l1[u], l1[u] = l; t2[u] = t1[u]; t1[u] = t; } else if(l > l2[u]){ l3[u] = l2[u], l2[u] = l, t2[u] = t; } else if(l > l3[u]) l3[u] = l; } Mx(f[u], l1[u] + l2[u]);}const int len = 2000, inf = 0x3fffffff;struct Segmentree{ int mx[N << 4]; void pushup(int x){ mx[x] = max(mx[x<<1], mx[x<<1|1]); } int modify(int x, int l, int r, int p, int v){ if(l == r){ int pre = mx[x]; mx[x] = v; return pre;} int mid = (l+r) >> 1, ans = 0; if(p <= mid) ans = modify(x<<1, l, mid, p, v); else ans = modify(x<<1|1, mid+1, r, p, v); pushup(x); return ans; } int query(int x, int l, int r, int L, int R){ if(L<=l && r<=R) return mx[x]; int mid = (l+r) >> 1, ans = 0; if(L<=mid) ans = max(ans, query(x<<1, l, mid, L, R)); if(R>mid) ans = max(ans, query(x<<1|1, mid+1, r, L, R)); return ans; } int mo(int x, int v){ x += len; return modify(1, 1, n + len, x, v);} int ask(int l, int r){ l += len, r += len; return query(1, 1, n + len, l, r);}}Seg;void solve(int u, int fa, int d, int lim){ if(d > lim) return; int tmp = Seg.ask(k - l1[u] - d + 1, n); if(f[u] <= k && 0 <= k - l1[u] - tmp + 1) ++ans; for(int i = 0; i < v[u].size(); i++){ int t = v[u][i]; if(t == fa) continue; int mxl = t == s1[u] ? f[s2[u]] : f[s1[u]]; if(t == t1[u]) Mx(mxl, l2[u] + l3[u]); else if(t == t2[u]) Mx(mxl, l1[u] + l3[u]); else Mx(mxl, l1[u] + l2[u]); if(mxl > k) continue; int l = (t == t1[u]) ? l2[u] : l1[u]; int tmp = Seg.ask(k - l - d + 1, n); if(tmp == 0) tmp = -inf; tmp = k + d + 1 - l - tmp; int pre = Seg.mo(l-d, l+d); solve(t, u, d + 1, min(lim, tmp)); Seg.mo(l-d, pre); }}int main(){ n = read(); k = read(); for(int i = 2; i <= n; i++){ int x = read() + 1; v[x].push_back(i); v[i].push_back(x); } dfs(1, 0); if(f[1] <= k) { cout << n * (n+1) / 2; return 0; } for(int i = 1; i <= n; i++){ if(i^1) dfs(i, 0); solve(i, 0, 1, n); } cout << (ans >> 1); return 0;}

​​序列​​​

#include#define N 500050using namespace std;int read(){ int x = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = (x + (x << 2) << 1) + (ch ^ 48), ch = getchar(); return x;}const int Mod = 1e9 + 7;int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b;}int mul(int a, int b){ return 1ll * a * b % Mod;}int n, m, a[N], b[N];struct Node{ int A, B; Node operator * (const Node &a){ return (Node){mul(A, a.A), add(mul(B, a.A), a.B)}; }}sum[N << 2];void pushup(int x){sum[x] = sum[x<<1] * sum[x<<1|1];}void build(int x, int l, int r){ if(l == r){ sum[x] = (Node){a[l], b[l]}; return; } int mid = (l+r) >> 1; build(x<<1, l, mid); build(x<<1|1, mid+1, r); pushup(x);}void modify(int x, int l, int r, int p){ if(l == r){ sum[x] = (Node){a[l], b[l]}; return; } int mid = (l+r) >> 1; if(p <= mid) modify(x<<1, l, mid, p); else modify(x<<1|1, mid+1, r, p); pushup(x);}Node query(int x, int l, int r, int L, int R){ if(L<=l && r<=R) return sum[x]; int mid = (l+r) >> 1; if(L>mid) return query(x<<1|1, mid+1, r, L, R); else if(R<=mid) return query(x<<1, l, mid, L, R); else return query(x<<1, l, mid, L, R) * query(x<<1|1, mid+1, r, L, R);}int main(){ n = read(), m = read(); for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(); build(1, 1, n); while(m--){ char op[3]; scanf("%s", op); if(op[0] == 'Q'){ int k = read(); Node ans = query(1, 1, n, 1, k); cout << add(ans.A, ans.B) << '\n'; } if(op[0] == 'C'){ int k = read(), A = read(), B = read(); a[k] = A; b[k] = B; modify(1, 1, n, k); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。