3 hahahahhahello

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

判断合法出栈序列

PIPI现有a-z 26个小球模拟出入栈操作,小球按照a~z的顺序压入栈,在栈顶的元素可以随时被取出,在游戏开始前给出任意26个字母的一些排列,问是否能够由出栈顺序得到这个排列。输入输入包含多组测试用例。每组测试用例包含26个字母组成的一个序列。输出若出栈顺序合法,输出"yes",否则输出"no".样例输入abcdefghijklmnopqrstuvwxyzza...

2019-06-25 19:44:32

FZU - 2203 单纵大法好(贪心+二分)

两年前的坑现在补上,经典的贪心+二分#include <stdio.h>#include <string.h>const int maxn = 200005;int N,K,A,M;int pos[maxn];bool vis[maxn];bool judge(int m){ int i,cnt,len; memset( vis,fals...

2019-05-23 21:17:05

HDU - 3345 War Chess(优先队列+BFS)

两年前的坑现在补上,广搜,把点加入优先队列里#include <stdio.h>#include <string.h>#include <queue>using namespace std;int n,m,total;char mp[108][108],ans[108][108];int vis[108][108];int to[4][2] ...

2019-05-23 21:15:22

POJ - 1330 Nearest Common Ancestors(倍增LCA)

裸的求LCA,用的倍增,就是为了记个模板,似懂非懂,以后有时间就弄懂这些算法(大概率不会了。。。。。。)#include <queue>#include <stdio.h>#include <string.h>using namespace std;const int MAXN = 10010;const int DEG = 20;stru...

2019-05-23 08:24:32

POJ - 3171 Cleaning Shifts(DP+线段树优化)

题意:头牛,每头牛在到时间段干活并需要数量的钱,想要在到时间段的每一时刻都有牛在干活,最少需要多少钱?思路:首先把不在到时间段干活的牛给去除,在把剩下的牛按照从小到大排序,表示从到都有牛干活的最下花费,挨个遍历每个时间段,有: 其中找最小值部分可以用线段树来优化#include &lt...

2019-05-21 19:44:25

POJ - 3734 Blocks(矩阵快速幂)

题意:个球,有红黄蓝绿4种颜色,要求红球和绿球有偶数个,有多少种排列方式?思路::红球与绿球都为偶数的个数:红球与绿球恰有一个为偶数的个数:红球与绿球都为奇数的个数#include <stdio.h>#include <vector>using namespace std;const int mod = 10007;typedef ...

2019-05-20 09:41:19

POJ - 3254 Corn Fields (状压DP)

题意:个格子,有些可以放牛,有些不可以放牛,放的牛不能相邻,问共有多少种放牛的方案?思路:状压,表示第行状态为前行的方案数目,外层循环一行一行的枚举,内层嵌套枚举第行的状态和第行的状态,最后答案为#include <stdio.h>#include <string.h>const int mod = 100000000;int dp[15][1 <&l...

2019-05-19 19:18:02

POJ - 2441 Arrange the Bulls (状压DP)

题意:头牛,个牛棚,每个牛棚只能有一头牛,每头牛都只能在自己喜欢的牛棚里,给每头牛安排位置,总共有多少种安排方案?思路:每个牛棚可以放牛也可以不放牛,个牛棚,故可以用状压,表示状态下,给前i头牛分配牛棚的方案数 ( & ,)当前状态只与上一状态有关,可以用滚动数组来节省空间#include <stdio.h>#include <string....

2019-05-19 18:23:31

POJ - 3411 Paid Roads(Dijkstra+状压)

题意:个城市,条单向路,每一条路从到,如果之前已经经过了城市,花费可以为也可以为,没有经过城市,花费为,求从城市到的最小花费思路:求最短路,多加一维表示已经走过的点的集合。#include <stdio.h>#include <string.h>#include <queue>#include <algorithm>const in...

2019-05-19 17:23:09

POJ - 1795 DNA Laboratory(状压DP)

题意:个只包含字母的字符串,求出包含这n个字符串的最短字符串思路:1.首先除去相同的和被包含在其它字符串里的字符串2.求出,把第i个字符串放到第j个字符串前花费3.状压,,第个字符串在最前面,状态为情况下的最小花费边界:递推方程:这样就求出了最短长度下的第一个字符串s4.从开始贪心的求出最优解#include <stdio.h>#include ...

2019-05-19 17:12:30

POJ - 2836 Rectangular Covering(状压DP+几何)

