据说多校赛的时候，可以直接用O（nm）的暴力for循环跑过 赛后补题就TLE了 找网上找到了一种很好的方法处理这种答案为0或者1的匹配问题 考虑dp【i】【j】 但是如果有交换的话，这种定义是不够的 所以再加一维变成dp【i】【j】【k】 然后转移用bitset转移+dp状态压缩一维 具体思路和细节见： HDOJ5745 DP+bitset

Description 给定一张航空图，图中顶点代表城市，边代表2城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。 (1)从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点(可途经若干城市)。 (2)除起点城市外，任何城市只能访问1次。 编程任务： 对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。 由于本OJ无Special Judge ， 所以只需要输出最多经过的城市数 Input 第1 行有2个正整数N 和V，N 表示城市数，N<100，V 表示直飞航线数。 接下来的N行中每一行是一个城市名，可乘...

计算几何的圆的模板题+二分判断 题目中给了n个圆，要求：在这n个圆中取某个圆的圆心，然后找到最小的半径，使得这个新的圆与这n个圆的相交面积，会不小于这n个圆的面积的一半 说起来，很绕口，但是因为n不大，是可以枚举的！ 对于每个圆心，我们都求一个最小的半径，然后n个值中间取最小的就是答案 那么，如何求得这个最小呢？很简单，化计算性问题为判定性问题 我们二分半径，然后验证这个半径会不会满足题中面积的条件 剩下的：就是靠kuangbin模板啊：就是如何已经两个圆的圆心和半径，然后求相交的面积 代码如下： #include<bits/stdc++.h>...

Description 在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。 编程任务： 对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 Input 第1 行有2 个正整数m和n，分别表示棋盘的行数和列数。 接下来的m行，每行有n个正整数，表示棋盘方格中的数。 Output 程序运行结束时，将取数的最大总和输出 Sample Input 3 3 1 2 3 3 2 3 2 3 1 Sample Output 11 题目链接： 方格取数问题 这个题是...

题目链接：codeforces 500C 这个题，不是难在写代码，而是难在了如何去证明这个结论（其实猜想也是只要胆子大，就是可以过的） 关键是从样例中找到这个题的解法！ 书的初始排列顺序是定好的！ 就是按照m本书的给定数据，从前到后，建立一个链表，然后去暴力操作就好！ 证明是所谓的理论证明吧，就是读的书是需要把该书上面的书全部拿走的。那么，越早阅读的书，放在越上面越好咯 那么，涉及到最重要的问题 数据结构是个链表：在暴力找到了需要读的书之后，需要把这个节点删除，然后插入到起点和起点的后一个点之中 然后就是个看基本功的题了 #include<bits...

题目链接：cf 711D 这个题主要是读题意比较难 因为是n个点，n条边，那么肯定会有环存在 那么，一旦出现了环，就出现了题中给的非法情况 那么，我们根据连通情况将图中的点分类（按照乘法原理，先各自计算当前的集合之中有几个数，然后相乘） 在每个集合中，如果出现了环，假设环中的点数为x，那么可以的方案数目为（2^x-2）（样例1） 如果既有环，又有链子，假设环中的点数为x，链子中的点数为y，那么可以的方案数目为（2^x-2）*（2^y），当然在操作中是只能求出x+y的（样例3） 那么，这个题就是dfs搜索搞定的 cf的题目很多都是需要数学方法先想明白，其实代码实现确实...

Description 一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。 每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。 试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。 编程任务：编程找出一个最佳餐巾使用计划. Input 第1 ...

给个负责任的OJ：汽车加油 Description 给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X 轴向右为正，Y轴向下为正，每个方格边长为1，如图所示。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在 行驶过程中应遵守如下规则： (1)汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 (2)汽车经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则免付费用。 (3)汽车在行驶过程中遇油库则应加满油并付加油费用A。 (4)在需要时可...

