0%

由于之前南京站的那块银牌,捡了个ec final的出线名额。打icpc至今还没有打过线下赛,非常兴奋。不过疫情期间,手续也相对麻烦,好在学校这边不需要提交什么特别的申请,辅导员也对我出去比赛非常支持,很快就搞定了。

4.16

出发去西安!

由于飞机票都比较坑(需要经停),所以我们选择了坐火车去。早上9点出发,结果刚好撞到早高峰,一度以为要误车了。不过还是提前20多分钟到重庆西站,而且西站人不算很多,很快就进去了。

火车上没网比较无聊,还好我提前下载了一季赛马娘。特别周也太可爱了吧!看了两集就喜欢上这匹马了!中间乐子也迷上了这部番,于是我俩就戴一个耳机一起看了。看了大概两小时吧,困了,就开始睡觉。睡醒忘了在干些啥了,好像是有网了,于是就开始耍电脑。

快到西安的那一段路,耳压变化明显,大概是因为在下山?

三点半多在鄠邑站下车,本来打算在车站吃肯德基的,结果到站了发现啥都没有,于是就直接打车去酒店了。

四点多一点就到酒店了。酒店住南山温泉。在门口申请了健康码之后,就可以办入住手续了。我们总共订了三个标间,我和乐子住一间,我另外两个队友住一间。不知道为什么,我们房间特别大,可能这就是欧皇吧?

酒店休息(床上打滚)了一会,就去西工大报道了。

酒店离西工大两公里远,也不知道为什么,我们决定走过去。走到一半大家就都后悔了,但是这时候又不好意思说打车,毕竟都要面子的嘛,然后,仿佛过了很久,我们终于走到了。

报道是六点结束,我们刚好提前半小时到报道处。提交了相关文件和核酸检测证明之后,很顺利的拿到了物资:一个参赛证、一件短袖T恤、一个书包、几张饭票和一个企业的宣传小册子。在厕所换上衣服,戴好参赛证后,按主办方的要求拍了张照,报道就算完成了。

然后就是愉快的干饭时间了!西工大食堂的饭菜还不错,我点的五花肉蛋包饭,相比来说,比重邮的蛋包饭要好吃太多了。食堂出来又感觉有点没吃饱,于是又在他们食堂门口买了几串烧烤。。

然后就直接回酒店了。在酒店玩了会电脑,就去打cf了。这场cf又没打好,卡dp卡了很久,导致一道很简单的01构造题没做出来,到嘴边的烂分没了。期间,乐子他们队在隔壁房间打训练赛,太优秀了吧qaq

4.17

为了吃酒店的早饭,特地起了个大早。酒店的早餐一般吧,种类不多,但是味道还算不错。接饮料的机器有点垃圾,停的时候要停好一会,导致咖啡满出来了。另外,沙拉和卷心菜都很好吃。

吃完回房间。因为昨天已经报道了,所以早上没什么事,于是就打开电脑补昨晚cf的构造题。昨天其实已经写的七七八八了,今天又写了会,wa了几发,就过了。

然后去洗了个澡,就去补觉了。

11点多,我两个队友和乐子出发去西工大。由于企业的宣讲并不是很感兴趣,于是中午就不和他们去学校了。点了份外卖,然后就开始改begonia(go写的rpc框架)的bug。改着改着就忘记外卖这回事了,推到github之后发现已经1点了外卖还没到!于是很生气地打电话过去对线。催了好几次后才送到,不过味道还算可以,老板娘态度也还算好,就没那么生气了,然后也忘了给差评。。。

摸了亿会鱼,就出发去西工大了。到学校是三点左右,刚好赶上开幕式,就顺便过去听了一下。开始是icpc委员会的一个忘了什么职位什么名字的教授致辞,然后只记得:西工大的老师致辞、选手代表宣誓、教练代表致辞。。听的有点无聊,三点四十左右开幕式结束,慢悠悠地前往比赛场地打热身赛。

比赛场地位于翱翔体育馆。进入场地的那一瞬间,还是让人很震撼的:非常宽广的场地,整洁又密集的桌子上放着队伍牌和电脑,抬头看,是有些晃眼的吊灯。进入集训队一年半的时间,第一次见到如此盛大的场面,有些兴奋,但随即又有些不安。

然后出了点小问题,转了一圈都没找到我们队伍的位置,然后问志愿者,才发现我们队的位置就在入口附近。

成功和队友会合后,不一会电脑也解锁了,然后打开电脑开始熟悉环境。

