C. Rectangles time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output You are given nn rectangles on a plane with coordinates of their b...

题意: A和B玩游戏,A先手,每次从1~n中选一个数,并去掉该数的所有因子,最后不能操作的人输 思路: 玄学题,想了好久没想到。。。 因为1是任何数的因子,所以只要选择其他数,必将1删去 考虑在2~n的数列中取数 若先手胜利:无需做任何改变,因为1是任何数的因子,一定会被删去,故不影响比赛 若先手失败:则A可以第一次取1,这样就变成B先手在2~n中取数,因为先手失败,所以B会失败,A则胜利 代码:...

题意: 给出一个数列,其中每有一个逆序数就花费x元,也可以花费y元交换相邻两个数,求处理这个数列的最小花费 思路: 可分析出,交换一次最多只能减少一个逆序数,所以只可能全部交换或者一个都不交换,故此题只需求出逆序数个数即可 O(nlogn)时间下求逆序数个数,可用归并排序法或树状数组法 使用树状数组求解,先将数列从大到小排序,每次选取最大的数放入,树状数组中记录某位置出现数的个数(某位置是否有数)...

题意: 构造一个字典序最小的数列,给出m个限定条件,对于每个限定条件,l:r,表示该数列中a[l:r]中各个数不相同 思路: 先将限定条件按最左最长排序,分三种情况讨论 1.若某区间完全被其他区间包含则略过 2.若两区间有重合部分,则重合部分不变,后部分从小到大填入可用数 3.若两区间没有重合部分,则两区间之间不相交部分都填1,后一区间从1开始填入数字 因每区间中满足不重复,且从小到大排列,适用s...

题意: 给出一个无向图,每个边有一个标号,在标号相同的边上走不增加花费,每走到标号不同的边上时,花费+1,求从1~n的最小花费 思路: 与最短路问题极为相似,考虑对最短路算法进行修改 在spfa算法的基础上,遍历每个点,使用set记录由哪条边到达该点,若花费相同时,优先选由相同标号边到达的点,不同时按照正常spfa选择花费小的点,这样既可得到答案 其他方法:bfs+dfs,从起点开始,进行bfs枚...

题意: 有n个点,m个操作,操作为增加一条边或删除一条边,每次操作后输出1~n/2个边的匹配个数,k边匹配的定义为:取k条边为一组,这一组边中没有公共点,求能找出多少组 思路: 因为n的范围2~10,数据很小,考虑状压dp,设计dp方程,dp[now][S]表示now状态下,点集为S时,已经匹配的方案数。 对于加边操作,dp[i][S]=dp[i-1][S]+dp[i-1][S-(u,v)],对应...

目录: 整除的性质 常见定理 模与余 3.1模运算 3.2同余的性质 3.3快速幂 数论重要定理及应用 4.1欧几里得定理 4.2扩展欧几里得 4.3线性同余方程(模线性方程) 4.4中国剩余定理(模线性方程组) 4.5乘法逆元 4.6二次同余方程 4.7唯一分解定理 素数及其相关定理 5.1反素数 5.2素数筛 5.3素性测试 5.4欧拉函数 5.5欧拉降幂公式 5.6积性函数 莫比乌斯相关 6...

题意: 有两个数列,a和b,a初始全为0,b初始为给定值,对于a有两种操作,区间加1,区间求[ai/bi]的和 思路: 本题难点在于如何在log时间下实现区间修改,若用常规考虑,区间修改时遍历所以叶子结点,则需要n的时间,一定超时 对于线段树结点,记录最小值和最小值来源,初始将各叶子结点的最小值赋成b[i]的值,每次区间加1时,将对应最小值-1,利用懒惰标记思想,仅当某结点的最小值为0时,才向下搜...

目录 排列 1.1不可重排列 1.2可重排列 1.3圆排列 1.4不尽相异元素全排列 1.5多重集的排列 组合 2.1不可重组合数 2.2可重组合 2.3不相邻组合 2.4多重集的组合 2.5常用组合数公式 2.6组合数取模(模板) 常用公式及定理 3.1二项式定理 3.2鸽巢原理 3.3常见恒等式 3.4帕斯卡恒等式 3.5卢卡斯定理推论 3.6容斥原理 3.7错排问题 常见数列及其性质 4.1...

回文自动机

ACM

  

2019-07-02 02:05:52

本文参考自原文链接 回文自动机,又叫回文树,是由俄罗斯人 MikhailRubinchik于2014年夏发明的(http://codeforces.com/blog/entry/13959). 这是一种比较新的数据结构,在原文中已有详细介绍与代码实现。 回文树其实不是严格的树形结构,因为它有是两棵树,分别是偶数长度的回文树和奇数长度的回文树,树中每个节点代表一个回文串。 为了方便,第一棵树的根是一...

股神

ACM

  

2019-07-03 23:01:01

经过分析,股票分别在第3、6、10、15.......天时跌,它们之间的差值为3、4、5.......,因此设置变量acc和temp分别记录差值和股票跌的日期,处理方法看代码。除第一天外其余时间股票均在涨,对记录股票价值的变量sum++即可。  ...

P1003 铺地毯 C++

ACM

  

2019-07-13 08:36:56

题目地址:https://www.luogu.org/problemnew/show/P1003 题目: 题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 nn 张地毯,编号从 11 到nn。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯...

上下界网络流

ACM

  

2019-07-13 22:30:31

//其实主要还是自己复习用 //假定读者能够熟练打dinic的板子 有上下界的网络流的核心是”调整”,我们通过一个初始的未必可行的流调整出一个可行流,还可以从可行的未必最大/最小的流调整出最大/最小流. 另一个常用技巧是有源汇的流和无源汇的流(循环流)的转换.除了无源汇可行流的求解,其他有源汇的上下界网络流都要用到这个技巧. 无源汇有上下界可行流(也就是循环流) 模型:一个...