xyq0220

未归档

题解(3)

/ 注册

全部文章 / 未归档（共101篇）

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

codeforces 1373G Pawns 线段树

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

线段树

2020-07-02

0 415

codeforces 1369E DeadLee

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

贪心

2020-06-30

0 323

codeforces 1373F Network Coverage

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

二分

2020-06-30

0 328

gym-102082，2018-2019, ICPC, Asia Yokohama Regional Contest 2018 J Colorful Tree

题意给定一个\(n\)个点的树，每个点有个初始颜色\(c_i\)，有\(m\)次询问，询问有两种： \(U~x_k~y_k\)，将第\(x_k\)个点的颜色改为\(y_k\)。 \(Q~y_k\)，找到一个边数最少的子图，使得这个子图包括所有颜色为\(y_k\)的点，输出这个子图的边...

树链剖分 LCA

2020-06-29

0 535

codeforces 1367 F1，F2 Flying Sort

题意给出一个长度为\(n\)的数组\(a\)，每次操作能将一个数移动到数组的首位或末尾，问最少经过多少次操作能将这个数组变成单调不降的。分析在\(F_1\)中数组\(a\)的每个数字互不相同，我们发现只要找到最长的连续上升子序列（连续指在数组排序后两个数字是相邻的），n减去它的长度\(l...

DP codeforces

2020-06-18

0 412