cojR15

Source

commetoj R15

A/D 双十一特惠

请先思考后再展开

首先答案肯定是$O(ln)$级别的,因为暴力做的话就是从高向低贪心

其实有经验的选手看到这个11111肯定直接化成$num=若干(10^k-1),即A=9num+cnt=恰cnt个10^k$

于是枚举cnt,限制就是$cnt \ge 数位和(A),数位和(A)=cnt (\bmod 9)$

注意每次重新求A复杂度肯定是错的,直接给你来个9999……就没了,但改成每次+1就是$O(位数)$的了,这个是势能分析的例题

1
2
3
4
5
6
7
8
9
10
11
12
13
char str[N];
int a[N],sum;void push(){for(int i=0;;i++){if(a[i]<=9)break;a[i]-=10,a[i+1]++,sum-=9;}}
void main()
{
int T=qread();
while(T--)
{
memset(a,0,sizeof a);scanf("%s",str+1);int ln=strlen(str+1);fo(i,1,ln) a[ln-i]=(str[i]-'0')*9;
sum=0;fo(i,0,ln+1) {if(a[i]>9) a[i+1]+=a[i]/10,a[i]%=10;sum+=a[i];}
for(int cnt=1;;cnt++) {a[0]++;sum++;push();
if(cnt>=sum and sum%9==cnt%9){write2(cnt);break;}}
}
}

C/F 可能 AC 人数计算

请先思考后再展开

先转化题意:给出一个序列,选择变量a表示ac人数,则要求数字1到a在序列中递增出现,且设数字a在位置t出现;然后将剩下的数分成最多两段,要求段内递增且第二段开头>t

1
2
3
4
5
6
7
8
9
10
fo(aa,0,n)
{
if(aa and pos[aa-1]>pos[aa]) break;
bool ok=1;
int cnt=0,lst=0;fo(i,1,n) if(a[i]>aa) {
if(lst>a[i]) {cnt++;if(i<=pos[aa]) ok=0;}
lst=a[i];
}
if(cnt<=1 and ok) chmin(mi,aa),chmax(mx,aa);
}

先通过第一个条件以及「t前面其他数也是递增」得出a的可行范围$[0,R]$

然后有两种情况,一是$a_{t+1}..a_n$递增,这样一段后缀的a都是可行的;二是$a_{t+1}..a_n恰一次断开,且满足leftmax<a_{t+1}$,这个也很好判

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int pos[N],a[N],cnt[N];
void main()
{
int T=qread();
while(T--)
{
int n=qread();fo(i,1,n) pos[i]=qread(),a[pos[i]]=i;
int R=0,lst=0;
while(R+1<=n and pos[R+1]>pos[R])
{
bool ok=1;fo(i,pos[R]+1,pos[R+1]-1) ok&=(lst<a[i]),lst=a[i];
if(!ok) break;R++;
}
cnt[n+1]=cnt[n]=0;fd(i,n-1,1) cnt[i]=cnt[i+1]+(a[i]>a[i+1]);
int mi=INF,mx=-1,left=0;
fo(aa,0,R)
{
if(aa) fo(i,pos[aa-1]+1,pos[aa]-1) chmax(left,a[i]);
if(!cnt[pos[aa]+1] or (cnt[pos[aa]+1]==1 and left<a[pos[aa]+1])) chmin(mi,aa),chmax(mx,aa);
}
if(mx<0) puts("-1 -1"); else write1(mi),write2(mx);
}
}

E 栈的数据结构题

请先思考后再展开

push设为1,pop设为-1,然后很容易发现,对于一个栈的回答就是右端点在tim,最大化左端点,使得区间和为pos

可以线段树上二分,每个节点记录管辖区间内最小后缀和、最大后缀和,从而判断在右边是否有这样的左端点

现在多个栈我就懵逼了……感觉需要利用离线,但并不知道离线有啥用……然后区间push也考虑过差分啥的也不太会搞。

但你看这个差分的轴是栈编号,那我如果依次处理每个栈的所有询问,差分不就能派上用场了么

那只要能回答这个后缀和就好了,双log随便写,把下面注释掉的地方改掉,就是单log了

