Codeplus7

清华算协Codeplus7比赛地址uoj上说明

官方录像

A 神秘序列 loj6722

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

注意pdf样例是错的,n=1应该是1 2

请先思考后再展开

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

思考的时候,建议将k看作,没有拓展长度的操作次数,那么很明显连续单调不减(只在长度变大时次数不变)

考虑如何求出n,考虑在长度达到n+1前的步数,第i个位置的次数一定是$c_i=1+\lfloor \frac{ \sum_{j=i+1}^n c_j}{i} \rfloor$,于是可以$O(nlogk)$二分出n

接着注意到,操作序列一定是$1,x,1,y,1,z,1,…$,于是c1确定,而去掉1以后问题是类似的

一般地,$S=n+k,c_i=\lceil S/(i+1) \rceil,S-=c_i,a_i=i-(S-1) \% (i+1)$

完整

1
2
3
4
5
6
7
8
9
10
11
ll c[N];
void main()
{
ll k=qread(),n=0;
for(int l=1,r=3e6;l<=r;)
{
int nn=(l+r)/2;ll sum=0;fd(i,nn,1) c[i]=1+sum/i,sum+=c[i];
if(sum-nn>=k) n=nn,r=nn-1; else l=nn+1;
} write2(n);
ll S=n+k;fo(i,1,n) c[i]=ceil(1.0*S/(i+1)),write1(i-(S-1)%(i+1)),S-=c[i];
}//本机带O2要0.9s,如果评测机菜的话可能需要调整下二分次数

B 教科书般的亵渎 loj6723

请先思考后再展开

水题,$O(mlogn+nlog^2n)$,完整

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 同余方程 loj6724

打表题,没啥意思

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