应姚神的要求写一点比赛总结 (bī bī) … 还有一些题解 (kǒu hú) 啥的。

RMK:感觉就是个流水账。(完结)

Todo List (Table)

A B C D E F G H I J K
$\sqrt{}$ $\sqrt{}$ AC AC ? AC ?
? AC WA TLE AC $\sqrt{}$ $\sqrt{}$
AC AC AC AC ? AC AC
AC AC ? ? RE ?
AC AC ? $\sqrt{}$ $\sqrt{}$ $\sqrt{}$ TLE WA
AC AC AC AC AC ? AC
? AC $\sqrt{}$ AC AC
RE WA AC $\sqrt{}$ ? AC AC

第一场

鸽了,大家都在社会实践。

第二场

虽然还在社会实践,但我抽空看了会题。
先发现F是个大暴力,然而学长没有写。

F.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 31;
ll v[N][N]; int n;

ll ans = 0;
void dfs(int k, ll sta, ll sum, int cnt)
{
if(cnt == n) { ans = max(ans, sum); return; }
if(2*n-k < n-cnt) return;
dfs(k+1, sta, sum, cnt);
ll new_sum = sum;
rep(i, 0, 2*n-1)
if(i == k) continue;
else if((1<<i)&sta) new_sum -= v[i][k];
else new_sum += v[i][k];
dfs(k+1, sta|(1<<k), new_sum, cnt+1);
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n);
rep(i, 0, 2*n-1) rep(j, 0, 2*n-1) read(v[i][j]);

dfs(1, 0, 0, 0);
printf("%lld", ans);
}

看到H觉得挺眼熟的,不过学长在写我就没细想。
结束后补了一下H复习一下单调栈。

H.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 1010;
int n, m; char mat[N][N];

int up[N][N], l[N][N], r[N][N];
int UP(int i, int j) { return i >= 0 ? up[i][j] : 0; }

int area[2];
pair<P, P> rect[2];

void solv(int row)
{
static P stk[N];
int t = 0;
stk[t++] = mkp(0, -1);
rep(j, 0, m-1)
{
while(t && stk[t-1].X >= up[row][j]) t--;
l[row][j] = t ? stk[t-1].Y+1 : j;
stk[t++] = mkp(up[row][j], j);
}

t = 0;
stk[t++] = mkp(0, m);
per(j, m-1, 0)
{
while(t && stk[t-1].X >= up[row][j]) t--;
r[row][j] = t ? stk[t-1].Y-1 : j;
stk[t++] = mkp(up[row][j], j);
}

rep(j, 0, m-1)
{
int cur = (r[row][j]-l[row][j]+1)*up[row][j];
pair<P, P> tmp = mkp(mkp(row-up[row][j]+1, l[row][j]),
mkp(row, r[row][j]));

if(cur > area[0])
{
area[1] = area[0]; rect[1] = rect[0];
area[0] = cur; rect[0] = tmp;
}
else if(rect[0] == tmp) continue;
else if(cur > area[1]) area[1] = cur, rect[1] = tmp;
}
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); read(m);
rep(i, 0, n-1) scanf("%s", mat[i]);
rep(i, 0, n-1) rep(j, 0, m-1)
up[i][j] = mat[i][j] == '1' ? UP(i-1, j) + 1 : 0;

rep(i, 0, n-1) solv(i);
int w = rect[0].Y.X-rect[0].X.X+1,
h = rect[0].Y.Y-rect[0].X.Y+1,
ans = max(area[1], max((w-1)*h, w*(h-1)));
printf("%d", ans);
}

D跟J想了一会,觉得不太可做。

D还是挺神奇的…
题面应该是这场比赛中最短的了,题意是求k小团($k\leq 10^6$)。
从空集开始暴力BFS即可(很像dijkstra)。

D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 110;
typedef __int128 big;
typedef pair<ll, pair<int, big>> node;
char g[N][N]; int n, k;
big msk[N]; ll w[N];

priority_queue<node, vector<node>, greater<node> > q;
ll solv()
{
q.push(mkp((ll)0, mkp(-1, (big)0)));
while(!q.empty())
{
node cur = q.top(); q.pop();
if(--k == 0) return cur.X;
rep(i, cur.Y.X+1, n-1)
if((((big)1<<i)&cur.Y.Y) == 0 && (cur.Y.Y&msk[i]) == cur.Y.Y)
q.push(mkp(cur.X+w[i], mkp(i, cur.Y.Y|((big)1<<i))));
}
return -1;
}

