AtCoder Beginner Contest 380 赛后总结

作者： 作者的头像   代码羊qwq ,  2024-11-19 12:24:48 ,  所有人可见 ,  阅读 5

2


可能更好的阅读体验

菜菜菜，不是你怎么这么菜。

A-C

模拟即可。

D

正常的方法

因为不管怎么粘合总是一个字符串在复制，所以我们只用考虑大小写问题。

我们设字符串为 $A$，被反转大小写的字符串为 $B$，那么这个字符串会长这样：$ABBABAABBAABABBA\cdots$，第一个 $A$ 的位置是 $0$ 的话，我们可以发现每一个 $B$ 在二进制中的 $1$ 的个数为奇数。

[HTML_REMOVED]
[HTML_REMOVED]证明[HTML_REMOVED]

我们知道，每一次反转字符串长度会乘 $2$。
所以字符串中的每一位象征着是经过多少次反转过后得到的。
所以每个字符串的位置在二进制下的 $1$ 的个数就是反转大小写的次数，
那么一定是反转奇数次才可以变换样式。
[HTML_REMOVED]

幽默方法

按照上面的方法先找出字符串的样子，发现被反转后的字符串的位置在 $\{1,2,4,7,8,11,\cdots\}$，丢到 oeis 中找到 A000069，发现规律是二进制中 $1$ 的个数。

[HTML_REMOVED]
[HTML_REMOVED]点击查看代码[HTML_REMOVED]

#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();

#define ll long long
#define i128 __int128

using namespace std;
inline int read() {
    int xx= 0;int f= 1;
    char c = getchar();
    while(c<'0'||c>'9') { 
        if(c=='-') f= -1;
        c= getchar();
    }
    while(c>='0'&&c<='9') {
        xx= (xx<<1)+(xx<<3)+(c^48);
        c= getchar();
    }
    return xx*f;
}
#define maxn 200050
string s;
int q;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>s>>q;
    int n=s.size();
    while(q--) {
        int x; cin>>x;
        int a=(x-1)/n;
        int cnt=0; //cout<<a<<':';
        while(a) cnt+=(a&1),a>>=1;
        if(!(cnt&1)) cout<<s[(x-1)%n]<<' ';
        else {
            int i=(x-1)%n;
            if(s[i]>='a') cout<<(char)(s[i]-32)<<' ';
            else cout<<(char)(s[i]+32)<<' ';
        }
    }
}

[HTML_REMOVED]

E

并查集基础练习题，我们记录连通块的左/右端点 $l,r$，父亲节点对应的颜色 $col$，颜色的个数 $siz$，那么每一次合并只用考虑区间左/右侧一个格子是否和现在的格子颜色相同，维护 $l,r$ 即可。合并时要注意使用的变量会不会因为更改导致前后表达的意思不同。

[HTML_REMOVED]
[HTML_REMOVED]点击查看代码[HTML_REMOVED]

#include<bits/stdc++.h>

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();

#define ll long long
#define i128 __int128

using namespace std;
inline int read() {
    int xx= 0;int f= 1;
    char c = getchar();
    while(c<'0'||c>'9') { 
        if(c=='-') f= -1;
        c= getchar();
    }
    while(c>='0'&&c<='9') {
        xx= (xx<<1)+(xx<<3)+(c^48);
        c= getchar();
    }
    return xx*f;
}
#define maxn 500050
int fa[maxn];
int col[maxn];
int l[maxn],r[maxn],siz[maxn];
int n,q;
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]); }
signed main() {
    in2(n,q);
    For(i,1,n) col[i]=i,fa[i]=i,l[i]=i,r[i]=i,siz[i]=1;
    while(q--) {
        int opt=read();
        if(opt==1) {
            int x=read(),c=read();
            int X=find(x);
            if(col[X]==c) continue;
            siz[col[X]]-=r[X]-l[X]+1;
            col[X]=c;
            siz[col[X]]+=r[X]-l[X]+1;
            if(l[X]>1) {
                int L=find(l[X]-1);
                if(col[L]==c) {
                    l[X]=l[L];
                    fa[L]=X;
                }
            }
            if(r[X]<n) {
                int R=find(r[X]+1);
                if(col[R]==c) {
                    r[X]=r[R];
                    fa[R]=X;
                }
            }
        } else {
            int c=read();
            cout<<siz[c]<<'\n';
        }
    }
}

[HTML_REMOVED]

F

