题意： 一次走两步 问最少添加几条边 可以完整的遍历整张图 思路： 考虑环的奇偶性。 如果有奇环，那么从奇环的任意点出发，一定能够走完这个环。 所以如果存在某个连通块是奇环，那么就只需要把剩下的连通块都连接到该连通块上即可，所需要的添加边数就是连通块数-1； 如果不存在奇环的话，先要将某个连通块变成奇环，增加一条边即可，然后再按照上述思路，所需要添加的边数就是连通块数-1+1，即连通块数。 当存在某个连通块是奇环时，我们来考虑剩下的连通块。其中如果有连通块是奇环的话，可以不予考虑，因为一定可以走完。只考虑连通块是偶环（不知道有没有这个词emm）的个数cnt。无论cnt是奇数还是偶数，偶数相加一...

兔时间限制: 1 Sec 内存限制: 128 MB[提交] [状态]题目描述小粉兔用集训队的奖金买下了一片地。 这片地上有 n 个房子，有些房子之间有道路，有些房子之间则是杂草。 她可以花费一定的代价拆毁一条道路，或是啃光一片草使得两个房子间可以通行（大雾）。 她喜欢生成树，所以她要让所有道路形成一棵生成树。 求最小花费。输入第一行一个数，n。 接下来 n 行，每行 n 个数，代表 ai,j。如果为正数，说明它们之间没有道路，需要 ai,j的花费来修建；如果为负数，说明它们之间有道路，需要 −ai,j的花费来拆毁。输出一行一个数，代表最小花费。样例输入 Copy30 1 -31 0 5-3 5...

Codeforces Round #544 (Div. 3) A. Middle of the Contest  题意：给两个时刻，求中间时刻。 思路：计算出总的分钟数/2即可，注意输出格式！ 代码： #include<bits/stdc++.h> using namespace std; int main(){ int a,b,c,d; scanf("%d:%d",&a,&b); scanf("%d:%d",&c,&d); int t1=a*60+b,t2=c*60+d; int sum=(t1+t2)/2; printf("%02d:%02d\n...

牛客算法竞赛入门课第二节习题 Part1必知：sort用法https://www.cnblogs.com/program-ai-cv-ml-se-fighting/p/11924550.html##update：吐泡泡思路：用栈模拟一下就好，但是要注意当两个小泡泡合成大泡泡时是否会有两个大泡泡消除。另外本题是多组输入。代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43860424&returnHomeType=1&uid=115850812 1.Laptop 思路：（sort排序+枚举） ...

前言： 还差B,J补完再写。 比赛感受：​ 还是很喜欢这套题的，可惜比赛时停电做了4题就溜了hhh​ 因为太菜了这篇只是写的简单题 第一次打rating赛，紫名快乐hhh A： AOE还是单体？ （贪心） 思路： 对于血量大于x的用AOE，反之用单体。 所以可以按照血量从小到大排序，用AOE击败n-x个人，剩x个人用单体击败。 这也就是兰子姐姐题解里的临界值hh 代码： #include<bits/stdc++.h> typedef long long ll; using namespace std; const int maxn=1e6+7; ll a[maxn],n,x; in...

