- 博客(109)
- 收藏
- 关注
原创 Catch That Cow POJ - 3278(一维bfs)
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,0...
2019-10-09 23:18:08 137
原创 Dungeon Master POJ - 2251(bfs搜索)
You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south...
2019-10-08 23:40:18 123
原创 TOYS POJ - 2318(计算几何向量叉乘)
POJ—2318Calculate the number of toys that land in each bin of a partitioned toy box.Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They...
2019-08-25 18:07:48 176
原创 2019暑期ACM集训总结
为期一个月的ACM暑假集训过去了,想一想,真是光阴似箭,但与以往的不同,没有哀伤,而是满满的充实,这一个月过着996的生活,和一群志同道合的朋友在一起学习尽管每天都很自闭但也是一件快乐而又享受的事。跟着杭电的暑假集训,发现了自己与那些牛人的差距。虽然我们可能不是天生神力,但是我们在努力,我们在努力追赶。有时候自己可能也会因为好几天的自闭想到过放弃,这条路太难了。但是自己足够努力了吗?就怕比你优秀的...
2019-08-25 09:25:42 189
原创 Wormholes POJ - 3259(最短路,求是否存在负环)
POJ—3259While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a ti...
2019-08-19 17:13:52 109
原创 Silver Cow Party POJ - 3268(找各个点到源点来回路程最短中的最大值)
POJ—3268One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1…N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (on...
2019-08-19 15:31:55 98
原创 最短路知识点总结(Dijkstra,Floyd,SPFA,Bellman-Ford)
Dijkstra算法:解决的问题:带权重的有向图上单源最短路径问题。且权重都为非负值。如果采用的实现方法合适,Dijkstra运行时间要低于Bellman-Ford算法。思路:如果存在一条从i到j的最短路径(Vi…Vk,Vj),Vk是Vj前面的一顶点。那么(Vi…Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于...
2019-08-19 14:03:17 173
原创 Frogger POJ - 2253(最短路,青蛙找对象,求所有路径中每条路径中的最大距离的最小值)
POJ—2253Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tour...
2019-08-19 10:21:51 167 1
原创 B. 掷骰子(概率dp,求逆元)
思路:求出n个骰子掷出点数之和为a的情况次数,对6^n求逆元再乘和为a的情况数,中间要注意取模,直接上代码,容易理解,最重要的一步就是dp就该情况出现的次数。#include<set>#include<map>#include<stack>#include<cmath>#include<queue>#include<...
2019-08-19 09:37:02 161
原创 I. Steve的难题(逆元取模)
#include<set>#include<map>#include<stack>#include<cmath>#include<queue>#include<vector>#include<cstdio>#include<cstring>#include<iostream>...
2019-08-19 09:29:51 79
原创 F - Crazy Calendar(网格中移石子,奇数nim)
题意:r*c方格中,每个格子有一定石子,每次移动每格任意数量石子,只能向下或者向右动一格,不能移动为败思路:显然是Nim,到右下曼哈顿距离为偶数的不用管,因为先手动一下后手动一下最后移到右下后还是先手的回合;奇数移动一格必到偶数格,所以奇数的Nim一下。很简单的入门题。#include<set>#include<map>#include<stack>...
2019-08-19 08:08:37 78
原创 F. Alex的午饭(巧妙计数,找出出现次数超过一半的那个数字)
中文题目题意就不多说了,这里面要注意,数的范围太大,不能用数组来计数,下面是一种比较巧妙的方式,刚开始我确实没想到,以前写过类似的忘了这种方法,详情看代码:#include<set>#include<map>#include<stack>#include<cmath>#include<queue>#include<ve...
2019-08-19 07:55:02 110
原创 J - Paint Chain HDU—3980(有环问题博弈,特判sg函数打表子状态)
题意:有n个珠子,每次必须涂色m个连续的。这 n个珠子是个环。询问胜负情况思路:对于是个环的情况,我们可以首先拿出一组m,如果n<m,先手必输。否则的话跑sg函数,注意此时sg函数跑的是后手的sg情况。这样环就转变为了链结构,对于一条链,sg[ i<m]=0, sg[m]=1, 每一个sg情况等于子问题的异或。因此转变为了 对于i>m的情况下, 如果从中拿出m个连...
2019-08-16 20:42:03 178
原创 G - Partitioning Game(石子不平均分堆,谁不能分谁输(sg函数打表子状态处理再异或))
题目意思:给你n堆石子,每堆有ai个石子,每次操作可以将一堆分成数量不相同的两堆(石子数量不能为0),谁没法分就输了,问你谁能赢。解题思路:用sg打表来做,假设有一堆石子数量为x的石子堆,那么他的后继状态就有(1, x - 1)、(2, x - 2)…等等(不能让两个数相等)想要计算出x的sg值就需要其后继状态的sg值,那么(1,x - 1)的sg值怎么求呢?毕竟他是一个二元组,不是简...
2019-08-16 17:04:54 200
原创 B - Incredible Chess(简单博弈升级版,运用nim)
题意:给两种黑白棋子,每一列均只有两种棋子各一枚,且棋子只能上下移动,谁最后无路可走谁输。思路:同上一题一样需要计算每一列中黑白棋子之间相差的格子数,因为本题可以两个方向移动,所以不能单纯将格子加起来去模2,需要用到尼姆博弈的思想将每列格子数异或起来,如果是0先手必败(白子先行)否则先手胜。#include <iostream>#include <algorithm&g...
2019-08-16 15:47:35 105
原创 C - Left Right(灰右白左简单博弈)
题意:给出黑白两种棋子,以及位置,灰色棋子只能往右走白色棋子只能往左走,谁最后无路可走谁输。思路:理解题意,将每一对黑白棋子之间的空格数求出来求和,然后对2取模,余数为0先手必败,否则先手胜。具体看代码#include <iostream>#include <algorithm>#include <cmath>#include <ctype....
2019-08-16 15:32:28 285
原创 H - Being a Good Boy in Spring Festival(先手胜第一步的方案数)
题目中文的很好理解,主要是明白怎么找到那个方案数,直接上代码看得明白。#include <iostream>#include <algorithm>#include <cmath>#include <ctype.h>#include <cstring>#include <cstdio>#include <...
2019-08-16 15:23:46 109
原创 E - Misere Nim(反nim博弈,最后一手拿石子的输)
思路:一般的nim博弈大家都会吧,一般的就是取最后一枚石子的人赢;先讨论 n 堆石子全部为1的情况:当 n 为奇数时,先手一定输,后手一定赢当 n 为偶数时,先手一定赢,后手一定输;当 n堆 不全部为1的情况:我们先看一般的nim博弈的必胜态:当前状态为必胜态,先手经最优策略 取过后,就到达必败态也就是平衡态,平衡态只能转移到不平衡态(必胜态),不平衡态经过 某一个途径 可以 转移...
2019-08-16 14:37:42 583
原创 D - Matrix Game(尼姆博弈模板题,最后不能拿石头的玩家输)
思路:把每一行的石子数加在一块,在进行异或操作,异或值为0先手必败。(尼莫博弈模板题)#include <iostream>#include <algorithm>#include <cmath>#include <ctype.h>#include <cstring>#include <cstdio>#inc...
2019-08-16 14:24:56 171
原创 K - 取石子游戏(斐波那契博弈模板题)
斐波那契博弈模板题,常规做法见代码:#include <iostream>#include <algorithm>#include <cmath>#include <ctype.h>#include <cstring>#include <cstdio>#include <sstream>#incl...
2019-08-16 14:19:28 106
原创 博弈论基本类别
.巴什博弈1、问题模型:有一个堆物品,物品数量为n个,两个人轮流从这堆物品中取物品,规定每次至少取一个,最多取m个,最后取光者得胜。2、解决思路:当n=m+1时,由于一次最多只能取m个,所以无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜,所以当一方面对的局势是n%(m+1)=0时,其面临的是必败的局势。所以当n=(m+1)*r+s,(r为任意自然数,s≤m)时,如果先取者要拿走...
2019-08-16 14:16:03 121
原创 Beating the Dataset LightOJ - 1274(概率,蒙答案求蒙错误的期望)
LOJ—1274You are in a contest, and unfortunately you don’t have much time. You have one problem in hand; you just glanced at the sample output and found that it just wants ‘YES’ or ‘NO’. So, you have ...
2019-08-16 10:00:53 227
原创 Dice (III) LightOJ - 1248(概率期望+几何分布(n面骰子,问看到所有的面一次的至少所需掷骰子次数的期望)
LOJ—1248题意:一个均匀的骰子有n个面 投色子, 要求最后要把骰子的每一面都看到了, 求扔骰子次数的期望。分析:1.几何分布上面我们定义只要E(x)=1/P,P表示第k次成功的概率扔出第一面成功的概率为P=1,E=1,因为第一面肯定没见过。扔出第二面成功的概率为P=(n-1)/n,E=n/(n-1)(因为实验独立,所以有n-1个可以当作第二面)扔出第i面成功的概率为P=...
2019-08-15 20:41:54 1226
原创 G - Kejin Player HDU—6656(概率DP&&逆元(区间升级期望))
HDU—6656Cuber QQ always envies those Kejin players, who pay a lot of RMB to get a higher level in the game. So he worked so hard that you are now the game designer of this game. He decided to annoy t...
2019-08-15 18:39:52 143
原创 E - Birthday Paradox LOJ—1104(生日悖论求两个人同一天生日的概率)
题意:已知星球上有多少天,问至少邀请多少人参加生日party能使party上至少两个人同一天生日的概率至少为0.5。算法:就是概率公式。参看wiki:生日悖论计算机率的方法是,首先找出p(n)表示n个人中,每个人的生日日期都不同的概率。假如n > 365,根据鸽巢原理其概率为0,假设n ≤ 365,则概率为:因为第二个人不能跟第一个人有相同的生日(概率是364/365),第三个...
2019-08-15 14:35:10 699
原创 C - Race to 1 Again LOJ—1038(概率DP//给定n/=d(d为n的因子)求n==1的期望次数)
【题意】给出一个数大于1的N,每次除以任意的一个他的因子,直到变为1,问从N除到1的次数的期望。【思路】递推,设该数为D,有N个因子,分别是1,n1,n2,n3…nn-2,D,那么选到每个因子的概率都是1/N,除非选到D,不然选到其他因子的话都要多1步,然后再计算D除以该因子的期望这就能得到公式了,设dp[D]为数D按规则变成1的期望步数那么dp[D] = 1/N * (dp[D/1...
2019-08-15 10:14:39 131
原创 cf思维题(给出4*n条边判断能不能构成n个等面积矩形)
Equal RectanglesYou are given 4n4n sticks, the length of the ii-th stick is aiai.You have to create nn rectangles, each rectangle will consist of exactly 44 sticks from the given set. The rectangle ...
2019-08-15 09:15:09 152
原创 cf思维题(判断能不能顺时针或者逆时针构成环)
Circle of StudentsThere are nn students standing in a circle in some order. The index of the ii-th student is pipi. It is guaranteed that all indices of students are distinct integers from 11 to nn (...
2019-08-15 09:11:44 122
原创 B - Discovering Gold LOJ—1030(概率DP掷筛子求期望)
题意:有n个格子,编号分别是1—N,每个格子下面有黄金,每到一个格子就掷骰子,掷到的点数就是你下一次跳跃的距离,骰子的有6面,点数分别为1~6,每次掷的点数是等概率的,如果你掷色子使你跳到第N格外面,则重新掷骰子。问到达n点的所获得黄金的期望是多少?思路:概率DP:一般求概率是正推,求期望是逆推。设dp[i]表示当前位置在i处到达N处得到的金币期望,dp[i]=SUM(dp[i+1]...
2019-08-14 10:17:04 292
原创 A Bug's Life POJ - 2492(权值并查集)
POJ—2492题意虫子有两种性别,有n只虫子,编号1~n,输入m组数据,每组数据包含a、b两只虫子,表示a、b为不同性别的虫子,根据输入的m组数据是否出现前后矛盾(如a、b在前面判断为同性,而后又得出a、b为异性)进行相应的输出。思路使用并查集求解,但该题比普通并查集题目复杂了一些,该题需要使用树中结点的权值来记录信息,在代码中使用数组r[]来记录某结点和其父结点之间的性别是否相同,...
2019-08-13 18:59:24 120
原创 小希的迷宫 HDU - 1272(并查集无向图判断是不是树)
HDU—1272思路:1.每输入一组数据,都要对其进行连接(Merge),如果两个点getf(a)==getf(b),那么说明他们已经是一个集合的了,如果再连接a,b两个点,就会构成回路,这里也就是要输出no.void Merge(int a,int b){ int A,B; A=getf(a); B=getf(b); if(A!=B) { ...
2019-08-13 17:21:08 111
原创 Parity game POJ - 1733(并查集奇偶问题求第几句话错误)
POJ—1733题意:给一个序列这个序列都是由0和1组成,现在随意拿出来一个序列,然后说出他的和是奇数还是偶数,因为有可能存在假话,让你判断前多少条没有假话,也就是查找第一个假话的位置-1思路:带权并查集,权值为 本节点到父亲节点的1的个数的奇偶性,偶数为0,奇数为1,由于n很大,我们开不了这么大的数组,但是m只有5000,所以我们考虑压缩一下#include<iostream&g...
2019-08-13 16:47:30 114
原创 Supermarket POJ - 1456(贪心+并查集求最大价值)
POJ—1456这里其实用贪心做,并查集只是用来作为工具,使得速度更加快。题意:是买卖N件东西,每件东西都有个截止时间,在截止时间之前买都可以,而每个单位时间只能买一件。问最大获利。思路:如果购买不冲突,那么全部买下来就可以了。存在冲突,就需要取舍。显然在冲突的时候我们选择价格高的更优,如此就可以用贪心的算法。先将物品按照价格从高到底的顺序排列,购买一个就在时间点上做一个标记,只要不冲突就...
2019-08-13 14:59:20 116
原创 True Liars POJ - 1417(并查集+DP)
POJ—1417题意: 给你p1个好人和p2个坏人,编号为1-p1+p2,然后给你n种操作x1 x2 no:x1说x2不是好人x1 x2 yes:x1说x2是好人在这里好人说的总是对的,坏人说的总是坏的,然后问你最后能不能唯一确定哪些是好人,并输出,否则输出”no“思路:首先,我们假设x1是好人,并且有 x1 x2 yes 那么,x2一定也是好人,如果有x1 ...
2019-08-13 11:52:07 186
原创 How Many Answers Are Wrong HDU - 3038(带权值并查集找假话数量)
HDU—3038题意:给你一个n和一个m,n代表n个数,m代表m次询问,每次询问给你一个a,b,s,代表第a个数到第b个数的和是s,让你输出m次询问中有几个错误答案。思路:利用带权并查集的方法。带权并查集就是在并查集的基础上加了个权值,用来维护元素之间的关系。那么,问题来了,他们之间的权值要怎么计算呢?1.首先,在找祖先的时候,也要把他们的权值进行改变,即v[x] += v[fa[x]...
2019-08-13 11:18:22 78
原创 Wireless Network POJ - 2236(并查集(维修更新合并))
POJ—2236题意:有 n 台损坏的电脑,要将他们逐台恢复。若两台电脑能相互通信,有两种情况,一是他们间的距离小于 d,二是他们都能到达第三台已修复的电脑,现在给出全部的电脑位置,对所有电脑进行上述的操作,O x 代表修复第 x 台,S x y 代表判断 x y 能否通信,若能输出 SUCCESS,否则输出 FALL思路:简单的并查集用并查集来保存电脑之间的连通情况,每次修好电脑后,...
2019-08-13 10:11:53 73
原创 F - Censor SCU - 4438(Hash字符串+前缀和)
SCU—4438题意:一个敏感词w和一个文本p,在文本中不断地删除敏感词w,求最后的剩下的文本p。思路:求出敏感词的hash值,定p的每一个字符都是以第一个字符开始的一个句子,求出它们的hash值入栈,当某一段的hash值等于敏感词的hash值时,将这段字符出栈。#include<bits/stdc++.h>#define ull unsigned long longus...
2019-08-13 09:39:21 1688
原创 G - 前m大的数 HDU - 1280(整数hash求前m大个数)
HDU—1280题目大意:有N个数,让他们两两求和,得到 (n)*(n-1)/2 个数,让你输出前m大个数(从大到小)思路:将各种组合可能得到的和作为下标,然后因为不同组合得到的和可能是一样的,所以再用一个数组cnt[]数组,就可以将相同的和都记录下来#include <iostream>#include <cstdio>#include <cmath&...
2019-08-13 09:28:29 104
原创 Equations—HDU_1496(巧用Hash)
HDU—1496题意:求有多少种解!#include <iostream>#include <fstream>#include <algorithm>#include <string>#include <set>#include <map>#include <queue>#include <...
2019-08-12 17:17:26 84
原创 Power Strings POJ - 2406(字符串hash求最小循环节)
POJ - 2406题目大意:给出一个字符串 问它最多由多少相同的字串组成 。如 abababab由4个ab组成。#include <bits/stdc++.h>using namespace std;#define ull unsigned long longconst int maxn=1000005;ull base =131;char s[1000005];...
2019-08-12 15:57:07 391
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人