然后热身赛开始了,然后爆0了。。。

打完后遇到乐子,发现他们也爆0 了,就很难过。

体育馆外,有些人去找西工大的同学玩了,我们剩下三个在西工大没有同学的,就在边上的超市买了点东西回酒店了。

晚饭出于好奇,外卖点了份羊肉泡馍。然后就上当了。大概是我找的店有问题吧,他家的羊肉泡馍很浓的羊骚味。吃了一点就不想再吃了,又点了一份炸排骨。

8:40,大家都回来之后,我们稍微讨论了一下今天的热身赛。总结了下教训就分开了。

晚上洗了个澡,就上床睡觉了。

然后。。一点左右,被窗外的施工的声音吵醒。其实晚上的时候就一直在施工,我以为过一会他们就下班了,睡前也懒得管。然后,施工一直持续到三点多,我也是三点多才睡着的。中间有想过报警,但是我一想到我只是个旅居在外的弱小大学生,想想还是算了。

4.18

虽然睡的晚,但还是早早就起床了。七点四十左右下楼吃早饭。有了昨天的教训,今天咖啡终于没撒出来。早上也没啥胃口,就随便吃了点沙拉。

8点左右打车去西工大。8点20到翱翔体育馆。

由于没有开始入场,我们就在体育馆外面等了一会。我两个队友早起去学校找打印店打印模板了(其实可以在酒店打印的)。

会合并且寄存好手机之后,就入场了。然后就开始调试电脑。建文件夹,打开IDE。在clion上配置external tools和keymap(主要是我自己用)。然后就等待发题了。

比赛开始后就分开读题。签到题是我看的,看完还是有点犹豫的。不过看到前面的队伍很快就过题了之后,我就开始写了。27分钟左右写完,提交,一遍过。看了眼排名,19名,开局还算不错。

然后开始写另一道全场题。然后就卡了。卡了很久,中间开了a和b,但是也没有想出来。一直到结束前的最后几分钟,才把全场题做出来。。

然后比赛就结束了。毫无悬念是个铁牌。不久乐子就找到我们了,他们第三题没做出来,挺可惜的。

然后就是去看颁奖典礼和闭幕式。

没想到的是闭幕式之前还有一波企业宣讲。然后我就听睡着了,一直到华为讲完才睡醒。闭幕式也没啥好说的,不过滚榜还是很有意思的。没有拿到顽强拼搏奖,还是有点可惜的。

闭幕式结束之后,去翱翔体育馆门口补了张照片,然后就坐车去大秦酒店参加晚宴。有两个同学觉得麻烦,就没去。

一开始我还以为大秦很近,结果坐了两个小时的车才到。到了之后都饿坏了,遂开始狼吞虎咽地扒饭。晚宴吃的是自助餐,菜还算好吃吧,可惜有点冷了。特别喜欢肥牛和五花肉。不过晚宴上还有个看起来像是酸辣粉一样的东西,拿了之后发现是芥末qaq。

然后就开始表演了。现场音响实在是有些一般,歌感觉不是很好听。然后就是一些演讲、游戏,和抽奖了。由于前几轮都没抽到我,于是就换了个头像希望转运。然后,就抽到了个平板。在大佬们略微有些羡慕的眼神中上台领奖,大概是我这次参赛唯二的高光了吧。

九点多发车回酒店。晚上11点到,洗了个澡,上GitHub看了一圈开源oj,就睡了。

第二天返程,很顺利,就不说了。

西安之旅就这样结束了。

总结

打铁了还是挺不甘心的吧,特别是现场赛打铁,让人更能感受和大佬之间的差距。

去年拿了银牌之后,其实还是有一点骄傲的。但同时也明白那个银牌还是有一点运气成分的(毕竟银牌题其实并没有做出来)。也一直想证明自己配得上这块银牌吧,包括2月3月也刷了不少题,不过就结果来看,做的题还是远远不够的。

总之,以后要好好训练了(不能再偷懒不打cf了)。

timudayi

链接:https://codeforces.com/problemset/problem/1514/D

题目大意

给定一个长为n的序列a,有q次询问,每次询问给定一个区间$[l, r]$,问最少要将这个区间划分多少次(不一定连续),使得每个划分(假设长度为len)里众数的个数f满足:$f\leq \lceil \frac {len} 2 \rceil$。

题目分析

如果对于$[l,r]$,众数个数已经小于等于$\lceil \frac{len} 2 \rceil$,那么就不用再划分子了。

否则,就存在这样一种构造法:

