Codeplus7

清华算协Codeplus7uoj上说明

官方录像,数据和官方题解加群(太大了

gmh

A

题意:给定k,构造长为n(自己定)的序列a满足$a_i \ge 0,a_n \ne 0$,每次选一个$a_i=i,变成0,且前面都++$,经过n+k次操作后能变成全0序列,$k \le 1e12$

请先思考后再展开

倒着考虑,发现方案是唯一的,等价于每次找到第一个0所在的i,$a_i=i,前面–$,此时可得35分(复杂度klog,原因见下)

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
int n,m,ans[N];
set<int> no[N];
void insert(int l,int r,int c)
{
while(1)
{
set<int>::iterator IT=no[c].lower_bound(l);if(IT==no[c].end() or *IT>r) break;
int x=*IT;no[c].erase(IT);
if(ans[x]==c-1) while(!no[ans[x]+1].count(x)) ans[x]++,bit.ad(x,1);
}
//deb;
}
bool hav[N];
void main()
{
n=qread(),m=qread();
fo(d,1,n) fo(j,0,n/d+2) no[j].insert(d);
while(m--)
{
int op=qread();
if(op==1)
{
int x=qread()-1;if(hav[x]) continue;hav[x]=1;
insert(x+1,n,1);
for(int l=1,r;l<=x;l=r+1) r=x/(x/l),insert(l,r,x/l+1);
}
else
{
int l=qread(),r=qread();
write2( bit.ask(l,r)+(r-l+1) );
}
}
}

C

请先思考后再展开

D

请先思考后再展开

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/95b4a9d.html
转载请注明出处,谢谢!