noone___'s blog
0%

72801202-AGC020

发表于 更新于 分类于
AGC020

D

多组询问，对于每组询问给出 $ABCD$ ，求出字符串满足：长度为 $AA+B$ ，由 $A$ 个 字符 $\text{A}$ 和 $B$ 个字符 $\text{B}$ 构成，且连续相同字符个数的最大值最小，且字典序最小。输出第 $C$ 位到第 $D$ 位

神仙题用二分构造

贪心得最小连续长度 $\displaystyle{k=\max\left\{\left\lceil\frac{A}{B+1} \right\rceil , \left\lceil\frac{B}{A+1} \right\rceil \right\}}$

那么这个串可以分成两部分：前一部分在 $k$ 限制下贪心填 $A$ ，后一部分不得已填 $B$

二分边界 $p$ 使 $p$ 的右半部分满足 $B>A\times k$ ，确保左边是 $A$ ，右边是 $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
int T,A,B,C,D,k;
int a,b;

inline void get(int pos){
    a=A-pos/(k+1)*k-pos%(k+1);
    b=B-pos/(k+1);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&A,&B,&C,&D);
        k=(A+B)/(min(A,B)+1);
        rei l=0,r=A+B;
        while(l<r){
            rei mid=l+r>>1;
            get(mid);
            b<=(ll) a*k ? l=mid+1 : r=mid;
        }
        get(l);
        r=l+1+b-a*k;
        for(rei i=C;i<=D;++i){
            if(i<=l) i%(k+1)!=0 ? printf("A") : printf("B");
            else (i-r)%(k+1)!=0 ? printf("B") : printf("A");
        }
        puts("");
    }
    getchar(),getchar();
    return 0;
}

E

定义一个 $01$ 串的压缩是如下的字符串变化过程：$0\rightarrow 0,1\rightarrow 1$ ；如果 $A\rightarrow P,B\rightarrow Q$ 合法，那么 $A+B\rightarrow P+QA+B→P+Q$ 也合法（其中 $+$ 代表字符串拼接）；如果 $S=\underbrace{A+A+\cdots+A}_{n\text{个}(n\ge 2)}$ ，那么 $S\rightarrow(A\times n)$ 也合法（其中 $\text{(, ), × }$ 为字符，$n$ 为数字，算作一个字符，即使其中有 $0/1$

定义 $01$ 串 $B$ 是 $A$ 的子集当且仅当：$|A|=|B|$ ； $\forall B_i=1,A_i=1$

现在给 $01$ 串 $S$ ，问它所有的子集的合法变化结果数的总和为多少。

不容易对子集直接求和，考虑解码时是 $S$ 子集的数量，设 $f(S)$ 表示字符串为 $S$ 时的答案

对于字符串的第一个字符：

  • $0/1$

    与其他部分编码无关，$S_1=1$ 时，编码字符串第一个可能是 $0/1$ , $\therefore f(S_{1\sim |S|})=2\times f(S_{2\sim |S|})$ ；$S_1=0$ 时，编码第一个只能是 $0$ , $\therefore f(S_{1\sim |S|})=f(S_{2\sim |S|})$

  • 左括号

    编码字符串开头为 $P\times k$ ，其中 $P$ 是字符串 $A$ 的代码，满足 $k\times |A|\leq |S|$ ，且 $\underbrace{A+A+…+A}_{k个}$ 是 $S_{1\sim k\times |A|}$ 的子集，即 $A$ 是 $S_{1\sim |A|},S_{|A|+1\sim 2\times |A|},…,S_{(k-1)\times |A|+1\sim k\times |A|}$ 的子集

其中 $g(S,k,|A|)$ 表示 $S_{1\sim |A|}\land S_{|A|+1\sim 2\times |A|}\land …\land S_{(k-1)\times |A|+1\sim k\times |A|}$

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
#define int __int128
#define ll __int128

const int mod=998244353;
map< pair<ll,int>,int> f;
char s[111];
int n;

int dfs(pair<ll,int> now){
    if(!now.second) return 1;
    if(f.count(now)) return f[now];
    rei ans=(ll) dfs( mk(now.first>>1,now.second-1))*((now.first&1)+1)%mod;
    for(rei A=1;A<=(now.second>>1);++A){
        ll S=((ll)1<<A)-1,tmp=now.first,sum=tmp&S;
        tmp>>=A; sum&=tmp&S; tmp>>=A;
        for(rei k=now.second-A-A;k>=0;k-=A,sum&=tmp&S,tmp>>=A) ans=(ans+(ll) dfs(mk(sum,A))*dfs(mk(tmp,k))%mod)%mod;
    }
    return f[now]=ans;
}

signed main(){
    scanf("%s",s); n=strlen(s);
    ll S=0;
    for(rei i=0;i<=n-1;++i) S=S<<1|(s[i]-'0');
    printf("%lld\n",dfs(mk(S,n)));
    getchar(),getchar();
    return 0;
}

F

