NOIp2017提高组游记

前言

NOIp2017已经结束了,由于复赛结束后我没有机会写游记,到这个周末才补上。虽然下个星期期中考

初赛日期2017/10/14,复赛2017/11/11和12,今年还是衢州。本文只包含复赛。

值得一提的是,复赛day1双十一和马拉松,day(-1)和day0是学校秋季运动会,当然我们甚至没机会去看开幕式。

day0

上午有一场两个半小时的模拟赛,题目确实不难,但是我只有230,而很多人都300,没什么信心。

T3给定一棵树,求保留最少的边使得覆盖的点不少于K,由于一条边可以覆盖1或2个点,可以用树形DP或贪心求出最多有几条边可以覆盖2个点,而我却写了二分图匹配,还写错了。还好交了暴力的30分。

12:30我们准时从西门出发,预计三个小时到,最终到四点左右才到达衢州饭店。路上基本也没干什么。

衢州饭店还是比较好的,我们住在三号楼一楼,要走过很长的走廊。矿泉水一个人一小瓶,杯子倒是很多。拖鞋是循环使用的,所以不能带走。我选了靠窗的床,事实证明还是很对的,因为可以方便放东西。无线网不太稳定,反而还是旁边的比较好。

从旅馆到衢州二中堵了很长时间,到学校领袋子,晚饭在学校吃。回去就快多了。晚上看了洛谷模板,包括(下次可以参考)

  • SSSP
  • KMP(看完认为还是滚回hash吧)
  • Dinic(初赛暗示网络流?)
  • 可并堆(还是不太会)
  • LCA(上午刚写过)
  • 树剖
  • 匈牙利
  • Tarjan割边割点
  • Lucas
  • exgcd(初赛前也看过)

我看了一会儿WARRIORS:Omen of The Stars #6 The Last Hope,再来一句StarClan, light my path, please. 规划好day1要带的物品后,我们十点多睡觉。

day1

6:20起床,去吃自助餐,并不是很好。我在9号考场,要走不少路才能到,不过去年也一样。

OS是Windows 7,我打开了仪表盘。果然没有Notepad++。

小凯的疑惑(math)

题意

给定a,b(a,b)=1a,b\vert (a,b)=1,求ax+byx,yNax+by\vert x,y\in\mathbb N不能表示的最大的数,保证有解。

1
3 7
1
11

数据范围

  • 对于30%的数据,a,b50a,b\le50
  • 对于60%的数据,a,b10,000a,b\le10,000
  • 对于100%的数据,1a,b1091\le a,b\le10^9

思路

看到这题我立刻想到了一道USACO的题目,猜想答案应该不大于ab+a+bab+a+b。对于ax+by=1ax+by=1,用exgcd求出x0,y0x_0,y_0,然后枚举cc,解为cx0+kb,cy0kbcx_0+kb,cy_0-kb,强制x0x\ge0,如果y<0y<0显然无解。不过我不知道复杂度,后来还列出了一个带上取整的不等式,解出的结果只含有a,ba,b,但是样例都不对,于是我放弃了。直接从abab向下枚举,输出第一个无解的数。好像a,b106a,b\le10^6都能很快算出。

时间复杂度O(?)\mathcal O(?),预计得分60/60+


结束后才知道大部分人都做出了这题,答案是ababab-a-b。所以我的时间复杂度为O(a+b)\mathcal O(a+b)

