题目链接 https://ac.nowcoder.com/acm/contest/9667/H 解题思路 代码1思路：两个优先队列，第一个优先队列是大根堆，存前k-1个数，第二个优先队列是小根堆，存第k个数。若插入的数比小根堆的堆顶小，就将该数插入到大根堆中，若大根堆中的元素个数超过k-1个，就将大根堆堆顶元素插入到小根堆中，同时将其从大根堆中弹出。代码2思路：与代码1类似，只不过将小根堆优化成了一个变量，由代码1思路讲解不难看出，小根堆的优势并没有体现，所以建立小根堆是完全没必要的。但是小根堆却提供了思路 AC代码1 #include<bits/stdc++.h> using n...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1052 解题思路 雨巨讲的思路：区间dp。记田忌为a，齐王为b。将两人的马从大到小排序。dp[i][j]表示a的从i到j匹马，与b的从n-j+i匹马到n匹马比赛的净胜数。judge(i,j)表示的是判断a的第i匹马与b的第j匹马的大小关系。 雨巨视频55min AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1005; int dp[N][N]; int n,a[N],...

小白月赛30链接 https://ac.nowcoder.com/acm/contest/9667 前言 简单的题我就直接写在这里了，稍微有难度的，我会通过链接的形式放在这篇博客里~ A 黑白边 解题思路 并查集 若不会并查集，有篇并查集基础讲解的博客大致思路：两个并查集，第一个并查集用于判断是否可以联通；第二个并查集用于计算最少白边数。判断联通的并查集好写，直接板子就行；但是计算最少白边的并查集怎么写？其实也是板子，只不过需要判断一下，当边为黑的时候进行“连边”，最后求出连通分支数-1就是最少白边数。为什么这样就能求出最少白边数？懂了吧，把黑边连起来会出现若干连通分支，若整个图还能连通就说明...

题目链接 http://poj.org/problem?id=1325 题目大意 k个工作（从0开始编号），a机器n个模式（模式从0开始编号），b机器有m个模式（模式从0开始编号）；每个工作都可以由机器a的一个模式或机器b的一个模式完成且只能由机器a的一个模式或机器b的一个模式完成；按一定顺序安排完成工作的顺序，使得切换机器的次数最少，求最少的切换机器次数；最开始机器a和机器b都处于0模式。 解题思路 建图： 将每个工作需要的两个种机器模式连边，那么每一条边就代表一种工作；左集合是一条边的一个端点，右集合是此边的另一个端点。建好图了就比较好想了，要将所有工作都完成，就意味着要把所有的边全部覆盖...

题目链接 http://poj.org/problem?id=1469 解题思路 二分图匹配提醒一下，cin好像TLE AC代码 #include<iostream> #include<cstring> #include<vector> using namespace std; const int N=400; vector<int> e[N]; int n,m,cnt,u,num,link[N],vis[N],T; bool dfs(int x) { for(int i=0;i<e[x].size();i++) { ...

题目链接 https://ac.nowcoder.com/acm/contest/9715/C 解题思路 找关系：总共m个重音符，除去最左边的重音符还剩m-1个，我们确定最左边重音符的位置，计算此时剩下的m-1个重音符的位置关系有多少种： 假设m-1=1，最左边的重音符偏移了0位，即如下图：此时，m-1个重音符的位置只能如图所示，即1种；最左边的重音符偏移了1位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，即蓝色圆形，即2种；最左边的重音符偏移了2位，即如下图：此时，m-1个重音符可以在标准位置不变也可以向前偏移一个位置，还可以偏移三个位置，即蓝色圆形，即3种； ...

题目链接 https://ac.nowcoder.com/acm/contest/9715/B 解题思路 我裂开我看错数据规模了，以为1e10，所以先统计了一下，昨晚搞了将近一个小时没搞出来，直接心态爆炸，我好fw啊咋办。直接暴力，求出a对应其他每一个字符的差值的绝对值，从小到大排序，选到k次位置，统计最大的选择个数。 AC代码1 //大佬代码 const int N=2000; int ans,d[N]; class Solution { public: /** * * @param k int整型 表示最多的操作次数 * @param s stri...

