avatar
文章
24
标签
19
首页
时间轴
标签
友链
关于
ruogu's blog
首页
时间轴
标签
友链
关于
杂题（一）
阅读量:|评论数:

ezoj566 乱搞/数学

http://ezoj.org.cn/contest/41/problem/566

这题给我提了个醒, 就是程序本身占的内存空间挺大的, bits头文件占的超过了2MB2MB.

设出现22次的是AA, 出现00次的是BB, 用所给的很容易能求出 A−B,A⊕BA-B,A \oplus B. 大抵发现还能求出模意义下的AB\frac{A}{B} …然后就能乱搞过了。

其实确定的解法是求出A2−B2A^2-B^2, 也很容易.

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
#include <cstdio>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
int n;
const int mod = 998244353;
//
int mul(int x, int y) { return 1ll * x * y % mod; }
int main() {
  n = getint();
  ll sum0 = 0, sum1 = 0;
  int hh0 = 0, hh1 = 0;
  int res = 1, hh = 1;
  rep(i, n) {
    int x = getint() - 1;
    sum0 += x;
    sum1 += i;
    hh0 ^= x;
    hh1 ^= i;
    res = mul(res, x + 1);
    hh = mul(hh, i + 1);
  }
  sum0 -= sum1;
  hh0 ^= hh1;
  for (int i = 0; i < n; i++) if (i - (i ^ hh0) == sum0 && mul(hh, i + 1) == mul(res, (i ^ hh0) + 1)) {
    printf("%d\n", i + 1);
    return 0;
  }
  return 0;
}

agc043B 数学

https://atcoder.jp/contests/agc043/tasks/agc043_b

我会判11,但是竟然不太会判00和22…(至少短时间内没想出来).

先做一次操作把1,2,31,2,3变成0,1,20,1,2.那么奇偶性很好判,直接组合数就行.

然后发现如果序列中有11,那么答案一定不是22…因为一段11两端的11很难被消去.

如果序列中没有11,可以把所有数除以22,答案也会除以22.

ezoj572 数论

https://ezoj.org.cn/contest/41/problem/572

4242pts: 发现答案是容斥… 是莫比乌斯函数…

9595pts: 直接不推柿子的得到 ansn=2∑i=1nϕi−1n2ans_n = \frac{2 \sum \limits_{i=1}^n \phi_i-1}{n^2} .当然, 直接利用莫比乌斯函数以及性质(积性卷积性还是积性)也能做, 就可以杜教筛了.

100100pts:

ezoj572

???

soj905 动态规划

http://120.27.222.204:12243/problem/905

我tmd一开始把韦恩图想错了… 然后比赛就崩了。限制11的集合AA, 限制22的集合BB, 并不满足 A∨B=ALLA \lor B = ALL.

但是直接抛开容斥，再想一个性质: 知道yy, 知道x∧yx \land y, 知道x∨yx \lor y, xx不就知道了嘛.也就是说算出x∧yx \land y的方案乘上x∨yx \lor y的方案就结束了.

算x∧yx \land y满足条件的方案就令fl,r,xf_{l,r,x}表示从高往低第xx位区间[l,r][l,r]还没分出胜负, 另一个同理. 这是我考场上就已经写好了的…

awsl

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int mod = MOD;
const int N = 15;
const int M = 35;
int n, m, f[N][N][M], a[N];
//
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
int g0(int l, int r, int x) {
  if (x < 0 || l > r) return 1;
  if (f[l][r][x] >= 0) return f[l][r][x];
  int res = 0, p = r + 1;
  while (p > l && (a[p - 1] >> x & 1)) --p;
  for (int i = p; i <= r + 1; i++) {
    int ansl = g0(l, i - 1, x - 1);
    int ansr = g0(i, r, x - 1);
    reduce(res += mul(ansl, ansr) - mod);
  }
  return f[l][r][x] = res;
}
int g1(int l, int r, int x) {
  if (x < 0 || l > r) return 1;
  if (f[l][r][x] >= 0) return f[l][r][x]; 
  int res = 0, p = r + 1;
  while (p > l && !(a[p - 1] >> x & 1)) --p;
  for (int i = p; i <= r + 1; i++) {
    int ansl = g1(l, i - 1, x - 1);
    int ansr = g1(i, r, x - 1);
    reduce(res += mul(ansl, ansr) - mod);
  }
  return f[l][r][x] = res;
}

