xlrll的博客

原创 “红旗杯“第十四届东北地区大学生程序设计竞赛 Color the blocks

找规律Color the blocksProblem DescriptionGiven you an N∗N grid graph,you can color any block black or white,but you have to meet the condition:For each block (x,y),it can’t be the same color as (x−3,y),(x−1,y+2),(x+1,y+2),(x+3,y).You need to calculate th

原创 网络流 模板(仅供个人复习用)

#include<bits/stdc++.h>using namespace std;const int MAXN = 300;const long long INF = 1e18;bool vis[MAXN][MAXN];long long flow[MAXN],c[MAXN][MAXN];vector<int> ve[MAXN];int d[MAXN];int n,m,s,t;bool bfs(){ memset(d,0,sizeof(d)); //mem

原创 试题 基础练习 十六进制转八进制

资源限制时间限制：1.0s 内存限制：512.0MB问题描述　　给定n个十六进制正整数，输出它们对应的八进制数。输入格式　　输入的第一行为一个正整数n （1<=n<=10）。　　接下来n行，每行一个由09、大写字母AF组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。输出格式　　输出n行，每行为输入对应的八进制正整数。　　【注意】　　输入的十六进制数不会有前导0，比如012A。　　输出的八进制数也不能有前导0。样例输入　　2　　39

原创 Python中文件的读写

文件的打开、读取、关闭：在Python中打开文件时我们会用到open()函数，使用格式为：open(file,[mode,[buffering.[encoding] ] ]),其中的file参数时必选的其他的都是可选的。其中file是指定文件的路径的。mode 指定文件打开方式，例如：‘r’ ： 只读模式(mode的默认参数)‘t’ ：文本模式(mode的默认参数)‘w’：写入模式，文件不存在会创建新的文件，存的就是覆盖原来的内容。‘x’：创建与写入模式，如果文件已存在，将会报错。‘a’：

原创 Python高阶函数 ：map()，filter()

python中的高阶函数,它可以把一个函数作为参数，而且可以把一个函数作为参数而且可可以把一个函数作为返回值，格式如下。map(func,seq) 其中第一个参数是函数，第二个参数是一个序列，作用是把序列seq中的元素依次传给函数func进行处理，返回一个迭代器。t_list=[1,2,3,4,5]def fc(x): return x**2;mp=map(fc,t_list)for i in mp: print("{} ".format(i)) 输出如下：1491625fi

原创 Python匿名函数:lambda 表达式

匿名函数只是一个lambda表达式，这个表达式的结果就是他的返回值。格式如下：lambda 参数 : 表达式def cl(r) : return r**2print("{}".format(cl(2)))上面代码的输出为4上面函数可以改成如下：t=lambda x: x**2;print("{}".format(t(2)))该函数输出的也是4这个表达式和上面的函数的作用是一样的。...

原创 Python中列表，元组，字典的一些基本用法

一 列表：创建列表：列表变量名 =[元素1，元素2，元素3，…];列表元素的访问：使用索引访问例如：>>> money=[10,11,12,20]>>> money[1]11>>> money[0]10>>> 当然索引也可以是负数，表示的是倒数第几个，例如：>>> money[-1]20>>> money[-3]11>>> 切片：list

原创 Python 处理字符串的一些函数和方法总结

原创 Python中math模块中的常用函数

原创 Python中的数学函数

原创 Python中的进制转换

