题意  给定一棵n个结点的树，现要你将每个结点u赋上一个权值​，使得若x,y之间有边，则，若x,y之间没有边，则  这里就不用二分图构造的正解了，毕竟在赛场上构造题想不到就是想不到（别骂了，比赛就没想到qwq我来提供一种随机大法的做法（赛后看dalao提交的因为n最大为100，所以很容易随机过 思路：  大致思路是先把所有边全部连起来，然后慢慢删边。 先把所有边全部连起来可以假设二进制的每一位都为1 删边的话只需要把二进制其中的几位修改即可，到底修改哪一位可以使用随机决定（50%的概率选择修改） 最后检验正确性即可 如果t了那就多交几发不就行了（bushi  代码  // Problem: T...

做法：动态规划，组合问题+容斥原理 前置芝士：容斥原理 思路：  1.当k很大，n和m很小时，可以考虑dp求解 2.当k很小，n和m很大时，可以采用组合问题+容斥原理从起点走到终点，只能向上或向右走，一共有多少种走法很容易联想到高中的组合问题，即(不考虑障碍点)又因为存在k个障碍点，应该减去起点到障碍点的走法*障碍点到终点的走法再考虑容斥原理即可  代码  // Problem: 魔改森林 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/problem/200324 // Memory Limit: 524288 MB // T...

题意  给定一个无向图，问最少在几个点上设置出口，可以使得不管哪个点坍塌，其余所有点都可以与某个出口连通。求设置出口的数量及方案数。  做法：Tarjan，割点 前置芝士：割点 思路：  目前可公开情报：1.孤点：数量+1，方案数不变2.连通块无割点：数量+2，方案数3.连通块存在一个割点，数量+1，方案数(在一个强连通分量中只要建立1个)4.连通块存在两个及以上割点，数量不变，方案数不变  ps:这题题目并没有考虑有多个连通图，以及孤点的存在，应加强数据。贴一组数据 1 2 3 6 1 2 1 3 2 4 2 5 3 6 3 8 0 Case 1: 3 1 Case 2: 5 1代码 #in...

做法：随机+贪心 思路：      是个定值,可以先用tmp存下来 只需求即可 我们可以用random_shuffle()用来对原数据进行重新排序，然后利用贪心的思想（每次把数加在最小的组里），即可满足均方差最小。 用while ((double)clock()/CLOCKS_PER_SEC<0.8)来卡时 代码 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0)...

做法：贪心 思路  先判断FFF和GGG谁能赢 再特判下第一轮能不能进行 如果FFF能赢，那么按照贪心的想法，FFF一定要取自己能取最多的数量，GGG一定要取自己能取最少的数量即FFF拿走后剩下不小于n-k的最小的质数，GGG拿1个。如果FFF拿完后剩下1，2，3的数，GGG不能拿，游戏结束。 如果GGG能赢，那么按照贪心的想法，FFF一定要取自己能取最少的数量，GGG一定要取自己能取最多的数量即FFF拿走后剩下小于n的最大的质数，GGG拿走后剩下大于n-k的最小的质数减1。如果FFF不能拿，游戏结束。  代码  // Problem: 质数与合数 // Contest: NowCoder /...

做法： 从后往前遍历字符串 时间复杂度： 代码 class Solution { public: /** * 反转字符串 * @param str string字符串 * @return string字符串 */ string solve(string str) { // write code here string ans=""; int n=str.length(); for(int i=n-1;i>=0;i--){ ans+=str[i]; } return ans; } };

 新的一年也要加油

做法  先确定合并数组后数组的大小从后往前赋值，依次比较A和B数组较大的值赋值过去如果A、B数组中其中一个数组已经全部赋值过去，那么另一个数组剩余值从后往前依次赋值即可  时间复杂度  代码 class Solution { public: void merge(int A[], int m, int B[], int n) { int cnt=n+m-1; n--,m--; for(int i=cnt;i>=0;i--){ if((m>=0&&A[m]>B[n])||n==-1) A[i]=A[m--]; else A[i]=B[n--]; } } };

做法：类最小生成树 思路：  1.先将边从大到小排 2.枚举最大边，然后进行连边 3.每次连边，如果连玩次边后发现s和t联通，那么最小边就是该边，并退出Kruskal 4.依次比较ans与最大边与最小边的比值 5.如果最大边枚举到不存在最小边s和t联通，那么退出枚举最小边  代码 #include <bits/stdc++.h> using namespace std; #define debug(a) cout<<#a<<":"<<a<<"\n" const int N=2e5+10,INF=0x3f3f3f3f; int n,m,...