给定一个周长为 $C$ 的圆周，和 $N$ 段 (半径与圆相同的) 圆弧，第 $i$ 段圆弧的长度为 $L_i$ ，现在，每段弧的位置在圆周上均匀分布：具体地，在圆周上等概率随机一个点，作为弧 $L_i$ 的终点。不同的弧的位置是互相独立的，即它们有相应的概率相交。求有多大的概率，使得这 $N$ 段圆弧的并覆盖整个圆周？

环上的问题并不是容易处理，因此首先固定一个点作为起点

一条弧的端点是一个比较好的选择，因为这样一条弧覆盖的就是整条链的前缀

考虑除了弧 $i$ 外剩下的弧，它们需要覆盖 $[L_i,N)$ 这段区间，不过，有可能存在一些弧包含了 $i$ ，从而它们覆盖了一个前缀和一个后缀

对于这种情况，可以通过指定 $i$ 是最长的弧 (即 $L_i=\max\{L_1,L_2,…,L_N\}$ ) 来避免

然后问题就转化为了一个连续型的线段覆盖问题

如果整个问题是离散的，那么容易通过 $DP$ 来解决，那现在是连续的，就要考虑化连续为离散

设弧 $i$ 的起点为 $P_i$ ，终点为 $P_i+L_i$ ，由于 $L_i\in \Z$ ，因此将 $P_i$ 拆成 $[P_i]+\{P_i\}$ ，$[P_i]$ 是一个 $[0,N)$ 上等概率分布的整型 (离散型) 随机变量，$\{P_i\}$ 是一个在 $[0,1)$ 上均匀分布的实随机变量

考察整个问题，整个圆弧能否被覆盖，更进一步地，某两条弧是否相交，可以发现，只和它们 $[P)i]$ 的值以及 $\{P_i\}$ 的大小关系” 有关

设 $P_i\leq P_j$ ，于是 $i,j$ 相交等价于 $[P_i]+\{P_i\}+L_i\geq [P_j]+\{P_j\}$ 若 $[P_i]+L_i\not ={P_j}$ ，则小数部分不影响不等号；否则 ，则 $[P_i]+\{P_i\}+L_i\geq [P_j]+\{P_j\} \Leftrightarrow \{P_i\}\geq \{P_j\}$

由于 $\{P_i\}$ 是独立同分布随机变量，因此它们的大小关系均匀分布的，由随机变量的连续性知，可以不妨假设 $\{P_i\}$ 两两不同，这不影响最终结果

那么，对每种可能的 $\{P_i\}$ 的大小关系，求出对应的答案 (概率)，然后最后再除以 $(N-1)!$ 就可以了

考虑对于一种特定的大小关系，如何计算概率

由于整个问题只和 $\{P_i\}$ 相对大小有关，设这 $N-1$ 个 $\{P_i\}$ 构成的集合恰为 $\left\{\frac{1}{N},\frac{2}{N},…,\frac{N-1}{N}\right\}$

每个 $P_i$ 的分布变成离散的：$0+\frac{i}{N},1+\frac{i}{N},…,(C-1)+\frac{i}{N}$

变得离散后，考虑计算方案数了，即，每段弧有 $C$ 种选择方案，求它们覆盖整个圆周的方案数

经典的状态压缩 $DP$ : 设 $f_{S,r}$ 表示用 $S$ 中的弧，最远覆盖到 $r$ (即 $[0,r]$ 被完全覆盖，$r$ 为右端点) 的方案数

边界是 $f_{0,L_N}=1$ (不妨设 $L_N=\max\{L_1,L_2,…,L_N\}$ ，注意最长的弧是预先放置好的)

考虑转移，枚举每个位置 ( $\frac{1}{N}$ 的倍数)，找到这个位置所能插入的弧 $i$ ，对于 $i\notin S$ ，将 $i$ 插入 $S$

同时，$r$ 需要在当前的起点后面，设这个弧能覆盖的右端点为 $to=\min\{P_i+L_i,C\}$ ，则转移为 $\displaystyle{f_{S\cup {i},\max\{r,to\}}+=f_{S,r}}$

$f_{U,C}$ 为总方案数，乘上 $\frac{1}{C^{N-1}}$ 即得概率

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
const int N=10;
int n,L,ALL,a[N],f[32][324];
ld ans;

inline int min(const int x,const int y){ return x<y ? x : y;}
inline int max(const int x,const int y){ return x<y ? y : x;}

inline ld solve(){
    int i,len=n*L+L;
    memset(f,0,sizeof f);
    f[0][ (n+1)*a[n] ]=1;
    for(i=1;i<len;++i)
        if(i%(n+1)){
            rei c=i%(n+1)-1,to=min(i+(n+1)*a[c],len);
            for(rei j=0;j<=ALL;++j) if(!(j>>c&1)) for(rei k=i;k<=len;++k) f[j|1<<c][ max(k,to) ]+=f[j][k];
        }
    return f[ALL][i];
}

int main(){
    int C=0;
    scanf("%d%d",&n,&L);
    ALL=~(-1 << --n);
    for(rei i=0;i<=n;++i) scanf("%d",&a[i]);
    sort(a,a+n+1);
    do ans+=solve(),++C;
    while(next_permutation(a,a+n));
    printf("%.12Lg\n",ans / (C*powl(L,n)));
    getchar(),getchar();
    return 0;
}