二进制是以0b或者0B开头八进制是以0o或者0O开头十六进制是以0x或者0X开头把一个数转换成二进制可以用bin()函数>>> bin(10)'0b1010'>>> bin(0x10)'0b10000'>>> 分别是把一个十进制10转换成2进制0b1010，还有把16进制10转换成0b10000把一个数转换成八进制可以用oct()函数>>> oct(10)'0o12'>>> oct(0x

原创 eval()函数与exec()函数

eval(str)可以把字符串str当作有效的表达式来求值并且返回运算结果。需要注意的是str只能是单个运算表达式，不可以进行赋值或其他复杂的代码逻辑。下面是一些运行实例：>>> eval("10+200")210>>> eval("10*10")100>>>>>> t1=100>>> t2=40>>> eval("t1+t2")140>>> exe

原创 Python中print()和input()的一些基本的用法

print()函数的使用格式是：print(*values [, sep=’ ’ [, end=’\n’ [, file=sys.stdout [, flush=False] ] ] ])其中的*values 是必选参数其中*表示参数可以有多个，如果有多个参数需要用逗号(,)隔开，有多个参数时输出的各个值之间用空格隔开。例如：>>> print(1,2)1 2>>>>>> a="python">>> b="hell

原创 愚人节的礼物（杭电oj）

**四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。Input本题目包含多组测试，请处理到文件结束。每组测试包含一个长度不大于1000,只包含’(’,’)'和’B’三种字符的字符串，代表Vayko设计的礼物透视图。你可以

原创 六度分离

Problem Description1967年，美国著名的社会学家斯坦利·米尔格兰姆提出了一个名为“小世界现象(small world phenomenon)”的著名假说，大意是说，任何2个素不相识的人中间最多只隔着6个人，即只用6个人就可以将他们联系在一起，因此他的理论也被称为“六度分离”理论(six degrees of separation)。虽然米尔格兰姆的理论屡屡应验，一直也有很多社会学家对其兴趣浓厚，但是在30多年的时间里，它从来就没有得到过严谨的证明，只是一种带有传奇色彩的假说而已。Le

原创 1sting

**规律是第i项等于i-1项和i-2项的和和斐波那契一样注意因为长度太长所以long long也存不下来所以得用数组Problem DescriptionYou will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, gi

原创 数列-训练套题T10T3

**只是做个笔记本题可用树状数组做注意最后的结果用long long 型的变量存储**数列(sequence.pas/c/cpp)问题描述一个简单的数列问题：给定一个长度为n的数列，求这样的三个元素ai, aj, ak的个数，满足ai < aj > ak，且i < j < k。输入数据第一行是一个整数n(n <= 50000)。第二行n个整数ai(0 <= ai <= 32767)。输出数据一个数，满足ai < aj > ak (i

原创 Count Inversions

只是做个笔记本题可用树状数组做题目描述给一个数组，算inverted pair的数目输入有多组测试样例。每组输入数据占一行，每一行是一个数组，数组之间的元素用空格分开输出每组输出结果占一行。对应于每组输入数据的inversions样例输入 Copy1 2 32 1 33 2 1样例输出 Copy013#include<bits/stdc++.h>using namespace std;const int MAXN=1000000;#define lowbi

原创 区间查询

只是做个笔记该题可以用树状数组题目描述食堂有N个打饭窗口，现在正到了午饭时间，每个窗口都排了很多的学生，而且每个窗口排队的人数在不断的变化。现在问你第i个窗口到第j个窗口一共有多少人在排队？输入输入的第一行是一个整数T，表示有T组测试数据。每组输入的第一行是一个正整数N（N<=30000），表示食堂有N个窗口。接下来一行输入N个正整数，第i个正整数ai表示第i个窗口最开始有ai个人排队。（1<=ai<=50）接下来每行有一条命令，命令有四种形式：(1)Add i j，i

原创 最少的交换

题目描述现在给你一个由n个互不相同的整数组成的序列，现在要求你任意交换相邻的两个数字，使序列成为升序序列，请问最少的交换次数是多少？输入输入包含多组测试数据。每组输入第一行是一个正整数n（n<500000），表示序列的长度，当n=0时。接下来的n行，每行一个整数a[i]（0<=a[i]<=999999999），表示序列中第i个元素。输出对于每组输入，输出使得所给序列升序的最少交换次数。样例输入 Copy59105431230样例输出 Copy60

原创 结果填空：素数个数

用 0,1,2,3⋯7 这 8 个数组成的所有整数中，质数有多少个（每个数字必须用到且只能用一次）。提示：以0 开始的数字是非法数字。递归回溯#include<bits/stdc++.h>using namespace std;const int MAXN=1000010;bool fff[MAXN];int ans=0;bool check(int x){ if(x==2||x==1) return false; for(int i=2;i<=sqrt(x);i++

原创 程序设计：找质数

一天蒜头君猜想，是不是所有的偶数（除了 2），都可以用两个质数相加得到呢？于是聪明的蒜头君就找你来验证了。输入格式第一行输入一个整数 t 表示测试组数。接下来 t 行，每行一个整数 n。输出格式输出两个整数，因为答案可能有多个，所有要求输出的这两个整数是所有答案中字典序最小的。样例输入 复制34820样例输出 复制2 23 53 17注意1不是质数下面是代码里面有注释#include<bits/stdc++.h>using namespace std;co

原创 判断整除

计蒜客里的习题用dp[i][j]表示前i个数可以形成j的余数（如果可以则为true否则为false）#include<bits/stdc++.h>using namespace std;const int MAXN=10010;int main(){ int n,k; int num[MAXN]; bool dp[MAXN][100]; fill(dp[0],dp[0]+MAXN*100,false); scanf("%d%d",&n,&k); fo

原创 Monkey Party

只为做个笔记#include<bits/stdc++.h>using namespace std;const int MAXN=1010*2;const int INF=0xffffffff;//小一点防止越界int dp[MAXN][MAXN],w[MAXN],sum[MAXN],s[MAXN][MAXN],n;void solve(){ for(int i=1;i<=n*2;i++){ sum[i]+=sum[i-1]; dp[i][i]=0; s[i][i

原创 开餐馆

蒜头君想开家餐馆. 现在共有 n 个地点可供选择。蒜头君打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列 m1, m2, … mn来表示他们的相对位置。由于地段关系, 开餐馆的利润会有所不同。我们用 p 表示在 m 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于 k。请你帮助蒜头君选择一个总利润最大的方案。输入格式标准的输入包含若干组测试数据。输入第一行是整数 T(1≤T≤1000)，表明有 T 组测试数据。紧接着有 T组连续的测试。每

原创 干草出售

农民约翰面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，约翰拉着他的马车到农民唐的农场中买一些稻草给奶牛过冬。已知约翰的马车可以装的下C(1≤C≤50,000) 立方的稻草。农民唐有 H(1≤H≤5,000) 捆体积不同的稻草可供购买，每一捆稻草有它自己的体积 (1≤V ≤C)。面对这些稻草约翰认真的计算如何充分利用马车的空间购买尽量多的稻草给他的奶牛过冬。现在给定马车的最大容积 C 和每一捆稻草的体积 V​ ，约翰如何在不超过

原创 踩方格

有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b. 走过的格子立即塌陷无法再走第二次；c. 只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走 n 步，共有多少种不同的方案。2 种走法只要有一步不一样，即被认为是不同的方案。输入格式允许在方格上行走的步数 n(n≤20)。输出格式计算出的方案数量。输出时每行末尾的多余空格，不影响答案正确性样例输入 复制2样例输出 复制7递归回溯记忆化搜索#includ

原创 魔法宝石(动态规划)

Bessie 去珠宝商店想要买一些魔法宝石。商店里有 n 个宝石，每个宝石的重量为 wi幸运值为 vi。Bessie 的购物车只能装重量之和不超过 mm 的商品，现在她想知道如何选择宝石，能让购买的幸运值之和最大。输入格式第一行两个整数 n,m，表示宝石的数量和购物车的承重能力。接下来 n 行，每行两个整数 wi,vi，表示每个宝石的重量和幸运值。样例输入复制4 61 42 63 122 7样例输出复制23裸背包问题#include<bits/stdc++.h>us

原创 铺砖

对于一个 2 行N 列的走道。现在用 1×2,2×2 的砖去铺满。问有多少种不同的方式。输入格式一个数字 N，0≤n≤250。输出格式方案数。（对 100007 取模）。输出时每行末尾的多余空格，不影响答案正确性样例输入12样例输出13样例输入28样例输出2复171思路特别简单就是动态规划 做一下笔记#include<bits/stdc++.h>using namespace std;const int MAXN=251;const int MOD=1000

原创 递推三角形(动态规划)

蒜头君拿出两根长度为 a, b的木棍，将两端钉在一起，做了一个可以开口大小可以变化的 V 字，如下图所示。现在有一堆长度为 1 或2 的木棍边角料（可以认为它们的数目无限多）。蒜头君想要用若干块边角料将点 X、Y 连接起来组成第三条边，使得这个三角形成为一个直角三角形，求方案数对 10007 取模的结果。注意连接的顺序不同，视为不同的方案，可根据样例进一步理解。输入格式输入为一行，是两个空格隔开的整数 a,b(1≤a,b≤1000)输出格式输出为一行，是一个整数，为取木棍的方案数对 1000710

原创 买书(动态规划)

小蒜手里有 n 元钱全部用来买书，书的价格为 10 元，20 元，50 元，100 元。问小蒜有多少种买书方案？（每种书可购买多本）输入格式一个整数 n，代表总共钱数。（1≤n≤1000）输出格式一个整数，代表选择方案种数。输出时每行末尾的多余空格，不影响答案正确性样例输入120样例输出12样例输入215样例输出20dp[i]表示组成金额i的方案数，初始化的时候令dp[0]=1;num[0],num[1],num[2],num[3]分别为10 20 50 100则dp[j]

原创 数字组合(动态规划)

小蒜有 n(1≤n≤20) 个正整数，找出其中和为 (t 也是正整数)的可能的组合方式。如：n=5 个数分别为 1,2,3,4,5 t=5；那么可能的组合有 5=1+4 和 5=2+3 和 5=5 三种组合方式。输入格式输入的第一行是两个正整数 n 和 t，用空格隔开，其中1≤n≤20, 表示正整数的个数，t 为要求的和 (1≤t≤1000)接下来的一行是 n 个正整数，用空格隔开。输出格式和为 tt 的不同的组合方式的数目。输出时每行末尾的多余空格，不影响答案正确性样例输入5 51 2

原创 大盗阿福(动态规划)

知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？输入格式输入的第一行是一个整数 T(T≤50) ，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数N(1≤N≤100,000)，表示一共有 N 家店铺。第二行是 NN 个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000。输出格式对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。提示对于第一组样例，阿福选择第 2 家店铺行窃，获得的现金数量为 88。

原创 放苹果(动态规划)

小蒜想知道把 M 个同样的苹果放在 N 个同样的盘子里，允许有的盘子空着不放，共有多少种不同的分法？（用 KK 表示）5，1，1 和 1，5，1 是同一种分法。输入格式第一行是测试数据的数目 t(0≤t≤20)。以下每行均包含两个整数 M 和 N，以空格分开。 1≤M,N≤10。输出格式对输入的每组数据 M 和 N，用一行输出相应的 K。输出时每行末尾的多余空格，不影响答案正确性样例输入17 3样例输出8**我们先令dp(m,n)表示水果为m个，盘子为n个时的情况可以分为两种情况

原创 L3-001 凑零钱 (30分)

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有 10​4​​ 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。输入格式：输入第一行给出两个正整数：N（≤10​4​​ ）是硬币的总个数，M（≤10​2​​ ）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。输出格式：在一行中输出硬币的面值 V​1​​ ≤V​2​​ ≤⋯≤V​k

原创 L2-032 彩虹瓶 (25分)

彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到 N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一

原创 L2-031 深入虎穴 (25分)

著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。输入格式：输入首先在

原创 L2-027 名人堂与代金券 (25分)

对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。输入格式：输入

原创 L2-026 小字辈 (25分)

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。输入格式：输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） —— 简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。输出格式：首先输出最小的辈分（老祖宗的辈分为 1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。输入样例：

原创 L2-025 分而治之 (25分)

**分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。输入格式：输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的