题意:平面上有n个点,要求用矩形去覆盖所有的点,每一个矩形至少覆盖两个点,每一个点可以被重复覆盖,求最小的能覆盖所有点的矩形的面积。思路:枚举两个点,一个矩形覆盖这两个点的最小面积是以这两个点为对角线,所以我们可以得到个矩形,求出这些矩形的面积和覆盖的点,接下来就是状压了: ...

2019-05-19 16:53:16

POJ - 2886 Who Gets the Most Candies? (线段树+反素数)

题意:有个小盆友围成一圈,从第个小朋友开始,选中谁谁退圈,每个小朋友都有一个数,这个数为正数表明下一个选中的小朋友即为这个小朋友左边第个小朋友,为负数表明下一个选中的小朋友为这个小朋友右边第个小朋友。每个小朋友退圈即可获得的因子数的糖果数,为这个小朋友是第几个退圈的,输出这个获得最多的糖果的小朋友的名字和她获得的糖果数。思路:个小朋友,获得最多的糖果的那个人的编号为中有最多因子数的那个数,所以...

2019-05-18 09:41:58

POJ-2991 Crane(线段树)

题意:给出n条线段,开始时n条线段一词首尾相连,与地面垂直,c次操作,每次操作给出,,让线段和之间德角度变为度,并输出第n条线段的前端坐标。思路:线段树,区间存储的线段的向量坐标,父亲节点的向量坐标就等于儿子节点的向量坐标相加,在存储一个角度变量,类似于懒惰标记的作用,将一条线段逆时针旋转v度后的坐标为顺时针:#include <math.h>#incl...

2019-05-16 21:40:47

POJ - 3279 Fliptile(反转)

题意:一个01矩阵,每翻转一个格子,这个格子的上下左右的格子都会被翻转,要把整个矩阵的格子都翻转为0,求需要翻转的最小次数,最小次数的解为多个时,输出字典序最小的一组。解不存在输出IMPOSSIBLE。思路:如果暴力搜索的话有种翻转的方法,超时。如果第一行是否翻转已经确定,那么第二行是否翻转也确定了,同理除了最后一行其余所有的格子是否翻转都已确定了,如果最后一行有1的话就说明不存在可行解。所以...

2019-05-15 14:40:24

POJ - 3320 Jessica's Reading Problem(尺取法)

题意:求最少的连续读的页数能读到所有的知识点思路:尺取法,把所有的知识点的编号放到set里求出知识点的个数,在尺取过程中用map记录当前以学知识点的个数。#include <map>#include <set>#include <stdio.h>#include <algorithm>#define maxn 1000005usi...

2019-05-15 14:20:28

组合数学基础

n元素集合的循环r排列的数目是: 特别的,n个元素的循环排列的数目是帕斯卡公式: 多重集合的排...

2019-05-14 08:17:17

数论基础

欧几里德算法即求两个数的最大公因子int GCD(int a,int b){ if(b == 0) return a; else return GCD(b,a % b);}扩展欧几里德算法它可以用来求解(a,b,c为整数)的方程的一组整数解,事实上,只有时,此方程才有整数解。具体实现ll exgcd(ll a,ll b,ll& x,ll&am...

2019-05-13 21:57:02

UVA - 11582 Colossal Fibonacci Numbers!(取模)

题意:输入两个非负整数a,b(0 <= a,b < 2^64)和 n(1<= n < 1000),输出f(a^b) % n,f为斐波那契数列。思路:所有计算都是对n取模的,不妨设F(i) = f(i) % n,当f(i - 1),f(i)出现重复时,整个序列就开始重复。余数最多有n种,所以最多n*n项就会出现重复,所以先计算出周期,再用快速幂求出a^b%M即可。#...

2019-05-11 21:06:35

POJ - 1061 青蛙的约会 (扩展欧几里得找最小正整数解)

题意:两只青蛙在圆圈上追赶,圆圈我们可以看作是一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。总长L米。现在要你求出它们跳了几次以后才会碰面。思路:设跳了t次以后才会碰面,则有(x + tm) % L = (y + tn) % L,即 (x + tm) - (y + tn) = PL,整理得:(n -...

2019-05-10 09:29:46

POJ - 3292 Semi-prime H-numbers (埃氏筛思想)

题意:H数为4n + 1这样的数,H数的乘法是封闭的,H素数只能表示为1和它本身的乘积,除了H素数,其余的都是H合数,半素数是恰好能表示为两个H素数的乘积,给出一个数X,输出这个数以及小于等于这个数的半素数的个数思路:埃氏筛思想#include <stdio.h>const int maxn = 1000005;int a[maxn],cnt[maxn];void in...

2019-05-09 21:46:40

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。