xyq0220
xyq0220
全部文章
分类
未归档(101)
题解(3)
归档
标签
去牛客网
登录
/
注册
xyq0220的博客
不积跬步无以至千里
全部文章
(共104篇)
牛客练习赛71 C- 数学考试 DP
牛客练习赛71 C- 数学考试 题意 求 的排列,有 个限制条件,第个限制条件 表示前 个数不能是 的排列,求符合要求的排列的个数。 答案对 20000311 取模。 做法1 设为满足限制的情况下放好了排列的前个数且最大值为的方案数,转移如下: ,说明这一位有限制。 否则,,表示若,那...
DP
2020-10-14
2
627
牛客练习赛71 E- 神奇的迷宫 点分治+NTT
牛客练习赛71 E- 神奇的迷宫 题意 给一颗个点的树,每条边的长度均为,Alice和Bob两人依次传送到树的某两个结点。对于任意一个人,传送到点的概率为,假设两人传送到的结点之间的最短距离为,那么他们挑战这个树的困难度为。 问他们挑战这个树的困难度的期望是多少。 分析 令表示两人最短距离为的概率...
点分治
ntt
2020-10-13
3
659
字符串hash模板
typedef long long ll; typedef unsigned long long ull; #define maxn 1005 struct My_Hash { ull base=131; ull p[maxn],ha[maxn]; void Insert(c...
字符串
2020-07-13
0
517
2020牛客暑期多校训练营(第二场)J 置换群,欧几里得求逆元
题意 给一个大小为\(n\)的全排列\(A\)和一个整数\(k\),让你找出一个置换排列\(P\),使得\(\{1,2,\dots,n\}\)对\(P\)做\(k\)次置换后为\(A\)。 分析 把\(A\)的所有环求出来,设这些环的大小为\(r_1,r_2,\dots,r_c\)。因为\(k...
欧几里得
群论
2020-07-13
0
444
Gym-101987 2018-2019 ACM-ICPC, Asia Seoul Regional Contest K-TV Show Game 2-sat,tarjan
题意 \(k\)盏灯,每盏灯有两种颜色R,B。有\(n\)个人,每个人猜三盏灯的颜色,让你求这\(k\)盏灯的颜色,使每个人都至少猜对两盏灯的颜色。 分析 转化成\(two-sat\)问题,对于每个人若猜错其中一盏灯,那么另外两盏灯的颜色必须猜对,建边,跑\(tarjan\),输出答案。 C...
2-sat
tarjan
2020-07-13
0
678
Gym-101810 G ACM International Collegiate Programming Contest, Amman Collegiate Programming Contest (2018)
题意 字符串\(S\)的能量\(P(S)\)定义为 \[P(S)=\sum_{i=1}^{n}N_i\times V_i \] \(N_i\)是满足\(S_i=S_j\)的下标\(j(i<j\le n)\)的个数,\(V_i\)是字符\(S_i\)的\(ASCII\)码。 给一...
贪心
DP
2020-07-11
0
424
Gym-102001,2018 ICPC Asia Jakarta Regional Contest K Boomerangs
题意 给一个\(n\)个点\(m\)条边的无向图\(G=(V,E)\),让你找最多有多少个回力镖,回力镖是一个三元组\((u,v,w)\)表示边\((u,v)\subseteq E\)且边\((v,w)\subseteq E\),每个边只能存在于一个回力镖中。 分析 dfs深搜,回溯过程中将当...
dfs
2020-07-08
0
717
codeforces 1373G Pawns 线段树
题意 给一个\(n\times n\)的空棋盘,棋盘的第\(k\)列是一个特殊的列,有\(m\)次操作,每次增加一个棋子或者移走一个棋子,如果能使用以下规则将所有棋子移动到第\(k\)列,那么这个棋盘是好的。 在格子\((x,y)\)位置的棋子,能移动到\((x,y+1),(x+1,y+1...
线段树
2020-07-02
0
561
codeforces 1369E DeadLee
题意 李的店里有\(n\)种美食,第\(i\)种美食有\(a_i\)个,李有\(m\)个朋友,第\(i\)个朋友喜欢第\(x_i\)和第\(y_i\)个两种不同的美食,每个朋友来到店会吃两种他喜欢的美食各一个,如果其中一种美食不够了就只吃另一种美食,李想让你帮他安排朋友到店的先后顺序,使他的每个朋...
贪心
2020-06-30
0
478
codeforces 1373F Network Coverage
题意 给一个\(n\)个点的环,每个点是一个容量为\(a[i]\)的空水池,给\(n\)个水桶,第\(i\)个桶里有\(b[i]\)升水,第\(i\)个桶只能给第\(i\)和第\(i+1\)个水池加水,特殊的,第\(n\)个桶只能给第\(n\)个和第\(1\)个水池加水,问是否能将所有水池加满。 ...
二分
2020-06-30
0
459
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页