DeF1ne's Blog


DeF1ne的博客

2025-08-18 妯℃嫙鑰冭瘯 in Xinyoudui

  • ~2.63K 字
  1. 1. 得分情况
  2. 2. 错误原因
    1. 2.1. T2
    2. 2.2. T3
  3. 3. 题解
    1. 3.1. T1 小信学习欧几里得算法
      1. 3.1.1. 题意
      2. 3.1.2. 思路
    2. 3.2. T2 涛涛的地铁
      1. 3.2.1. 题意
      2. 3.2.2. 思路
    3. 3.3. T3 最短路
      1. 3.3.1. 题意
      2. 3.3.2. 思路
    4. 3.4. T4 时光里的卡牌
      1. 3.4.1. 题意
      2. 3.4.2. 思路

8:00——8:40 想，做T1

8:40——10:30 想，做T2

10:30——12:00 打T3部分分，想T4

得分情况

题目 T1 T2 T3 T4
分数/状态 100/AC 85/RE WA/RE/0Pts 0//

错误原因

T2

数组开小了，导致Runtime Error

这件事告诉我们数组一定要开大，但是开大了又可能会MLE，最后建议使用vector

T3

注意到20分的时候，wi=0w_i=0，遂使用Dijkstra模板，但是因为数组又没开大导致小样例WA，大样例RE

这个数组怎么这么坏啊

题解

T1 小信学习欧几里得算法

题意

输入nn，计算所有数对(a,b)(1≤a<b≤n)(a,b)(1\le a<b\le n)中，使得lcm(a,b)÷gcd⁡(a,b)lcm(a,b)\div \gcd(a,b) 为质数的数对个数

思路

设a=gx,b=gy,gcd⁡(x,y)=1a=gx,b=gy,\gcd(x,y)=1，则

lcm(a,b)gcd⁡(a,b)=xy \frac{lcm(a,b)}{\gcd(a,b)}=xy

要求xyxy为质数，唯一确定的构造方法便是x=1,y=px=1,y=p(p为质数)，计算方式为

∑p≤n⌊np⌋ \sum_{p\le n}{\lfloor \frac{n}{p}\rfloor}

T2 涛涛的地铁

题意

给出nn个地铁站，mm条线路，pp家公司，每条线路隶属于一个公司ww，票价为cc

给出qq个询问：从uu站到vv站，最多乘坐kk家公司的地铁，求最小花费，若无法到达输出-1

数据限制：n≤100,p≤6,q≤106,c≤104,m≤p×n×(n−1)n\le 100,p\le 6,q\le 10^6,c\le10^4,m\le p\times n\times (n-1)

好家伙这么贵的票价这么多的地铁公司这么多线路，涛涛同学是不是生活在ToˉkyoT\bar{o}kyo

思路

注意到p≤6p\le 6，可以直接状压枚举每个公司

然后使用FloydFloyd求每对点之间最短距离即可，最后前缀最小化求出答案，时间复杂度Θ(2p×n3)\Theta(2^p\times n^3)，可以AcceptedAccepted

数组一定要开大啊喂

T3 最短路

题意

从城镇11出发，到城镇nn，走最短的路径，路径上有市场，可以做一次买卖（先买后卖或者先卖后买）

求最短路

在最短路的前提下，求最大利润

思路

先使用BFS，找到最短路

在所有的最短路径上，找出收益最大的方案

  1. 构建DAG
  2. 建立前缀最大差，后缀最大差
  3. 枚举，寻找最优解

T4 时光里的卡牌

题意

共有2n2n张牌，初始上面nn张牌是解锁的

每轮操作

  • 从已解锁的牌中等概率选一张，加入手牌
  • 得分+=当前手牌所有牌的和
  • 如果还有未解锁的牌，解锁最上面的一张

思路

我们首先思考单张牌的贡献

假设第ii张牌在第kk回合被抽走

  • 当前回合贡献一次，因为在手牌中
  • 之后每轮都会贡献一次

所以这张牌的贡献是

(2n−k+1)×ai (2n-k+1)\times a_i

我们再来思考抽中概率

bj=min⁡(n,2n−j+1) b_j=\min(n,2n-j+1)

表示第jj轮开始时已解锁的牌数量

期望贡献

情况1：i≤ni\le n(初始已经解锁)

概率公式

Pr[k]=1bk∏k−1j=1bj−1bj Pr[k]=\frac{1}{b_k}\prod^{j=1}_{k-1}\frac{b_j-1}{b_j}

期望贡献

E[i]=ai∑k=12n(2n−k+1)×1bk∏k−1j=1bj−1bj E[i]=a_i\sum^{2n}_{k=1}(2n-k+1)\times \frac{1}{b_k}\prod^{j=1}_{k-1}\frac{b_j-1}{b_j}

情况2：i>ni>n（后来解锁）

E[i]=ai∑k=i−n+12n(2n−k+1)×1bk∏k−1j=i−n+1bj−1bj E[i]=a_i\sum^{2n}_{k=i-n+1}(2n-k+1)\times \frac{1}{b_k}\prod^{j=i-n+1}_{k-1}\frac{b_j-1}{b_j}

化简

注意到∏\prod部分与前缀积相似

定义

P[k]=∏j=1kbj−1bj,p[0]=1 P[k]=\prod^{k}_{j=1}\frac{b_j-1}{b_j},p[0]=1

所以说

  • 对于初始牌

    E[i]=ai∑k=12n(2n−k+1)×P[k−1]bk E[i]=a_i\sum^{2n}_{k=1}(2n-k+1)\times \frac{P[k-1]}{b_k}

  • 对于后来的牌

    E[i]=ai∑k=i−n+12n(2n−k+1)×P[k−1]p[i−n]×bk E[i]=a_i\sum^{2n}_{k=i-n+1}(2n-k+1)\times \frac{P[k-1]}{p[i-n]\times b_k}

代码实现

  1. 预处理b数组

  2. 预处理p数组

  3. 预处理w数组

  4. 预处理前缀和prew数组

  5. 计算期望

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
Share
Take a look