假设众数个数为f,那么就剩下的数有len-f个,这些len-f个非众数数可以和len-f+1个众数一起划分到一个子区间中。剩下的众数就单独划分到一个集合中,总共需要$1+f-(len-f+1)=2*f-len$个划分。

那么现在的问题就是怎么快速求众数了。

一般来说,要使用莫队算法。但是在这道题中,出现次数未超过$\lceil \frac{len} 2 \rceil$的众数并没有意义,所以我们也可以用主席树求。具体看代码,时间复杂度$O(n\log n)$。

AC代码

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"

using namespace std;
const int N = 3e5 + 10;

struct Tree {
int *sum, *ls, *rs;
int n, cnt;

Tree(int n) {
sum = new int[n << 5];
ls = new int[n << 5];
rs = new int[n << 5];
cnt = 0;
}

int build(int l, int r) {
int rt = ++cnt;
sum[rt] = 0;
if (l < r) {
int mid = (l + r) >> 1;
ls[rt] = build(l, mid);
rs[rt] = build(mid + 1, r);
}

return rt;
}

int update(int pre, int l, int r, int x) {
int rt = ++cnt;
ls[rt] = ls[pre], rs[rt] = rs[pre], sum[rt] = sum[pre] + 1;
if (l < r) {
int mid = (l + r) >> 1;
if (x <= mid) ls[rt] = update(ls[pre], l, mid, x);
else rs[rt] = update(rs[pre], mid + 1, r, x);
}

return rt;
}

// 查找有没有大于一半的
int query(int u, int v, int l, int r, int lim) {
if (l >= r) return sum[v] - sum[u];
if (sum[v] - sum[u] <= lim) return 0;
int x = sum[ls[v]] - sum[ls[u]], y = sum[rs[v]] - sum[rs[u]];

int mid = (l + r) >> 1;
int res;
if (x > lim && (res = query(ls[u], ls[v], l, mid, lim)) > lim) return res;
if (y > lim && (res = query(rs[u], rs[v], mid + 1, r, lim)) > lim) return res;
return 0;
}
};

int n, q, m;
int a[N], b[N], rt[N];

int main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
b[i] = a[i];
}

sort(b + 1, b + 1 + n);
m = unique(b + 1, b + 1 + n) - (b + 1);

Tree t(N);
rt[0] = t.build(1, m);
for (int i = 1; i <= n; i++) {
int p = lower_bound(b + 1, b + 1 + m, a[i]) - b;
rt[i] = t.update(rt[i - 1], 1, m, p);
}

while (q--) {
int l, r;
scanf("%d%d", &l, &r);
int lim = ceil((r - l + 1.0) / 2);
int f = t.query(rt[l - 1], rt[r], 1, m, lim);

printf("%d\n", max(1, 2 * f - (r - l + 1)));
}
}

A. Alexey and Train

链接:https://codeforces.com/problemset/problem/1501/A

题目大意

有一列火车,要从站台1开往站台n,现在给你预期到达时间$a_i$和预期发车时间$b_i$,以及列车在从i-1站驶向i站时的延误时间$tm_i$,求火车到达站台n的时间。

当延误时,列车在站台i停靠的时长T应满足:

  • $T\geq \lceil\frac {b_i - a_i} 2\rceil$
  • 使实际发车时间$\geq$预期发车时间

分析

简单模拟,计算出到达每一站的时间和从每一站出发的时间即可。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int a[N], b[N], t[N];
int aa[N], bb[N];
int n;

int main() {
int T; cin >> T;
while (T--) {
memset(aa, 0, sizeof aa);
memset(bb, 0, sizeof bb);
cin >> n;

for (int i = 1; i <= n; i++) scanf("%d%d", a + i, b + i);
for (int i = 1; i <= n; i++) scanf("%d", t + i);
for (int i = 1; i <= n; i++) {
aa[i] = a[i] - b[i - 1] + t[i] + bb[i - 1];
bb[i] = max(aa[i] + (int)ceil((b[i] - a[i] + 0.0) / 2), b[i]);
}

cout << aa[n] << endl;
}
}

B. Napoleon Cake

链接:https://codeforces.com/problemset/problem/1501/B

题目大意

一个长度为n数组,初始值都是0,有n次操作,操作i给定$a_i$,让你给区间$[i-a_i+1,i]$都加上1,最后问你哪些位大于0,哪些位等于0。

分析

因为可以很显然的转化为区间维护问题,没多想就直接上树状数组了,就ac了(幸好没卡$n\log n$)。

