题目链接：http://poj.org/problem?id=2289题目大意：杰米有n个联系人（名字不会重复），现在每个联系人都有一些可能的分组，现在她要把所有的联系人把分组。要求最多人的分组人数最少。思路：先二分一下这个最小值mid，然后设置右边的点容量为mid。直接跑二分图多重匹配。如果==n。说明可行。 /* 匈牙利算法解决多重匹配问题 */ #include <map> #include <set> #include <cmath> #include <queue> #include <cstdio> #inclu...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3829题目大意：思路：如果A喜欢==B不喜欢||A不喜欢==B喜欢。那么A和B不能同时满足。连一条边。因为如果孩子的喜欢动物是猫，那么他/她的不喜欢动物一定是狗，反之亦然。那么可以证明一定一个二分图。就是求二分图的最大独立集。 #include <map> #include <set> #include <cmath> #include <queue> #include <cstdio> #include <vector&...

题目链接：https://ac.nowcoder.com/acm/problem/20241题目大意：思路：f[i][0/1][0/1][0/1]:表示i-1, i, i+1放不放雷的方案数。其实只要记录i和i+1就可以了。因为i-1可以从上一个转移状态的i得到。初始化： #include <bits/stdc++.h> #define LL long long using namespace std; int a[10005]; LL f[10005][2][2][2]; int main(){ int n; scanf("%d", &n)...

题目链接：https://ac.nowcoder.com/acm/contest/6013/H题目大意：题目大意：给你n个线段。给你一个区间1-1e6.让你覆盖这些区间，要求区间上没有一个点被覆盖>k次，问最少有多少线段用不上，就是：n-最多可以用多少线段。 分析：我们知道如果k=1.是一个典型的贪心。按右端点排序从小到大选择。贪心的选择就可以了。如果k！=1.其实是一样的就是k次贪心。把之前选择的线段去掉再重复这个贪心选择过程k次。当然模拟k次肯定是不行的。我们考虑用一个数据结构来维护这个区间覆盖次数。支持区间修改，区间查询。-线段树。这道题就写完了。 当然用另外一种维护方法可以直接用...

题目链接：https://ac.nowcoder.com/acm/contest/6012/C题目大意：思路： #include <bits/stdc++.h> using namespace std; const int MOD=998244353; const int MAXN=2002020; int fac[MAXN+5],facinv[MAXN+5]; long long quickmul(int a,int b){ long long ret=1; for(; b ; b >>=1 ,a =(long long) a * a % MOD...

题目链接：https://ac.nowcoder.com/acm/problem/19314题目大意：就是有一棵树，每个节点有一个防御力mi[i], 你的攻击力为P，你1是根节点，每次你可以选择一个节点i进行攻击，对i造成的伤害为P，对i的子孙j造成 的伤害，并且攻击i节点时，保证他的所有祖先全部被击败，mi[i]<0就被击败。问你最少的攻击次数，把树上节点全部打败。思路：ps:siz[], di1[], di2[]:直接维护1-i的前缀和会爆LL #include<bits/stdc++.h> #define LL long long using namespace std...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3416题目大意：有n座城市m条单向边。问从A城市到B城市有多少种走法，每条边只能经过一次。思路：我们跑出最短路图，建图流量为1，然后直接最短流。 #include<bits/stdc++.h> #define LL long long using namespace std; const LL maxn=100005; const LL INF=10000000000000000; LL d[maxn], cur[maxn], start, tend; struct node { ...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3081题目大意：一群小孩子在玩过家家，选择有n个男孩和n个女孩。每个女孩都可以首先选择一个未与之吵架的男孩组成一个家庭。另外，如果女孩X是她的朋友，那么女孩X也可以选择这个男孩作为她的男朋友。此外，友谊是相互的，这意味着只要a和b是朋友并且b和c是朋友，则a和c是朋友。一旦每个女孩找到他们的男朋友，他们就会开始这场游戏的新一轮比赛-婚姻竞赛。在每个回合结束时，每个女孩都会开始寻找新的男朋友，而她以前从未选择过。游戏就这样继续下去。现在，这是您的问题，这2n个孩子总共可以玩几轮？ 思路： #incl...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3605题目大意：地球有n个人(1 <= n <= 100000)，有m个星球(1 <= m <= 10)每个人都有一些想去的星球，用一行成都为m的01串表示。1：表示想去这个星球，0表示不想去。每个星期有居住的人口数限制，问你能不能安排好所有人。 #include<bits/stdc++.h> #define INF 1e9 using namespace std; const int maxn =2000+10; struct Edge { int ...

题目链接：https://ac.nowcoder.com/acm/problem/15031题目大意：思路：除了可能是凹多边形外，就是裸的三角剖分。f[i][j]编号为i，i+1, i+2, ... j的点形成的多边形的最优三角剖分。因为i-j这条边为底，一定属于一个三角形，我们枚举k为顶点进行转移就可以了。f[l][r]=min(f[l][r], max(max(f[l][k], f[k][r]), calc(a[l], a[r], a[k])));如果是凹边形，可能出现一个情况。f[2][7],k=5时。内部有点。那么这个点和2，7，5的连线形成3个三个三角形的面积和为s(2, 7, 4)...

题目链接：https://ac.nowcoder.com/acm/problem/18386题目大意：思路：看完题的第一个思路：前缀和+二分。发现空间给的很小前缀和MLE。那我们换一种二分思路：保存每个字符的位置i。枚举区间左端点l。二分>=l的26个字符的最远位置r。r-l+1就是左端点为l的最小区间长度。尺取：满足条件l++，否则r++ #include <bits/stdc++.h> #define LL long long using namespace std; char s[1000005]; vector<int> v[26]; int main(...

题目链接：https://ac.nowcoder.com/acm/problem/50995题目大意：思路：贪心+优先队列：我们按时间从小到大排序，当前时间T。并且维护已经选取的商品的最小利润。如果当前商品的时间==T。那么从优先队列来里面找到最小值如果<当前商品的利润：替换。如果当前商品的时间<T，直接选取。 思路：并查集：我们按商品的利润从大到小排序，那么我们希望从前往后贪心。并且把每个商品放在自己过期时间前越后越好。我们用并查集来维护时间。f[i]=-1：第i天空闲。否则f[x]=y。x前面第一个空闲的天数是f[y]。如果找到空闲天x.维护f[x]=f[x-1] 1： #in...

题目链接：https://ac.nowcoder.com/discuss/437998题目大意：思路：我们按价值排序，枚举中位数，那么中位数左右选择大小最小的m/2（m/2-1）个数。如果和<=s那么可以满足条件。现在就是预处理s1[i]:1-i选择m个物品，价值最小的和。s[i]:n-i选择m个物品，价值最小的和。我们用优先队列来维护m个最小的和。预处理后就枚举。 m是奇数：那么枚举的数就是中位数。m是偶数：我们希望右边的最小值越小越好。并且s2[i]:从1-n一定是单调递增。那么我们二分下。右边选取的位置就可以了。 #include <bits/stdc++.h> #de...

题目链接：https://ac.nowcoder.com/acm/contest/5944/I题目大意：n节点的一棵树。燃完一条边长度为L的边需要2*L的时间。现在m个点同时点火。问树什么时候彻底燃完。思路：多源最短路，建立超级源点。连接这m个点。跑最短路。枚举每条边。染完的最短时间。取得max。 一条u-v-w边：dis[u]+a=b+dis[v]并且a+b=w。 #include<bits/stdc++.h> #define LL long long using namespace std; const LL maxn=500005; const LL mod=1e9+7; L...