int main()
{
freopen("std.in", "r", stdin);
read(n); read(k);
rep(i, 0, n-1) read(w[i]);
rep(i, 0, n-1) scanf("%s", g[i]);

rep(i, 0, n-1) rep(j, 0, n-1)
if(g[i][j] == '1') msk[i] |= (big)1<<j;
printf("%lld", solv());
}

然后我们爆零了???
赛后发现A和B是两道水题…A猜个结论,B线性递推乱搞搞。
E也挺有意思的,不过开始题看错了。

题意:一个$n*m$的棋盘($n\leq 50000, m\leq 10$),某些点的状态是墙,可以左右移动或者向下移动。每次操作或询问$(1, x_i)$到$(n, y_i)$的路径方案数,或修改点$(x_i, y_i)$的状态。


口胡
记$f(i, j)$为从$(1, x_i)$出发,经过$(i-1, j)$走到$(i, j)$的方案数,很容易写出状态方程。
然后每一行的转移可以写成一个矩阵,将所有行的矩阵乘起来得到$M$,答案就是$M_{x_iy_i}$。
每次修改都只会修改所在行的矩阵,用线段树维护这些矩阵的乘积即可。

E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 12, M = 50010;
const ll Z = 1e9+7;

int m, n, q;
struct matrix
{
ll a[N][N];
ll* operator [] (int idx) { return a[idx]; }
matrix operator * (matrix b)
{
matrix c;
rep(i, 0, n-1) rep(j, 0, n-1)
{
c[i][j] = 0;
rep(l, 0, n-1) (c[i][j] += a[i][l]*b[l][j]%Z) %=Z;
}
return c;
}
} sgt[M*4], w[M], id;
void build(int i, int b, int e)
{
if(b == e) { sgt[i] = w[b]; return; }
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
build(lc, b, mid); build(rc, mid+1, e);
sgt[i] = sgt[lc] * sgt[rc];
}
matrix query(int i, int b, int e, int l, int r)
{
if(e<l || r<b) return id;
if(l<=b && e<=r) return sgt[i];
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
return query(lc, b, mid, l, r) * query(rc, mid+1, e, l, r);
}
void modify(int i, int b, int e, int x)
{
if(b == e) { sgt[i] = w[b]; return; }
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
if(x <= mid) modify(lc, b, mid, x); else modify(rc, mid+1, e, x);
sgt[i] = sgt[lc] * sgt[rc];
}

char maze[M][N];
void init(int row)
{
int lst = 0;
rep(h, 0, n-1) rep(l, 0, n-1) w[row][h][l] = 0;
rep(i, 0, n-1)
{
if(maze[row][i] == '1') lst = i+1;
else if(i == n-1 || maze[row][i+1] == '1')
{
// [lst, i] consecutive 0
rep(h, lst, i) rep(l, lst, i) w[row][h][l] = 1;
}
}
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(m); read(n); read(q);
rep(i, 0, m-1) scanf("%s", maze[i]), init(i);
build(1, 0, m-1);

rep(i, 1, q)
{
int x, y, z; read(x); read(y); read(z);
y--; z--;
if(x == 1)
{
maze[y][z] = maze[y][z] == '1' ? '0' : '1';
init(y); modify(1, 0, m-1, y);
}
else
{
ll ans = 0;
if(maze[0][y] == '0' && maze[m-1][z] == '0')
ans = sgt[1][y][z];
printf("%lld\n", ans);
}
}
}

J目前还不会。

第三场

说实话,比赛体验极差,只过了签到题。
B还WA了一次,漏了一个初始条件。后来开了个D,找出循环节后就一直WA到比赛结束…
自我检讨一下:

  1. 打了一年cf…不太习惯多校的出题风格
  2. 校赛后就没怎么写题,荒废了好久
  3. 刚回家比较迷糊

(找了这么多借口,掩盖不了我太菜了的事实orz)

  1. A:没见过,看到奇怪的区间修改想到了分块,不过想了一会不知道怎么下手。
  2. B:签到题
  3. D:小学生都知道的$1\cdots 1=\frac{10^{k+1}-1}{9}$,我当时给忘了,循环节是打表看出来的… 之后的计数一直wa,我是固定i算j的我感觉没问题啊…弃疗了(ps:标算是固定j算i的)
  4. F:$O(n^3)$枚举上下边界和右边界,然后单调队列搞一搞就好了,不过我再一次看错题,看成了$n*m$的矩阵orz
  5. H:是学长写的
  6. J:是个大模拟?早知道让队友写了…

