82801202-AGC021

B

无限大的平面上给出 $n$ 个点，任选一点出发，走到离自己欧几里得距离最近的点停下，求到每个点停下的概率

对于点 $x$ ，对该点到其余点的 $atan2$ 函数值排序

设相邻两个向量的夹角 $\theta$ ，对于点 $i$ 答案为 $\displaystyle{\frac{\max_{1\leq j\leq N,j\not ={i}}\{\theta_{i\rightarrow j},0\}}{2\times \pi}}$

const int N=110;
const double PI=acos(-1.0);
int n,tot; double ans;
double slope[N];
struct Point{ int x,y; }p[N];

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);
    for(rei i=1;i<=n;++i){
        tot=0; ans=0.0;
        for(rei j=1;j<=n;++j) if(i!=j) slope[++tot]=atan2(p[j].y-p[i].y,p[j].x-p[i].x);
        sort(slope+1,slope+1+tot);
        ans=max(ans,PI-(slope[tot]-slope[1]));
        for(rei j=2;j<=tot;++j) ans=max(ans,(slope[j]-slope[j-1])-PI);
        printf("%.10lf\n",ans/(2*PI));
    }
    getchar(),getchar();
    return 0;
}

D

给定字符串 $S(1\leq S\leq 300)$ ，最多更改其中的 $k$ 个字符 ，求 $S$ 和 $S’(S的反串)$ 的 $\text{LCS}$ 的最长长度

有神仙结论：字符串的最长回文子序列 $\text{lps}$ 的长度等于其自身与反转的最长公共子序列的长度

• 证明

  要求得到 $|LPS|=|LCS|$ ，即 $|LPS|\leq |LCS| \And |LPS|\geq |LCS|$

  显然只需要考虑 $|LPS|\geq |LCS|$

  设 $T$ 是 $S,S’$ 的一个最长公共子序列，不妨设 $|T|$ 是奇数（偶数时证明同理可得）

  设 $T$ 的第 $k$ 位是 $S$ 的第 $i$ 位与 $S’$ 的第 $j$ 位的匹配

  令

  $$\begin{aligned} n=|S|,m=|T| \\ S_l=S_{1\sim i-1},S_r=S_{i+1\sim n} \\ S'_l=S'_{1\sim j-1},S'_r=S'_{j+1\sim m} \\ T_l=T_{1\sim k-1},T_r=T_{k+1\sim m} \end{aligned}$$

  那么有 $T_l$ 是 $S_l$ 和 $S’_l$ 的一个最长公共子序列， $T_r$ 是 $S_r$ 和 $S’_r$ 的一个最长公共子序列

  • 若 $S’_r$ 是 ${S_l}’$ 的一个后缀

    $\because T_r$ 是 $S_r$ 和 $S’_r$ 的最长公共子序列 $\therefore T_r$ 一定是 ${S_l}’$ 和 ${S’_l}’$ 的公共子序列，则 ${T_r}’+T_k+T_r$ 是 $S$ 的一个回文子序列。则 $|LPS|\geq |LCS|$

  • 否则

    $S_l$ 一定是 ${S’_r}’$ 的一个前缀，那么 $S’_l$ 就是 $S_r’$ 的一个前缀，同理得 $|LPS|\geq |LCS|$

  综上得证

那么转化为求更改最多 $K$ 个字符后 $S$ 的最长回文子序列长度

区间 $dp$ ，$dp_{i,j,k}$ 含义显然

$$dp_{i,j,k}= \begin{cases} \max\{dp_{i+1,j,k},dp_{i,j-1,k}\} &\text{显然的更新} \\ \max\{dp_{i+1,j-1,k}+2\} &s_i=s_j \\ \max\{dp_{i+1,j-1,k-1}+2\} &k!=0 \\ \end{cases}$$

注意这三个判断并不冲突

const int N=310;
char s[N];
int f[N][N][N],K,n,ans;