代码

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 <fstream>
#include <algorithm>
using namespace std;
ifstream fin("math.in");
ofstream fout("math.out");
void exgcd(int a, int b, long long &x, long long &y)
{
if (!b)
{
x = 1;
y = 0;
}
else
{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
int main()
{
int a, b;
fin >> a >> b;
if (a > b)
swap(a, b);
long long x, y;
exgcd(a, b, x, y);
for (long long c = 1ll * a * b; c >= 0; c--)
{
long long k = -x * c / b;
if (x * c + 1ll * k * b < 0)
k++;
long long ny = y * c - 1ll * k * a;
if (ny < 0)
{
fout << c << endl;
return 0;
}
}
return 0;
}

用来对拍的暴力:

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 <fstream>
using namespace std;
ifstream fin("math.in");
ofstream fout("math.ans");
int main()
{
int a, b;
fin >> a >> b;
for (int c = a * b + a + b; c; c--)
{
bool flag = false;
for (int i = 0; i <= c; i += a)
if ((c - i) % b == 0)
{
flag = true;
break;
}
if (!flag)
{
fout << c << endl;
break;
}
}
return 0;
}

时间复杂度(complexity)

题意

给定一个LL行只含有for循环的程序,初值和末值可以是常数或nn,判断其复杂度分析是否正确。可能存在循环不匹配和变量重名错误需要判断。多组数据。

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
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
1
2
3
4
5
6
7
8
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

数据范围

  • 对于30%的数据,数据保证小明给出的每个程序的前L/2L/2行一定为以F开头的语句,第L/2+1L/2+1行至第LL行一定为以E开头的语句,L10L\le10
  • 对于50%的数据,若x,yx,y均为整数,xx一定小于yy,且只有yy有可能为nn
  • 对于70%的数据,不存在语法错误。
  • 对于100%的数据,L100L\le100

思路

麻烦的题目,不过我自认为有优势,看起来有点像COWBASIC。nn和常数怎么判断呢?不过我很快想到了数值法,把很大的数代入nn,求一下实际复杂度和理论复杂度,如果误差是很小的则认为正确。

接下来的问题在于确定nn的值。一开始我以为最多有50层循环,后来发现由于字母的限制最多只有25层。一开始我选择了{500,1000}\{500,1000\},后来发现太小了。最终我选择了{109,2×109}\{10^9,2\times10^9\},用double计算。最大误差取0.010.01

还有表达式计算的问题,我发现每层栈里应该保存该层循环次数和该层累计的数值。

时间复杂度O(L)\mathcal O(L),预计得分100


结束后才得知只需要模拟一下,因为每层循环只能执行00,Θ(1)\Theta(1)Θ(n)\Theta(n)次。注意判断执行00次时的问题即可。

代码

很长……调了不少时间

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
#include <fstream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("complexity.in");
ofstream fout("complexity.out");
const int N = 105, vn[] = {1000000000, 2000000000};
double s[N][2], res[2];
bool vis[26];
struct line
{
int opt, l, r;
} prog[N];
int str2int(const string &s)
{
stringstream ss(s);
int x;
ss >> x;
return x;
}
double calc(const line &p, int n)
{
int l = p.l, r = p.r;
if (l == 1000)
l = n;
if (r == 1000)
r = n;
return max(r - l + 1, 0);
}
int main()
{
int t;
fin >> t;
while (t--)
{
int l;
string comp;
fin >> l >> comp;
memset(vis, 0, sizeof(vis));
bool valid = true;
string st;
for (int i = 1; i <= l; i++)
{
char opt;
fin >> opt;
if (opt == 'F')
{
char var;
string l, r;
fin >> var >> l >> r;
if (vis[var - 'a'])
valid = false;
vis[var - 'a'] = true;
st += var;
prog[i].opt = 1;
if (l == "n")
prog[i].l = 1000;
else
prog[i].l = str2int(l);
if (r == "n")
prog[i].r = 1000;
else
prog[i].r = str2int(r);
}
else
{
if (st == "")
valid = false;
else
{
vis[st[st.length() - 1] - 'a'] = false;
st.erase(st.length() - 1, 1);
}
prog[i].opt = 2;
}
}
if (st != "")
valid = false;
if (!valid)
{
fout << "ERR\n";
continue;
}
for (int t = 0; t < 2; t++)
{
s[0][1] = .0;
int sp = 0;
for (int i = 1; i <= l; i++)
if (prog[i].opt == 1)
{
s[++sp][0] = calc(prog[i], vn[t]);
s[sp][1] = .0;
}
else
{
if (s[sp][1] == .0)
s[sp][1] = 1.;
s[sp - 1][1] += s[sp][0] * s[sp][1];
sp--;
}
double th;
if (comp == "O(1)")
th = 1.;
else
th = pow(vn[t], str2int(comp.substr(4, comp.length() - 5)));
if (s[0][1] == .0)
s[0][1] = 1.;
res[t] = s[0][1] / th;
}
if (fabs(1 - res[0] / res[1]) < 0.01)
fout << "Yes\n";
else
fout << "No\n";
}
return 0;
}

逛公园(park)

题意

求有向图中1>N1->N长度不超过d+Kd+K的路径数,其中dd1>N1->N的最短路长度,可能有0边,如果有无穷条合法路径输出1-1。多组数据

1
2
3
4
5
6
7
8
9
10
11
12
2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
1
2
3
-1

数据范围

测试点编号 TT NN MM KK 是否有0边
1 5 5 10 0
2 5 1000 2000 0
3 5 1000 2000 50
4 5 1000 2000 50
5 5 1000 2000 50
6 5 1000 2000 50
7 5 100000 200000 0
8 3 100000 200000 50
9 3 100000 200000 50
10 3 100000 200000 50

思路

T2用了较多时间。毫无思路,当然K=0K=0就是最短路计数,而K>0K>0好像可以用K短路之类的方法。于是我还求了NN为起点的最短路,然后从11开始dfs,如果当前距离+最短路>d+K>d+K剪枝。不知道有多少分。

时间复杂度{O((n+m)logn)K=0O(?)K>0\begin{cases}\mathcal O((n+m)\log n)&K=0\\ \mathcal O(?)&K>0\end{cases},预计得分30/30+

代码

这份代码没有包含functional,在VC++下std::greater\未定义。

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
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("park.in");
ofstream fout("park.out");
const int N = 100005, M = 200005, INF = 1e9;
int n, m, k, p, head[N], v[M], w[M], nxt[M], e, d[N], f[N];
int rhead[N], rv[M], rw[M], rnxt[M], re, rd[N], ans;
bool vis[N];
inline void add_edge(int u, int v, int w)
{
::v[++e] = v;
::w[e] = w;
nxt[e] = head[u];
head[u] = e;
}
inline void radd_edge(int u, int v, int w)
{
::rv[++re] = v;
::rw[re] = w;
rnxt[re] = rhead[u];
rhead[u] = re;
}
void dfs(int u, int dist)
{
if (dist + rd[u] > d[n] + k)
return;
if (u == n)
{
ans = (ans + 1) % p;
return;
}
for (int i = head[u]; i; i = nxt[i])
dfs(v[i], dist + w[i]);
}
int main()
{
int t;
fin >> t;
while (t--)
{
fin >> n >> m >> k >> p;
e = re = 0;
fill(head + 1, head + n + 1, 0);
fill(rhead + 1, rhead + n + 1, 0);
while (m--)
{
int u, v, w;
fin >> u >> v >> w;
add_edge(u, v, w);
radd_edge(v, u, w);
}
typedef pair<int, int> state;
fill(d + 1, d + n + 1, INF);
d[1] = 0;
priority_queue<state, vector<state>, greater<state>> Q;
Q.push(make_pair(0, 1));
fill(f + 1, f + n + 1, 0);
f[1] = 1;
fill(vis + 1, vis + n + 1, false);
while (!Q.empty())
{
state k = Q.top();
Q.pop();
if (vis[k.second])
continue;
vis[k.second] = true;
for (int i = head[k.second]; i; i = nxt[i])
if (d[k.second] + w[i] < d[v[i]])
{
f[v[i]] = f[k.second];
Q.push(make_pair(d[v[i]] = d[k.second] + w[i], v[i]));
}
else if (d[k.second] + w[i] == d[v[i]])
(f[v[i]] += f[k.second]) %= p;
}
if (k == 0)
fout << f[n] << endl;
else
{
fill(rd + 1, rd + n + 1, INF);
rd[n] = 0;
priority_queue<state, vector<state>, greater<state>> Q;
Q.push(make_pair(0, n));
fill(vis + 1, vis + n + 1, false);
while (!Q.empty())
{
state k = Q.top();
Q.pop();
if (vis[k.second])
continue;
vis[k.second] = true;
for (int i = rhead[k.second]; i; i = rnxt[i])
if (rd[k.second] + rw[i] < rd[rv[i]])
Q.push(make_pair(rd[rv[i]] = rd[k.second] + rw[i], rv[i]));
}
ans = 0;
dfs(1, 0);
fout << ans << endl;
}
}
return 0;
}

剩下的时间

听说很多人都会做T1和T3,大多200+,我感到很绝望,希望T2不要炸。听说T1是小学奥数题,以及有人做过原题。而T3则是“图论算法集合”?

下午没看几页书,晚饭据说从学校打包到旅馆,还必须在员工餐厅里吃,不过zyy好像早跑了。晚上看了一集下午的《自然传奇》,心态好了很多。fks提出敲一下[ZJOI2008]树的统计,他很快就A了,我很害怕没去写,万一真的考了树剖呢。不过吸取一下把int开成char的教训。睡得比前一天早。

day2

奶酪(cheese)

题意

一块长宽无限高为hh的奶酪里有nn个半径均为rr的空洞,下表面z=0z=0,上表面z=hz=h。两个空洞相交或相切可以从一个到达另一个,与表面相交或相切则可以从表面到达空洞。求能否从下表面到达上表面。多组数据

1
2
3
4
5
6
7
8
9
10
3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
1
2
3
Yes
No
Yes

数据范围

  • 对于20%的数据,n=1n=1
  • 对于40%的数据,n8n\le8
  • 对于80%的数据,h,r,x,y,z10,000h,r,\vert x\vert,\vert y\vert,\vert z\vert\le10,000
  • 对于100%的数据,1n1,000,1h,r,x,y,z1091\le n\le1,000,1\le h,r,\vert x\vert,\vert y\vert,\vert z\vert\le10^9

思路

计算几何,吃笔记本稳了?分治?不过看到n1,000,T20n\le1,000,T\le20就很简单了,不就是直接bfs。注意一下long long应该就可以了吧。不会卡常吧?

时间复杂度O(Tn2)\mathcal O(Tn^2),预计得分100


果然那么简单还是有陷阱的,(2×109)2×3=12×1018>263(2\times10^9)^2\times3=12\times10^{18}>2^{63}!所以要unsigned long long或者把左边的一项移到不等式右边。只有80了。

让我欣慰的是,有人直接用浮点数开根,可能被卡常,还有人用了int……另外据说z0z\ge0

代码

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
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("cheese.in");
ofstream fout("cheese.out");
const int N = 1005;
int x[N], y[N], z[N];
bool vis[N];
inline long long sqr(long long x)
{
return x * x;
}
int main()
{
int t;
fin >> t;
while (t--)
{
int n, h, r;
fin >> n >> h >> r;
queue<int> Q;
for (int i = 1; i <= n; i++)
{
fin >> x[i] >> y[i] >> z[i];
if (abs(z[i]) <= r)
{
vis[i] = true;
Q.push(i);
}
else
vis[i] = false;
}
while (!Q.empty())
{
int k = Q.front();
Q.pop();
for (int j = 1; j <= n; j++)
if (!vis[j] && sqr(x[k] - x[j]) + sqr(y[k] - y[j]) + sqr(z[k] - z[j]) <= 4 * sqr(r))
{
vis[j] = true;
Q.push(j);
}
}
bool ans = false;
for (int i = 1; i <= n; i++)
if (vis[i] && abs(z[i] - h) <= r)
{
ans = true;
break;
}
if (ans)
fout << "Yes\n";
else
fout << "No\n";
}
return 0;
}

宝藏(treasure)

题意

给定一张无向图,需要选定一个点ss,每条边的代价ci=wi×(min(dists,ui,dists,vi)+1)c_i=w_i\times(\min(dist_{s,u_i},dist_{s,v_i})+1),求生成树最小代价和。

1
2
3
4
5
6
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
1
4

数据范围

  • 对于20%的数据,保证输入是一棵树
  • 对于40%的数据,所有wiw_i相等
  • 对于70%的数据,n8,wi5,000n\le8,w_i\le5,000
  • 对于100%的数据,1n12,0m1,000,wi500,0001\le n\le12,0\le m\le1,000,w_i\le500,000

思路

重边显然取min,这样边数只有n(n1)2\frac{n(n-1)}2,但好像基于边比较难做。似乎暴力也很难写,但我yy出了一种奇怪的做法:类似Prim,每次选择一个不在生成树中的点加入,更新最短路,然后继续搜。具体见代码。如果无解怎么办?

时间复杂度O(n3n!)\mathcal O(n^3n!),预计得分70


应该是状压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 <fstream>
#include <algorithm>
using namespace std;
ifstream fin("treasure.in");
ofstream fout("treasure.out");
const int N = 15, INF = 1e9;
int n, m, mat[N][N], d[N], ans;
void dfs(int k, int now)
{
if (now > ans)
return;
if (k == n)
ans = now;
for (int i = 1; i <= n; i++)
if (d[i] < INF)
for (int j = 1; j <= n; j++)
if (mat[i][j] && d[j] == INF)
{
d[j] = d[i] + 1;
dfs(k + 1, now + mat[i][j] * (d[i] + 1));
d[j] = INF;
}
}
int main()
{
fin >> n >> m;
while (m--)
{
int u, v, w;
fin >> u >> v >> w;
if (!mat[u][v] || w < mat[u][v])
mat[u][v] = mat[v][u] = w;
}
ans = INF;
for (int i = 1; i <= n; i++)
{
fill(d + 1, d + n + 1, INF);
d[i] = 0;
dfs(1, 0);
}
fout << ans << endl;
return 0;
}

列队(phalanx)

题意

给定一个n×mn\times m的矩阵AAAi,j=(i1)m+jA_{i,j}=(i-1)m+jqq次操作(n,m,q3105n,m,q\le3*10^5),每次删除一个位置(x,y)(x,y),然后将第xx行向左补齐,再将第mm列向前补齐,最后在An,mA_{n,m}填上删除的数。求每次删除的数。

1
2
3
4
2 2 3
1 1
2 2
1 2
1
2
3
1
1
4

数据范围

思路

果然有数据结构题,然而并不会做。不过部分分很丰富,有点天天爱跑步的感觉。

前30%直接暴力,而50%比较有趣,q500q\le500,远小于矩阵规模,可见很多行除第mm列外根本不会变。那么可以在每次询问时如果xx行第一次出现,暴力构建,再进行操作,当然也要维护第mm列的数。每行的数据可以用一个指针数组或者std::vector记录。

再考虑n=1n=1的情况,问题简化为一个数列,每次删除一个数,把它放在最后。随机访问的链表?好像不太对。不过如果不删除数,只是简单的打标记flagyflag_y,然后最后新增,问题就转换为求第一个iij=1iflagj=yi\vert i-\sum_{j=1}^i flag_j=y,显然可以二分。前缀和可以用树状数组维护,log2n\log^2 n,如果线段树树上二分可以做到logn\log n,完美解决。具体实现时,发现不必写递归版的线段树,非递归的更简单。

如果只有x=1x=1,发现只要用队列维护第mm列即可。

好像输入输出很大,想到模拟赛fstream被卡常的经历,我还写了输入输出优化。

时间复杂度{O(qlogm)x=1O((n+m)q)otherwise\begin{cases}\mathcal O(q\log m)&x=1\\ \mathcal O((n+m)q)&\text{otherwise}\end{cases},预计得分80

代码

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
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
const int N = 50005, N2 = 600005, SZ = 1e6;
unsigned last[N], *a[N];
int tree[N2 * 4];
long long val[N2];
FILE *fin = fopen("phalanx.in", "r"), *fout = fopen("phalanx.out", "w");
char ibuf[SZ], *ip = ibuf, *iend = ibuf, obuf[SZ], *op = obuf, *oend = obuf + SZ;
inline char nextchar()
{
if (ip == iend)
{
iend = ibuf + fread(ibuf, 1, SZ, fin);
ip = ibuf;
}
return *ip++;
}
inline void nextchar(char c)
{
if (op == oend)
{
fwrite(obuf, 1, SZ, fout);
op = obuf;
}
*op++ = c;
}
template <typename Int>
inline void read(Int &x)
{
char c;
for (c = nextchar(); isspace(c); c = nextchar())
;
x = 0;
for (; isdigit(c); c = nextchar())
x = x * 10 + c - '0';
}
int dig[20];
template <typename Int>
inline void writeln(Int x)
{
int len = 0;
do
dig[++len] = x % 10;
while (x /= 10);
for (; len; len--)
nextchar(dig[len] + '0');
nextchar('\n');
}
int main()
{
int n, m, q;
read(n);
read(m);
read(q);
if (n <= 5e4 && m <= 5e4 && q <= 500)
{
for (int i = 1; i <= n; i++)
last[i] = 1u * i * m;
while (q--)
{
int x, y;
read(x);
read(y);
if (!a[x])
{
a[x] = new unsigned[m + 1];
for (int i = 1; i < m; i++)
a[x][i] = 1u * (x - 1) * m + i;
}
a[x][m] = last[x];
unsigned tmp = a[x][y];
for (int i = y + 1; i <= m; i++)
a[x][i - 1] = a[x][i];
for (int i = x + 1; i <= n; i++)
last[i - 1] = last[i];
last[n] = tmp;
writeln(tmp);
}
for (int i = 1; i <= n; i++)
if (a[i])
delete[] a[i];
}
else
{
//solve x=1
queue<long long> last;
for (int i = 1; i <= n; i++)
last.push(1ll * i * m);
for (int i = 1; i <= m; i++)
val[i] = i;
for (int t = 1; t <= q; t++)
{
int x, y;
read(x);
read(y);
int id = 1, l = 1, r = m + q, sum = 0;
while (l < r)
{
int mid = (l + r) / 2;
if (mid - tree[id * 2] - sum >= y)
{
r = mid;
id *= 2;
}
else
{
sum += tree[id * 2];
l = mid + 1;
id = id * 2 + 1;
}
}
long long tmp = val[l];
tree[id] = 1;
while (id > 1)
tree[id /= 2]++;
last.pop();
last.push(tmp);
val[m + t] = last.front();
writeln(tmp);
}
}
fwrite(obuf, 1, op - obuf, fout);
return 0;
}

剩下的时间

我感觉day2比day1简单,听说不少人T1出现了一些偏差。而T3我也很高兴拿了这么多部分分。快到时,选手程序已经公开,cfb在洛谷上交他的程序,车上气氛活跃。大约16点回到学校西门。

我们去机房交自己的程序,看洛谷的数据。我手忙脚乱的改输入输出,还CE了一次。所幸我的成绩没有太大的偏差,反而高了。洛谷比赛结束时有3.4K用户参加排名,其中有45个AK。

几天后

洛谷455,绍一490,学军420,波动比较大。不过据说洛谷的分数比较准确。

初测440,浙江省Rank125,学校Rank18,年段第六。浙江一等奖分数线据说大约395。

math complex park cheese treasure phalanx 总分
60 100 30 100 70 80 440

浙江省分数线360,共305人获奖,大约53%……因为特派员已经被提高了5分……

按照公式有理有据,自从历年一等奖不占名额后,一等奖人数大幅增加。明年350人应该没问题了。