补题:
A用了根号算法的想法,记得有一篇集训队论文(2014《根号算法——不只是分块》)详细的讨论过这种做法。
F我的$O(n^3)$超时了…可能写的比较丑。

F.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 502;
int max_w[N][N][N], min_w[N][N][N];
int max_q[N], min_q[N], max_i[N], min_i[N];
int n, m, a[N][N], h1, t1, h2, t2;

inline bool jud() { return max_q[h1] - min_q[h2] <= m; }
inline void upd(int l)
{
while(h1 != t1 && max_i[h1] < l) h1++;
while(h2 != t2 && min_i[h2] < l) h2++;
}
inline void ins(int max_x, int min_x, int r)
{
while(h1 != t1 && max_x >= max_q[t1-1]) t1--;
while(h2 != t2 && min_x <= min_q[t2-1]) t2--;
max_q[t1] = max_x; max_i[t1++] = r;
min_q[t2] = min_x; min_i[t2++] = r;
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
int T; read(T);
while(T--)
{
read(n); read(m);
rep(i, 1, n) rep(j, 1, n) read(a[i][j]);
rep(i, 1, n) rep(up, 1, n)
{
max_w[i][up][up] = min_w[i][up][up] = a[up][i];
rep(dn, up+1, n)
max_w[i][up][dn] = max(max_w[i][up][dn-1], a[dn][i]),
min_w[i][up][dn] = min(min_w[i][up][dn-1], a[dn][i]);
}

int ans = 0;
rep(up, 1, n) rep(dn, up, n)
{
h1 = t1 = h2 = t2 = 0; int l = 1;
rep(r, 1, n)
{
ins(max_w[r][up][dn], min_w[r][up][dn], r);
while(l <= r && !jud()) upd(++l);
ans = max(ans, (r-l+1)*(dn-up+1));
}
}
printf("%d\n", ans);
}
}

G其实挺简单的…分治一下就好了,不过开始写了个朴素的分治T了。

题意:给定数列$a_1, …, a_n$,求满足$sum(a_l\cdots a_r)\geq 2*max(a_l\cdots a_r)~(l\leq r)$ 的$(l, r)$的个数。($n\leq 3\times 10^5$)


分治一波:对区间$[l, r]$,找到$a_l\cdots a_r$中的最大值,记为$a_{mid}$

  1. 然后处理[l, r]中包含$a_{mid}$的区间,这样就固定了max值;
  2. 之后递归处理$[l, mid-1]$和$[mid+1, r]$即可。

第1步用$O(n)$的做法是会T的(如双指针),比如$a$如果是递增的,整个复杂度就$O(n^2)$了。
考虑枚举$[l, mid]$和$[mid, r]$中长度较短的区间,然后对另一个区间二分,这样的话,就是$O(n\log^2{n})$的了。
另:找$a_{mid}$的过程可以用线段树或者st表。

G.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 3e5+10;
int n; ll a[N], pref[N], suff[N];

ll ans;
struct SegTree
{
ll sgt[N*4]; int idx[N*4];
void build(int i, int b, int e, ll *w)
{
if(b == e) { sgt[i] = w[b]; idx[i] = b; return; }
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
build(lc, b, mid, w); build(rc, mid+1, e, w);
sgt[i] = max(sgt[lc], sgt[rc]);
idx[i] = sgt[i] == sgt[lc] ? idx[lc] : idx[rc];
}
Pll query(int i, int b, int e, int l, int r)
{
if(e<l || r<b) return mkp(0, -INF);
if(l<=b && e<=r) return mkp(idx[i], sgt[i]);
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
P la = query(lc, b, mid, l, r), ra = query(rc, mid+1, e, l, r);
return la.Y > ra.Y ? la : ra;
}
} t;

void calc_r(int l, int r, int mid)
{
rep(i, mid, r)
{
ll up = pref[i] - 2*a[mid];
int j = upper_bound(pref+l-1, pref+mid, up) - pref + 1;
ans += j-l;
}
}

void calc_l(int l, int r, int mid)
{
rep(i, l, mid)
{
// lst j, pref[j] < pref[i] + 2x
ll up = pref[i-1] + 2*a[mid], j = mid-1;
int b = mid, e = r;
while(b <= e)
{
int m = (b+e)>>1;
if(pref[m] < up) j = m, b = m+1; else e = m-1;
}
ans += r-j;
}
}