原题链接 因为太菜了只能写写水题 A. Sum of Round Numbers 题意： 把每位的数都分出来，比如9876就分成9000，800，70，6 思路： 不要求顺序的，所以可以直接用vector存一下非零位，输出即可。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; deque<ll>q; int main(){ vector<int>v; int t;cin>>t; while(t--){ v.clear(); ll res=1; ll n;...

丝毫没有感觉到用到数据结构，可能是太水了 Hotelier  题意：酒店里有10个房间和两个门（左边和右边），进门后先安排最近的房间，客人可以随时离开房间。给定一个长度为n的字符串，L表示客人从左边的门进入，R表示客人从右边的门进入，0~9表示该房间的客人离开房间。求最后房间的状态。 思路：直接模拟即可。对于每一个L或R，分别从开始或结尾遍历到第一个为没有人的房间；对于数字，直接让该a[i]=0即可。 代码： #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; int a[maxn],n; int m...

原题链接 给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。 输入格式 第一行包含整数n。 第二行包含n个数字，其中第 i 个数字表示第 i 堆石子的数量。 输出格式 如果先手方必胜，则输出“Yes”。 否则，输出“No”。 数据范围 1≤n≤105, 1≤每堆石子数≤109 输入样例： 2 2 3 输出样例： Yes 先上一波代码 #include<bits/stdc++.h> using namespace std; int main(){ int n;...

二分是一个很高贵的方法。（语出实验室某大佬） 我觉得也是，二分是一种巧妙地暴力。 二分 二分法在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个部分中并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间，因此效率很高。 若求解的问题的定义域为整数域，对于长度为N的求解区间，算法需要logn次来确定出分界点。 对于定义域在实数域上的问题，可以类似于上面的方法，判断R-L的精度是否达到要求，即R-L>=eps。 如果我们指定二分的次数t，那么对于初始的求解区间长度L，算法结束后的r-l值会为L/2^t。 二分算法的复杂度O(二分次数*单次判定复杂度)。 （以...

Go Home 题目描述 There is a kangaroo at coordinate 0 on an infinite number line that runs from left to right, at time 0. During the period between time i−1 and time i, the kangaroo can either stay at his position, or perform a jump of length exactly i to the left or to the right. That is, if his coordin...

一.原理： 1.结构： 完全二叉树（不懂的点这个呀：传送门） 2.可以维护的内容： sum,max,min等 struct node{ int l,r;//左右端点 int sum,maxx,minn;//要维护的值 }  3.示意图（直接盗用学长课件里的图啦） 线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。（来自课件） （其实这个的原理跟模拟堆差不多，那篇博客被我鸽了 ）  4.说明： 区间[l,r]一般分为[l,mid],[mid+1,r]; mid=floor...

一.最简单的最长上升子序列 AcWing 895. 最长上升子序列 这是一道典型的dp例题， dp的两个重要元素：状态表示和状态计算。其中维度的选择是很关键的，要求既能够表示出转移过程中的状态，而且能够计算出结果，在此基础上，要求维度尽可能小。 我们这里可以用dp[i]来表示以第i个数结尾的数值上升的子序列的集合，属性是max；那么对于状态转移的话，我们可以这样考虑：每一个上升子序列以倒数第二个数选什么来分类。可以有以下情况，dp[i-1]=0（即当前是第一个数），a[k] (k=0,1,……i-1); 要注意这里面并不是每一个状态都存在，我们只需要把存在的状态进行转移就可。 状态转移方程还是...

今天上午的训练赛涉及到的，顺便补一下叭。   一.定义   相信大家都听说过著名的七桥问题，而欧拉回路就是伟大的数学家欧拉为了解决七桥问题提出的。 首先介绍一下基本概念：在一个图中，经过每条边一次并且只经过一次的回路被称为欧拉回路，路径被称为欧拉路径。根据名字就可以知道，回路是起点终点相同的，而路径是起点终点不同的。 其实欧拉路径就是小时候玩的一笔画游戏（真是万物皆可图论）   二：性质和定理   特性：起点和终点的度都是奇数，中间点的度数必是偶数   结论：   1.在无向图中，所有边都连通：   （1）存在欧拉路径的充要条件：所有点度数为奇数的点只能有0或2个   （2）存在欧拉回路（起点...

换位置游戏 万物皆可图论 可以先跳过题面~ 题目描述 N 个小朋友（编号为 1 到 N）正在玩一个换位置游戏。从左到右依次排列着 N 个凳子 （编号为 1 到 N，最左边的为 1 号凳子，最右边的为 N 号凳子），每个凳子上都有一个数字 （凳脚处红色数字），每个数字互不相同，且都是不超过 N 的正整数。 游戏开始前，1 号小朋友坐在 1 号凳子上，2 号小朋友坐在 2 号凳子上，然后依次下去， N 号小朋友坐在 N 号凳子上。比如当 N=4 时，游戏开始前小朋友们坐凳子的状态如下图 1 所示：  图 1 游戏开始前 4 位小朋友坐凳子的状态 坐定后，游戏开始。每位小朋友看一下自己坐的凳子凳脚处...