但是,fzh大佬指出,差分前缀和可以在$o(n)$的复杂度内解决问题,是我菜了

AC代码(树状数组)

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>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

ll n, a[N], t[N << 2];

void init() {
memset(t, 0, sizeof(int) * (n << 2));
}

int lowb(int x) {
return x & (-x);
}

void update(int x, ll k) {
for (; x <= n; x += lowb(x)) t[x] += k;
}

int query(int x) {
ll res = 0;
for (; x > 0; x -= lowb(x)) res += t[x];
return res;
}

void modlify(int l, int r) {
if (l > r) return;
l = max(l, 1);
update(l, 1);
update(r + 1, -1);
}

int main() {
int T;
cin >> T;
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
init();

for (int i = n; i > 0; i--) {
if (a[i] > 0) modlify(i - a[i] + 1, i);
}

for (int i = 1; i <= n; i++) {
if (query(i) > 0) printf("1 ");
else printf("0 ");
}
puts("");
}
}

C. Going Home

链接:https://codeforces.com/problemset/problem/1501/C

题目大意

给定n个数($n\leq 2e5$)$a_1,a_2……a_n$($a_i\leq2.5e6$),找出四个不同的整数x,y,z,w,使得$a_x+a_y=a_z+a_w$。

分析

看到题目你是不是想到了meeting in the middle?如果是,那么你答对了$\sqrt{max(n)}$。

如果只看n的范围,不难猜测,我们需要在$O(n\log n)$的时间内解决这个问题,显然这几乎是不可能(是我能解决)的。但是$a_i$的值域给了一个非常奇怪的数2.5e6,这让我们有了操作空间。

首先,如果同一个数出现超过三次,那么可以很显然的得到答案,所以,我们考虑所有数出现的次数都小于等于3的情况。

此时,就算序列a中的每一个数都出现了3次,我们依然有超过5e4个不同的数

我们先把序列a从小到大排列,再把重复的数去掉,得到新的序列$A_1,A_2……A_m$。再对序列A做差分,得到序列$b1,b2……bm-1$,其中$b_i=a_{i+1}-a_i$。

此时,我们可以得到结论:$若i-j\geq 2 \ 且\ b_i=b_j $,那么i+1,j,i,j+1就是所求解。

那么我们假设出题者非常恶毒,他想使所有的$b_i$都尽量不相等!那么在最严苛的条件下,就有:

这时就恰好无解了(很烦)。

我们在这个条件下我们对序列b求和:

$又\because \ \ \ \ \ \sum b_i=max\{a_i\}-min\{a_i\}=2.5e6=A_m-A_1$(因为是差分)

$\therefore\ \ \ A_m-A_1=\frac {n^2} 4$

如果此时,我们将某个$b_i(i>2)$减少1,那么就变成了:

$\therefore\ \ \ A_m-A_1=\frac {n^2} 4-1<\frac {n^2} 4$

注意,序列b是对序列A差分得到,因此b的和永远是$A_m-A_1(等式左边)$,但是,$\frac {n^2} 4$是由等差数列求和算的。当$b_i$发生变化时,序列b就不再是等差数列,因此求和也不可以再直接由等差数列求和得到(但是可以通过补全为等差数列求和得到)。

不难发现某个$b_i(i>2)$减少1后,就必然会出现元素相同的情况,此时满足$i-j\geq 2 \ 且\ b_i=b_j $,因此一定有解。

同理,如果继续减小$b_i(i>2)$,也必然会有解的,

因此,当$\therefore\ \ \ A_m-A_1<\frac {n^2} 4$时,我们一定能找到解。

由于,$A_m-A_1<2.5e6$,所以只要$n>1000\sqrt 10\approx3162.27$,就必然有解,且必然有一组解是在序列A中两对不相交的相邻的两个数。

如果不满足这个条件,由于数据很小,暴力就好了 ,芜湖!

另外如果你足够有耐心,也可以精确算出必然有解的条件(注意上述过程只是估算,实际上n的取值最好大于3200)。

AC代码

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>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

struct node {
// val = x - y (n>3e3)
// val = x + y (else)
int val, x, y;

node(int v, int xx, int yy) : val(v), x(xx), y(yy) {}

bool operator<(const node &rhs) const {
return val < rhs.val;
}
};

int a[N], b[N], n;


int main() {
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
b[i] = a[i];
}

