- 博客(25)
- 收藏
- 关注
RSS订阅
原创 蒙德里安的梦想
蒙德里安的梦想题目描述求把N×MN\times MN×M的棋盘分割成若干个1×21\times 21×2的的长方形，有多少种方案。例如当N=2，M=4N=2，M=4N=2，M=4时，共有555种方案。当N=2，M=3N=2，M=3N=2，M=3时，共有333种方案。如下图所示：输入格式输入包含多组测试用例。每组测试用例占一行，包含两个整数NNN和MMM。当输入用例N=0，M=0N=0，M=0N=0，M=0时，表示输入终止，且该用例无需处理。输出格式每个测试用例输出一个结果，每个结果占一
2020-11-19 14:21:58
222
原创 排序算法
一、冒泡排序我们在喝可乐的时候会发现：有一些小泡泡会不断的往上浮，而冒泡排序正是收到这种现象的启发而发明。冒泡排序的做法很简单：从前往后一直做遇到a[i]>a[i+1]a[i] > a[i + 1]a[i]>a[i+1] 就交换#include <bits/stdc++.h>using namespace std;#define MAXN 1000005int a[MAXN];int main(){ int n; scanf("%d", &am
2020-11-17 15:28:31
92
原创 高精度运算
高精度运算前言高精度加法高精度减法高精度乘法高精度除法前言高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称
2020-11-17 09:18:14
1107
原创 求组合数
平时在做题的时候经常会用到求组合数，但是一般情况下普通求Cmn\text{C} ^n_mCmn都会超时，这里介绍四种求组合数的方法：1. 乘一个除一个一般情况下求组合数的方法都是乘一个除一个就比如C53=5×4×33×2×1C^3_5 = \frac{5 \times 4 \times 3}{3 \times 2 \times 1}C53=3×2×15×4×3 但是我们顺着做除不尽，所以我们把分母反着做，C53=5×4×31×2×3=C^3_5 = \frac{5\times4\times3}{
2020-11-05 19:42:00
1175
原创 邮局选址
题目描述在一个镇上有n个村子，每个村子住着数量不等的居民。这些村子可以看做是排列在一条直线上的若干个整数点。现在镇长要在村子里建一个邮局。请问将邮局建在哪一个村子，可以使得所有居民走到邮局的距离和最小。输入格式第一行一个整数n，表示有n个村子。接下来有n行，每行两个数，表示第i个村子的坐标和居民数。保证所有村子的坐标都是正整数。输出格式输出两个数，第一个数表示建邮局的村子的坐标，第二个数表示最小的距离和。如何有多个村子适合建邮局，输出坐标最小的那个。输出结果中间有1个空格间隔。样例样例输入
2021-05-11 11:53:49
386
原创 选择卡片
题目描述TakTakTak有张卡片，在第（1≤i≤n1 \leq i \leq n1≤i≤n）张上写着一个整数xix_ixi。他想选择张卡片中的111张或者多张卡片，使这些卡片上的数字平均值等于AAA。他想知道有多少种选择卡片的方法？输入格式输入共有两行。第一行有两个正整数NNN和AAA，分别表示卡片的总数和平均值。第二行包含NNN个整数，分别表示NNN张卡片上的整数。输出格式输出一个整数，表示选择若干张卡片的平均值为的方案总数样例样例输入14 87 9 8 9样例输出15
2021-04-24 19:31:00
464
原创 环形最大子段和
题目描述给出一个首尾相连的循环序列，从中找出连续的一段，使得该段中的数和最大。注意：至少要选一个元素输入格式第一行一个整数n，表示有n个数。（1<=n<=100000）第二行有n个整数，每个数的绝对值不超过100000.输出格式输出最大的字段和。样例样例输入42 -4 1 4样例输出7首先，我们先来看看普通的最大字段和是怎么做的：设dp[i]dp[i]dp[i]为以iii为结尾的最大子段和。所以dp[i]=dp[i−1]+a[i]dp[i] = dp[i -
2021-04-16 10:59:31
703
原创 Superhero打怪
伟大的英雄问题描述伟大的Superhero守护着52nk掌管的国家。Superhero的攻击力为，初始健康值为，Superhero前面有个怪物，第个怪物的攻击力为，初始健康值为。第只怪物的攻击力为，初始健康值为。如果Superhero或怪物的健康值为正数(大于或等于)，则视作仍然活着；如果其健康值为非正数(小于或等于)，则视作死亡。为了保护国家的人民，Superhero会和怪物战斗，直到Superhero死了或者所有的怪物死了。在每次战斗中，Superhero可以选择一个任意的活着的怪物，与之战
2021-04-01 17:39:10
261
原创 最小生成树 大扫除
问题描述现在要打扫约翰的牧圈。已经很多年没打扫了。所以这次的计划是用河水来冲。牧圈排成整齐的格子，每相邻的两个之间都有门。要想让水进去，就必须打开这些门。这不是件容易的事情。因为有些圈里土堆得很高。因此打开门就很费劲。为了使花的力气最小，总是把门推向土低的一边。你的任务是计算最少得费多少劲。我们用土的厚度来描述这个值。输入格式第一行是宽度w和高度h，其中3<=w，h<=40。以下h行数据，描述了土的高度，也就是我们所浪费体力的度量。数据的范围在1到100之间。输出格式你得到的结果。所
2021-01-29 17:59:26
258
原创 埃及分数
在古埃及，人们使用单位分数的和（形如1a\frac{1}{a}a1的，aaa是自然数）表示一切有理数。如：23=12+16\frac{2}{3}=\frac{1}{2} + \frac{1}{6}32=21+61，但不允许23=13+13\frac{2}{3}=\frac{1}{3} + \frac{1}{3}32=31+31，因为加数中有相同的。对于一个分数ab\frac{a}{b}ba，表示方法有很多种，但是哪种是最好的呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分
2020-11-21 14:11:36
1046
原创 渡轮问题 题解
题目描述Palmia 河在某国从东向西流过，并把该国分为南北两个部分。河的两岸各有 N 座城市，且北岸的每一个城市都与南岸的某个城市是友好城市，而且友好关系是一一对应的。现在要求在两个友好城市之间建立一条航线，但由于天气的原因，所有航线都不能相交，因此，就不可能给所有的友好城市建立航线。 问题：当给出城市个数和友好关系的信息之后，选择一种修建航线的方案，能建最多的航线而不相交。输入格式第1行：2个空格分开的整数XXX, YYY，表示Palmia河岸的长度，表示河的宽度第2行：1个整数N (
2020-10-23 09:00:29
1015
原创 UVA11261 - Bishops
传送门1传送门2题目描述Little Sultan has a new chess set. But he finds it more amusing to make some new variants of his ownthan the original game of chess. Here he challenges you with one of his new variants. On a n × nchessboard m bishops are placed. You have
2020-10-22 00:09:19
145
原创 ZOJ 3080 Chibi（Floyd）
赤壁传送门题目描述watashi’s mm is so pretty as well as smart. Recently, she has watched the movie Chibi. So she knows more about the War of ChiBi. In the war, Cao Cao had 800,000 soldiers, much more than his opponents’. But he was defeated. One of the mistakes
2020-10-21 14:21:52
123
原创 挖地雷 题解
挖地雷题目描述在一个地图上有N个地窖，依次编号为1…N，每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径。例如在下图中：上图表示，地窖1可以挖到地窖2，地窖3；地窖2可以挖到地窖4；地窖3可以挖到地窖4，地窖5；地窖4可以挖到地窖5。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着某条路径接着往下挖（仅能选择一条路径），当某个地窖无连接时挖地雷工作结束。试设计一个挖地雷的方案，使某人能挖到最多的地雷。输入格式第1行：1个整数N（1<=N<=
2020-10-20 11:12:54
1216
原创 POJ1160 Post Office题解
POJ1160 Post Office传送门题目描述在笔直的大道上建有nnn个大别墅，两个大别墅之间的距离是他们的横坐标之差的绝对值，保证大别墅之间的距离只能是整数，且没有别墅的位置是相同的。现在需要建立mmm座大超市(m≤n)(m \leq n)(m≤n)，大超市只能建立在别墅所在的位置，现在需要你写个程序，给定了所有别墅的位置和大超市的数目，计算出每个别墅离最近的大超市的距离总和的最小值。输入格式第一行包括两个整数nnn和mmm第二行包括n个整数，代表别墅的位置，以升序的形式列出。
2020-10-19 17:26:07
275
原创 SYZOJ#186 [额]你猜是不是DP
[额]你猜是不是DP传送门题目描述现在给两个仅包含小写字母的字符串a,b ，求a 与b的最长公共连续子串的长度。输入格式两个字符串输出格式一个整数，为输入的两个字符串的最长公共连续子串的长度输入qaqaaaqqqaqa输出4解释最长连续公共子串为qaqa，长度为4这道题我们只需要把两个字符串的每一个前缀的哈希值求出来，然后二分公共串的长度，如果当前二分到的这个长度lll可以找到公共子串，那么我们一定可以找到l−1l-1l−1，l−2l-2l−2，……，11
2020-10-14 10:05:33
120
原创 洛谷P3370 【模板】字符串哈希
题目描述如题，给定 NNN 个字符串（第 iii 个字符串长度为 MiM_iMi ，字符串内包含数字、大小写字母，大小写敏感），请求出 NN 个字符串中共有多少个不同的字符串。友情提醒：如果真的想好好练习哈希的话，请自觉，否则请右转PJ试炼场:)输入格式第一行包含一个整数 NNN，为字符串的个数。接下来 NNN 行每行包含一个字符串，为所提供的字符串。输出格式输出包含一行，包含一个整数，为不同的字符串个数。输入输出样例输入5abcaaaaabcabcc12345
2020-10-14 09:35:21
389
原创 新年趣事之打牌 题解
新年趣事之打牌题目描述过年的时候，大人们最喜欢的活动，就是打牌了。xiaomengxian不会打牌，只好坐在一边看着。 这天，正当一群人打牌打得起劲的时候，突然有人喊道：“这副牌少了几张！”众人一数，果然是少了。于是这副牌的主人得意地说：“这是一幅特制的牌，我知道整副牌每一张的重量。只要我们称一下剩下的牌的总重量，就能知道少了哪些牌了。”大家都觉得这个办法不错，于是称出剩下的牌的总重量，开始计算少了哪些牌。由于数据量比较大，过了不久，大家都算得头晕了。 这时，xiaomengxian大声说：“你们看我
2020-10-13 17:39:26
1066
1
原创 迎春舞会之三人组舞(版本2) 题解
迎春舞会之三人组舞(版本2)题目描述HNSDFZ的同学们为了庆祝春节，准备排练一场舞 n个人选出3×m3\times m3×m人，排成m组，每组3人。 站的队形——较矮的2个人站两侧，最高的站中间。 从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度”越低。 计算公式为 h=(a−b)2h=(a-b)^2h=(a−b)2 (a、b为较矮的2人的身高) 那么问题来了。 现在候选人有n个人，要从他们当中选出3×m3\times m3×m个人排舞蹈，要求总体的“残疾程度”最低。输入格式
2020-10-13 15:43:29
332
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人