void solv(int l, int r)
{
if(l>=r) return;
Pll tmp = t.query(1, 1, n, l, r);
int mid = tmp.X;
if(r-mid > mid-l) calc_l(l, r, mid); else calc_r(l, r, mid);
solv(l, mid-1); solv(mid+1, r);
}

int main()
{
// freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);

int T; read(T);
while(T--)
{
read(n);
rep(i, 1, n) read(a[i]);
t.build(1, 1, n, a);
pref[0] = suff[n+1] = 0;
rep(i, 1, n) pref[i] = pref[i-1] + a[i];
per(i, n, 1) suff[i] = suff[i+1] + a[i];

ans = 0;
solv(1, n);
printf("%lld\n", ans);
}
}

立一个flag:第四场认真打
谨记:

  1. 认真读题
  2. 如果有想法要多想想
  3. 卡住的时候可以尝试枚举几个量、更换枚举项
  4. 运用19年来学习的数学技巧orz

第四场

Update: flag倒了

讲道理这一场的游戏体验还行,感觉都能写一点。

先写了E,不过wa了一次;然后刚想暴力分层跑J,但一想感觉会T,就扔给学长了;然后开始写B,暴力一发T了,开始yy离线分治,但发现自己不会求两组线性基的交;然后写A和D,乱搞搞就过了;然后觉得还有时间开了C,觉得分治+线段树可做,但线段树写挂了…然后也没时间修B了,就弃疗了。

赛后发现我solo了…但我太菜了solo不动啊orz。每场都三百名开外…没脸见人了。

补题:
发现J暴力分层可以过…

J.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

#define I(i, u) ((i)*n+(u))
const int N = 1e6+10, M = 1e3+10;
struct edge { int v, nxt; ll w; } g[N*5];
int head[N], sz = 0;
pair<P, ll> edg[M];
void add(int u, int v, ll w)
{
// printf("%d-%d %d\n", u, v, w);
g[++sz].w = w; g[sz].v = v;
g[sz].nxt = head[u]; head[u] = sz;
}

bool used[N]; ll d[N];
ll dij(int n, int s, int t)
{
// printf("dij: %d->%d\n", s, t);
priority_queue<Pll, vector<Pll>, greater<Pll> > q;
fill(used, used + n + 1, 0);
fill(d, d + n + 1, INF);
d[s] = 0; q.push(make_pair(0, s));
while(!q.empty())
{
int u = q.top().second; q.pop();
if(used[u]) continue; used[u] = 1;
for(int i = head[u], v; i; i = g[i].nxt)
if(d[v = g[i].v] > d[u] + g[i].w)
{
d[v] = d[u] + g[i].w;
q.push(make_pair(d[v], v));
}
}
return d[t];
}

int n, m;
ll g0[M][M];
int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
int S, T, k;
read(n); read(m); read(S); read(T); read(k);
rep(i, 1, n) rep(j, 1, n) g0[i][j] = INF;
rep(i, 1, m)
{
int u, v; ll w; read(u); read(v); read(w);
g0[v][u] = g0[u][v] = min(g0[u][v], w);
}

int tot = 0;
rep(i, 1, n) rep(j, i+1, n)
if(g0[i][j] != INF) edg[++tot] = mkp(mkp(i, j), g0[i][j]);

rep(i, 0, k)
rep(j, 1, tot)
{
int u = edg[j].X.X, v = edg[j].X.Y; ll w = edg[j].Y;
add(I(i, u), I(i, v), w);
add(I(i, v), I(i, u), w);
if(i < k)
{
add(I(i, u), I(i+1, v), 0);
add(I(i, v), I(i+1, u), 0);
}
}
printf("%lld", dij((k+1)*n, I(0, S), I(k, T)));
}

发现C直接分治不用线段树…

C.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 3e6+10;
int n; ll a[N], b[N], pref[N], suff[N];

ll ans = -INF;
# define w(i) max(i-l, r-i)
void solv(int l, int r)
{
if(l>r) return;
ll x = a[l]; int mid = l;
rep(i, l+1, r)
if(a[i] < a[mid] || (a[i] == a[mid] && w(i) < w(mid)))
x = a[i], mid = i;
ll s1 = 0, s2 = 0;

if(x > 0)
{
per(i, mid-1, l) s1 = max(s1, suff[i]-suff[mid]);
rep(i, mid+1, r) s2 = max(s2, pref[i]-pref[mid]);
}
else
{
per(i, mid-1, l) s1 = min(s1, suff[i]-suff[mid]);
rep(i, mid+1, r) s2 = min(s2, pref[i]-pref[mid]);
}
ans = max(ans, x*(s1+s2+b[mid]));
solv(l, mid-1); solv(mid+1, r);
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n);
rep(i, 1, n) read(a[i]);
rep(i, 1, n) read(b[i]);
rep(i, 1, n) pref[i] = pref[i-1] + b[i];
per(i, n, 1) suff[i] = suff[i+1] + b[i];