题目链接 https://vjudge.net/problem/POJ-1274 解题思路 不愧是最FW的OJ，屁OJ，用链式前向星RUNTIME ERROR，用vector过了。匈牙利算法板子题。思想的话，懒得讲了…… AC代码 #include<iostream> #include<cstdio> #include<cstring> #include<vector> #define ll long long using namespace std; const int N=250; int n,m,v,ans,num,link[N]; bo...

题目链接 https://codeforces.com/problemset/problem/887/B 解题思路 居然直接“暴力”？看代码很好懂。 在这我就来分析一下为什么顶多产生两位数：最小三位数为100，要产生别的三位数满足题意，就必须要能产生100，所以我们来证明没法产生100，就证明出了没法产生任意三位数：首先，一个或者两个正方体是没办法产生三位数的，所以不做讨论；当存在三个正方体时，总共2 * 6 = 18个数，要想产生100，至少要满足，存在两个0以构成100，存在两个1以构成11，存在两个2以构成22，……，存在两个9以构成99，算一下发现这总共2 * 10 = 20个数，最多...

题目链接 https://www.luogu.com.cn/problem/P7107 解题思路 https://www.luogu.com.cn/blog/291706/solution-p7107贪心的思路还是比较简单的，但是代码细节的实现还是有点难的。下面的代码会着重强调一些细节说是贪心又像模拟 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; int main() { int n,p; ll m,k; cin>>n>>m>&gt...

题目链接 https://ac.nowcoder.com/acm/contest/9557/C 解题思路 代码1思路：非严格的树上第二长路径，要么等于最长路径，要么等于最长路径-1。当最长路径的个数多于1条的时候，答案就是最长路径，反之为最长路径-1。num[i]表示以i为根的树最长子链的个数，d[i]表示以i为根的树最长子链的长度，sum表示最长路径的个数，mx表示最长路径的长度。代码2思路：保存最长路径长度和次长路径长度，保存最长子链长度和次长子链长度。这种我只能看懂，但是理解不了细节，所以，自己看吧QWQ 两种代码的思想都是先跟新最长路径的信息再更新的最长子链的信息，读者自行理解，比较难...

题目链接 http://codeforces.com/contest/779/problem/E 解题思路 感觉思路比较简单，但是模拟的过程是真的难啊大致思路：输入统计，为数，或者为计算式，若为计算式还需要记录左右操作数为问号还是变量。我们优先遍历每一个二进制位，再看每个变量本位为1的个数，统计问号在本位为0时所有变量中本位为1的个数，统计问号为1时所有变量中本位为1的个数，根据最小值或最大值进行字符串拼接。我觉得还是得看代码 AC代码 #include<bits/stdc++.h> using namespace std; const int N=5e3+10; struct...

题目链接 牛客（无数据规模）：https://ac.nowcoder.com/acm/problem/20302洛谷（有数据规模）：https://www.luogu.com.cn/problem/P4155数据规模： 解题思路 贪心+倍增；好难讲，直接讲代码吧。f数组就是倍增数组，f[i][j]表示编号为i的战士，尽量优地选其身后的1<<j个战士能奔袭的最远，最后那个战士的编号就是f[i][j]。不是很好理解，往后看看应该可以明白f[i][0]的赋值通过贪心，类似于区间覆盖问题，每次选“左端点”小于“编号为i的战士的左端点”的战士，f[i][0]存被选战士的编号。f[i][j]...

完全数 解题思路 签到？正常统计因子和就行，大了就直接跳，时间复杂度为根号级别，莫得问题。 AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; int f; ll n,ans=1; int main() { cin>>n; for(int i=2;i<=sqrt(n);i++)//从2开始 { if(n%i==0) ans+=i+n/i; if(ans>n){f=1;break;}//因子和大于n直接break就...