这道题就是一道模拟题 也没有什么细节 反正蛮好写的
代码
#include <bits/stdc++.h> using namespace std; const int N = 1005; int hx, hy, lx, ly, now, ma, h; int vis[2 * N][2 * N], T; char opt[105]; void deal(int sta, char opt, int del) { if(sta == 1) { if(opt == 'E' || opt == 'W') { if(opt == 'E') hx = hx + h, lx = lx + 1; if(opt == 'W') hx = hx - 1, lx = lx - h; for(int i = lx;i < hx;i ++) { vis[i][ly] += del; if(vis[i][ly] > ma) ma = vis[i][ly]; } now = 3; return ; } if(opt == 'N' || opt == 'S') { if(opt == 'N') hy = hy + h, ly = ly + 1; if(opt == 'S') hy = hy - 1, ly = ly - h; for(int i = ly;i < hy;i ++) { vis[lx][i] += del; if(vis[lx][i] > ma) ma = vis[lx][i]; } now = 2; return ; } } if(sta == 2) { if(opt == 'E' || opt == 'W') { if(opt == 'E') hx = hx + 1, lx = lx + 1; if(opt == 'W') hx = hx - 1, lx = lx - 1; for(int i = ly;i < hy;i ++) { vis[lx][i] += del; if(vis[lx][i] > ma) ma = vis[lx][i]; } now = 2; return ; } if(opt == 'N' || opt == 'S') { if(opt == 'N') hy = hy + 1, ly = ly + h; if(opt == 'S') hy = hy - h, ly = ly - 1; for(int i = ly;i < hy;i ++) { vis[lx][i] += del; if(vis[lx][i] > ma) ma = vis[lx][i]; } now = 1; return ; } } if(sta == 3) { if(opt == 'E' || opt == 'W') { if(opt == 'E') hx = hx + 1, lx = lx + h; if(opt == 'W') hx = hx - h, lx = lx - 1; for(int i = lx;i < hx;i ++) { vis[i][ly] += del; if(vis[i][ly] > ma) ma = vis[i][ly]; } now = 1; return ; } if(opt == 'N' || opt == 'S') { if(opt == 'N') hy = hy + 1, ly = ly + 1; if(opt == 'S') hy = hy - 1, ly = ly - 1; for(int i = lx;i < hx;i ++) { vis[i][ly] += del; if(vis[i][ly] > ma) ma = vis[i][ly]; } now = 3; return ; } } } void Solve( ) { while(T --) { scanf("%d",& h); scanf("%s",opt + 1); int len = strlen(opt + 1); lx = 1000, ly = 1000, hx = 1001, hy = 1001; ma = 1; now = 1; vis[1000][1000] = 1; for(int i = 1;i <= len;i ++) { deal(now, opt[i], 1); } if(now == 1) { printf("%d %d ", lx - 1000, ly - 1000); } if(now == 2) { for(int i = ly;i < hy;i ++) { if(i != hy - 1) printf("%d ", lx - 1000); else printf("%d ", lx - 1000); } for(int i = ly;i < hy;i ++) { if(i != hy - 1) printf("%d ", i - 1000); else printf("%d ", i - 1000); } } if(now == 3) { for(int i = lx;i < hx;i ++) { if(i != hx - 1) printf("%d ", i - 1000); else printf("%d ", i - 1000); } for(int i = lx;i < hx;i ++) { if(i != hx - 1) printf("%d ", ly - 1000); else printf("%d ", ly - 1000); } } printf("%d ",ma); lx = 1000, ly = 1000, hx = 1001, hy = 1001; ma = 0; now = 1; vis[1000][1000] = 0; for(int i = 1;i <= len;i ++) { deal(now, opt[i], -1); } } } int main( ) { freopen("block.in","r",stdin); freopen("block.out","w",stdout); scanf("%d",& T); Solve( ); }
第二题是一个数论题 然后我们都没有弄出来 就先不改了
这道题本来是哈希的 然后zjj同学写了可持久化线段树 我就学习了一波可持久化线段树
哈希的做法是 对于每一个节点 维护一个对他进行操作的哈希值
比如我对这个节点进行过$12345$操作 那么就将这个玩意儿变成一个哈希值 就是那个乘$base$ + 'char'的那个玩意儿
最后查询每个节点和标准串的哈希值 如果一样答案就加一
那么现在是zjjdalao的做法 是对于每一个节点维护三个值 $max,min,tag$
分别表示在该区间内进行的操作的最大值 最小值 以及这个区间内是否还有合法的 如果有就是$1$ 否则为$0$
然后一些东西写在注释里面了
代码
#include <bits/stdc++.h> using namespace std; const int N = 2 * 1e5 + 5; int n,k,t,ans; struct node { int ma, mi; bool tag; node(int mi = 0, int ma = 0, bool tag = 0) : mi(mi),ma(ma),tag(tag) { } }f[4 * N]; void update(int o) { if(f[2 * o].tag && f[2 * o + 1].tag) { f[o] = node(min(f[2 * o].mi, f[2 * o + 1].mi), max(f[2 * o].ma, f[2 * o + 1].ma), 1); } else if(f[2 * o].tag) { f[o] = node(f[2 * o].mi, f[2 * o].ma, 1); } else if(f[2 * o + 1].tag) { f[o] = node(f[2 * o + 1].mi, f[2 * o + 1].ma, 1); } else f[o].tag = 0; } void build(int o, int l, int r) { if(l == r) { f[o] = node(0, 0, 1); return ; } int mid = l + r >> 1; build(2 * o, l, mid); build(2 * o + 1, mid + 1, r); update(o); } void modify(int o, int l, int r, int L, int R, int x) { if(l >= L && r <= R) { if(f[o].ma == f[o].mi) { if(f[o].ma == x) { f[o] = node(f[o].mi + 1, f[o].ma + 1, 1); return ;// 如果这个节点合法 就给它升级 } else { f[o].tag = 0; return ;//不合法 } } } int mid = l + r >> 1; if(f[o].ma == f[o].mi) f[2 * o].mi = f[2 * o].ma = f[2 * o + 1].ma = f[2 * o + 1].mi = f[o].ma; //下放标记 如果我之前访问到这里直接return 现在儿子未作修改 就会出问题 if(L <= mid && f[2 * o].tag) modify(2 * o, l, mid, L, R, x); //只有合法我才去走 否则可能被一行的下放标记救活 直接错掉 并且这样才能保证时间复杂度 if(mid < R && f[2 * o + 1].tag) modify(2 * o + 1, mid + 1, r, L, R, x); update(o); } void Init( ) { scanf("%d%d",& n,& k); build(1, 1, n); scanf("%d",& t); for(int i = 1;i <= t;i ++) { int l, r, k; scanf("%d%d%d",& l, & r, & k); modify(1, 1, n, l, r, k - 1); } } void dfs(int o, int l, int r) { if(l == r) { if(f[o].ma == k) ans ++; return ; } int mid = l + r >> 1; if(f[2 * o].tag) { if(f[o].mi == f[o].ma) { f[2 * o].mi = f[2 * o].ma = f[o].mi; }//一边走一边下放标记 dfs(2 * o, l, mid); } if(f[2 * o + 1].tag) { if(f[o].mi == f[o].ma) { f[2 * o + 1].mi = f[2 * o + 1].ma = f[o].ma; } dfs(2 * o + 1, mid + 1, r); } } int main( ) { freopen("deco.in","r",stdin); freopen("deco.out","w",stdout); Init( ); dfs(1, 1, n); printf("%d ",ans); }