$n+m+l\le 12$，一眼搜索剪枝。
如果有一种操作使得之后的情况都可以转换为我胜，那么这就是我的必胜点，反之就是我的必败点。
注意是可以从桌上拿起一张牌，不是必须。
然后就是要记忆化搜索，注意要记录此时是谁操作，因为有可能出现两个人手牌一样但是操作方不一样。

[HTML_REMOVED]
[HTML_REMOVED]点击查看代码[HTML_REMOVED]

#include<bits/stdc++.h>

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();

#define ll long long
#define i128 __int128

using namespace std;
inline int read() {
    int xx= 0;int f= 1;
    char c = getchar();
    while(c<'0'||c>'9') { 
        if(c=='-') f= -1;
        c= getchar();
    }
    while(c>='0'&&c<='9') {
        xx= (xx<<1)+(xx<<3)+(c^48);
        c= getchar();
    }
    return xx*f;
}
#define maxn 15
short f[2][(1<<12)+114][(1<<12)+514];
int a[maxn];
int n,m,l;
int out[maxn],top;
void put(int x) {
    m0(out);
    top=0;
    while(x) out[++top]=x&1,x>>=1;
    For(i,1,13) cout<<out[i]; 
    puts("");
}   
bool dfs(int dep,int s1,int s2) {
//  cout<<dep<<'\n';put(s1); put(s2); puts("---");

    bool res=0;
    if(f[dep][s1][s2]!=-1) return f[dep][s1][s2];
    if(dep&1) {
        res=0;
        For(i,0,n+m+l-1) {
            if(!((s1>>i)&1)) continue;
            if((s2>>i)&1) continue;
            For(j,0,n+m+l-1) {
                if(((s1|s2)>>j)&1) continue;
                if(a[i+1]>a[j+1]) 
                    if(!dfs((dep^1),(s1^(1<<i))|(1<<j),s2)) res=1;
            }
            if(!dfs((dep^1),(s1^(1<<i)),s2)) res=1;
        }       
    } else {
        res=0;
        For(i,0,n+m+l-1) {
            if(!((s2>>i)&1)) continue;
            if((s1>>i)&1) continue;
            For(j,0,n+m+l-1) {
                if(((s1|s2)>>j)&1) continue;
                if(a[i+1]>a[j+1])
                    if(!dfs((dep^1),s1,(s2^(1<<i))|(1<<j))) res=1;
            }
            if(!dfs((dep^1),s1,(s2^(1<<i)))) res=1;
        }       
    }
    f[dep][s1][s2]=res;
    return res;
}
signed main() {
    mem(f,-1);
    in3(n,m,l);
    For(i,1,n+m+l) in1(a[i]);
    cout<<(dfs(1,(1<<(n))-1,(1<<(m+n))-(1<<n))?"Takahashi":"Aoki");
}

[HTML_REMOVED]

G

好题啊！
我们枚举区间左端点 $i$，发现整个序列被分为了 $3$ 个部分，左边部分 $A$，中间部分 $B$，右边部分 $C$。
我们讨论一下每个部分对答案的贡献：
- $AA$/$CC$/$AC$，因为数字是固定的，所以这三部分的答案也是固定的。
- $AB$/$BC$，由于个个逆序对不相互影响，所以这两部分答案也是固定的。
- $BB$，有 $\frac{k\times(k-1)}{2}$ 种方法选数，对于每一对数构成逆序对的概率都是 $\frac{1}{2}$，故这部分答案为 $\frac{k\times(k-1)}{4}$。
我们可以用树状数组求逆序对的方法来维护各个部分的值：
- 在 $A$ 的右边加入一个值，那么会答案会更改成：
- $AA$：由于在右侧加入，想要构成逆序对必须要和前面的比这个数大的数进行匹配；
- $AB$/$AC$：由于在相对的左侧加入，所以要和比自己小的数进行匹配。
- 在 $B$ 中加入一个值，那么答案会更改成：
- $AB$：相对在右边，故和比自己大的数匹配；
- $AC$：相对在左边，故和比自己小的数匹配；
- 在 $C$ 的左侧加入一个值，那么答案会更改成：
- $AC$/$BC$：相对在右边，故比自己大的数匹配；
- $CC$：在左边，故和比自己小的数匹配。

删去一个值同理。
由于树状数组是 $O(\log n)$ 的，故总时间复杂度为 $O(n\log n)$。
注意判断是否溢出，根据需要选择 __int128 或者 long long。

[HTML_REMOVED]
[HTML_REMOVED]点击查看代码[HTML_REMOVED]

#include<bits/stdc++.h>
#define int i128
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();