set<node> s;
if (n > 3e3) {
int ans[4];

sort(a, a + n);
node t(0, 0, 0);
for (int i = 1; i < n; i++) {
if (i > 1 && s.count(node(a[i] - a[i - 1], 0, 0))) {
auto x = s.find(node(a[i] - a[i - 1], 0, 0));
printf("YES\n");
ans[0] = x->x;
ans[1] = i - 1;
ans[2] = x->y;
ans[3] = i;
break;
}
if (i > 1) s.insert(t); // 注意这里的细节,不能直接插入
t = node(a[i] - a[i - 1], i, i - 1);
}

for (int k = 0; k < 4; k++) {
int i = ans[k];
for (int j = 0; j < n; j++)
if (a[i] == b[j]) {
int ok = 1;
for (int kk = 0; kk < k; kk++)
if (ans[kk] == j) {
ok = 0;
break;
}
if (ok) ans[k] = j;
}
}

for (int an : ans) printf("%d ", an + 1);
puts("");
} else {
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if (i != j && !s.count(node(a[i] + a[j], 0, 0)))
s.insert(node(a[i] + a[j], i, j));

for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) if (i != j) {
if (s.count(node(a[i] + a[j], 0, 0))) {
auto p = s.find(node(a[i] + a[j], 0, 0));
if (p->x != i && p->y != j && p->x != j && p->y != i) {
printf("YES\n");
printf("%d %d %d %d\n", i + 1, j + 1, p->x + 1, p->y + 1);
return 0;
}
}
}
printf("NO\n");
}
}

链接:https://codeforces.ml/contest/1463/problem/B

题目大意

给你一个序列a[1..n],其中$1\leq a_i \leq 10^9$,S为a所有元素的和。要求构造一个”美丽序列“B[1..n]满足:

  • $1≤b_i≤10^9 $
  • 要么$b_i$ 整除$b_{i+1}$ ,要么$b_{i + 1}$ 整除$b_i$ 。
  • $2\sum_{i=1}^{n}{|a_i-b_i|}\leq S$

保证一定有解,输出任意一种。

分析

很有意思但是不难的构造题。

因为是第三个条件的左边有个系数2,不难想到利用2进制进行构造。具体做法为,对于任意$a_i$,其对应的$b_i$就是$2^{\lfloor \log_{2}{a_i}\rfloor}$,也就是$a_i$的二进制最高位。

这时我们不难发现,$|a_i-b_i|\leq \frac{a_i}2$,所以一定是满足条件3的。同时,因为B[1..n]都是2的幂,因此任意B的任意两个元素必然有一个可以整除对方。于是这道题就这么做完了(又水了一骗博客)

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 50 + 5;

int a[N], n;

int getB(int x) {
for (int i = 0; i <= 31; i++) {
if ((1 << i) > x) return 1 << (i - 1);
}
return 1;
}

int main() {
int T; cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; i++) {
scanf("%d", a + i);
printf("%d ", getB(a[i]));
}
printf("\n");
}
return 0;
}

链接:https://ac.nowcoder.com/acm/contest/9925/B

题目大意

给你2个n×m扫雷图A、B,图中没有雷的格子会有一个数字x,表示这个格子周围9×9的格子中有多少个雷。现在你可以最多修改B图$\frac {nm}2$次来使得两个图中的数字之和相等,输出修改后的B图。

分析

考虑数字和就等于相邻(雷格子,非雷格子)二元组的个数,于是把整个地图全反过来这个二元组个数不变,然后 $B$ 与 $A$之间以及 $B$ 与 $inv(A)$ ,即把 $A$ 所有格子全部取反的扫雷地图之间总有一个偏差不超过一半的,所以就选其中偏差不超过一半的然后变过去就行。

AC代码

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>
using namespace std;
const int N = 1000 + 5;
int ga[N][N], gb[N][N];
int n, m, cntOri, cntInv;

void print() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
printf("%c", gb[i][j] ? 'X' : '.');
printf("\n");
}

}

int main() {
cin >> n >> m;
char ch;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf(" %c", &ch);
ga[i][j] = ch == 'X' ? 1 : 0;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf(" %c", &ch);
gb[i][j] = ch == 'X' ? 1 : 0;
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cntOri += ga[i][j] ^ gb[i][j] ^ 1 ;
cntInv += ga[i][j] ^ gb[i][j];
}

int f = cntOri > cntInv ? 0 : 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
gb[i][j] = ga[i][j] ^ f;
}
print();
}

题目大意

一开始给你一个数n=1和一个模数M(不一定为质数),之后会有q($q<10^5$)次操作,每次操作操作给两个数f,x($x<10^9$)

  • f=1时,表示给n乘上x
  • f=2时,表示给n除以第x次操作乘的那个数