看上去就是DP的一个题，由于自己太菜了，还是不会做 先给个提交的地方：cf 711C 这个题看到数据，很明显是dp，因为n，m，k的值都不大，我们可以建立矩阵来推理 很明显答案跟dp【n】【k】有关 也就是dp【i】【j】代表前i个树涂完之后，有了j个匹配的最小花费 但是，这样怎么转移呢？！ 很明显，数组还可以再开得大一点，多加一维（又相当于多了一个分层图） dp【i】【j】代表前i个树涂完之后，有了j个匹配，最后一棵树（第i颗树）的颜色为k，的最小花费 那么初始值： 看第一课树是不是染色已经染好了 如果a【i】=0，那么就是需要染色 那么就需要枚举第三维的K...

题目链接：cf 704A 这个题是一个很好的题，首先理解题意就比较费劲，然后看上去是一个模拟的题，是需要用数据结构来维护的，暴力写是超时的 分析题意： 题目中给定了三种操作 操作1：第x种应用增加一个未读消息 操作2：我把第x种应用的消息全部读完（标记为已读） 操作3：我把所有的应用的消息按照时间从先到后的顺序，读取x个 在读取的时候，是可能会有重复读取的。 n=1e5，q=1e5 然后，每个操作之后，我们需要输出的是，在每个操作之后，当前的消息库中总共还有多少个未读消息 学到了一个线段树来维护未读消息的姿势！ 竟然这样写没有超时，我很诧异 首先，搞两个数组...

这个题吧，纯属看模板好不好。。。 题意很简单，求【1，n】中的素数有多少个，n很大，1e11的范围 原来普通的数学方法构造的打表是TLE或者MLE的 Lehmer快速求素数 用这个方法呢，就可以形成一个模板类的素数打表了 思想是小数据用打表中的值输出，大数据用Lehmer的公式化归一下就可以往下递归，然后推到表格中的数值了 模板贴一下吧，链接中也有： #include<bits/stdc++.h> using namespace std; #define MAXN 110 #define MAXM 10010 #define MAXP 666666...

题意：有N对数值排成一列，一个是KEY值，一个是VALUE值 如果相邻的KEY值不是互斥的（最大公约数不为1），那么我们就可以把它们消掉，得到的分数就是他们的VALUE值的和 同时，因为这两个值消去了，那么原来不相邻的数就可以相邻了 区间DP还是比较明显的 一方面是因为n小，n最大为300，符合n<1000的区间DP的要求 另一方面是对数值的操作，我们必须知道相邻的数值的情况，才会知道大区间的情况 这个题的坑点在于： 我们需要设计两个数组来搞 dp【i】【j】：从i点到j点的区间【i，j】的最大的VALUE值 ok【i】【j】：从i点到j点的区间【i，j】是不是...

打表其实还是很明显的 因为满足2^a*3^b*5^c*7^d这个样子的，在【1，1e9】中其实是没有多少的 那么，我们先把2，3，5，7的次方数组打出来，然后枚举a，b，c，d 然后把所有满足条件的数放到一个数组中，然后查询搞一发就可以了 主要还是在枚举和二分细节上注意别出错就好 #include<bits/stdc++.h> #include<algorithm> using namespace std; #define LL __int64 const LL maxn=1E9; LL x[1000050]; LL pow2[100],pow3[10...

Description W公司有m个仓库和n 个零售商店。第i 个仓库有ai个单位的货物;第j个零售商店需要bj个单位的货物。 货物供需平衡，即sigma(ai)==sigma(bj)。 从第i个仓库运送每单位货物到第j个零售商店的费用为Cij。试设计一个将仓库中所有货物运送到零售商店的运输方案， 使总运输费用最少。 Input 第1行有2 个正整数m和n，分别表示仓库数和零售商店数。 接下来的一行中有m个正整数ai，1≤i≤m，表示第i个仓库有ai个单位的货物。 再接下来的一行中有n个正整数bj，1≤j≤n，表示第j个零售商店需要bj个单位的货物。 接下来的m行，每行有n个整数，表示从...