int main() {
  n = getint(); m = getint(); int res = 1;
  rep(i, n) a[i] = getint();
  memset(f, -1, sizeof(f)); res = mul(res, g0(0, n - 1, m - 1));
  //rep(i, n) a[i] = ~a[i] & (~(-1 << m));
  memset(f, -1, sizeof(f)); res = mul(res, g1(0, n - 1, m - 1));
  cout << res << endl;
  return 0;
}

soj906 计算几何/动态规划

http://120.27.222.204:12243/problem/906

我场上写了模拟退火, 得了2020…

其实在我印象里, n=50n=50是很可以退的, 但是这题不太行. 这题等价于有5050次询问, 而且条件苛刻, 必须要恰好形成凸包才行.

可以先预处理每个三角形内的点的权值. 把所有点极角排序, 令dps,i,x,ydp_{s,i,x,y}表示起点为ss, 已经有ii个点, 最后两个点是x,yx,y的最小权值. 这样的话, 每次都要增加s,x,ys,x,y三个点形成的三角形内的权值. 复杂度O(n5)O(n^5)但是常数相当小, 可以过.

另外, 这是我又一次不会写凸包…

agc043d 组合计数/动态规划

https://atcoder.jp/contests/agc043/tasks/agc043_d

这题我已经想清楚问题的本质了, 但是完全不会dp…

agc043d

这是sundz的博客, 前面我都想清楚了, 就是不会直接dp…

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int B = 6005;
int n, mod, f[B][B << 1];
//
void reduce(int &x) { x += x >> 31 & mod; }
int mul(int x, int y) { return 1ll * x * y % mod; }
int main() {
  n = getint(); mod = getint();
  f[3 * n][B] = 1;
  for (int i = 3 * n; i > 0; i--) {
    rep(j, B << 1) if (f[i][j]) {
      reduce(f[i - 1][j + 1] += f[i][j] - mod);
      if (i >= 2 && j >= 1) reduce(f[i - 2][j - 1] += mul(f[i][j], i - 1) - mod);
      if (i >= 3) {
        reduce(f[i - 3][j] += mul(f[i][j], (i - 1) * (i - 2)) - mod);
      }
    }
  }
  int res = 0;
  for (int i = B; i < (B << 1); i++) {
    reduce(res += f[0][i] - mod);
  }
  cout << res << endl;
  return 0;
}

从大往小考虑一个计数器cntcnt, 如果是一个大小为33的组就不动, 如果是一个大小为22的组就cnt−1cnt-1, 如果是一个大小为11的计数器就cnt+1cnt+1. 这时, 如果把大小为22的组的生成看做括号匹配, cnt+1cnt+1有两种意思, 一种是表示单独成一组, 一种是表示匹配一个之前已经生成的变成长度为22的. 这题也要注意, 在生成的时候就要把后面选择的方案数乘上, 这已经比较经典了(为啥我还不会…).

agc043c sg函数/贪心

https://atcoder.jp/contests/agc043/tasks/agc043_c

agc043c

