xyq0220
xyq0220
全部文章
未归档
题解(3)
归档
标签
去牛客网
登录
/
注册
xyq0220的博客
不积跬步无以至千里
全部文章
/ 未归档
(共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
513
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
456
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
684
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
430
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
721
codeforces 1373G Pawns 线段树
题意 给一个\(n\times n\)的空棋盘,棋盘的第\(k\)列是一个特殊的列,有\(m\)次操作,每次增加一个棋子或者移走一个棋子,如果能使用以下规则将所有棋子移动到第\(k\)列,那么这个棋盘是好的。 在格子\((x,y)\)位置的棋子,能移动到\((x,y+1),(x+1,y+1...
线段树
2020-07-02
0
569
codeforces 1369E DeadLee
题意 李的店里有\(n\)种美食,第\(i\)种美食有\(a_i\)个,李有\(m\)个朋友,第\(i\)个朋友喜欢第\(x_i\)和第\(y_i\)个两种不同的美食,每个朋友来到店会吃两种他喜欢的美食各一个,如果其中一种美食不够了就只吃另一种美食,李想让你帮他安排朋友到店的先后顺序,使他的每个朋...
贪心
2020-06-30
0
486
codeforces 1373F Network Coverage
题意 给一个\(n\)个点的环,每个点是一个容量为\(a[i]\)的空水池,给\(n\)个水桶,第\(i\)个桶里有\(b[i]\)升水,第\(i\)个桶只能给第\(i\)和第\(i+1\)个水池加水,特殊的,第\(n\)个桶只能给第\(n\)个和第\(1\)个水池加水,问是否能将所有水池加满。 ...
二分
2020-06-30
0
468
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
658
codeforces 1367 F1,F2 Flying Sort
题意 给出一个长度为\(n\)的数组\(a\),每次操作能将一个数移动到数组的首位或末尾,问最少经过多少次操作能将这个数组变成单调不降的。 分析 在\(F_1\)中数组\(a\)的每个数字互不相同,我们发现只要找到最长的连续上升子序列(连续指在数组排序后两个数字是相邻的),n减去它的长度\(l...
DP
codeforces
2020-06-18
0
541
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页