CF1612

还是要增强码力捏,G 没调出来,凉。

[A Distance]

solution

题面:$T$ 组询问,给出 $(0,0)$ 和 $(a,b)$,问是否存在一个点使得它到这两个点的曼哈顿距离都为两个点的曼哈顿距离的一半。

做法:奇偶判判就好了。时间复杂度 $O(T)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
inline void MAIN(){
res x=read(),y=read();
if((x+y)&1)puts("-1 -1");
else {
if(x&1){
printf("%d %d\n",(x+1)/2,(y-1)/2);
}
else printf("%d %d\n",x/2,y/2);
}
}
}

[B Special Permutation]

solution

题面:给出 $a,b,n$,问是否存在一个 $n$ 的排列,使得左半边的最小值为 $a$,右半边的最大值为 $b$,保证 $n$ 为偶数。

做法:直接把比 $a$ 的放在左边就好了,时间复杂度 $O(n)$。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
int n,a,b;
int ans[N];
int ansx;
inline void MAIN(){
n=read(),a=read(),b=read();
ans[ansx=1]=a;
for(res i=n;i;i--){
if(ansx==n/2)break;
if(i==b)continue;
if(i<=a){puts("-1");return;}
ans[++ansx]=i;
}
ans[++ansx]=b;
for(res i=1;i<=n;i++){
if(ansx==n)break;
if(i>=b){puts("-1");return;}
if(i==a)continue;
ans[++ansx]=i;
}
for(res i=1;i<=ansx;i++)printf("%d ",ans[i]);puts("");
}
}

[C Chat Ban]

solution

题面:给出一个 $k,n$,问类似 ( 这张图 $k$ 为 $3$ ) 的东西,前几列的和会大于等于 $n$?

做法:可以 $O(1)$ 直接开根算,但没必要,二分一下得了。时间复杂度 $O(\log)$。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=100+10;
namespace MAIN{
inline void MAIN(){
res k=read();
RG LL n=Read();
if((LL)k*(k+1)/2>=n){
res l=1,r=k,ret=0;
while(l<=r){
res mid=(int)(((LL)l+r)>>1);
if((LL)mid*(mid+1)/2>=n)r=mid-1,ret=mid;
else l=mid+1;
}
printf("%d\n",ret);
}
else {
n-=(LL)k*(k+1)/2;
if(n>(LL)k*(k-1)/2)printf("%d\n",2*k-1);
else {
res l=1,r=k-1,ret=0;
while(l<=r){
res mid=(int)(((LL)l+r)>>1);
if((LL)k*(k-1)/2-(LL)mid*(mid-1)/2>=n)l=mid+1,ret=mid;
else r=mid-1;
}
printf("%d\n",k-ret+k);
}
}
}
}

[D X-Magic Pair]

solution

题面:给出 $(a,b)$,每次操作可将其中一个数变成 $|a-b|$,给出 $x$,问变化的过程中是否有一个 $a$ 或 $b$ 能变成 $x$?

做法:一眼 $\gcd$,分析一下发现 $\gcd$ 过程中的变化已经包含了所有数。所以直接模拟 $\gcd$ 即可,时间复杂度 $O(\log)$。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
bool Gcd(RG LL a,RG LL b,RG LL x){
if(a<b)swap(a,b);
if(a<x)return 0;
if(!b)return a==x;
if(b==x)return 1;
if(a%b==x%b)return 1;
if(Gcd(b,a%b,x))return 1;
return 0;
}
inline void MAIN(){
RG LL a=Read(),b=Read(),x=Read();
if(x>max(a,b)||x%gcd(a,b))puts("NO");
else {
puts(Gcd(a,b,x)?"YES":"NO");
}
}
}

[E Messages]

solution

题面:$n$ 个学生,每个人有一个他应该看的书 $m_i$ 和一个能看的数量 $k_i$。你可以给出 $t$ 本书的编号( $t$ 由你来定),那么这些学生就会随机从这 $t$ 本书中挑出 $k_i$ 本看,如果看到他应该看的就贡献 $+1$,如果 $k_i\geq t$ 则要全看。问如何安排才能让贡献的期望最大。

