回归梦想

题解

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2)

/ 注册

全部文章 / 题解（共270篇）

Matrix Equation 来自专栏

题意：题目给出两个矩阵X,Y,现在有两种操作Z = X × YD = X⊙Y问是否存在一个矩阵C，使得A×C=B⊙C式子成立，问矩阵C能有多少个题解：这个式子在模2意义下的加法就等于异或也就相当于那现在有将BC移到左边然后将Ci,j的系数进行合并得到：aik =Aik A i,i = = B...

**** 数论高斯消元

2021-01-25

4 731

Xor Transformation 来自专栏

题目：给定一个X和Y，对于X每次可以选择一个A（0<=A<X），使得X = X xor A，现在要求在5步内将X变为Y，请输出操作数目，以及每步的A 题解：我一开始被题目给的样例个迷惑了，以为将Y分解开，然后再加一步X就可以了，但发现想复杂了对于W = (X ^ Y)，也就是W，X，...

** 思维

2021-01-24

0 703

Fight against involution 来自专栏

题目：对抗内卷（大佬经常说别再卷了）有一门课程n个学生选，期末要写一篇论文每个同学写的字数有一个下限和一个上限，课程的成绩是按学生字数的排名来给分的，排名越高分数越高，每个同学都想得到更高的成绩，而且他们都想写最少字数，那么在满足每个同学不能比原计划分数低的情况下求出所有同学总共要写的最少字数。 ...

*** 思维 icpc2020济南

2021-01-24

0 762

Stone Game 来自专栏

题意：有n堆石头，每堆石头最多只有三个石头（最少1个），每两堆石头（这两堆各含石头x个和y个）合一起的费用为(x mod 3) * (y mod 3)，现在把所有堆合成一堆，问最小费用题目第一行给出三个数，第i个数表示有i个石头的堆有多少个题解：费用是(x mod 3) * (y mod 3)...

** 思维题 icpc2020济南

2021-01-24

0 978

Tree Constructer 来自专栏

题目：题意：如果点x和y有连边，当且仅当a[x] or a[y] = 2^60^ - 1 （两者是充分必要）现在给你边的关系，问你每个点的值应该是多少？（给出一种情况即可）题解：构造题，思路非常巧妙2^60^就是（1<<60）,减去1也就是从第一位到第59位都是1（第六十位是0...

构造 01染色 **** 思维 icpc2020济南

2021-01-24

1 825

[SDOI2011]消耗战

[SDOI2011]消耗战题意：给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少. 题解：树型dp+虚树dp[x]:切断x及其子树上询问点的最小代价预处理出minv[pos]代表从11到pos路径上最小的边权如果pos...

dfs序 **** 虚树

2021-01-21

0 644

B-Suffix Array

B-Suffix Array 题意：一个字符串只含有a和b，先给出b数组的构造方式：对于每个位置i来说：如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j 否则b[i]=0现在对字符串每个后缀都构造B数组，并按照字典序排序题解：参考博客题目标题就已经透露...

后缀数组 ***** 思维

2021-01-20

2 641

H.Minimum-cost Flow

H.Minimum-cost Flow 题目：其实就是给出每条边的单位费用，q次查询，每次查询改变所有边的容量（所有边容量一样），问最后流出1流量的最小花费是多少？题解：暴力做法肯定是每次询问都改一次容量，但是肯定会超时，想想其他方法对于题目的每次询问，每条增广路的容量为u/v，所需最大流是1...

最小费用最大流 **** 思维

2021-01-20

0 574

1 or 2

题目描述Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices ai and bi. Find out whether is possible for him to choose...

ing 带花树 ***

2021-01-20

0 586

Codeforces1437 E. Make It Increasing（LIS）

Codeforces1437 E. Make It Increasing（LIS）题意：你有一个长度为n的数列a和一个含有k个不同整数的集合b，b中的数都在[1,n]内。现在你可以进行一些操作，每次操作中你可以选择两个数i和x，并将x赋值给ai。其中1<=i<=n，但i不能...

LIS 思维

2021-01-19

0 725