xyq0220

分类

未归档(101) 题解(3)

/ 注册

全部文章（共104篇）

牛客练习赛71 C- 数学考试 DP

牛客练习赛71 C- 数学考试题意求的排列，有个限制条件，第个限制条件表示前个数不能是的排列，求符合要求的排列的个数。答案对 20000311 取模。做法1 设为满足限制的情况下放好了排列的前个数且最大值为的方案数，转移如下：，说明这一位有限制。否则，，表示若，那...

DP

2020-10-14

2 502

牛客练习赛71 E- 神奇的迷宫点分治+NTT

牛客练习赛71 E- 神奇的迷宫题意给一颗个点的树，每条边的长度均为，Alice和Bob两人依次传送到树的某两个结点。对于任意一个人，传送到点的概率为，假设两人传送到的结点之间的最短距离为，那么他们挑战这个树的困难度为。问他们挑战这个树的困难度的期望是多少。分析令表示两人最短距离为的概率...

点分治 ntt

2020-10-13

3 486

字符串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 400

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 339

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 534

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 294

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 566

codeforces 1373G Pawns 线段树

题意给一个\(n\times n\)的空棋盘，棋盘的第\(k\)列是一个特殊的列，有\(m\)次操作，每次增加一个棋子或者移走一个棋子，如果能使用以下规则将所有棋子移动到第\(k\)列，那么这个棋盘是好的。在格子\((x,y)\)位置的棋子，能移动到\((x,y+1),(x+1,y+1...

线段树

2020-07-02

0 412

codeforces 1369E DeadLee

题意李的店里有\(n\)种美食，第\(i\)种美食有\(a_i\)个，李有\(m\)个朋友，第\(i\)个朋友喜欢第\(x_i\)和第\(y_i\)个两种不同的美食，每个朋友来到店会吃两种他喜欢的美食各一个，如果其中一种美食不够了就只吃另一种美食，李想让你帮他安排朋友到店的先后顺序，使他的每个朋...

贪心

2020-06-30

0 318

codeforces 1373F Network Coverage

题意给一个\(n\)个点的环，每个点是一个容量为\(a[i]\)的空水池，给\(n\)个水桶，第\(i\)个桶里有\(b[i]\)升水，第\(i\)个桶只能给第\(i\)和第\(i+1\)个水池加水，特殊的，第\(n\)个桶只能给第\(n\)个和第\(1\)个水池加水，问是否能将所有水池加满。 ...

二分

2020-06-30

0 328