2019 CUST程序设计竞赛-正式赛题解

H Arithmetic Sequence

• 一个数也是数列,所以输出一行1一行X即可

F Successione di Fixoracci

• ,计算长度为3的循环节

J Printout

• 找出第一个大于n的X
• 假设第一个大于n的位置为p,初始化答案为n*x[p],
• 枚举p后面的x[i+1]*X[i],维护最小值

L Homework Stream

• 两个vector分别记录k依赖的作业和依赖于k的作业

I Fate Grand Order

• 期望=开心值*概率
• 将m个活动按期望值从大到小排序,取前n/3个的期望之和

B Bowling Game

M Orx Zone

• 容斥做法:总区间数-不包含'r'的区间数-不包含'x'的区间数+同时不包含'r'和'x'的区间数
• 双指针做法:对于每一个l,扫出最左的r,使得[l,r]中含有至少一个'r'和'x',那么这个l对应的区间数就是n-r+1,累加到答案上

E Shortest Code

• 按照题意模拟即可
• 处理好连续多空格的情况就可以,开个变量记录一下第一个空格左边的字符和最后一个空格右边的字符

A Rubbish

• bfs+set 判联通块,每次进队前将点从set中删去
• 卡了dfs，可能卡了并查集

G Segment Tree

• 双向链表+set
• 复杂度玄学
• 模拟就给过(大概)

K Master of Graph

• 修改特定编号的点,所以和图没关
• 查询:线段树区间查询
• 修改:每个点的修改次数十分有限,因此一开始暴力单点修改,标记已经被修改成全是个位数的区间,不再往下修改

C REN

• 首先得明确一点:由于给出块的形状,无论如何地形不会向下减少,所以只需要记录最上一层的状态即可
• 定义为第i块,当前地形为j,连续消去k,存块位存着p类块的最大得分
• j:0为平,1为左,2为右
• 转移
  • 出库的块舍弃
  • 出库的块下落
  • 出库的块放进存块位(当存块位为空合法)
  • 出库的块换存块位的块(存块位不为空合法),存块位的块下落

D Capture the Flag

• m<=1e9
• 预处理出哈希值不同的sqrt(1e9)个串,用map存
• 那么不击中的概率为
• 1e6连续不击中的概率为,所以随机生成串即可