每次操作后输出n对M取模的值。

分析

因为M不为质数,所以显然不能用逆元。x也很大,高精很有可能被卡时间复杂度。此时不难想到万能数据结构——分块。

具体做法是,将每次乘的数放到一个块里,然后对于每个块维护乘数模M的结果ans[i]。当f=1时,将x插入到相应的块中,同时将ans[i]乘上x再取模。当f=2时,将块中的x直接修改为1,并暴力重构块。

每次操作后n的值就是ans[]的积。

当然线段树也是可以的。

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

struct opt {
int f, x;
}o[N];

int block[1000 + 5][2000 + 5], p[1000 + 5], ans[1000 + 5];
int arr[N];
int n, q, m, lenBlock;

int id(int x) {
return lower_bound(arr, arr + q, x) - arr;
}

void build() {
memset(p, 0, sizeof p);
for (int i = 0; i < n; i++) ans[i] = 1;
}

void process(int x) {
ans[x] = 1;
for (int i = 0; i < p[x]; i++) ans[x] = ans[x] * 1ll * block[x][i] % m;
}

int getAns() {
int res = 1;
for (int i = 0; i < n; i++) res = res * 1ll * ans[i] % m;
return res;
}

void add(int x) {
int pos = id(x), i = pos / lenBlock;
block[i][p[i]++] = x;
ans[i] = ans[i] * 1ll * x % m;
}

void del(int x) {
int pos = id(x), i = pos / lenBlock;
for (int j = 0; j < p[i]; j++) if (block[i][j] == x){
block[i][j] = 1;
break;
}
process(i);
}


int main() {
int T; cin >> T;
for (int kase = 1; kase <= T; kase++) {
cin >> q >> m;
for (int i = 0; i < q; i++) {
scanf("%d %d", &o[i].f, &o[i].x);
arr[i] = o[i].x;
}
sort(arr, arr + q);
lenBlock = sqrt(q + 0.5);
n = ceil((q + 0.0) / lenBlock);
build();
printf("Case #%d:\n", kase);
int res = 1;
for (int i = 0; i < q; i++) {
if (o[i].f == 1) add(o[i].x), res = res * 1ll * o[i].x % m;
else del(o[o[i].x - 1].x), res = getAns();
printf("%d\n", res);
}
}
}

题目大意

有一个对于一个有序数对$(a,b)$和$k1,k2,b1$,要求满足等式

问这样的a,b 有多少对?以字典序输出。

分析

当n=1时,有

$a^{k1+b1}+b\equiv0(modC)$ ————式1

当n=2时,有

$a^{k1+b1}a^{k1}+bb^{k2}\equiv0(modC)$ ————式2

又因为 $a^{k1+b1}a^{k1}+ba^{k1}\equiv0(modC)$

所以有$a^{k1}\equiv b^{k2}(modC)$

显然,当n等于1,2时都满足等式的话,后面也是一定会满足的(归纳法)。

所以我们只要判断前两种情况就好了。具体来说,枚举a的所有可能值(1~C-1),然后根据式1算出b,再去判断a,b是否满足式2。由于是从小到大枚举a,因此一定是满足字典序的

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll C, k1, k2, b1;

ll qpow(ll base, ll p) {
if (p <= 0) return 1;
ll res = qpow(base, p >> 1);
res = res * 1ll * res % C;
if (p & 1) res = res * 1ll * base % C;
return res;
}

int main() {
int kase = 0;
while (cin >> C >> k1 >> b1 >> k2) {
printf("Case #%d:\n", ++kase);
int ans = 0;
for (ll a = 1; a < C; a++) {
ll b = C - qpow(a, k1 + b1);
if ((qpow(a, (k1 << 1) + b1) + qpow(b, k2 + 1)) % C == 0) {
printf("%lld %lld\n", a, b);
ans++;
}
}
if (ans == 0) printf("-1\n");
}
}

github地址:https://github.com/allegro/bigcache

简介

先扒一波官方文档凑字数

Fast, concurrent, evicting in-memory cache written to keep big number of entries without impact on performance. BigCache keeps entries on heap but omits GC for them. To achieve that, operations on byte slices take place, therefore entries (de)serialization in front of the cache will be needed in most use cases.

机器翻译:快速,并发,驱逐内存中的高速缓存,以保持大量的条目不影响性能.BigCache将条目保存在堆中,但忽略了它们的GC。为此,对字节片进行操作,因此在大多数用例中都需要缓存前面的条目(反序列化)。

