Yuki_fx

未归档

/ 注册

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

CodeForces 356A - Knight Tournament

题目背景和大致意思是，王国要举行骑士比赛。骑士编号从1—N；开始给定骑士的数目和比赛的场数。接着每一行给定一个区间L和R，和一个骑士编号X，区间L—R里面的人都被X击败。骑士被击败以后就出局，不在继续参加。最后输出每个人是谁击败的他，如果没人击败他，那么他肯定赢到最后，是冠军，输出0...

2017-08-10

0 429

POJ 1325 Machine Schedule(二分图匹配)

题目大意：有两个机器A和B，A机器有n个模式，B机器有m个模式,两个机器最初在0模式然后有k个作业，每个作业有三个参数i，a，b i代表作业编号，a和b代表第i作业要么在A机器的a模式下完成【或者】在B机器的b模式下完成问两个机器总共最少变换多少次可以完成所有作业解题思路：很水的一个二...

图论二分图

2017-08-10

0 380

POJ 1258 Agri-Net

最小树模板题目，没有建图过程。题目给的就是邻接矩阵。题意：农夫要把各个农场的互联网连接起来。每个都有一定的费用。问最小费用。把题目抽象出来就是最小生成树。题目给的是邻接矩阵，发现是关于对角线对称的，无向图。可以用Prim算法。这里我Krustral和Prim算法都用了。 ...

最小生成树图论

2017-08-10

0 501

HDU3718ZOJ3425 Similarity（The 2010 ACM-ICPC Asia Chengdu Regional Contest，加权二分图的最优匹配）

简单说就是求出两个字符串的相似程度。题目意思说的是学生得到一个任务，把不同物品分类，比如苹果，香蕉属于水果等，为了方便，给每个类别用字母编号。就得到题目中的字符串。每个学生的分类标准不一样，所以有不用的答案。现在问有多少个是正确的。最后结果是正确的答案除以总数。比如第一个样例，ABC 和...

图论二分图

2017-08-09

0 388

[ZOJ]2103 Marco Popo the Traveler（dfs+欧拉路）

题目意思就是马可波罗要去城市旅游，要求走遍所有城市之间的路一次且仅一次。这就是典型的欧拉回路，欧拉通路问题。属于图论中的欧拉图。题目有个附加条件，每两个城市之间最多只有一条高速公路，每条高速公路有颜色，只有汽车轮胎的颜色和路的颜色一样才可以通行。汽车轮胎的颜色可以更改，但只能在城市里面更改。...

图论欧拉图

2017-08-09

0 616

HDU 1848 Fibonacci again and again(博弈 SG运用)

有3堆石头，每堆石头可以操作的方法都一样，且相互之间不会影响。根据SG定理，把他分为3堆独立的石头。求SG函数，最后异或起来 #include<iostream> #include<cstdio> #include<cstring> #include<...

博弈

2017-08-09

0 409

HD1847 Good Luck in CET-4 Everybody!（巴什博弈）

看到这道题目，没有多想，就直接用SG函数，打表以后，如果SG为0，那么就是输态。否则就是赢态；这道题没有仔细分析。看了别人的博客以后，才知道是一个简单的巴什博弈，当时3的倍数的时候，必败。打表出来的结果，发现是循环，循环节是3，以1,2,0循环。根据打表情况画出PN图 1 2 ...

博弈

2017-08-09

0 407

HDU 1564 Play a game(巴什博弈)脑洞

两个人玩游戏，在一个N*N的矩阵里面。一开始给出矩阵的大小。然后两个人轮流玩游戏，问谁可以赢。游戏规则是，玩家从左下角出发。每次走一格。只能在前一个玩家的基础上，走原有格子的上面或者下面。走最后一个格子的人赢（也就是说第一个不能走格子的人输）别人归类为巴什博弈。给出矩阵大小，我们...

博弈

2017-08-09

0 479

HDU1874畅通工程续（Floyd算法）

简单的最短路径，给地图。再给两个点，求这两个点之间的最短路径。直白的做法就是Floyd算法。时间复杂度比较高，但是做这道题目足够了。这道题目有一个坑点，就是两个点之间可能有若干条路径，那么要求最短路径的时候，必然只会选择最短的一天。毕竟其他的效果都是一样。所以在输入的时候就处理下，每次输...

2017-08-09

0 438

POJ 1232 Ubiquitous Religions（基础并查集）

并查集的基础题目，最简单套个模板就可以通过 #include<iostream> #include<cstdio> #include<cstring> #include<functional> #include<algorithm> i...

并查集图论

2017-08-07

0 407