2019.9.14校内考试

T1:

   发现正方形棋盘,其边长为2k(1<k<10),而且2k(1<k<10)-1能被3整除,就想到了分治(主要还是qbzt的老师讲过)。每次将大棋盘从中间分成4个正方形的小棋盘,根据坏点在第几个棋盘分类处理,最后在棋盘大小分为2的时候就可以结束递归了。

AC代码:

2019.9.14校内考试
 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int a,map[514][514],len[10]={1,2,4,8,16,32,64,128,256,512},k,ex,ey;
 7 
 8 void erfen(int zx,int zy,int yx,int yy,int hx,int hy)
 9 {
10     int zhongx=(zx+yx)>>1,zhongy=(zy+yy)>>1;
11     if(zhongx==zx&&zhongy==zy)//最后要终止递归时在分类把小棋盘剩下的未确认数的点填一下 
12     {
13         if(zx==hx&&zy==hy)
14         {
15             map[zx+1][zy]=map[zx+1][zy+1]=map[zx][zy+1]=4;
16         }
17         if(zx==hx&&zy+1==hy)
18         {
19             map[zx][zy]=map[zx+1][zy]=map[zx+1][zy+1]=3;
20         }
21         if(zx+1==hx&&zy==hy)
22         {
23             map[zx][zy]=map[zx][zy+1]=map[zx+1][zy+1]=2;
24         }
25         if(zx+1==hx&&zy+1==hy)
26         {
27             map[zx][zy]=map[zx+1][zy]=map[zx][zy+1]=1;
28         }
29         return;
30     }
31     if(hx<=zhongx&&hy<=zhongy)//已经确定数的点在左上
32     {
33         map[zhongx+1][zhongy+1]=map[zhongx+1][zhongy]=map[zhongx][zhongy+1]=4;
34         erfen(zx,zy,zhongx,zhongy,hx,hy);
35         erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy);
36         erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1);
37         erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1);
38     }
39     if(hx>zhongx&&hy<=zhongy)//已经确定数的点在左下 
40     {
41         map[zhongx+1][zhongy+1]=map[zhongx][zhongy]=map[zhongx][zhongy+1]=2;
42         erfen(zx,zy,zhongx,zhongy,zhongx,zhongy);
43         erfen(zhongx+1,zy,yx,zhongy,hx,hy);
44         erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1);
45         erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1);
46     }
47     if(hx<=zhongx&&hy>zhongy)//在右上 
48     {
49         map[zhongx+1][zhongy+1]=map[zhongx][zhongy]=map[zhongx+1][zhongy]=3;
50         erfen(zx,zy,zhongx,zhongy,zhongx,zhongy);
51         erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy);
52         erfen(zx,zhongy+1,zhongx,yy,hx,hy);
53         erfen(zhongx+1,zhongy+1,yx,yy,zhongx+1,zhongy+1);
54     }
55     if(hx>zhongx&&hy>zhongy)//在右下 
56     {
57         map[zhongx][zhongy+1]=map[zhongx][zhongy]=map[zhongx+1][zhongy]=1;
58         erfen(zx,zy,zhongx,zhongy,zhongx,zhongy);
59         erfen(zhongx+1,zy,yx,zhongy,zhongx+1,zhongy);
60         erfen(zx,zhongy+1,zhongx,yy,zhongx,zhongy+1);
61         erfen(zhongx+1,zhongy+1,yx,yy,hx,hy);
62     }
63 }
64 
65 void print()//输出矩阵 
66 {
67     for(int i=1;i<=a;i++)
68     {
69         for(int j=1;j<a;j++)
70             putchar(map[i][j]+'0'),putchar(' ');
71         putchar(map[i][a]+'0'),putchar('\n');
72     }
73 }
74 
75 int main()
76 {
77     freopen("chessboard.in","r",stdin);
78     freopen("chessboard.out","w",stdout);
79     cin>>k>>ey>>ex;
80     a=len[k];
81     map[ex][ey]=7;
82     erfen(1,1,a,a,ex,ey);
83     print();
84     return 0;
85 } 
View Code

T2:

   将前n-1条边与n个点组成的树建出来,用线段树维护在DFS序的一段区间的所有点中从根节点到某个点的路径长度加上这个点向上到根节点的路径长度之和的最小值。修改后n-1条边中的边为单点修改(只影响一个点回到根节点的路径长度),修改前n-1条边中的边为区间修改(影响从根节点到到 以该边终点为根的子树中所有点的路径的长度)。查询也分两种情况:y在x的子树中、y不在x的子树中。细节什么的看代码(by _rqy)吧:

2019.9.14校内考试
  1 #include <cstdio>
  2 #include <cctype>
  3 #include <vector>
  4 #define ll long long
  5 #include <algorithm>
  6 const ll maxn = 200005;
  7 const ll inf = 1e13;
  8 struct edge{
  9     ll from, to, w;
 10     edge(ll c, ll a, ll b):from(c), to(a),w(b){}
 11     edge(){}
 12 }e[maxn << 1];//存所有边(因为修改边时得看边的编号) 
 13 ll n, q, cnt, dfn, ans;
 14 ll fa[maxn][20];
 15 ll f[maxn], dep[maxn], deep[maxn], l[maxn], que[maxn], r[maxn];
 16 //dep(对应结构体里的dat)从根节点走到某个点的路径的长度
 17 //f 从某个点向上走到根节点的路径的长度==这个点连向根节点的边的长度 
 18 std::vector<ll> to[maxn];//树中的边 
 19 void add_edge(ll u, ll v, ll w) {
 20     e[++cnt] = edge(u, v, w); 
 21     to[u].push_back(cnt);
 22 }
 23 ll read() {
 24     ll x = 0, f = 1;
 25     char ch = getchar();
 26     while(!isdigit(ch)) {
 27     if(ch == '-') f = -1;
 28     ch = getchar();
 29     }
 30     while(isdigit(ch)) {
 31     x = x * 10 + ch - '0';
 32     ch = getchar();
 33     }
 34     return x * f;
 35 }
 36 struct seg{
 37     ll l, r, min, dat, tag1, tag2; //tag1:dep, tag2:f
 38 }t[maxn<<2];//线段树 
 39 void update(ll k) {
 40     t[k].min = std::min(t[k<<1].min, t[k<<1|1].min);
 41 }
 42 void pushdown(ll k) {
 43     if(t[k].l == t[k].r) return;
 44     if(t[k << 1].l == t[k<<1].r) t[k<<1].dat += t[k].tag1;
 45     if(t[k << 1|1].l == t[k<<1|1].r)t[k<<1|1].dat += t[k].tag1;
 46     t[k<<1].min += t[k].tag2 + t[k].tag1;
 47     t[k<<1|1].min += t[k].tag2 + t[k].tag1;
 48     t[k<<1].tag1 += t[k].tag1;
 49     t[k<<1].tag2 += t[k].tag2;
 50     t[k<<1|1].tag1 += t[k].tag1;
 51     t[k<<1|1].tag2 += t[k].tag2;
 52     t[k].tag1 = t[k].tag2 = 0;
 53 }
 54 void build(ll k, ll l, ll r) {//建线段树 
 55     t[k].l = l, t[k].r = r, t[k].tag1 = t[k].tag2 = 0;
 56     if(l == r) {
 57     t[k].min = dep[que[l]] + f[que[l]];
 58     t[k].dat = dep[que[l]];
 59     return;
 60     }
 61     ll mid = (l + r) >> 1;
 62     build(k << 1, l, mid);
 63     build(k << 1|1, mid+1, r);
 64     update(k);
 65 }
 66 void modify(ll k, ll x, ll y, ll a, ll arg = 0) {
 67     pushdown(k);
 68     ll l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
 69     if(x <= l && r <= y) {
 70     if(arg == 0) {//区间修改 
 71         t[k].tag1 += a; //tag1:由dat(或dep,毕竟dat和dep都一个意思)的变化而打的标记 
 72         t[k].min += a;
 73         if(t[k].l == t[k].r) t[k].dat += a;
 74     }
 75     else {//单点修改 
 76         t[k].tag2 += a;//tag2:由f的变化而打的标记 
 77         t[k].min += a;
 78     }
 79     return;
 80     }
 81     if(x <= mid) modify(k << 1, x, y, a, arg);
 82     if(y > mid) modify(k << 1|1, x, y, a, arg);
 83     update(k);
 84 }
 85 ll pos(ll k, ll p) {
 86     pushdown(k);
 87     ll l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
 88     if(l == r) return t[k].dat;
 89     if(p <= mid) return pos(k << 1, p);
 90     else return pos(k << 1|1, p);
 91 }
 92 ll query(ll k, ll x, ll y) {
 93     pushdown(k);
 94     ll l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
 95     if(x <= l && r <= y) return t[k].min;
 96     ll ans = inf;
 97     if(x <= mid) ans = std::min(ans, query(k << 1, x, y));
 98     if(y > mid) ans = std::min(ans, query(k << 1|1, x, y));
 99     return ans;
100 }
101 void dfs(ll x, ll fa) {
102     l[x] = ++dfn;
103     que[dfn] = x;
104     for(ll i = 0; i < to[x].size(); i++) {
105     ll v = e[to[x][i]].to;
106     if(v != fa) {
107         dep[v] = dep[x] + e[to[x][i]].w;
108         deep[v] = deep[x] + 1;
109         dfs(v, x);
110     }
111     }
112     r[x] = dfn;
113 }
114 void pre() {
115     scanf("%lld %lld", &n, &q);
116     for(ll i = 1; i < n; i++) {
117     ll u = read(), v = read();
118     add_edge(u, v, read());
119     fa[v][0] = u;
120     }
121     for(ll i = 1; i < n; i++) {
122     ll u = read(), v = read();
123     f[u] = read();
124     e[++cnt] = edge(u, v, f[u]);
125     }
126     for(ll i = 1; i <= 18; i++)
127     for(ll j = 1; j <= n; j++)
128         fa[j][i] = fa[fa[j][i-1]][i-1];
129     dfs(1, 0);
130     build(1, 1, dfn);
131 }
132 ll get(ll x, ll d) {
133     ll D = deep[x];
134     ll p = D - d;
135     if(p < 0) return -1;
136     ll u = x;
137     for(ll i = 18; i >= 0 && p; i--) {
138     if((1<<i) <= p) {
139         p -= (1<<i);
140         u = fa[u][i];
141     }
142     }
143     return u;
144 }
145 void solve() {
146     while(q--) {
147     ll k = read(), x = read(), y = read();
148     if(k == 2) {
149         if(x > (n-1)) {
150         modify(1, l[e[x].from], l[e[x].from], y - f[e[x].from], 1);
151         f[e[x].from] = y;
152         }
153         else {
154         ll delta = y - e[x].w;
155         ll u = e[x].to;
156         modify(1, l[u], r[u], delta);
157         e[x].w = y;
158         }
159     }
160     else {
161         ll k = get(y, deep[x]);
162         if(k == x) ans = pos(1, l[y]) - pos(1, l[x]);
163         else ans = query(1, l[x], r[x]) - pos(1, l[x]) + pos(1, l[y]);
164         printf("%lld\n", ans);
165     }
166     }
167 }
168 int main() {
169 #ifdef orz
170     freopen("input", "r", stdin);
171 #endif
172     pre();
173     solve();
174 }
View Code