做法:注意到 $k$ 比较小。考虑枚举 $t$,会发现我们可以快速计算出一本书的期望,若我们对每一本书按 $k$ 分别存,稍微推下式子就会发现是个后缀和乘 $t$ 加上一个 $k$ 乘前缀和。注意到 $t$ 大于 $20$ 后,每本书的贡献就不会变了。所以直接暴力枚举 $t$,每次暴力排序选出前 $t$ 个。然后 $t>20$ 后整体排好序,一个个选进来即可。时间复杂度 $O(nk\log n)$。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
int n;
int m[N],k[N];
int sn[N][22];
LL A[N];
pair<LL,int> B[N];
RG LL ans;
int mx;
vector<int> Ans;
inline void MAIN(){
n=read();
for(res i=1;i<=n;i++)m[i]=read(),k[i]=read(),sn[m[i]][k[i]]++;
for(res i=20;i;i--)for(res j=1;j<=N-10;j++)sn[j][i]+=sn[j][i+1];
res Fl=0;
for(res t=1;t<=20;t++){
for(res i=1;i<=N-10;i++)A[i]+=sn[i][t],B[i]=mp(A[i],i);
sort(B+1,B+N-10+1),reverse(B+1,B+N-10+1);
RG LL ret=0;
for(res i=1;i<=t;i++){
if(!B[i].fi){Fl=1;break;}
ret+=B[i].fi;
}
if(Fl)break;
if((LL)mx*ret>(LL)t*ans||mx==0){
ans=ret,mx=t,vector<int>().swap(Ans);
for(res i=1;i<=t;i++)Ans.pb(B[i].se);
}
}
if(!Fl){
for(res i=1;i<=N-10;i++)B[i]=mp(A[i],i);
sort(B+1,B+N-10+1),reverse(B+1,B+N-10+1);
RG LL ret=0;
for(res i=1;i<=20;i++)ret+=B[i].fi;
res las=0;
for(res t=21;t<=n;t++){
if(!B[t].fi)break;
ret+=B[t].fi;
if((LL)mx*ret>(LL)t*ans){
ans=ret,mx=t;
for(res i=las+1;i<=t;i++)Ans.pb(B[i].se);
las=t;
}
}
}
printf("%d\n",mx);
for(auto x:Ans){
if(!x)break;
printf("%d ",x);
}
puts("");
}
}

[F Armor and Weapons]

solution

题面:你初始有属性值为 $1$ 的铠甲和武器。一组铠甲和武器组合的能量为属性值之和,但有 $q$ 种属性值的组合的能量为属性值之和 $+1$。你每次操作可以获得一个属性值在最大能量之下的铠甲或武器,问获得到属性值为 $n$ 的铠甲和属性值为 $m$ 的武器的最小操作次数。

做法:感觉写个暴搜的复杂度就是对的啊,这不是算成倍增吗。。。感觉把那种单调的直接删掉,复杂度就是一个 $\log$ 了啊。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
int n,m;
map<Pair,int> M;
vector<Pair> f,g,h;
int ans;
inline void MAIN(){
n=read(),m=read();
res q=read();
while(q--){
res x=read(),y=read();
M[mp(x,y)]=1;
}
f.pb(mp(1,1));
while(233){
if(f[0]==mp(n,m)){printf("%d\n",ans);return;}
vector<Pair>().swap(g);
for(auto x:f){
res s=x.fi+x.se+M[x];
g.pb(mp(min(s,n),min(x.se,m))),g.pb(mp(min(x.fi,n),min(s,m)));
}
sort(g.begin(),g.end()),reverse(g.begin(),g.end());
res mx=0;
vector<Pair>().swap(h);
for(auto x:g){
if(x.se<=mx)continue;
mx=x.se,h.pb(x);
}
f=h,ans++;
}
}
}

[G Max Sum Array]

solution

题面:给出 $n$ 个数 $a_i$,表示你拥有 $a_i$ 个 $i$。现要将这 $\sum a_i$ 个数填到一个序列里,使得所有相同数的数对的下标差之和最大。输出这个最大值与填充的方案数。

做法:先单独考虑一个 $i$,设它有 $c$ 个,填充的位置分别为 $id_j$,那么它们的贡献就是 $\sum (2j-1-c)id_j$。于是从贪心角度来看,若一个数的 $2j-1-c$ 越大就越应该往后填。于是设 $now$ 表示当前最后的位置,维护下当前的 $2j-1-c$ 有几个数,那么这些数的贡献就是 $\sum (now-i)(2j-1-c)$,方案数就是数量的阶乘,这个可以直接 $O(1)$ 算。然后将 $2j-1-c-2$ 的位置加上这些数。于是就做好了,时间复杂度 $O(n+a)$。

坑:最开始的时候我不是想着维护 $2j-1-c$,反而是想排序,然后从大到小,这样每次就会带着两个东西在算而已了,但实现就会比较复杂。。。所以没写完。

code
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
//2021.11.26 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e6+1;
namespace MAIN{
int n;
int a[N];
int sum;
int ans=1;
int fac[N];
int fl[N*2+10];
inline void MAIN(){
n=read(),fac[0]=fac[1]=1;
for(res i=2;i<=n;i++)fac[i]=mul(fac[i-1],i);
for(res i=1;i<=n;i++)a[i]=read(),fl[a[i]-1+N]++,fl[-1-a[i]+N]--;
sort(a+1,a+n+1),reverse(a+1,a+n+1);
res now=0;
for(res i=1;i<=n;i++)add(now,a[i]);
res inv2=qpow(2);
for(res i=N*2;i;i--){
if(!fl[i])continue;
add(sum,mul(mul(Add(i,kcz-N),fl[i]),Add(now,kcz-mul(fl[i]-1,inv2))));
ans=mul(ans,fac[fl[i]]);
fl[i-2]+=fl[i],add(now,kcz-fl[i]);
}
printf("%d %d\n",sum,ans);
}
}