- 博客(37)
- 收藏
- 关注
RSS订阅原创 算法实验4：棋盘覆盖
棋盘覆盖问题Description在一个2k x 2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。Inputk，dr，dc。k定义如前，dr，dc分别表示特殊方格所在的行号和列号 1= < k < =6Output按照左上，右上，左下，右下的顺序用分治法求解。特殊方格标0，其他位置按上述顺序依次标记。Sa
2020-09-10 08:16:05
515
原创 算法实验1：x^n mod 1003
算法实验1：x^n mod 1003题目描述Description给定整数x和n,求x的n次幂 mod 1003Input整数x和n。 1<=x,n<=1,000,000,0000Outputx^n mod 1003Sample Input2 10Sample Output21分析幂函数，x^n，当数值过大时，需要进行处理这里用了一种思想，首先将n转换成二进制数值，例如x^10，这里将（10）转换成（1010）从左边高位数值第一位进行舍弃，初始（xx），依次判断，如
2020-09-03 09:16:55
1819
原创 E .[模板]欧拉筛（修改）
题目描述lglg最近爱上了炒股，他想在股票市场内买一些股票。现在有编号为1，2，3，…，100000000的100000000支股票，每个股票的价值等于其编号的阶乘(例如编号为5的股票的价值就是120)。lglg是一个很挑剔的人，他只喜欢编号为质数的股票，但他很有钱，因此他希望买下所有编号小于等于N(1<=N<=1e8)并且编号为质数的股票，请你帮他算一算这些股票的价值之和。由...
2019-11-19 18:33:41
185
原创 B.丁姐姐喜欢LCS
题目描述丁姐姐最近迷上了LCS(The longest common substring)!今天她想找个其它东西玩，于是她找到了两个字符串A和B，现在她想知道它们尾头衔接形成的最长字符串,例如A = abc,B = bca从A的尾部开始，A串的bc与B串的bc头尾衔接。输入描述:输入数据包含多个测试样例，每个测试样例占两行，第一行是字符串A，第二行是字符串B，保证每个字符串的长度不超过10...
2019-11-19 18:26:06
125
原创 四川大学第二届SCUACM新生赛（同步赛）F
[模板]后缀自动机题目描述：这是一道模板题:给定两个字符串S和T，询问S中是否存在一个后缀P，使得T的任何一个前缀的字典序都大于P。注意：数据里同时含有大写与小写字母，比较字典序时严格按照 Ascii 编码进行比较，即我们认为 A<B<C…<Z<a<b<c<…<z 。输入描述:每组数据有两行只包含英文字母的字符串，第一行是S,第二行是T (...
2019-11-18 16:50:06
196
原创 洛谷.P5613 [MtOI2019]黑蚊子多
题目描述Hikari 的面前有 n(1≤n≤1000) 级台阶，每 1s她可以向上跳 m(1≤m≤n)级台阶。（不在中间的台阶上停留）台阶上有 k(k≤10)个特殊的平台 ai，Hikari 在该平台 停留 时会使得 m 增加 1。请问 Hikari 到达台阶顶部花费的时间。输入格式共 2 行。第 1 行输入 3个非负整数 n,m,k。第 2 行输入 k 个正整数，第 i 个正整数表...
2019-11-08 16:18:18
567
原创 奇特的数
1.斐波那契数列：问题：常见的就是兔子问题：如果一对兔子每月能生一对小兔（一雄一雌），而每对小兔在牠出生后的第三个月里，又能开始生一对小兔，假定在不发生死亡的情况下，由一对出生的小兔开始，50个月后会有多少对兔子？从第一个月开始以后每个月的兔子总数是1,1,2,3,5,8,13,21,34,55,89,144,233…，所以当n＞1时，Fn+2 = Fn+1+Fn，而F0=F1=1。黄金分...
2019-10-16 18:44:54
171
原创 Holding Bin-Laden Captive!
Holding Bin-Laden Captive!DescriptionWe all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!“O...
2019-10-11 18:46:41
105
原创 Barn Repair 修理牛棚 oj2310
Description在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛，有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买的木板总长度...
2019-10-09 20:43:32
196
原创 算法：快速幂
快速幂取模用法：用于求解 a 的 b 次方，而b是一个非常大的数，用O（n）的复杂度会超时。假如求 x ^ n 次方，我们可以把 n 表示为 2^k1 + 2k2 + 2^k3….，可以证明所有数都可以用前式来表示。（其实就是二进制表示数的原理）即 x^n = x2k1 * x2k2 * x2k3……那么就可以利用二进制来加快计算速度了。假如 x^23 , 23转化为二进制为 10111...
2019-10-09 16:04:23
99
原创 算法:x^n
Description问题很简单，求x^n.请编写pow()函数.声明如下：int pow(int x,int n,int p)//pow的功能是实现x^n，最后１个参数p没有用。系统会自动在程序的最后加上如下代码：int main(){int x,n;scanf("%d %d",&x,&n);printf("%d\n",pow(x,n,1));return ...
2019-10-09 16:03:21
911
原创 The Hardest Problem Ever
DescriptionJulius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to survive, he decided to create one of the first ...
2019-10-09 15:51:48
200
原创 实验课.简单数学（基本数学题)
算法:x^nDescription问题很简单，求x^n.请编写pow()函数.声明如下：int pow(int x,int n,int p)//pow的功能是实现x^n，最后１个参数p没有用。系统会自动在程序的最后加上如下代码：int main(){ int x,n; scanf("%d %d",&x,&n); printf(...
2019-09-11 19:31:54
208
原创 acm.小节
DescriptionJulius Caesar lived in a time of danger and intrigue. The hardest situation Caesar ever faced was keeping himself alive. In order for him to survive, he decided to create one of the first ...
2019-09-10 19:40:19
169
原创 洛谷.P2550 [AHOI2001]彩票摇奖
题目描述为了丰富人民群众的生活、支持某些社会公益事业，北塔市设置了一项彩票。该彩票的规则是：(1) 每张彩票上印有 7 个各不相同的号码，且这些号码的取指范围为 1~33。(2) 每次在兑奖前都会公布一个由七个各不相同的号码构成的中奖号码。(3) 共设置 7 个奖项，特等奖和一等奖至六等奖。兑奖规则如下：特等奖：要求彩票上 7 个号码都出现在中奖号码中。一等奖：要求彩票上有 6 个号码...
2019-09-09 21:13:54
424
原创 ACM日常训练. Number Triangles 数字金字塔(2317)
Description考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。 每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和...
2019-09-09 19:27:18
294
原创 ACM日常训练.Calf Flac
Description据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。 在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母’A’-‘Z’和’a’-‘z’。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。 我们将保证最长的回文不会超过2,000个...
2019-09-07 16:40:26
133
原创 ACM日常训练.Milking Cows 挤牛奶
Description三个农民每天清晨5点起床，然后去牛棚给3头牛挤奶。第一个农民在300时刻(从5点开始计时，秒为单位)给他的牛挤奶，一直到1000时刻。第二个农民在700时刻开始，在 1200时刻结束。第三个农民在1500时刻开始2100时刻结束。期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻)，而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300时...
2019-09-07 16:33:18
213
原创 实验课.简单数学（基本数学题）
求解约数问题：该问题整理了一个题型的两种问题：一个数约数的个数，两个数区间内约数的个数。一个数约数的个数Descriptionmmoaay小侄子今年上初中，老师出了一道求约数个数的题目，比如8的约数有1,2,4,8共4个。当数比较小的时候可以人工算，当n较大时就难了。mmoaay嫌麻烦，现在让你编个程序来算。Input一行一个整数。最后以0结束。Output分别求出这些整数的约...
2019-09-05 19:01:09
347
原创 实验课.简单数学（基本数学题）
很早就想整理一下，但一直苦苦哀叹，（其实就是我懒）简单数学题暂时分为四个基本点：1.求阶乘最右侧的数字：当时这道题一直炸，其实思路很好懂，就是细节的处理。初始思路：不断对十求余；但是仔细思考一下，不断求余的话，量太大了，开ll也会炸掉；以下为AC代码：（1）：#include#include#include#include#include#include#includ...
2019-09-05 18:29:34
235
原创 洛谷.欧式几何
题意翻译19世纪的德国数学家赫尔曼·闵可夫斯基(Hermann Minkowski)研究了一种名为出租车几何学的非欧几何。 在==出租车几何里T1(x1,y1),T2(x2,y2)两点之间的距离被定义为dis(T1,T2)=|x1-x2|+|y1-y2|(曼哈顿距离)。 其他定义均与欧几里得几何相同。例如圆的定义：在同一平面内，到定点(圆心)的距离等于定长(半径)的点的集合。我们对欧几里得几何...
2019-08-31 10:40:41
307
原创 洛谷.P1887 乘积最大3
题目描述link.请你找出M个和为N的正整数，他们的乘积要尽可能的大。输出字典序最小的一种方案。输入格式一行，两个正整数N,M输出格式M个和为N的，乘积尽可能的大的正整数。思路：首先从最简单的问题开始分析，假设m=2，即分为两组使和最大，那么：已知x+y=k（k为常数），S=x*y，当x=y时，有S的最大值。由此可以类推：当一个数n被分为m份时，当每份数量相等，这m个数的乘积...
2019-08-31 10:34:55
1094
1
原创 洛谷.P3741 honoka的键盘（dalao勿进，纯属错题笔记）
题目背景honoka 有一个只有两个键的键盘。题目描述一天，她打出了一个只有这两个字符的字符串。当这个字符串里含有"VK"这个字符串的时候，honoka 就特别喜欢这个字符串。所以，她想改变至多一个字符（或者不做任何改变）来最大化这个字符串内"VK"出现的次数。给出原来的字符串，请计算她最多能使这个字符串内出现多少次"VK"。(只有当"V"和"K"正好相邻时，我们认为出现了"VK"。)输入...
2019-08-30 20:02:44
490
原创 洛谷.P1059 明明的随机数
题目描述明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数(N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。输入格式输入有两行，第1行为1个正整数，表示所生成的随机数的个数N第2行有...
2019-08-30 19:15:09
306
原创 洛谷.P2705 小球
题目描述有 R 个红色盒子和 B 个蓝色盒子，还有 R 个红色小球和 B 个蓝色小球。每个盒子只能装一个小球，每个小球都要放在一个盒子里。如果把一个红色小球放在一个红色盒子里，那么得分是 C。如果把一个蓝色小球放在一个蓝色盒子里，那么得分是 D。如果把一个红色小球放在一个蓝色盒子里，那么得分是 E。如果把一个蓝色小球放在一个红色盒子里，那么得分也是 E。现在给出 R，B，C，D，E。应该如何放置...
2019-08-28 15:30:46
791
原创 洛谷.P2669 金币
题目描述国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续N天每天收到N枚金币后，骑士会在之后的连续N+1N+1N+1天里，每天收到N+1N+1N+1枚金币。请计算在前KKK天里，骑士一共获得了多...
2019-08-28 14:59:16
480
原创 洛谷.P1307 数字反转
题目描述给定一个整数，请将该数各个位上数字反转得到一个新数。新数也应满足整数的常见形式，即除非给定的原数为零，否则反转后得到的新数的最高位数字不应为零（参见样例2）。输入格式一个整数 NNN输出格式一个整数，表示反转后的新数。#include<cstdio>#include<cstring>#include<algorithm>#include...
2019-08-28 14:36:51
210
原创 数学小思路
对于每一个数n，==除非它是完全平方数，否则它一定有偶数个因子。==因为如果i是n的因子，那么n/i也一定是n的因子。例如当n=20时，i=4是20的因子，那么n/i=5也是20的因子，这样，n的因子都是成对出现的，所以n有偶数个因子。但是，有一种特殊情况，即n/i=i。例如4/2=2。由于i和n/i是同一个数，算因子只能是一个，这时n的因子就是奇数个，再把n/i=i变形，得n=i*i，即n是完...
2019-08-25 10:37:33
238
原创 洛谷.P1319 压缩技术
题目描述设某汉字由N × N的0和1的点阵图案组成。我们依照以下规则生成压缩码。连续一组数值：从汉字点阵图案的第一行第一个符号开始计算，按书写顺序从左到右，由上至下。第一个数表示连续有几个0，第二个数表示接下来连续有几个1，第三个数再接下来连续有几个0，第四个数接着连续几个1，以此类推……例如: 以下汉字点阵图案：00010000001000000111100010000001000...
2019-08-25 10:32:39
1167
原创 洛谷.P2084 进制转换
题目背景无题目描述今天小明学会了进制转换，比如（10101）2 ，那么它的十进制表示的式子就是 : 124+0*23+122+0*21+1*2^0，那么请你编程实现，将一个M进制的数N转换成十进制表示的式子。注意：当系数为0时，该单项式要省略。输入格式两个数，M和N，中间用空格隔开。输出格式共一行，一个十进制表示的式子。注意！对于100%的数据，1<M<10，...
2019-08-25 09:47:02
906
原创 洛谷.P1876 开灯（完全平方数）
题目背景该题的题目是不是感到很眼熟呢?事实上，如果你懂的方法，该题的代码简直不能再短。但是如果你不懂得呢？那。。。（自己去想）题目描述首先所有的灯都是关的（注意是关！），编号为1的人走过来，把是一的倍数的灯全部打开，编号为二的的把是二的倍数的灯全部关上，编号为3的人又把是三的倍数的灯开的关上，关的开起来……直到第N个人为止。给定N，求N轮之后，还有哪几盏是开着的。输入格式一个数N，...
2019-08-24 11:51:50
665
原创 洛谷.P4414 [COCI2006-2007#2] ABC
题意翻译**【题目描述】**三个整数分别为 A ， B ， C . 这三个数字不会按照这样的顺序给你，但它们始终满足条件： A＜B＜C . 为了看起来更加简洁明了，我们希望你可以按照给定的顺序重新排列它们。**【输入格式】**第一行包含三个正整数 A ， B 和 C ，不一定是按这个顺序。这三个数字都小于或等于100。第二行包含三个大写字母 “A” 、 “B” 和 “C” （它们之间_没有 _...
2019-08-24 11:34:24
1260
原创 洛谷.P1765 手机_NOI导刊2010普及
题目描述一般的手机的键盘是这样的：1 2 abc 3 def4 ghi 5 jkl 6 mno7 pqrs 8 tuv 9 wxyz0 #要按出英文字母就必须要按数字键多下。例如要按出x就得按9两下，第一下会出w，而第二下会把w变成x。0键按一下会出一个空格。你的任务是读取若干句只包含英文小写字母和空格的句子，求出要在手机上打出这个句子至少需要按多少下键盘。输入格式一行一个句...
2019-08-24 11:00:08
581
原创 洛谷.P2192 HXY玩卡片
题目描述HXY得到了一些卡片，这些卡片上标有数字0或5。现在她可以选择其中一些卡片排成一列，使得排出的一列数字组成的数最大，且满足被90整除这个条件。同时这个数不能含有前导0，即0不能作为这串数的首位。如果不能排出这样的数，输出“-1”。输入格式第一行，卡片的个数n。第二行，分别给出了这n个数（只能为数字5或0）。输出格式仅一行，如果可以排出，则输出这个数。否则输出“-1”。{说明...
2019-08-23 18:16:09
304
原创 洛谷.P1424 小鱼的航程(改进版)
题目背景:原来的题目太简单，现改进让小鱼周末也休息，请已经做过重做该题。题目描述:有一只小鱼，它平日每天游泳 250 公里，周末休息（实行双休日)，假设从周 x(1≤x≤7)x(1\le x \le 7)x(1≤x≤7) 开始算起，过了 n(n≤106)n(n\le 10^6)n(n≤106) 天以后，小鱼一共累计游泳了多少公里呢？输入格式:输入两个整数x,n(表示从周x算起，经过n天）...
2019-08-22 20:33:28
233
原创 洛谷.P4956Davor
题目描述After successfully conquering the South Pole, Davor is preparing for new challenges. Next up is the Arctic expedition to Siberia, Greenland and Norway. He begins his travels on 31 December 2018, ...
2019-08-22 09:22:26
384
原创 同余定理
一.定义：给定一个正整数，若两个整数a和b满足差（a-b）可以被m整除，即（a-b）/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。二.解：两个不同的整数a、b，被一个整数m相除时，得到相同的余数，那么我就可以称a、b同余； 因为a、b同余所以当他们相减时，余数就抵消掉了，剩下的那部分就是能被m整除的。可以这么理解：既定a，b等a=mq1+r1，b=mq2+r，...
2019-08-22 09:07:13
567
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人