#include <stdio.h> #include <cstring> #include <cstdlib> #include <cmath> #include <iostream> #include <algorithm> #define maxn 500010 using namespace std; struct point { int l,r,val; }tr[maxn*4]; int m,n; int a[maxn]; void buildtree(int x,int l,int r) { ...

题目链接： https://www.luogu.org/problemnew/show/P2472 分析： 这道题用最大流解决。 首先构建模型。 一根柱子可以跳入和跳出，于是拆成两个点：入点和出点。 每一根柱子的入点和出点连一条流量为高度的边，来限制蜥蜴跳入的次数。 当柱子a可以调到柱子b时，就从a的出点向b的入点连边，流量inf。 S向所有有蜥蜴的柱子的入点连边，流量为1 T表示地图外一点，当一根柱子能跳到地图外时，则出点向T连流量为inf的边。 然后跑最大流即可。 这里要注意数组的范围以及拆点。 代码： #include<cstdio> #includ...

CF292A CF304B CF383A CF409D CF409F CF632A CF652B CF656A CF656B CF656D CF659A CF678A CF697A CF735D CF777A CF784A CF784E CF859A CF292A CF304B CF383A CF409D CF409C CF632A CF652B CF656A CF656B CF656D CF659A CF678A CF697A CF735D CF777A CF784A CF784E CF859A

题目： 给出一个正整数n，打印出所有从 1 1 1~ n n n的素数(即质数); 1.傻瓜解法 int i,n; while(scanf("%d",&n)!=EOF) { for(i=2;i<n;i++) if(n%i==0) ...

题目链接： https://www.luogu.org/problemnew/show/P2055 分析： 这道题比较简单，二分图的练习题（当然最大流同理）。 易得我们可以将人放在一侧，床放在一侧。 A与B认识就互相向对方的床连边流量为1 A不回家则S向A连流量为1的边。 A有床则向T连流量为1的边。 跑最大流即可。 最后判断是否等于不回家的人数。 然鹅因为作者较懒，于是写了二分图，大家可以两种方法都看看。 代码： #include<cstdio> #include<vector> #include<cstring> using na...

题目链接： https://www.luogu.org/problemnew/show/P2598 分析： 我们知道此题的目的是将狼和羊分割开，很容易想到狼在S，羊在T中。 首先，我们可以在狼，羊，空地这三者中四连通的连边，流量为1，此时可以表示无篱笆，割一条边就代表建起了长度为1的篱笆。 然后考虑狼如何向S连边呢？ 因为狼和S之间的边我们是不能割掉的！ 所以把流量赋值为inf即可。 羊和T同理。 然后跑最大流，即为最小割。 代码： #include<cstdio> #include<vector> #include<cstring> ...

题目链接： https://www.luogu.org/problemnew/show/P2057 分析： 由0和1的选择我们直觉的想到0与S一堆，1与T一堆。 但是发现，刚开始的主意并不一定是最终的结果。 于是用源点S表示最终选择0的集合。 汇点T表示最终选择1的集合。 如果一个人P选择了0，那么 S − > P ...

题目链接： https://www.luogu.org/problemnew/show/P3275 分析： 本题就是一个裸的差分约束。 核心： x = 1 x=1 x=1时， a = ...

题目链接： https://www.luogu.org/problemnew/show/P3324 分析： 因为本题的时间<stron>较多，不能枚举，但发现有单调性，于是二分答案，二分使用的时间 T T T</stron> 每个攻击装置造成的伤害总量已知，为 T ∗ ...

首先整理一下条件： 1、恰好进出每个需打扫的房间各一次 2、进出每个房间不能通过同一个门 （其实前两个条件是一回事） 3、要求每条路线都是一个闭合的环线 4、每条路线经过的房间数大于2 让你在一个n*m的矩阵中，找出是否能按照约定方案打扫全部指定房间。 首先不难得出一个结论：有奇数个需要打扫的房间时一定无解。 证明？ 每一次打扫都要满足条件3和4，而闭合的环线为多边形，显然必须对称（即通过平移可得到矩形），不难看出：每一次都能且只能打扫偶数个房间。 然后稍作分析，发现每个格子的度为2（即进入此房再出去）。 考虑建图。 一个房间上下左右有门，我们自然而然想到一个点向周围四个连边，就...

题目链接：http://poj.org/problem?id=2201 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=50010; int stack[N]; int pre[N],lson[N],rson[N]; struct node { int key,value,id; }a[N]; bool operator <(co...

#include <stdio.h> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <queue> #define maxn 10010 #define maxm 100010 #define inf 0x7fffffff using namespace std; int n,m,s,t; int ...

题目链接：https://www.luogu.org/problemnew/show/P1129 分析： 这道题不是很好想，但只要想的出来，代码不成问题。 思路1 举几个例子，我们发现， 对于任何数来说，同一行的永远在同一行，同一列的永远在同一列 进一步研究，发现所有行所有列要有1，且至少要有n个1两两不同行不同列 对于每个 1 1 1，设坐标为 ( ...

题目链接： https://www.luogu.org/problemnew/show/P4304 分析： 最大独立集 最大独立集=总点数-最大匹配数 独立集：点集，图中选一堆点，这堆点两两之间没有连边 最大独立集：尽可能多得选点，使得其满足独立集的性质 这是网络流二分图经典题目，值得练习 代码： #include<cstdio> #include<utility> #include<vector> using namespace std; int x[9]={0,-1,-2,1,2,-1,-2,1,2}; int y[9]={0,-2,-...