int main(){
    scanf("%s%d",s+1,&K);
    n=strlen(s+1);
    for(rei i=1;i<=n;++i) f[i][i][0]=1;
    for(rei l=1;l<=n;++l)
    for(rei i=1;i+l<=n;++i)
        for(rei k=0,j=i+l;k<=K;++k){
            f[i][j][k]=max(f[i+1][j][k],f[i][j-1][k]);
            if(s[i]==s[j]) f[i][j][k]=max(f[i][j][k],f[i+1][j-1][k]+2);
            if(k) f[i][j][k]=max(f[i][j][k],f[i+1][j-1][k-1]+2);
        }
    for(rei i=0;i<=K;++i) ans=max(ans,f[1][n][i]);
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

E

$n$ 值变色龙，初始时均为蓝色，喂 $k$ 次球，每次让指定变色龙吃下指定颜色的球，变色龙蓝变红当且仅当吃的红球数严格多余蓝球数，反之亦有，求最后使所有变色龙变红的方案数，这里，方案数指 $k$ 个球按顺序组成的颜色序列不同

设 $R$ 个红球 ，$B$ 个蓝球

当 $RN$ 时一定有解，将多出来的这部分暂时搁置，只考虑 $B\leq R<B+N$ 的情况

得出有解的的必要条件为 $R\geq B,R\geq N$

• R=B

  那么每只变色龙必须吃球 $RB$ ,而若最后一只吃的是 $BR$ 则无解，故转化为考虑 $(R=R，B=R-1)$ 的情况

• R>B

  有一些结论：

  • 一个变色龙最多不会吃超过 $1$ 个 $R$ ，且吃完后最多吃 $1$ 个 $B$
  • 对于多个蓝球，全部喂给一条变色龙优于喂给多个
  • 任何变色龙的 $R-B\leq 1$

  那么要将组合分为：

  • 若干配对的 $RB$
  • 若干 $R=B+1$

  显然 $组合 R=B+1$ 至多产生 $R-B$ 个，即，当 $N\leq R-B$ 时所有情况均可，否则需要有 $N-(R-B)$ 个 $组合 RB$

  且 $B$ 必须在 $R$ 后面出现

  这个条件等价于: 对于序列的任何一个前缀，$B-R\leq B-(N-(R-B))=R-N$ 个

  即，统计 $(0,0)\rightarrow (R,B)$ 中处于直线 $y=x+(R-N)$ 及其下方的 $HV$ 格路数量

  总方案数为 $\displaystyle{\binom{R+B}{R}-\binom{R+B}{2\times R-N+1}}$

• 再考虑 $R=B$ 时，总方案数为 $\displaystyle{\binom{2\times R-1}{R}-\binom{2\times R-1}{2\times R-N+1}}$

综上，再加上省略的比 $N$ 多出来的东西，答案为

$$\sum_{\max \left\{ \left \lfloor K/2 \right \rfloor + 1, N \right\} \leq R \leq K} \left( \binom K R - \binom K {2 R - N + 1} \right) + \left[ 2 \mid K \right] \left[ K \geq 2 N \right] \left( \binom {K - 1} {K / 2} - \binom {K - 1} {K - N + 1} \right)$$

把这一坨化简试试：

• 当 $k$ 奇数，只有左边的式子

  $$\begin{aligned} 原式&=\sum_{\max\{\frac{K+1}{2},N\}\leq R\leq K} \left(\binom{K-1}{R-1} + \binom{K-1}{R} - \binom{K-1}{2R-N} - \binom{K-1}{2R-N+1}\right) \\ &=\sum_{i\geq \max\{\frac{K+1}{2},N-1\}\leq R\leq K} \binom{K-1}{i} + \sum_{i\geq \max\{\frac{K+1}{2},N\}} \binom{K-1}{i} - \sum_{i\geq \max\{K+1-N,N\}} \binom{K-1}{i} &\text{emmm这一步稍微有点玄学}\\ &=\sum_{i\geq \max\{\frac{K+1}{2},N-1\}\leq R\leq K} \binom{K-1}{i} + \sum_{\max\{\frac{K+1}{2},N\}\leq i\leq \max\{K+1-N,N\}} \binom{K-1}{i} \\ \end{aligned}$$

  • $N\leq \frac{K+1}{2}$

    $$\begin{aligned} 原式&=\sum_{i\geq \frac{K-1}{2}}\binom{K-1}{i} + \sum_{\frac{K+1}{2}\leq i< K+1-N}\binom{K-1}{i} &\text{这里注意k是奇数，边界注意内个是小于号} \\ &\text{如果这里向下有困难的话就只考虑 $N< \frac{K+1}{2}$ 的情况，再单独考虑相等，那时仅有第一个式子有意义，小于号使第二个式子不存在合法的 $i$ ,结论不变} \\ &=\sum_{\frac{K-1}{2}\leq i\leq K-1} \binom{K-1}{i} + \sum_{N-1\leq i\leq \frac{k-3}{2}} \binom{K-1}{i} &\text{完善一下第一个的范围，画个数轴，整数范围内就能得到下式}\\ &=\sum_{i=N-1}^{K-1} \binom{K-1}{i} &\text{typora里面空的怎么这么多啊}\\ \end{aligned}$$

  • $N>\frac{K+1}{2}$

    $$\begin{aligned} 原式&=\sum_{i\geq N-1}\binom{K-1}{i} + \sum_{N\leq i<N} \binom{K-1}{i} \\ &=\sum_{i=N-1}^{K-1}\binom{K-1}{i} \\ \end{aligned}$$

• 当 $K$ 为偶数

  这里推到显然相同，只是原式中的第二个会在 $N\leq \frac{K}{2}$ 时对式子产生贡献，使其不变，这里推到略去

综上所述，有人是懒狗但我不说是谁 原式始终为 $\sum_{i=N-1}^{K-1}\binom{K-1}{i}$

const int N=5e5+100;
const int mod=998244353;
int n,K,inv[N];
ll ans;

inline void fix(ll &x){ x>=mod ? x-=mod : 0;}

int main(){
    scanf("%d%d",&n,&K);
    rei cur=1;
    n=K---n; inv[1]=1;
    for(rei i=2;i<=n;++i) inv[i]=(ll) (mod-mod/i)*inv[mod%i]%mod;
    for(rei i=0;i<=n;++i) fix(ans+=cur),cur=(ll) cur*(K-i)%mod *inv[i+1]%mod;
    printf("%d\n",(int) ans%mod);
    getchar(),getchar();
    return 0;
}