写完就过让人感觉好没实感啊,这不是我的风格吧……

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
struct Data{
int sum,mi,mx;
friend Data operator + (Data a,Data b){return (Data){a.sum+b.sum,min(b.mi,b.sum+a.mi),max(b.mx,b.sum+a.mx)};}
};
int n,q;
namespace SGT
{
#define lc x<<1
#define rc x<<1|1
#define mid (l+r)/2
Data now[N<<2];
void ad(int x,int pos,int num,int l=1,int r=q)
{
if(l==r){num+=now[x].sum;now[x]=(Data){num,num,num};return;}
pos<=mid?ad(lc,pos,num,l,mid):ad(rc,pos,num,mid+1,r);
now[x]=now[lc]+now[rc];
}
// int sum(int x,int fl,int fr,int l=1,int r=q)
// {
// if(l==fl and r==fr) return now[x].sum;
// if(fr<=mid) return sum(lc,fl,fr,l,mid); if(fl>mid) return sum(rc,fl,fr,mid+1,r);
// return sum(lc,fl,mid,l,mid)+sum(rc,mid+1,fr,mid+1,r);
// }
int S;
int solve(int x,int tim,int ned,int l=1,int r=q)
{
if(r<=tim)
{
if(ned<now[x].mi or now[x].mx<ned) {S+=now[x].sum;return 0;}
if(l==r) {S+=now[x].sum;return l;}
if(now[rc].mi<=ned and ned<=now[rc].mx) return solve(rc,tim,ned,mid+1,r);
S+=now[rc].sum;return solve(lc,tim,ned-now[rc].sum,l,mid);
}
if(tim<=mid) return solve(lc,tim,ned,l,mid);
int ret=solve(rc,tim,ned,mid+1,r);if(ret) return ret;
return solve(lc,tim,ned-S,l,mid);
// return solve(lc,tim,ned-sum(rc,mid+1,tim,mid+1,r),l,mid);
}
};
int ans[N],num[N];vc< pair<pr,int> > qes[N];vc<pr> chg[N];
void main()
{
n=qread(),q=qread();int cnt=0;
fo(i,1,q)
{
char str[10];scanf("%s",str);
if(str[0]=='f'){int id=qread(),pos=qread();qes[id].PB(MP(MP(i,pos),++cnt));}
else if(str[1]=='u'){int l=qread(),r=qread();num[i]=qread();chg[l].PB(MP(i,1));chg[r+1].PB(MP(i,-1));}
else {int l=qread(),r=qread();chg[l].PB(MP(i,-1));chg[r+1].PB(MP(i,1));}
}
fo(i,1,n)
{
for(auto t:chg[i]) SGT::ad(1,t.FR,t.SE);
for(auto qq:qes[i]) SGT::S=0,ans[qq.SE]=num[SGT::solve(1,qq.FR.FR,qq.FR.SE)];
}
fo(i,1,cnt) write2(ans[i]);
}

G 孤独的吉姆6

请先思考后再展开

可以先做做这个的B感受一下,于是若n偶则n个奇数点,否则n-1个奇数点1个偶数点

先把最大生成树建出来(根据MST那套理论是唯一的),要删只删树边;至于其他边都是保留的,先假设所有点都是奇数点统计出每个点不考虑树边的度数情况

从小到大枚举树上的边并尽可能保留,每次统计两边联通块度数和的奇偶性

当n偶数,两边都是偶数就删掉,都奇数则保留,以后可能询问到的联通块x和y都在一起所以并不需要修改

当n奇数,

目前子树一定强制偶数点:一定是一奇一偶,放在偶那边变成都奇,这样就能保留,但因为不知道在哪里所以并不做修改

目前子树一定没有偶数点:都偶删掉,都奇保留,不可能一奇一偶

于是发现并不需要知道有与否也并不需要特判n的奇偶性,只在都偶的时候删掉

问题在于如何实现。因为我们要算的是断开那两个联通块的信息,而在kruskal上其他地方可能和某个孩子连起来,所以自然的想法可能是在原树上维护,如果能维护这道题我将绝杀,可惜维护不得……

看了看题解发现kruskal是没毛病的,咱快乐讨论一下,发现是完全等价于,直接修改那条边对应两个点的度数,然后询问两个联通块是可以通过计算两个子树各自度数和得到的,因为是异或可以用树状数组维护,$O(nlogn)$

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
namespace BIT
{
bool bit[N];int lowbit(int x){return x&-x;}
void ch(int x){while(x<N)bit[x]^=1,x+=lowbit(x);}
bool ask(int x){bool ret=0;while(x>=1)ret^=bit[x],x-=lowbit(x);return ret;}
int sum(int l,int r){return ask(l-1)^ask(r);}
};
int dfnid,dfn[N],siz[N],son[N][2];
void pre(int x)
{
dfn[x]=++dfnid;siz[x]=1;
if(son[x][0]) pre(son[x][0]),pre(son[x][1]),siz[x]+=siz[son[x][0]]+siz[son[x][1]];
}
struct DSU
{
int fa[N],val[N];DSU(){fo(i,0,N-1)fa[i]=i;}
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
}dsu;
pr edge[N];vc<int> mst;bool del[N];int to[N];
int d[N];
void main()
{
int n=qread(),m=qread();fo(i,1,m){int x=qread()+1,y=qread()+1;edge[i]=MP(x,y);}
fo(x,1,n) d[x]=1;int cnt=n;
fd(i,m,1){
int x=edge[i].FR,y=edge[i].SE,fx=dsu.findfa(x),fy=dsu.findfa(y);if(fx==fy) {d[x]^=1,d[y]^=1;continue;}
dsu.fa[fx]=dsu.fa[fy]=++cnt;son[cnt][0]=fx,son[cnt][1]=fy;mst.PB(i);to[i]=cnt;
}
pre(cnt);
fo(x,1,n) if(d[x]) BIT::ch(dfn[x]);
reverse(all(mst));
for(auto id:mst)//从小到大
{
int lc=son[to[id]][0],rc=son[to[id]][1];
bool a=BIT::sum(dfn[lc],dfn[lc]+siz[lc]-1),b=BIT::sum(dfn[rc],dfn[rc]+siz[rc]-1);
if(a or b) BIT::ch(dfn[edge[id].FR]),BIT::ch(dfn[edge[id].SE]); else del[id]=1;
}
fo(i,1,m) write(del[i]^1);
}

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