Henry_WYH

分类

题解(13)

/ 注册

全部文章（共13篇）

#文本生成器加强版#

本题是JSOI2007文本生成器的加强版，在于文章的长度扩大了一百倍，因此我们需要对我们一开始的DP进行优化。观察一下原题的DP，写成这样：状态定义：f[i][p]表示生成到第i位字符，位于字典的AC自动机的p位置，且不含有任意字典串作为子串的方案数 f[0][0]=1; for(int...

AC自动机预处理优化

2022-04-07

0 531

F375

F-375 先判断数位和是不是三的倍数，然后无脑做就行了，相当于打一张表，只要统计三位数是125的倍数存不存在就行了，多判断一个三个0的情况 string p; int sum =0; int cnt[10]; void print(int a,int b,int c){ cnt[a]--...

打表

2021-12-04

5 776

题解 | #[CQOI2007]矩形RECT#

#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace s...

C++

2021-11-11

2 857

题解 | #[SCOI2010]游戏#

https://www.luogu.com.cn/problem/P1640 两种做法：【1】我们可以发现老套路，这种一个物体连接两个结点的一般是物体做边连接两个点来构成一张图。然后我们从1开始选择，每选择一个就删去一条边。记住如果当前图上有环的话，可以多选一条边。至于怎么维护这个关系，带权并...

二分图并查集

2021-11-11

1 557

题解 | #快餐店#

算法：基环树DP 这道题是我学完基环树后自己做出来的第一道题目hh，虽然调了很久和这道题目有些类似的题目有IOI2008 Island 这题 https://www.luogu.com.cn/problem/P4381 下面来说这一题的思路： n点n边，任意两点之间都有一条双向边，因此这是一颗基环...

基环树树形DP

2021-10-16

3 543

题解 | #[ZJOI2008]骑士#

做法1： 1.通过并查集维护连通性找出所有基环树的环的起点终点 2.对于每一个起点终点dfs不选这个点（和没有上司的舞会一摸一样的dfs），取max累加答案 #include<iostream> #include<cstdio> #include<algorithm&g...

2021-10-14

1 651

题解 | #Balls#

Time: O(n) Memory: O(1) int n; double s = 1.0 , p = 0.5; //================================= int main(){ n=read(); rep(i,1,n) s = (s + 1....

2021-10-12

1 459

题解 | #Let's Play Osu!#

期望长度： ki=(ki−1+1)×pi k_i=(k_{i−1}+1)×p_i ki=(ki−1+1)×pi 期望分数： fi=fi−1×(1−pi)+(fi−1+2×ki−1+1)×pi f_i=f_i−1×(1−p_i)+(f_i−1+2×k_i−1+1)×p_i fi=fi−1×(...

2021-10-12

2 397

题解 | #[SCOI2008]奖励关#

倒着推导 f[i][st]+=((pre[j]&st)==pre[j]?max(f[i+1][st],f[i+1][st∣(1<<j)]+score[j]):f[i+1][st])/k;f[i][st] += ((pre[j] \& st)==pre[j]?max(f[i...

2021-10-12

3 428

题解 | #抽卡#

(f[st]+1)∗∑p[j]=∑jp[j]∗f[st∣(1<<j)](f[st] + 1) * \sum p[j] = \sum_{j} p[j] * f[st|(1<<j)] (f[st]+1)∗∑p[j]=∑jp[j]∗f[st∣(1<<j)] 看不懂的话...

2021-10-12

2 405