solv(1, n);
printf("%lld", ans);
}

数据是谁出的我要打死他>_<

B的话可以线性基求交+线段树,离线分治会T。
其实我线段树开始也T了,因为很执着地想把整个区间的线性基的交求出来再判断。
其实线段树查询的过程中是不用求交($O(n^2)$)的,对于每个小区间判断一下($O(n)$)即可。
离线分治因为只将每个区间拆成两个,而且冗余的求交次数太多,所以只能过90%。
求交部分代码:(其实我还不太懂)

intersect
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void intersect(uint *a, uint *b, uint *ans)
{
fill(ans, ans+up, 0);
uint c[K], d[K];
rep(i, 0, up-1) c[i] = d[i] = b[i];
rep(i, 0, up-1)
{
uint x = a[i];
if(!x) continue;
int j = i; uint T = 0;
for(; j >= 0; j--)
if((x>>j)&1)
{
if(c[j]) x ^= c[j], T ^= d[j];
else break;
}
if(!x) ans[i] = T; else c[j] = x, d[j] = T;
}
}

离线分治:

B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 50010, K = 35;
int up = 32;
void gauss(int n, uint *a, uint *b)
{
rep(i, 1, n) per(j, up-1, 0)
if((a[i]>>j)&1)
{
if(b[j]) a[i] ^= b[j];
else { b[j] = a[i]; break; }
}
}

int n, m;
uint bs[N][K], its[N][K];
bool check(uint *b, uint x)
{
per(i, up-1, 0) if((x>>i)&1) x ^= b[i];
return x == 0;
}

void intersect(uint *a, uint *b, uint *ans)
{
fill(ans, ans+up, 0);
uint c[K], d[K];
rep(i, 0, up-1) c[i] = d[i] = b[i];
rep(i, 0, up-1)
{
uint x = a[i];
if(!x) continue;
int j = i; uint T = 0;
for(; j >= 0; j--)
if((x>>j)&1)
{
if(c[j]) x ^= c[j], T ^= d[j];
else break;
}
if(!x) ans[i] = T; else c[j] = x, d[j] = T;
}
}

struct node { int l, r; uint x; } ask[N];
vector<int> pool[N];
bool ans[N];
void solv(int l, int r)
{
if(l == r)
{
foreach(i, pool[l]) if(ask[*i].r == l)
ans[*i] = check(bs[l], ask[*i].x);
return;
}
int mid = (l+r)>>1; vector<int> stk;
rep(i, l, mid) foreach(j, pool[i])
if(ask[*j].r > mid && ask[*j].r <= r) stk.pb(*j);
uint tmp[K];
rep(i, 0, up-1) tmp[i] = (uint)1<<i;
per(i, mid, l) intersect(i==mid ? tmp : its[i+1], bs[i], its[i]);
rep(i, mid+1, r) intersect(i==mid+1 ? tmp : its[i-1], bs[i], its[i]);

foreach(i, stk)
{
// intersect(its[ask[*i].l], its[ask[*i].r], tmp);
ans[*i] = check(its[ask[*i].l], ask[*i].x) &&
check(its[ask[*i].r], ask[*i].x);
}
solv(l, mid); solv(mid+1, r);
}

int main()
{
// freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); read(m);
uint tmp[K];
rep(i, 1, n)
{
int sz; read(sz);
rep(j, 1, sz) read(tmp[j]);
gauss(sz, tmp, bs[i]);
}

rep(i, 1, m)
{
read(ask[i].l); read(ask[i].r); read(ask[i].x);
pool[ask[i].l].pb(i);
}
solv(1, n);
rep(i, 1, m) printf(ans[i] ? "YES\n" : "NO\n");
}

线段树:

B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 50010, K = 35;
int up = 32;
void gauss(int n, uint *a, uint *b)
{
rep(i, 1, n) per(j, up-1, 0)
if((a[i]>>j)&1)
{
if(b[j]) a[i] ^= b[j];
else { b[j] = a[i]; break; }
}
}