虽然redis具有非常不错的性能(官方数据读的速度是110000次/秒,写的速度是81000次/秒),但是这并不等于我们一个进程在一秒可以对redis做好几万次操作。比如,现在基本都是用TCP协议建立与本地redis的连接,那么每次对redis进行操作都要把数据打包发到运输层,运输层再发到网络层,然后才返回发到本地的redis进程上。虽然使用pipeline可以减少一部分I/O时间消耗,但总归还是有性能瓶颈,很难达到每秒几万的操作效率。

因此,在没有使用分布式服务器的情况下,进程内缓存就显得很好用了。

此外,bigcache还拥有以下非常好用的特性:

  • 即使拥有百万记录也非常快(主要用哈希实现)
  • 提供并发访问
  • 在预定的时间后移除记录

简单使用

又来扒拉一波官方文档

1
2
3
4
5
6
7
8
9
10
11
import "github.com/allegro/bigcache"

func main() {
// 声明一个缓存
cache, _ := bigcache.NewBigCache(bigcache.DefaultConfig(10 * time.Minute))

cache.Set("my-unique-key", []byte("value"))

entry, _ := cache.Get("my-unique-key")
fmt.Println(string(entry))
}

使用该库主要有以下几个特点

  • 主要操作只有Set、Get、Delete、Len
  • 只能存取[]byte类型
  • config对象的设置对速度的影响较大
  • 需要用自定义的config时需要实现Hasher接口

config对象简介

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
// Config for BigCache
type Config struct {
// Number of cache shards, value must be a power of two
// 分片类型的数量,用于并发优化
Shards int

// Time after which entry can be evicted
// 第一次删除的时间
LifeWindow time.Duration

// Interval between removing expired entries (clean up).
// If set to <= 0 then no action is performed. Setting to < 1 second is counterproductive — bigcache has a one second resolution.
// 删除的时间间隔
CleanWindow time.Duration

// Max number of entries in life window. Used only to calculate initial size for cache shards.
// When proper value is set then additional memory allocation does not occur.
// 大概就是删除队列的初始大小,在一开始分配,超过了就动态扩容
MaxEntriesInWindow int

// Max size of entry in bytes. Used only to calculate initial size for cache shards.
// 单个value的最大大小,用于计算初始cache shards大小
MaxEntrySize int

// Verbose mode prints information about new memory allocation
// 机器翻译:详细模式打印有关新内存分配的信息
Verbose bool

// Hasher used to map between string keys and unsigned 64bit integers, by default fnv64 hashing is used.
// 你要使用的哈希函数
Hasher Hasher

// HardMaxCacheSize is a limit for cache size in MB. Cache will not allocate more memory than this limit.
// It can protect application from consuming all available memory on machine, therefore from running OOM Killer.
// Default value is 0 which means unlimited size. When the limit is higher than 0 and reached then
// the oldest entries are overridden for the new ones.
// 最大占用内存,不够用时会覆盖就内存,和redis有点像
HardMaxCacheSize int

// OnRemove is a callback fired when the oldest entry is removed because of its expiration time or no space left
// for the new entry, or because delete was called.
// Default value is nil which means no callback and it prevents from unwrapping the oldest entry.
// 由于各种原因删除数据时会触发的回调函数
OnRemove func(key string, entry []byte)

// OnRemoveWithReason is a callback fired when the oldest entry is removed because of its expiration time or no space left
// for the new entry, or because delete was called. A constant representing the reason will be passed through.
// Default value is nil which means no callback and it prevents from unwrapping the oldest entry.
// Ignored if OnRemove is specified.
// 用于传递释放数据的原因,有Expired,NoSpace,Deleted三种
OnRemoveWithReason func(key string, entry []byte, reason RemoveReason)

onRemoveFilter int

// Logger is a logging interface and used in combination with `Verbose`
// Defaults to `DefaultLogger()`
// 日志
Logger Logger
}

优化的一些原理

1、并发优化

由于bigcache支持并发,因此势必会用锁(事实用的是读写锁)。在高并发场景下,如果只用一把读写锁,势必会显著影响读写速度。解决方案是用分块的思想(想必大家在数据结构上都听老师口糊过),把整个内存分成N个部分,每个部分单独分配一把锁保证并发安全。在哈希函数足够优秀的情况下,就可以实现同时允许好几个协程进行读写。

所以这部分的优化主要是N的选择以及哈希函数的选择。

(1)N的选择

