51nod-1067 Bash游戏 V2

发表于 博弈 分类,标签:
 有一堆石子共有N个。AB两个人轮流拿,A先拿。每次只能拿1,3,4颗,拿到最后1颗石子的人获胜。假设AB都非常聪明,拿石子的过程中不会出现失误。给出N,问最后谁能赢得比赛。例如N=2。A只能拿1颗,所以B可以拿到最后1颗石子。Input第1行:一个数T,表示后面用作输入测试的数的数量。(1 <= T <= 10000)第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)Output共T行,如果A获胜输出A,如果B获胜输出B。Input示例3234Output示例BAA思路:打表后可以看出有明显的规律。代码:#include<iostream>#include<alg...

51nod-1042 数字0-9的数量

发表于 动态规划 分类,标签:
 给出一段区间a-b,统计这个区间内0-9出现的次数。比如10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。Input两个数a,b(1 <= a <= b <= 10^18)Output输出共10行,分别是0-9出现的次数Input示例10 19Output示例11111111111思路:跟51nod1009题上类似,然后特殊处理0就行。代码如下,直接从1009题代码修改来的没优化。。。#include<bits/stdc++.h>using namespace std;#define LL long long...

51nod-1009 数字1的数量

发表于 动态规划 分类,标签:
 给定一个十进制正整数N,写下从1开始,到N的所有正数,计算出其中出现所有1的个数。例如:n=12,包含了5个1。1,10,12共包含3个1,11包含2个1,总共5个1。Input输入N(1 <= N <= 10^9)Output输出包含1的个数Input示例12Output示例5思路:对于数N,可以将其划分为三个部分,n-k(i)-m,  k(i)为N的第i为数字,n为第i位数前面部分组成的数,m为第i位数后面部分组成的数。第i位上1的个数计算,p为10^(len(m)):若k(i)大于1:(n+1)*p;若k(i)等于1:n*p+m+1;若k(i)小于1:n*p;代码#include<bits/stdc++.h>using namespace std;#def...

51nod-1092 回文字符串

发表于 DP 分类,标签:
 回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。每个字符串都可以通过向中间添加一些字符,使之变为回文字符串。例如:abbc添加2个字符可以变为acbbca,也可以添加3个变为abbcbba。方案1只需要添加2个字符,是所有方案中添加字符数量最少的。Input输入一个字符串Str,Str的长度 <= 1000。Output输出最少添加多少个字符可以使之变为回文字串。Input示例abbcOutput示例2思路:将输入的字符串s1倒转后变成s2,然后求s1和s2的最长公共子序列的长度,然后将s1字符串的长度减去公共子序列的长度就是最后需要输出的答案。代码:#include<bits/stdc++.h>using namespace std;#define LL lo...

51nod-1094 和为k的连续区间

发表于 动态规划 分类,标签:
 一整数数列a1,a2,...,an(有正有负),以及另一个整数k,求一个区间[i,j],(1<=i<=j<=n),使得a[i]+...+a[j]=k。Input第1行:2个数N,K。N为数列的长度。K为需要求的和。(2 <= N <= 10000,-10^9 <= K <= 10^9)第2 - N + 1行:A[i](-10^9 <= A[i] <= 10^9)。Output如果没有这样的序列输出No Solution。输出2个数i, j,分别是区间的起始和结束位置。如果存在多个,输出i最小的。如果i相等,...

L1-046. 整除光棍

发表于 数论 分类,标签: 天梯赛
 这里所谓的“光棍”,并不是指单身汪啦~说的是全部由1组成的数字,比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如,111111就可以被13整除。现在,你的程序要读入一个整数x,这个整数一定是奇数并且不以5结尾。然后,经过计算,输出两个数字:第一个数字s,表示x乘以s是一个光棍,第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。提示:一个显然的办法是逐渐增加光棍的位数,直到可以整除x为止。但难点在于,s可能是个非常大的数——比如,程序输入31,那么就输出3584229390681和15,因为31乘以3584229390681的结果是111111111111111,一共15个1。输入格式:输入在一行中给出一个不以5结尾的正奇数x(<1000)。输出格式:在一行中输出相应的最小的s和n,其间以1个空格分...

51nod-1095 Anigram单词

发表于 STL容器 分类,标签:
 一个单词a如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的Anigram,例如单词army和mary互为Anigram。现在给定一个字典,输入Q个单词,从给出的字典中找出这些单词的Anigram。Input第1行:1个数N,表示字典中单词的数量。(1 <= N <= 10000)第2 - N + 1行,字典中的单词,单词长度 <= 10。第N + 2行:查询的数量Q。(1 <= Q <= 10000)第N + 3 - N + Q - 2行:用作查询的单词,单词长度 <...

51nod-1119 机器人走方格 V2

发表于 数论 分类,标签:
 基准时间限制:1 秒空间限制:131072 KB分值: 10 难度:2级算法题 收藏 关注M*N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod10^9+7的结果。Input第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)Output输出走法的数量 Mod 10^9 + 7。Input示例2 3Output示例3思路:仔细观察发现其实是求C(n+m-2,m-1),求这个组合,因为mod是10^9+7是素数,所以可用费马小定理求乘法逆元。代码:#include<bits/stdc++.h>usi...

51nod-1126 求递推序列的第N项(矩阵快速幂)

发表于 数论 分类,标签:
 有一个序列是这样定义的:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.给出A,B和N,求f(n)的值。Input输入3个数:A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)Output输出f(n)的值。Input示例3 -1 5Output示例6思路:矩阵快速幂,直接套模板。代码:#include<bits/stdc++.h>using namespace std;#define LL long long#defin...

高僧斗法

发表于 博弈 分类,标签:
  问题描述  古时丧葬活动中经常请高僧做法事。仪式结束后,有时会有“高僧斗法”的趣味节目,以舒缓压抑的气氛。  节目大略步骤为:先用粮食(一般是稻米)在地上“画”出若干级台阶(表示N级浮屠)。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人,其它任意。(如图1所示)  两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶,但会被站在高级台阶上的小和尚阻挡,不能越过。两个小和尚也不能站在同一台阶,也不能向低级台阶移动。  两法师轮流发出指令,最后所有小和尚必然会都挤在高段台阶,再也不能向上移动。轮到哪个法师指挥时无法继续移动,则游戏结束,该法师认输。  对于已知的台阶数和小和尚的分布位置,请你计算先发指令的法师该如何决策才能保证胜出。输入格式  输入数据为一行用空格分开的N个整数,表示小和尚的位置。台阶序号从1算起,所以最后一个小和尚的位置即是台阶的总数...