int n, m;
uint bs[N][K], its[N][K];
bool check(uint *b, uint x)
{
per(i, up-1, 0) if((x>>i)&1) x ^= b[i];
return x == 0;
}

void intersect(uint *a, uint *b, uint *ans)
{
fill(ans, ans+up, 0);
uint c[K], d[K];
rep(i, 0, up-1) c[i] = d[i] = b[i];
rep(i, 0, up-1)
{
uint x = a[i];
if(!x) continue;
int j = i; uint T = 0;
for(; j >= 0; j--)
if((x>>j)&1)
{
if(c[j]) x ^= c[j], T ^= d[j];
else break;
}
if(!x) ans[i] = T; else c[j] = x, d[j] = T;
}
}
struct SegTree
{
uint sgt[N*4][K];
void build(int i, int b, int e)
{
if(b == e)
{
rep(j, 0, up-1) sgt[i][j] = bs[b][j];
return;
}
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
build(lc, b, mid); build(rc, mid+1, e);
intersect(sgt[lc], sgt[rc], sgt[i]);
}
bool query(int i, int b, int e, int l, int r, uint x)
{
if(e<l || r<b) return 1;
if(l<=b && e<=r) return check(sgt[i], x);
int mid = (b+e)>>1, lc = i<<1, rc = lc|1;
return query(lc, b, mid, l, r, x) &&
query(rc, mid+1, e, l, r, x);
}
} t;

int main()
{
// freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); read(m);
uint tmp[K];
rep(i, 1, n)
{
int sz; read(sz);
rep(j, 1, sz) read(tmp[j]);
gauss(sz, tmp, bs[i]);
}
t.build(1, 1, n);

rep(i, 1, m)
{
int l, r, x;
read(l); read(r); read(x);
printf(t.query(1, 1, n, l, r, x) ? "YES\n" : "NO\n");
}
}

I是个后缀自动机?有时间学一下再写。

第五场

这次训练已经过半了,不过好像水平并没有什么长进…

开场秒了A,B扔给了学长,花了一个小时写G,刚写完发现subsequence看成了substring,弃疗。学长用高精度做的B超时了,我想了想乱搞了一个十进制快速幂,少取几次模就过了。因为前一天刚拔了两颗牙脑子不太转的动,之后就划了两小时的水。

第六场

写了A和B,学长的开了D然后wa了,然后学长开了J却一直没有动静,我就自闭了…

赛后发现D不单调,G是个大暴力,E构造,H挺有意思的。

E:构造一个n个节点的self-complementary的图

H:一个n个节点,m条边的无向图,边权均为1,一个点集$S_a$,一个点集$S_b$,随机从$S_a$中取一点$A$,从$S_b$中取一点$B$,从所有点中取一点$C$,记$f(A, B, C)=min_v\{dist(A,v)+dist(B,v)+dist(C,v)\}$,求f的期望 $n,m\leq 10^5, |S_a|,|S_b|\leq 20$



枚举A和B,添加一点S,对于每个点v,记$w(S,v)=dist(A,v)+dist(B,v)$。则对任意一点C,$f(A, B, C)=dist(C, S)$, 因为边权都是1,再用bfs优化一下。

第七场

这是我们最靠前的一场?不过签完到后就一直处于智障模式,B考了个方程求根的板子。C写了个主席树…然后突然想起来实数域上三次以上都可约,没脸见线代老师了orz。后来开了H想了好久无果,学长写E写自闭了,然后就没有了。

赛后发现E离散化一下就可以用线段树了,H是个数位dp(跟我以前写的数位dp不太一样orz),果然还是我dp太烂了唉。

H:求$1\leq x\leq A,1\leq y\leq B$,满足$x~and~y<C$或$x~xor~y>C$的$(x,y)$的个数。


从高到低做二进制位,核心在于如果某一位已经满足了一个限制条件,再低的位就没有限制了。比如A=1101, x=10??,由于在第3位0<1,x的后两位可以随便填。
这样把四个限制条件全考虑进状态,dp一下即可