(from xht37 https://www.luogu.com.cn/blog/xht37/solution-at5800)

这实在太妙了, 完全想不到!

列几个注意点吧:

1.1.首先发现101810^{18}非常大,便必须想到贪心的选.

2.2.这种在图上贪心可以先转化成单向边然后sgsg函数.

3.3.这种DAG博弈转移图, SGSG函数上界O(m)O(\sqrt{m}).

证明(by sundz): 归纳! 如果sgsg为多少, 图上至少有多少边这样.

4.4.即使没有这个上界, 也可以通过fwtfwt权值来求得答案.

zroi1272/sdwc2019 数论/复刻

http://zhengruioi.com/problem/1272

zroi1272

果然我的数论不很好, 做过一遍都不太会了.

其主要宗旨是希望把gcdgcd的柿子转化成斐波那契数对一个数取模.

zroi1270 动态规划/复刻

http://zhengruioi.com/problem/1270

要记录一个结论, 合并的时候只关注根节点在点分树的深度.

http://zhengruioi.com/download.php?type=tutorial&id=1270具体可以看题解.

soj908 矩阵快速幂/组合/动态规划

http://120.27.222.204:12243/problem/908

这题有个很easy的9090分暴力: 维护状态maskmask, 其中第ii位表示第ii个数是否已经小于了第i+1i+1个数. 这样复杂度是O(23n∣S∣)O(2^{3n}|S|)的.

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 10005;
const int M = (1 << 7) + 5;
int n, k, m, len;
char s[N];
struct matrix {
  int d[M][M];
  matrix() { memset(d, 0, sizeof(d)); }
  inline matrix operator *(matrix &b) {
    matrix ans;
    rep(i, m) rep(j, m) if (d[i][j]) {
      rep(k, m) {
        reduce(ans.d[i][k] += mul(d[i][j], b.d[j][k]) - mod);
      }
    }
    return ans;
  }
  void p() {
    rep(i, m) {
      rep(j, m) cout << d[i][j] << " ";
      cout << endl;
    }
    cout << endl;
  }
} a, res;
//
namespace INIT {
int f[2][M], g[M][M][2];
inline int calc(int msk0, int msk1, int x) {
  if (g[msk0][msk1][x] != -1) return g[msk0][msk1][x];
  if (__builtin_popcount(msk1) & 1) return g[msk0][msk1][x] = -2;
  msk1 |= (x << n); int ans = msk0; 
  rep(i, n) if (!(msk0 >> i & 1) && (msk1 >> i & 1) > (msk1 >> (i + 1) & 1)) {
     return g[msk0][msk1 ^ (x << n)][x] = -2;
  }
  rep(i, n) if (!(msk0 >> i & 1) && (msk1 >> i & 1) < (msk1 >> (i + 1) & 1)) {
    ans |= (1 << i);
  }
  return g[msk0][msk1 ^ (x << n)][x] = ans;
}
void solve() {
  memset(g, -1, sizeof(g));
  rep(ss, m) {
    memset(f, 0, sizeof(f));
    f[0][ss] = 1; 
    rep(i, len) rep(j, m) if (f[i & 1][j]) {
      int val = f[i & 1][j]; f[i & 1][j] = 0;
      rep(k, m) {
        int t = calc(j, k, s[i] - '0');
        //cout << j << " " << k << " " << s[i] - '0' << " " << t << endl;
        if (t >= 0) reduce(f[(i & 1) ^ 1][t] += val - mod);
      }
    }
    rep(i, m) a.d[ss][i] = f[len & 1][i];
  }
}
}
int main() {
  n = getint(); k = getint(); m = (1 << n);
  scanf("%s", s); len = strlen(s);
  INIT :: solve(); 
  rep(i, m) res.d[i][i] = 1;
  while (k) {
    if (k & 1) res = res * a;
    a = a * a;
    k >>= 1;
  }
  cout << res.d[0][m - 1] << endl;
  return 0;
}

然后赛后发现有人跟我写了类似的竟然过了… 把矩乘写成下面这样!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
zz cf(zz x,zz y){
	zz z;
	memset(z.a,0,sizeof z.a);
	for (int i=0;i<v;i++)
		for (int k=0;k<v;k++)
			if (x.a[i][k])
				for (int j=0;j<v;j+=8){
					z.a[i][j]+=x.a[i][k]*y.a[k][j];
					z.a[i][j+1]+=x.a[i][k]*y.a[k][j+1];
					z.a[i][j+2]+=x.a[i][k]*y.a[k][j+2];
					z.a[i][j+3]+=x.a[i][k]*y.a[k][j+3];
					z.a[i][j+4]+=x.a[i][k]*y.a[k][j+4];
					z.a[i][j+5]+=x.a[i][k]*y.a[k][j+5];
					z.a[i][j+6]+=x.a[i][k]*y.a[k][j+6];
					z.a[i][j+7]+=x.a[i][k]*y.a[k][j+7];
				}
	for (int i=0;i<v;i++)
		for (int j=0;j<v;j++)z.a[i][j]%=M;
	return z;
}

sundz教我的真正的做法:

cf1329C 贪心

http://codeforces.com/contest/1329/problem/C

有一个很显然的想法，就是尽量删根，然后递归子树。这个想法是对的。

首先这样删一定删的是最大的，比删子树里的任意一个优。

那是否会先删子树内的，再删根呢？不可能。我们将这个树贪心的维护成若干条链，表示我删了这个点，儿子哪个点继承上来。若不能删除根，显然从这个点所在的链的最深处深度为gg。这条链在以后的任何操作中都不会再改变形态了，所以这个根永远也删不了了。

我在考场上的想法就是强行维护链并把链头扔进pq里。只不过每删一个点，都可能扔进去loglog个点，复杂度就是O(nlog2n)O(nlog^2n)，错了。

cf1329A 贪心

http://codeforces.com/contest/1329/problem/A

好难受。。做的最差的一次AA。我交的第一发读错题了，以为可以按任意顺序放入。后面的wa体现了自己水平之弱。

先来说说我考试的时候的想法。首先一个想法是所有的线段按顺序从左往右分配，而且左端点单调递增。维护一个pospos表示上一条线段的左端点，维护一个prepre表示前缀最大右端点。考虑我这条线段的右端点至少超过prepre多少，并且我这条线段的左端点至少是pos+1pos+1。这样可以固定一个最左的左端点。

我列一下我这题犯过的错误（按发现顺序）：

1.1.n,mn,m搞混了。

2.2.读错题，以为可以按任意顺序放，还把长度sortsort了一下。

3.3.忘记判右端点超过nn了。

4.4.令右端点超过prepre至少多少的数值为xx。如果x=0x=0，其实右端点可以比prepre小，我忘记判了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 1e5 + 5;
int n, m, res[N];
ll suf[N];
pii a[N];
//
int main() {
  n = getint(); m = getint();
  rep(i, m) a[i] = mp(getint(), i);
  for (int i = m - 1; i >= 0; i--) suf[i] = suf[i + 1] + a[i].first;
  int now = -1, pre = -1;
  memset(res, -1, sizeof(res));
  rep(i, m) {
    if (suf[i] < n - now - 1) return !printf("%d\n", -1);
    if (m - i > n - pre - 1) return !printf("%d\n", -1);
    ll x = max(1ll * n - now - 1 - suf[i + 1], 0ll);
    assert(x <= a[i].first);     
    int p = max(1ll * pre + 1, 1ll * now + x - a[i].first + 1);
    if (!x) p = pre + 1;
    if (p + a[i].first - 1 >= n) return !printf("%d\n", -1);
    res[a[i].second] = p; pre = p; now = max(now, p + a[i].first - 1);
  }
  assert(res[m - 1] + a[m - 1].first - 1 < n);
 
  rep(i, m) printf("%d ", res[i] + 1);
  return 0;
}

证明这种想法虽然说起来也挺简单，但是并不适合cf的AA题。

真正的方法是resi=max(i,n−suf[i]+1)res_i=max(i, n - suf[i]+ 1)。

wsl

uoj513 线性基/结论

http://uoj.ac/contest/51/problem/513

https://www.cnblogs.com/suwakow/p/12635190.html

基本想出来7070分了，又被suwakow吊打了qaq。

首先可以猜出来，如果有方案一定能在m+1m+1步完成（逃。

为什么呢？

考虑操作22，我们先令所有点为黑色，那么其实每把一个点染黑色就是这个点所连的边全部翻转。所以操作22只会出现一次。

而对于操作11，其实只会出现非树边的个数次。简单环一定由非树边和所在树链构成，其实只异或一次就好了。

上面利用了异或的性质（我感觉我可能又会忘记），我们发现最多只需要m−(n−1)+1m-(n-1)+1次就能完成所有操作了。

以上对每条边弄个bitsetbitset线性基就是7070了，然后神仙就出场了！

uoj513

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 305;
int n, m;
bitset<N> b, a[N], c[N];
//
bool ins(bitset<N> &f) {
  for (int i = n - 1; i >= 0; i--) {
    if (!f[i]) continue;
    if (c[i].none()) return c[i] = f, true;
    f ^= c[i];
  }
  return false;
}
void solve() {
  n = getint(); m = getint();
  rep(i, n) c[i].reset(), a[i].reset();
  b.reset();
  for (int i = 0; i < m; i++) {
    int x = getint() - 1, y = getint() - 1, z = getint();
    a[x][y] = a[y][x] = 1; 
    a[x][x].flip(); a[y][y].flip();
    b[x] = b[x] ^ z; b[y] = b[y] ^ z;
  }
  rep(i, n) ins(a[i]);
  printf("%s\n", ins(b) ? "no" : "yes");
}
int main() {
  int t = getint();
  rep(i, t) solve();
  return 0;
}

第一次知道线性基可以这么写。。下次就不用烦恼记不住了。

下次应该尽可能快速想出7070。。100100比较困难，毕竟所有题都是要考虑的，不能像练习一样猛想一题，历史早已证明这样做后果之严重了。

soj911 状压dp

有个很显然的状压dp，就是O(nm2m)O(nm2^m)的，有33到66的常数。我已经卡到33的常数1.2s1.2s左右，还是过不了。julao们卡常过了。。

正解是斜着dp。。这算是一个套路吧，以后记住了。

soj911

uoj515 线段树

这个8585好多人想到了。考虑维护一棵线段树，每个节点维护好这个区间的最长上升子序列长度以及区间最小值。查询的时候先往右边走再往左边走。这样的复杂度是O(nlog2n)O(nlog^2{n})的，可以看看sundz的代码。

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
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_dolor
#define pii pair<int,int>
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 1e6;
const int INF = 1<<30;
int a[mxN+3];
int n,q;

struct SegmentTree
{
	struct SgTNode
	{
		int mn,cnt;
	} sgt[(mxN<<2)+3];
	int calc(int u,int le,int ri,int x)
	{
//		printf("calc %d %d %d\n",le,ri,x);
		if(le==ri) {return sgt[u].mn<x?1:0;}
		int mid = (le+ri)>>1;
		if(sgt[u<<1|1].mn<x) {return sgt[u].cnt-sgt[u<<1|1].cnt+calc(u<<1|1,mid+1,ri,x);}
		else {return calc(u<<1,le,mid,x);}
	}
	void pushup(int u,int le,int ri)
	{
		int mid = (le+ri)>>1;
		sgt[u].mn = min(sgt[u<<1].mn,sgt[u<<1|1].mn);
		sgt[u].cnt = sgt[u<<1|1].cnt+calc(u<<1,le,mid,sgt[u<<1|1].mn);
//		printf("sgt[%d].cnt=%d\n",u,sgt[u].cnt);
	}
	void build(int u,int le,int ri,int a[])
	{
		if(le==ri) {sgt[u].mn = a[le],sgt[u].cnt = 1; return;}
		int mid = (le+ri)>>1;
		build(u<<1,le,mid,a); build(u<<1|1,mid+1,ri,a);
		pushup(u,le,ri);
	}
	void modify(int u,int le,int ri,int pos,int x)
	{
		if(le==ri) {sgt[u].mn = x; return;}
		int mid = (le+ri)>>1;
		if(pos<=mid) {modify(u<<1,le,mid,pos,x);} else {modify(u<<1|1,mid+1,ri,pos,x);}
		pushup(u,le,ri);
	}
	pii query(int u,int le,int ri,int lb,int rb,int x)
	{
//		printf("[%d,%d] %d\n",le,ri,x);
		if(le>=lb&&ri<=rb) {return mkpr(min(x,sgt[u].mn),calc(u,le,ri,x));}
		int mid = (le+ri)>>1;
		if(rb<=mid) return query(u<<1,le,mid,lb,rb,x);
		else if(lb>mid) return query(u<<1|1,mid+1,ri,lb,rb,x);
		else
		{
			pii retr = query(u<<1|1,mid+1,ri,mid+1,rb,x),retl = query(u<<1,le,mid,lb,mid,min(sgt[u<<1|1].mn,x));
			return mkpr(retl.first,retr.second+retl.second);
		}
	}
} sgt;

int main()
{
	n = read(),q = read();
	for(int i=1; i<=n; i++) a[i] = read();
	sgt.build(1,1,n,a);
	while(q--)
	{
		int opt = read();
		if(opt==2)
		{
			int l = read();
			pii ans = sgt.query(1,1,n,l,n,INF);
			printf("%d\n",ans.second);
		}
		else
		{
			int x = read(),val = read();
			sgt.modify(1,1,n,x,val);
		}
	}
	return 0;
}

tql！

至于正解，首先要学会segment_tree beats。

然后把问题转换成扫描线——从后往前加入，维护按时间的线段树。我们这时只有两件事情：

1.1.区间取minmin。

2.2.单点求该点取minmin了多少次。

这时，我们可以如同segment_tree beats的套路一样，维护区间最大值，次大值以及标记即可。

详见代码。

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 ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define getchar() (*input_pos++)
const int TT = 5e7;
char input_buffer[TT], output_buffer[TT];
char *input_pos = input_buffer, *output_pos = output_buffer;
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
void write(int x) {
  if (!x) return;
  write(x / 10); *output_pos++ = '0' + x % 10;
}
void writeln(int x) {
  write(x);
  *output_pos++ = '\n';
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 1e6 + 5;
int n, q, res[N], mx[N << 2], mx2[N << 2], tag[N << 2];
vector<iiii> a[N];
vector<int> vq[N];
bool fg[N];
pii lst[N];
//
void pd(int k) {
  if (tag[k]) {
    if (mx[2 * k + 1] > mx[k]) tag[2 * k + 1] += tag[k], mx[2 * k + 1] = mx[k];
    if (mx[2 * k + 2] > mx[k]) tag[2 * k + 2] += tag[k], mx[2 * k + 2] = mx[k];
    tag[k] = 0;
  }
}
void up(int k) {
  mx[k] = max(mx[2 * k + 1], mx[2 * k + 2]);
  if (mx[2 * k + 1] == mx[2 * k + 2]) {
    mx2[k] = max(mx2[2 * k + 1], mx2[2 * k + 2]);
  }
  else if (mx[2 * k + 1] > mx[2 * k + 2]) {
    mx2[k] = max(mx2[2 * k + 1], mx[2 * k + 2]);
  }
  else {
    mx2[k] = max(mx[2 * k + 1], mx2[2 * k + 2]);
  }
}
void modify(int l, int r, int x, int y, int k, int v) {
  if (l >= y || x >= r || v >= mx[k]) return;
  if (x <= l && r <= y && v > mx2[k]) {
    ++tag[k]; mx[k] = v;
    return;
  } 
  int mid = (l + r) >> 1; pd(k);
  modify(l, mid, x, y, 2 * k + 1, v);
  modify(mid, r, x, y, 2 * k + 2, v);
  up(k);
}
int qry(int l, int r, int p, int k) {
  if (r - l == 1) return tag[k];
  int mid = (l + r) >> 1; pd(k);
  if (p < mid) return qry(l, mid, p, 2 * k + 1);
  else return qry(mid, r, p, 2 * k + 2);
}
int main() {
  fread(input_buffer, 1, TT, stdin);
  memset(mx2, -1, sizeof(mx2));
  rep(i, N << 2) mx[i] = INF;
  n = getint(); q = getint();
  for (int i = 0; i < n; i++) lst[i] = mp(getint(), 0);
  rep(i, q) {
    int op = getint(), x = getint() - 1;
    if (op == 1) {
      int y = getint();
      a[x].emplace_back(lst[x].first, mp(lst[x].second, i));
      lst[x] = mp(y, i);
    }
    else {
      vq[x].emplace_back(i);
      fg[i] = true;
    }
  }
  rep(i, n) a[i].emplace_back(lst[i].first, mp(lst[i].second, q));
  for (int i = n - 1; i >= 0; i--) {
    for (auto &u : a[i]) {
      modify(0, q, u.second.first, u.second.second, 0, u.first);
    }
    for (auto &u : vq[i]) res[u] = qry(0, q, u, 0);
  }
  rep(i, q) if (fg[i]) writeln(res[i]);
  fwrite(output_buffer, 1, output_pos - output_buffer, stdout);
  return 0;
}

uoj66 结论/数学

http://uoj.ac/problem/66

直接猜嘛，是22的幂次肯定好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var t, n, i, ii, res, c: longint;
begin
	read(t);
	for ii := 1 to t do begin
		read(n); c := 1; res := 0;
		while n > 0 do begin
			if n mod 2 = 1 then begin
				res := res + c - 1;
			end;
			c := c * 2;
			n := n div 2;
		end;
		writeln(res);
	end;
end.

uoj66

这题练习了我的猜结论能力，反应能力，归纳证明能力，pascalpascal代码能力，正是一石四鸟的好题！

soj920/loj6213 结论/斜率优化

http://120.27.222.204:12243/problem/920

有个显然的5050。首先知道这个三角形的高要么00要么bib_i。

证明：假设其他三角形已经取到最优解了（肯定没有互相包含）。令这个三角形高为xx，假设左边三角形右端点距它中点距离pp，右边左端点距它中点距离qq，令p≤qp\leq q，那么它的贡献是个分段下凸二次函数。

我手算了一下，如果某个二次函数原来已经变成单调增的了，当变成下个二次函数的时候，下一个二次函数的对称轴在该变化点左侧，也就是仍是单调增。

还有个性质，三角形不会互相包含。

然后暴力枚举就有5050。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const ll inf = 2e18;
const int N = 25;
ll res;
int n, a[N], b[N], p[N];
//
bool cmp(int x, int y) {
  return a[x] - b[x] < a[y] - b[y];
}
int main() {
  n = getint();
  rep(i, n) a[i] = getint(), b[i] = getint(), p[i] = getint();
  rep(mask, 1 << n) {
    bool fg = true;
    rep(i, n) if (mask >> i & 1) {
      for (int j = i + 1; j < n; j++) if (mask >> j & 1) {
        if (a[i] - b[i] <= a[j] - b[j] && a[i] + b[i] >= a[j] + b[j]) {
          fg = false; break;
        }
        if (a[j] - b[j] <= a[i] - b[i] && a[j] + b[j] >= a[i] + b[i]) {
          fg = false; break;
        }
      }
      if (!fg) break;
    }
    if (!fg) continue;
    vector<int> v;
    rep(i, n) if (mask >> i & 1) v.emplace_back(i);
    sort(v.begin(), v.end(), cmp);
    ll ans = 0;
    rep(i, v.size()) {
      int x = v[i];
      ans -= 4ll * p[x] * b[x];
      ans += 4ll * b[x] * b[x];
      if (!i) continue;
      int px = a[v[i - 1]] + b[v[i - 1]], py = a[x] - b[x];
      if (py < px) {
        ans -= 1ll * (px - py) * (px - py);
      } 
    }
    res = max(res, ans);
  }
  cout << res << endl;
  return 0;
}

然后6565挺显然的吧，直接把三角形排序，令dpidp_i表示以ii结尾最大权值是什么。

然后是正解：

soj920

其实也不必要李超树，直接在凸包上二分就行了。

这题还是想的速度太慢，到比赛最后才猜出取值只有两种，这类题目应该就是这样吧，否则还能咋样（退火/爬山）？

soj921/loj3285

http://120.27.222.204:12243/problem/921

6060很easy。

正解不会。

soj922 数论/杜教筛/容斥原理

http://120.27.222.204:12243/problem/922

竟然没想出来qaq。我不知道打比赛的时候我脑子哪里错了。

soj922

除了杜教筛，有一个注意点是要对每个⌊nx⌋\lfloor\frac{n}{x}\rfloor，求∑i=0⌊nx⌋ik\sum\limits_{i=0}^{\lfloor\frac{n}{x}\rfloor}i^k，用sundz法，我们可以设一个阀值BB，当⌊nx⌋≤B\lfloor\frac{n}{x}\rfloor\leq B时，我们用线性筛爆算自然数幂和，否则插值。在这题中，复杂度是nk/B+Bnk/B+B，令B=nkB=\sqrt{nk}，最终复杂度就是O(nk)O(\sqrt{nk})。

uoj514 生成函数/容斥/计数

http://uoj.ac/problem/514

不会。

soj84 高斯消元/异或方程组

http://120.27.222.204:12243/problem/84

我吐了，这样的题我都不会。。

首先明确题意，CC图指的是所有点度数是偶数的图。

两句话：

1.1.当是树的时候只有两种分配方法，按度数奇偶性分配。

2.2.对于每个ii，令aia_i表示它的集合，要求⨁(i,j)∈E(xi⊕xj⊕1)=0\bigoplus_{(i,j)\in E} (x_i \oplus x_j \oplus 1)=0。然后直接高斯消元就完啦。

cf1333F 模拟

https://codeforces.com/contest/1333/problem/F

这破题就是个div2div2 AA吧。直接9min9min就ACAC了。

1.1.如果在xx和kxkx中选一个，肯定选xx。

2.2.如果要让gcd<xgcd<x，对于每个y≥xy \geq x，ky(k>1)ky(k>1)一定不选。

那直接倒着扫一遍就完啦。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 5e5 + 5;
int n, res[N];
bool fg[N];
//
int main() {
  n = getint();
  int p = n, c = n;
  for (int i = 2; i <= n; i++) res[i] = 1;
  for (int i = n; i >= 1; i--) {
    for (int j = i + i; j <= n; j += i) {
      if (!fg[j]) { fg[j] = true; --c; }
    }
    while (p > c) res[p--] = i;
  }
  for (int i = 2; i <= n; i++) printf("%d ", res[i]);
  return 0;
}

cf1333E 构造

这题反倒想了比较久。初始没想出来3∗33*3怎么构造。

[165289734]\begin{bmatrix} 1&6&5\\2&8&9\\7&3&4 \end{bmatrix}\quad

主要宗旨是让queenqueen的第八步在99的那个位置，使她离最后一步77差一个小飞。

把n∗nn*n的最后99步这样分配在左上角，就ok了。

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
#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 505;
int n, a[N][N];
//
int main() {
  n = getint();
  if (n <= 2) return !printf("%d\n", -1);
  int p = n * n;
  a[1][2] = p--; a[1][1] = p--; a[2][0] = p--;
  a[0][1] = p--; a[0][2] = p--; a[2][2] = p--;
  a[2][1] = p--; a[1][0] = p--; a[0][0] = p--;
  for (int i = 3; i < n; i++) {
    if (i & 1) {
      int x = 0, y = i;
      while (x <= i) a[x++][y] = p--;
      x = i, y = i - 1;
      while (y >= 0) a[x][y--] = p--;
    }
    else {
      int x = i, y = 0;
      while (y <= i) a[x][y++] = p--;
      x = i - 1, y = i;
      while (x >= 0) a[x--][y] = p--;
    }
  }
  rep(i, n) {
    rep(j, n) printf("%d ", a[i][j]);
    printf("\n");
  }
  return 0;
}

cf1333C two pointers

https://codeforces.com/contest/1333/problem/C

虽然也会，但是想的有点复杂。

其实直接考虑固定右端点，有多少个左端点就行，可以two pointers维护。

https://codeforces.com/contest/1333/submission/75850582

文章作者: ruogu
文章链接: http://ruogu-alter.github.io/2020/04/01/%E6%9D%82%E9%A2%98-%E4%B8%80/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ruogu's blog！
总结
评论
簡