首先N肯定不是越大越好,因为太大会带来很多不必要的开销(增加内存使用和寻找所在分块的时间),且性能提升也未必会很明显,所以要在性能和花销上寻找一个平衡。框架作者推荐的值是1024。

另外,N的值最好是2的幂,因为这样底层可以直接用位运算取模,进一步减少时间开销。

(2)Hash算法的选择

太玄学了还是算了

看了半天还是用他内置的FNV64a算法吧。

2、GC优化

Go1.5对GC进行了优化,如果map中的键值对都是基本类型,则GC会忽略他们。

因此框架作者利用这一特性,在每个分块中用map[uint64]uint32和一个预先分配的大字节数组(数组还是切片暂时没有证实)存储数据,把缓存对象序列化的后放到预先分配好的大字节数组中,把它的哈希值作为map[uint64]uint32的key,然后把它在数组中的offset作为map[uint64]uint32的value。

谈谈如何设计算法快速求出斐波那契第$n(n < 10^{18})$项?由于结果很大,因此输出对99999989取模的结果。

提示:1、99999989是质数;2、浮点数在经历多次运算后可能会出现精度不够的情况而导致答案错误;3、中的pow函数很慢,因此您可能需要重新设计pow函数。

参考公式:斐波那契的通项公式为:

$\frac 1 {\sqrt{5}}[(\frac {1+\sqrt{5}} 2)^n-(\frac {1-\sqrt{5}} 2)^n]$

参考答案:

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
#include <stdio.h>

typedef long long ll;
int MOD = 99999989; //模数,这里保证是一个奇质数
int inv5 = 50122571; // 根号5的对MOD取模的结果,暴搜得到
//这是负根号5:49877418
//也可以用二次剩余定理求,但这里没必要

// 朴素快速幂,时间上已经足够所以没有用欧拉函数优化
int qpow(int base, ll p, int mod) {
if (p <= 0) return 1;
int res = qpow(base, p >> 1, mod);
res = res * 1ll * res % mod;
if (p & 1) res = res * 1ll * base % mod;
return res;
}

// 逆元,费马小定理
int inv(int x, int mod) {
return qpow(x, mod - 2, mod);
}

// 模意义下取绝对值
int abs(int x, int mod) {
return (x % mod + mod) % mod;
}

//用通项公式求斐波那契第n项,时间 O(log MOD)
int fib(int n, int mod) {
int a = abs(1 + inv5, mod) * 1ll * inv(2, mod) % mod;
int b = abs(1 - inv5, mod) * 1ll * inv(2, mod) % mod;
return inv(inv5, mod) * 1ll * abs(qpow(a, n, mod) - qpow(b, n, mod), mod) % mod;
}

int main() {
int n, mod = MOD;
scanf("%d", &n);
printf("%d\n", fib(n, mod));
return 0;
}

链接:https://ac.nowcoder.com/acm/contest/7817/E

题目大意

给定一个区间$[n,m]$,统计这个区间内所有数的因数个数之和(包括1和自身),$1\leqslant n \leqslant m\leqslant 10^{12}$

题目分析

考虑一个数m的情况:由于所有因数总是成对出现,我们只需要枚举$[1,\sqrt{m}]$即可找出m的所有因数。

引申到区间,首先我们发现,$[n,m]$中所有数的因数对中,较小的那一个一定会小于$\sqrt{m}$,写成命题的话就是:

如果$a*b=x且x\in[n,m],那么min\{a,b\}\leqslant\sqrt{m} $

根据这个性质,我们从1到$\sqrt{m}$枚举其中一个因子 $x$,找到这样两个整数$l$,$r$使得:

为什么$l,r$要比x大呢?这是为了防止重复计算。如果我们有这样一个数$y$使得

那么在缺少这个限制时$y$和$y-1$这一对因数就会在$x=y,x=y-1$时分别被计算一次,答案就比正确答案大2。($ y-2,y-3…$同理)

这样,$[n,m]$中所有以x为因子的数的个数就是$r-l+1$,由于因数成对出现,我们就找到了$2*(r-l+1)$个因数。

值得注意的是平方数会多算一个因数,最后要把多余的数减掉。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
typedef long long ll;

ll n, m, ans;

ll calc(ll k) {
ll l = n / k + (n % k ? 1 : 0), r = m / k;
l = max(l, k); //防止重复统计
return 2 * (r - l + 1);
}

int main() {
cin >> n >> m;
for (ll i = 1; i * i <= m; ++i) {
ans += calc(i);
if (i * i >= n) ans--;
}
cout << ans << endl;
}