H.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 35;
ll f[N][2][2][2][2];
ll A, B, C;
ll dfs(int i, int c1, int c2, int l1, int l2)
{
if(i == -1) return 1;
if(f[i][c1][c2][l1][l2] != -1) return f[i][c1][c2][l1][l2];
ll ret = 0;
rep(x, 0, l1 ? ((A>>i)&1) : 1) rep(y, 0, l2 ? ((B>>i)&1) : 1)
{
int nd = x&y, xr = x^y;
int n_l1 = l1 && (x == ((A>>i)&1)),
n_l2 = l2 && (y == ((B>>i)&1));
int n_c1 = 1, n_c2 = 1;
if(!c1)
{
if(nd == ((C>>i)&1)) n_c1 = 0;
else if(nd > ((C>>i)&1)) continue;
}
if(!c2)
{
if(xr == ((C>>i)&1)) n_c2 = 0;
else if(xr < ((C>>i)&1)) continue;
}
// printf(">>%d x=%d y=%d\n", i, x, y);
ret += dfs(i-1, n_c1, n_c2, n_l1, n_l2);
}
// printf("f[%d][%d][%d][%d][%d] = %lld\n", i, c1, c2, l1, l2, ret);
return f[i][c1][c2][l1][l2] = ret;
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
int T; read(T);
while(T--)
{
read(A); read(B); read(C);
int len = max(ceil(log2(A)), ceil(log2(B)));
len = max(len, (int)ceil(log2(C)));
rep(i, 0, len) rep(c1, 0, 1) rep(c2, 0, 1)
rep(l1, 0, 1) rep(l2, 0, 1) f[i][c1][c2][l1][l2] = -1;


ll res = dfs(len, 0, 0, 1, 1) - max(A-C+1, 0ll) - max(B-C+1, 0ll);
printf("%lld\n", A*B - res);
}
}

第八场

我有个饭局,鸽了。

第九场

这场也太数学了吧。

  1. A比较懵;
  2. B用求根公式,抄个二次剩余的板子开根就可以过。
  3. D是个裸的折半枚举。
  4. E用并查集维护一下连通块,然后是求所有连通块大小的一个4次对称多项式,对称多项式不太好维护,维护等幂和比较方便,然后在用牛顿恒等式算一下就行,窝推了好久…对不起线代老师orz。
  5. J我猜想最优解的对称轴一定在某一行的中点,然后把所有中点排个序,扫一遍乱搞搞就好了。

然后H不太会就自闭了,发现学长的D不知道为啥写挂了…后来我就下线了。
赛后得知H是个主席树的板子;A的话,斐波那契数列模n有循环节的,考虑$10^9=2^9\times 5^9$,分别对$2^9$和$5^9$暴力求解后,用crt合并即可。

第十场

没认真写,B一直段错误,D怎么改都WA,然后就下线了。

赛后得知D WA是因为在可能撒谎的情况下,结果爆了…听说换成python就过了?

F是骗人的,用线段树维护列的气球个数,暴力枚举选中的三行,从线段树中暴力删除选中行中气球,然后查询列的前三大,更新答案。因为气球就n个,删除均摊$O(N\log{N})$,查询显然是$O(N\log{N})$的。

J按高度排个序然后斜率优化就行了,方程
$$
f[i][j] = max_{j\leq p<i}\{f[p][j-1] + h[p+1]\cdot sum(w[p+1\cdots i])\}
$$

注意一下求斜率时,分母等于0要特判,不然0/0会得到nan。

J.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 5010, M = 2010;
int n, m;
ll f[N][M], pref[N]; Pll a[N];
# define h(i) (a[i].X)
# define w(i) (a[i].Y)
inline ll F(int k, int j) { return f[k][j-1] - h(k+1) * pref[k]; }
inline ll G(int k) { return h(k+1); }
inline int sgn(ll x)
{
if(x == 0) return 0;
else return x > 0 ? 1 : -1;
}
inline ld grad(int s, int t, int j)
{
ld d = G(t) - G(s);
if(d == 0) return sgn(F(t, j) - F(s, j)) * 1e100;
else return (F(t, j) - F(s, j)) / d;
}

void calc()
{
static int q[N];
rep(j, 2, m)
{
int h = 0, t = 0;
q[t++] = j-1;
rep(i, j, n)
{
while(t-h > 1 && grad(q[h], q[h+1], j) > -pref[i]) h++;
int k = q[h];
f[i][j] = f[k][j-1] + h(k+1) * (pref[i] - pref[k]);
while(t-h > 1 &&
grad(q[t-1], i, j) > grad(q[t-2], q[t-1], j)) t--;
q[t++] = i;
}
}
}

int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); read(m);

ll sum = 0;
rep(i, 1, n)
{
read(w(i)), read(h(i));
sum += w(i) * h(i);
}

sort(a+1, a+n+1);
rep(i, 1, n) pref[i] = pref[i-1] + w(i);

f[0][1] = -INF;
rep(i, 1, n) f[i][1] = h(1) * pref[i];