#define ll long long
#define i128 __int128

using namespace std;
inline int read() {
    int xx= 0;int f= 1;
    char c = getchar();
    while(c<'0'||c>'9') { 
        if(c=='-') f= -1;
        c= getchar();
    }
    while(c>='0'&&c<='9') {
        xx= (xx<<1)+(xx<<3)+(c^48);
        c= getchar();
    }
    return xx*f;
}
#define maxn 200050
const int mod = 998244353;
int c[4][maxn]; 
/*
1:A
2:B
3:C
*/
int ans[6];
/*
1:AA
2:AB
3:AC
4:BC
5:CC
*/
int n,k;
int a[maxn];
void add(int idx,int x,int val) {
    for(;x<maxn;x+=lb(x)) c[idx][x]+=val;
}
int query(int idx,int x) {
    int res=0;
    for(;x;x-=lb(x)) res+=c[idx][x];
    return res;
}
int re_cnt(int idx,int x,bool flg) {
    if(!flg) return query(idx,x-1);
    else return query(idx,n)-query(idx,x);
}
void upd_a(int x,int val) {
    add(1,x,val);
    ans[1]+=re_cnt(1,x,1)*val;
    ans[2]+=re_cnt(2,x,0)*val;
    ans[3]+=re_cnt(3,x,0)*val;
}
void upd_b(int x,int val) {
    add(2,x,val);
    ans[2]+=re_cnt(1,x,1)*val;
    ans[4]+=re_cnt(3,x,0)*val;
}
void upd_c(int x,int val) {
    add(3,x,val);
    ans[3]+=re_cnt(1,x,1)*val;
    ans[4]+=re_cnt(2,x,1)*val;
    ans[5]+=re_cnt(3,x,0)*val;
}
int qpo(int a,int b) {
    int res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a*=a;
        a%=mod;
        b>>=1;
    }
    return res;
}
int inv(int x) {return qpo(x,mod-2); }
signed main() {
    in2(n,k);
    For(i,1,n) in1(a[i]);
    For(i,1,k) upd_b(a[i],1);
    Rep(i,n,k+1) upd_c(a[i],1);
    int res=(ans[1]+ans[2]+ans[3]+ans[4]+ans[5]+(k*(k-1))*inv(4))%mod;
    For(i,1,n-k) {
        upd_b(a[i],-1);
        upd_a(a[i],1);
        upd_c(a[i+k],-1);
        upd_b(a[i+k],1);
        res=(res+ans[1]+ans[2]+ans[3]+ans[4]+ans[5]+(k*(k-1))*inv(4))%mod;
    }
    cout<<(ll)((res*inv(n-k+1))%mod);
}

[HTML_REMOVED]

13 评论

用户头像
codwarm   1天前         踩      回复

哇好强

用户头像
Conan15   1天前         踩      回复

很好的题解，但是“点击查看代码”是什么东西（）

用户头像
代码羊qwq   1天前         踩      回复

从博客搬过来忘删掉了（）

用户头像
Conan15   1天前    回复了 代码羊qwq 的评论         踩      回复

G 题的 BB 情况 算概率那边是什么意思，能讲一下吗

用户头像
代码羊qwq   1天前    回复了 Conan15 的评论         踩      回复

我们先放一个数，他的期望位置是序列的终点，那么放第二个数是在左边的期望和在右边的期望相等，故构成一组逆序对的概率为 $\frac{1}{2}$。

用户头像
代码羊qwq   1天前    回复了 代码羊qwq 的评论         踩      回复

终点 $\to$ 中点

用户头像
Conan15   1天前    回复了 代码羊qwq 的评论         踩      回复

ok，那选数方案是怎么算的？

用户头像
代码羊qwq   1天前    回复了 Conan15 的评论         踩      回复

您指的是哪个？

用户头像
Conan15   1天前    回复了 代码羊qwq 的评论         踩      回复

$\frac{k(k+1)}{2}$

用户头像
代码羊qwq   1天前    回复了 Conan15 的评论         踩      回复

dbq我打错了www应该是 $\frac{k(k-1)}{2}$

用户头像
代码羊qwq   1天前    回复了 Conan15 的评论         踩      回复

对不起qwq

用户头像
Conan15   1天前    回复了 代码羊qwq 的评论         踩      回复

没事，那我懂了，后面的也要改成 $\frac{k(k-1)}{4}$ awa

用户头像
代码羊qwq   1天前    回复了 Conan15 的评论         踩      回复

哦哦哦好的多谢qwq