阿里嘎多懒羊羊桑_

未归档

题解(36)

/ 注册

全部文章 / 未归档（共25篇）

牛客——图的遍历（dfs染色）

题意：一次走两步问最少添加几条边可以完整的遍历整张图思路：考虑环的奇偶性。如果有奇环，那么从奇环的任意点出发，一定能够走完这个环。所以如果存在某个连通块是奇环，那么就只需要把剩下的连通块都连接到该连通块上即可，所需要的添加边数就是连通块数-1；如果不存在奇环的话，先要将某个连通块变成...

2020-05-21

0 1031

UPC——兔（最小生成树）

兔时间限制: 1 Sec 内存限制: 128 MB[提交] [状态]题目描述小粉兔用集训队的奖金买下了一片地。这片地上有 n 个房子，有些房子之间有道路，有些房子之间则是杂草。她可以花费一定的代价拆毁一条道路，或是啃光一片草使得两个房子间可以通行（大雾）。她喜欢生成树，所以她要让所有道路形成...

2020-05-21

0 549

Codeforces Round #640 (Div. 4)

原题链接因为太菜了只能写写水题 A. Sum of Round Numbers 题意：把每位的数都分出来，比如9876就分成9000，800，70，6 思路：不要求顺序的，所以可以直接用vector存一下非零位，输出即可。代码： #include<bits/stdc++.h> u...

2020-05-10

0 498

Nim游戏——简单博弈论

原题链接给定n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。输入格式第一行包含整数n。第二行包含n个数字，其中第 i 个数字表示第 i 堆石子的数量。输出格式...

2020-05-06

0 1120

二分&三分

二分是一个很高贵的方法。（语出实验室某大佬）我觉得也是，二分是一种巧妙地暴力。二分二分法在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个部分中并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间，因此效率很高。若求解的问题的定义域为整数域，对于长度为N...

2020-05-06

0 641

UPC Go Home（贪心 || 前缀和+二分）（STL二分函数的使用）

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...

2020-05-06

0 587

【数据结构】线段树（入门）

一.原理： 1.结构：完全二叉树（不懂的点这个呀：传送门） 2.可以维护的内容： sum,max,min等 struct node{ int l,r;//左右端点 int sum,maxx,minn;//要维护的值 } 3.示意图（直接盗用学长课件里的图啦）线段树的每个节点表示一个区...

2020-05-06

0 640

【动态规划】LIS最长上升子序列【入门】

一.最简单的最长上升子序列 AcWing 895. 最长上升子序列这是一道典型的dp例题， dp的两个重要元素：状态表示和状态计算。其中维度的选择是很关键的，要求既能够表示出转移过程中的状态，而且能够计算出结果，在此基础上，要求维度尽可能小。我们这里可以用dp[i]来表示以第i个数结尾的数值上...

2020-05-06

0 914

铲雪车骑马修栅栏（欧拉路径和欧拉回路）

今天上午的训练赛涉及到的，顺便补一下叭。一.定义相信大家都听说过著名的七桥问题，而欧拉回路就是伟大的数学家欧拉为了解决七桥问题提出的。首先介绍一下基本概念：在一个图中，经过每条边一次并且只经过一次的回路被称为欧拉回路，路径被称为欧拉路径。根据名字就可以知道，回路是起点终点相同的，而...

2020-05-06

0 763

UPC 换位置游戏（BFS || 并查集判环）

换位置游戏万物皆可图论可以先跳过题面~ 题目描述 N 个小朋友（编号为 1 到 N）正在玩一个换位置游戏。从左到右依次排列着 N 个凳子（编号为 1 到 N，最左边的为 1 号凳子，最右边的为 N 号凳子），每个凳子上都有一个数字（凳脚处红色数字），每个数字互不相同，且都是不超过 N 的...

2020-05-06

0 665