calc();
printf("%lld", sum - f[n][m]);
}

E按题意模拟一下就好,类似于归并排序,只不过这里是分四块。
细节比较多,调了好久。

E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define foreach(i, x) for(auto i = x.begin(); i != x.end(); i++)
#define forG(i) for(int i = head[u], v; i; i = g[i].nxt)
#define INF (ll)0x3f3f3f3f
#define EPS 1e-8
#define X first
#define Y second
#define mkp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define lbound lower_bound
#define ubound upper_bound
#define rnd(x) (rand()%(x)+1)
#define squ(x) ((x)*(x))
#define disp0(A){foreach(i,A)cout<<A[i]<<" ";cout<endl;}
#define disp(A, l, r) {rep(_i,l,r)cout<<A[_i]<<" ";cout<<endl;}
#define disp2(A, l, r, b, e){ \
rep(_i,l,r){rep(_j,b,e)cout<<A[_i][_j]<<"\t";cout<<endl;} \
cout<<endl; \
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, int> Pli;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
template<class T> inline T lowbit(T x) {return x&(-x);}
template<class T> T gcd(T a, T b) {return b?gcd(b,a%b):a;}
template<class T> inline T Pow(T a, T b, T p)
{T ret=1;a%=p;for(;b;b>>=1,a=a*a%p)if(b&1)(ret*=a)%=p;return ret;}
template<class T> inline void read(T &ret)
{
T x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
ret = x*f;
}

const int N = 1e6+10;
Pll a[N];
const int D[2][4] = {{0, 1, 2, 3}, {3, 2, 1, 0}};
const int OFS[4][2] = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};
const int ROT[2][4] = {{3, 0, 0, 1}, {1, 0, 0, 3}};
const int MIR[4] = {1, 0, 0, 1};

inline int id(int i, int x0, int y0, Pll &p)
{
if(p.X - x0 >= ((ll)1<<(i-1)))
{
if(p.Y - y0 >= ((ll)1<<(i-1))) return 2;
else return 1;
}
else
{
if(p.Y - y0 >= ((ll)1<<(i-1))) return 3;
else return 0;
}
}

Pll b[N];
void hilbert(int i, ll x0, ll y0, int dir, int l, int r, int mir)
{
// printf("hilbert(%d, %lld, %lld, %d, %d, %d, %d)\n",
// i, x0, y0, dir, l, r, mir);

if(r <= l) return;
if(i == 0) return;
int cnt[4] = {0, 0, 0, 0}, det[4];
rep(j, l, r)
{
// printf("(%lld, %lld) id=%d, p=%d\n",
// a[j].X, a[j].Y,
// id(i, x0, y0, a[j]),
// D[mir][(id(i, x0, y0, a[j])+dir)%4]);
cnt[D[mir][(id(i, x0, y0, a[j])+dir)%4]]++;

}
rep(j, 0, 3) cnt[j] = det[j] = cnt[j] + (j > 0 ? det[j-1] : 0);
rep(j, l, r)
{
int p = --cnt[D[mir][(id(i, x0, y0, a[j])+dir)%4]];
b[l+p] = a[j];
}
rep(j, l, r) a[j] = b[j];

rep(j, 0, 3)
{
int p = D[mir][(j+dir)%4],
nl = j > 0 ? det[j-1] : 0, nr = det[j];

// printf("p=%d\n", p);;
hilbert(i-1,
x0+OFS[p][0]*((ll)1<<(i-1)),
y0+OFS[p][1]*((ll)1<<(i-1)),
(dir+ROT[mir][j])%4,
l+nl,
l+nr-1,
mir^MIR[j]);
}
}

int n, k;
int main()
{
freopen("std.in", "r", stdin);
// freopen("std.out", "w", stdout);
read(n); read(k);
rep(i, 1, n) read(a[i].X), read(a[i].Y);
hilbert(k, 1, 1, 0, 1, n, 0);
rep(i, 1, n) printf("%lld %lld\n", a[i].X, a[i].Y);
}

后记

十场训练,我参加了八场。
排名一直靠后,最好也就185。不过可以理解,毕竟我们队的输出一直小于2,有一个队友一直没写过题,果壳的cpc的小组快凉了,大家都没有什么积极性…我也有些动摇了。
还有一个客观原因就是不太适应这样的出题风格吧,毕竟OI出身,大一一年基本在打cf,好不容易爬上1900,已经习惯了那种递增的难度分布。

另外关于silly mistakes的总结,我写在了wa.pdf里。