T3:

   子任务1就是kmp裸题,没什么好说的。

   子任务2用一遍kmp优化一下加暴力就过了,也没什么好说的(主要还是数据水)。

      正解看不懂。。。

   子任务3用卷积(下标和为常数),没什么会说的。。。

见正解代码(by _rqy):

2019.9.14校内考试
  1 #include <algorithm>
  2 #include <cmath>
  3 #include <complex>
  4 #include <cstdio>
  5 #include <cstring>
  6 typedef long long LL;
  7 const int N = 1000000;
  8 char s[N], p[N];
  9 int n, m;
 10 int something[N];
 11 namespace Task1{
 12   int* const nxt = something;
 13   void getNxt() {
 14     nxt[0] = nxt[1] = 0;
 15     for (int i = 1, j = 0; i < m; ++i) {
 16       while (j && p[i] != p[j]) j = nxt[j];
 17       nxt[i + 1] = (p[i] == p[j] ? ++j : 0);
 18     }
 19   }
 20   void solve() {
 21     int ans1 = 0, ans2 = 0;
 22     getNxt();
 23     for (int i = 0, j = 0; i < n; ++i) {
 24       while (j && p[j] != s[i]) j = nxt[j];
 25       if (p[j] == s[i] && (++j == m)) {
 26         ++ans1;
 27         ans2 ^= i - m + 1;
 28       }
 29     }
 30     printf("%d %d\n", ans1, ans2);
 31   }
 32 };
 33 namespace Task2{
 34   int *const f = something;
 35   void getF() {
 36     f[0] = m;
 37     int rmax = 0, ri = 0;
 38     for (int i = 1; i < m; ++i) {
 39       f[i] = std::max(0, std::min(f[i - ri], rmax - i));
 40       while (p[f[i]] == p[i + f[i]]) ++f[i];
 41       if (i + f[i] > rmax)
 42         rmax = i + f[ri = i];
 43     }
 44   }
 45   void solve() {
 46     int ansv[4] = {0, 0, 0, 0};
 47     getF();
 48     int rmax = 0, ri = 0;
 49     for (int i = 0; i < n; ++i) {
 50       int ans = std::max(0, std::min(rmax - i, f[i - ri]));
 51       while (i + ans < n && ans < m && s[i + ans] == p[ans]) ++ans;
 52       if (i + ans > rmax)
 53         rmax = (ri = i) + ans;
 54       ansv[i % 4] ^= ans;
 55     }
 56     printf("%d %d %d %d\n", ansv[0], ansv[1], ansv[2], ansv[3]);
 57   }
 58 };
 59 namespace Task3{
 60   const int N = 400000;
 61   typedef std::complex<double> Complex;
 62   const double pi = acos(-1.0);
 63   Complex PA[N], PB[N];
 64   LL A[N], B[N], C[N];
 65   void FFT(Complex *P, int len, int opt) {
 66     for (int i = 1, j = len >> 1, k; i < len; ++i) {
 67       if (i < j) std::swap(P[i], P[j]);
 68       k = len;
 69       do j ^= (k >>= 1); while (~j & k);
 70     }
 71     for (int h = 2; h <= len; h <<= 1) {
 72       Complex wn = Complex(cos(2 * pi * opt / h), sin(2 * pi * opt / h));
 73       for (int j = 0; j < len; j += h) {
 74         Complex w = Complex(1.0, .0);
 75         for (int k = 0; k < h / 2; ++k) {
 76           Complex tmp = P[j + k], tmp2 = P[j + k + h / 2] * w;
 77           P[j + k] = tmp + tmp2;
 78           P[j + k + h / 2] = tmp - tmp2;
 79           w *= wn;
 80         }
 81       }
 82     }
 83     if (opt == -1) {
 84       for (int i = 0; i < len; ++i)
 85         P[i] /= len;
 86     }
 87   }
 88   void upd(LL *A, LL *B, LL *C, int n, int m) { //A += B[0..n-1] * C[0..m-1]
 89     int len = 1;
 90     while (len < n + m) len <<= 1;
 91     for (int i = 0; i < n; ++i) PA[i] = B[i];
 92     for (int i = n; i < len; ++i) PA[i] = .0;
 93     for (int i = 0; i < m; ++i) PB[i] = C[i];
 94     for (int i = m; i < len; ++i) PB[i] = .0;
 95     FFT(PA, len, 1);
 96     FFT(PB, len, 1);
 97     for (int i = 0; i < len; ++i)
 98       PA[i] *= PB[i];
 99     FFT(PA, len, -1);
100     for (int i = 0; i < len; ++i)
101       A[i] += (LL)(PA[i].real() + (PA[i].real() > 0 ? 0.5 : -0.5));
102   }
103   inline LL sqr(LL x) { return x * x; }
104   inline LL cube(LL x) { return x * x * x; }
105   void solve() {
106     for (int i = 0; i < n; ++i)
107       B[i] = sqr(s[i] - 'a' + 1);
108     for (int i = 0; i < m; ++i)
109       C[i] = (p[m - i - 1] == '?' ? 0 : p[m - i - 1] - 'a' + 1);
110     upd(A, B, C, n, m);
111     for (int i = 0; i < n; ++i)
112       B[i] = -2 * (s[i] - 'a' + 1);
113     for (int i = 0; i < m; ++i)
114       C[i] = sqr(C[i]);
115     upd(A, B, C, n, m);
116     LL t = 0;
117     for (int i = 0; i < m; ++i) if (p[i] != '?')
118       t += cube(p[i] - 'a' + 1);
119     int ans1 = 0, ans2 = 0;
120     for (int i = 0; i <= n - m; ++i) if (A[i + m - 1] == -t) {
121       ++ans1;
122       ans2 ^= i;
123     }
124     printf("%d %d\n", ans1, ans2);
125   }
126 }
127 int main() {
128   int task;
129   scanf("%d%s%s", &task, s, p);
130   n = strlen(s);
131   m = strlen(p);
132   if (task == 1) Task1::solve();
133   if (task == 2) Task2::solve();
134   if (task == 3) Task3::solve();
135   return 0;
136 }
View Code

 

上一篇:枚举类和注解


下一篇:多进程