世纪末的星期
/**
* 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。
* 还有人称今后的某个世纪末的12月31日，如果是星期一则会....
* 有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!!
* 于是，“谣言制造商”又修改为星期日......
* 1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？
* 请回答该年份（只写这个4位整数，不要写12月31等多余信息）
*/
public class 世纪末的星期 {
public static void main(String[] args) {
//从2000年开始
int i = 2000;
// 0 1 2 3 4 5 6 代表七天
int index = 4;
while (true) {
int days = 365;
if ((i%100!=0 && i%4==0) || i%400==0)
days = 366;
int yu = days % 7;
index = (index + yu) % 7;
// System.out.println(i+":"+index);
if (i % 100 == 99)
if ((index == 6)) {
System.out.println(i);
break;
}
i++;
}
}
}马虎的算式
/**
* 小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。
*
* 有一次，老师出的题目是：36 x 495 = ?
*
* 他却给抄成了：396 x 45 = ?
*
* 但结果却很戏剧性，他的答案竟然是对的！！
*
* 因为 36 * 495 = 396 * 45 = 17820
*
* 类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54
*
* 假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0）
*
* 能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？
*
* 请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。
*
* 满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。
*
* 答案直接通过浏览器提交。
* 注意：只提交一个表示最终统计种类数的数字，不要提交解答过程或其它多余的内容。
*/
public class 马虎的算式 {
public static void main(String[] args) {
//a>0 c>0
int total=0;
for(int a=1;a<10;a++) // a
for(int b=1;b<10;b++) //b
if(a!=b)
for(int c=1;c<10;c++) // c
if((b!=c)&&(a!=c))
for(int d=1;d<10;d++) //d
if((a!=d)&&(b!=d)&&(c!=d))
for(int e=1;e<10;e++) //e
if((a!=e)&&(b!=e)&&(c!=e)&&(d!=e))
// ab * cde = adb * ce
if((a*10+b)*(c*100+d*10+e)==(a*100+d*10+b)*(c*10+e))
total++;
System.out.println(total);
}
}振兴中华
/**
* 小明参加了学校的趣味运动会，其中的一个项目是：跳格子。
*
* 地上画着一些格子，每个格子里写一个字，如下所示：（也可参见p1.jpg）
*
* 从我做起振
* 我做起振兴
* 做起振兴中
* 起振兴中华
*
*
* 比赛时，先站在左上角的写着“从”字的格子里，可以横向或纵向跳到相邻的格子里，但不能跳到对角的格子或其它位置。一直要跳到“华”字结束。
*
*
* 要求跳过的路线刚好构成“从我做起振兴中华”这句话。
*
* 请你帮助小明算一算他一共有多少种可能的跳跃路线呢？
*
* 答案是一个整数，请通过浏览器直接提交该数字。
* 注意：不要提交解答过程，或其它辅助说明类的内容。
*/
//35
public class 振兴中华 {
public static void main(String[] args) {
int[][] dp = new int[6][6];
// 1 2 3 4 5
for(int i=1;i<=5;i++) //预处理
// 实际只用到[4][5]
dp[i][1] = dp[1][i] = 1;
// 2 3 4 5 即从第二位开始遍历递归
for(int i=2;i<=5;i++)
for(int j=2;j<=5;j++)
/*
* 向上或向左搜寻
*/
dp[i][j] = dp[i][j-1] + dp[i-1][j];
System.out.println(f(4,5));
}
/*
* 从我做起振
* 我做起振兴
* 做起振兴中
* 起振兴中华
*/
static int f(int x,int y){
if(x==1 && y==1)
return 1;
if(x==1)
return f(x,y-1);
if(y==1)
return f(x-1,y);
return f(x-1,y) + f(x,y-1);
}
}黄金连分数
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
/**
* 黄金分割数0.61803... 是个无理数，这个常数十分重要，在许多工程问题中会出现。有时需要把这个数字求得很精确。
*
* 对于某些精密工程，常数的精度很重要。也许你听说过哈勃太空望远镜，它首次升空后就发现了一处人工加工错误，对那样一个庞然大物，其实只是镜面加工时有比头发丝还细许多倍的一处错误而已，却使它成了“近视眼”!!
*
*
* 言归正传，我们如何求得黄金分割数的尽可能精确的值呢？有许多方法。
*
* 比较简单的一种是用连分数：
*
* 1
* 黄金数 = ---------------------
* 1
* 1 + -----------------
* 1
* 1 + -------------
* 1
* 1 + ---------
* 1 + ...
*
*
*
* 这个连分数计算的“层数”越多，它的值越接近黄金分割数。
*
* 请你利用这一特性，求出黄金分割数的足够精确值，要求四舍五入到小数点后100位。
*
* 小数点后3位的值为：0.618
* 小数点后4位的值为：0.6180
* 小数点后5位的值为：0.61803
* 小数点后7位的值为：0.6180340
* （注意尾部的0，不能忽略）
*
* 你的任务是：写出精确到小数点后100位精度的黄金分割值。
*
* 注意：尾数的四舍五入！ 尾数是0也要保留！
*
* 显然答案是一个小数，其小数点后有100位数字，请通过浏览器直接提交该数字。
* 注意：不要提交解答过程，或其它辅助说明类的内容。
*/
/**
* 斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）
* 以兔子繁殖为例子而引入，故又称为“兔子数列”，
* 指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
* 在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
* 在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。
*/
public class 黄金连分数 {
public static void main(String[] args) {
BigInteger a=BigInteger.ONE;
BigInteger b=BigInteger.ONE;
//斐波那契数列的迭代形式
for (int i = 3; i < 500; i++) {
BigInteger t=b;
b=a.add(b);//大整数的加法
a=t;
}
//大浮点数的除法
BigDecimal divide = new BigDecimal(a,110).divide(new BigDecimal(b,110), BigDecimal.ROUND_HALF_DOWN);
//截取字符串
System.out.println(divide.toPlainString().substring(0,103));
}
//0.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911375
/**
* 0.6180339887
* 4989484820
* 4586834365
* 6381177203
* 0917980576
* 2862135448
* 6227052604
* 6281890244
* 9707207204
* 18939113748
* 向上取一位
*/
}有理数类
/**
* 有理数就是可以表示为两个整数的比值的数字。一般情况下，我们用近似的小数表示。但有些时候，不允许出现误差，必须用两个整数来表示一个有理数。
*
* 这时，我们可以建立一个“有理数类”，下面的代码初步实现了这个目标。为了简明，它只提供了加法和乘法运算。
*/
public class Rational
{
private long ra;
private long rb;
// 辗转相除法取最简公因子
private long gcd(long a, long b){
if(b==0) return a;
return gcd(b,a%b);
}
public Rational(long a, long b){
ra = a;
rb = b;
long k = gcd(ra,rb);
if(k>1){ //需要约分
ra /= k;
rb /= k;
}
}
// 加法
// public Rational add(Rational x){
// return ________________________________________; //填空位置
// }
public Rational add(Rational x){
return new Rational(ra*x.rb+rb*x.ra, rb*x.rb); //填空位置 answer
}
/**
*
* new Rational(ra*x.rb+rb*x.ra, rb*x.rb)
* new Rational(this.ra * x.rb + x.ra * this.rb, this.rb * x.rb)
*
*/
// 乘法
public Rational mul(Rational x){
return new Rational(ra*x.ra, rb*x.rb);
}
public String toString(){
if(rb==1) return "" + ra;
return ra + "/" + rb;
}
}三部排序
/**
* 一般的排序有许多经典算法，如快速排序、希尔排序等。
*
* 但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。
*
* 比如，对一个整型数组中的数字进行分类排序：
*
* 使得负数都靠左端，正数都靠右端，0在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过1次线性扫描就结束战斗!!
*
* 以下的程序实现了该目标。
*/
public class 三部排序 {
public static void main(String[] args) {
}
static void sort(int[] x)
{
int p = 0;
int left = 0;
int right = x.length-1;
while(p<=right){
if(x[p]<0){
int t = x[left];
x[left] = x[p];
x[p] = t;
left++;
p++;
}
else if(x[p]>0){
int t = x[right];
x[right] = x[p];
x[p] = t;
right--;
}
else{
// _________________________; //代码填空位置
p++; //代码填空位置 answer
}
}
}
}
/**
* 如果给定数组：
* 25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0
* 则排序后为：
* -3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25
*/错误票据
import java.util.*;
/**
* 某涉密单位下发了某种票据，并要在年终全部收回。
* 每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
* 因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
* 你的任务是通过编程，找出断号的ID和重号的ID。
* 假设断号不可能发生在最大和最小号。
* 要求程序首先输入一个整数N(N<100)表示后面数据行数。
* 接着读入N行数据。
* 每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000）
* 每个整数代表一个ID号。
*
* 要求程序输出1行，含两个整数m n，用空格分隔。
* 其中，m表示断号ID，n表示重号ID
*
* 例如：
* 用户输入：
* 2
* 5 6 8 11 9
* 10 12 9
*
* 则程序输出：
* 7 9
*
*
* 再例如：
* 用户输入：
* 6
* 164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
* 172 189 127 107 112 192 103 131 133 169 158
* 128 102 110 148 139 157 140 195 197
* 185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
* 149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
* 113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
*
* 则程序输出：
* 105 120
*
*
* 资源约定：
* 峰值内存消耗（含虚拟机） < 64M
* CPU消耗 < 2000ms
*
*
* 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
*
* 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
* 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
* 注意：主类的名字必须是：Main，否则按无效代码处理。
*/
public class 错误票据 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<Integer>();
int N = sc.nextInt();
sc.nextLine();//吃掉整数后面的换行符
for (int i = 0; i < N; i++) {
String line = sc.nextLine();
String[] split = line.split(" ");
for (int j = 0; j < split.length; j++) {
list.add(Integer.parseInt(split[j]));
}
}
// System.out.println(list.size());
Collections.sort(list);
int a = 0, b = 0;
for (int i = 1; i < list.size(); i++) {
if (list.get(i) - list.get(i - 1) == 2)
a = list.get(i) - 1;
if (list.get(i) - list.get(i - 1) == 0)
b = list.get(i);
}
System.out.println(a + " " + b);
}
}幸运数
/**
* 幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。
*
* 首先从1开始写出自然数1,2,3,4,5,6,....
*
* 1 就是第一个幸运数。
* 我们从2这个数开始。把所有序号能被2整除的项删除，变为：
*
* 1 _ 3 _ 5 _ 7 _ 9 ....
*
* 把它们缩紧，重新记序，为：
*
* 1 3 5 7 9 11 13 15 17 19.... 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, ...
*
* 此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,...)
*
* 最后剩下的序列类似：
*
* 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...
*
* 本题要求：
*
* 输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
* 程序输出 位于m和n之间的幸运数的个数（不包含m和n）。
*
* 例如：
* 用户输入：
* 1 20
* 程序输出：
* 5
*
* 例如：
* 用户输入：
* 30 69
* 程序输出：
* 8
*
* 资源约定：
* 峰值内存消耗（含虚拟机） < 64M
* CPU消耗 < 2000ms
*
*
* 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
*
* 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
* 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
* 注意：主类的名字必须是：Main，否则按无效代码处理。
*/
public class 幸运数 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int[] a = new int[n+1];
for(int i=1;i<=n;i++)
a[i] = i;
for(int i=1;i<=n;i++)
if(i%2==0)
a[i] = Integer.MAX_VALUE;
Arrays.sort(a);
int t = n;
for(int i=2;i<=t;i++) {
int k = a[i];
if(k==Integer.MAX_VALUE)
break;
for(int j=k;j<=t;j+=k)
a[j] = Integer.MAX_VALUE;
Arrays.sort(a,1,t);
for(int j=1;j<=t;j++)
if(a[j]==Integer.MAX_VALUE) {
t = j;
break;
}
}
int ans = 0;
for(int i=1;i<=n;i++) {
if(a[i]>m && a[i]<n)
ans++;
}
System.out.println(ans);
}
}带分数
import java.util.Scanner;
/**
* 100 可以表示为带分数的形式：100 = 3 + 69258 / 714
*
* 还可以表示为：100 = 82 + 3546 / 197
*
* 注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
*
* 类似这样的带分数，100 有 11 种表示法。
*
* 题目要求：
* 从标准输入读入一个正整数N (N<1000*1000)
* 程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
* 注意：不要求输出每个表示，只统计有多少表示法！
*
*
* 例如：
* 用户输入：
* 100
* 程序输出：
* 11
*
* 再例如：
* 用户输入：
* 105
* 程序输出：
* 6
*
*
* 资源约定：
* 峰值内存消耗（含虚拟机） < 64M
* CPU消耗 < 3000ms
*
*
* 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
*
* 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
* 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
* 注意：主类的名字必须是：Main，否则按无效代码处理。
*/
public class 带分数 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
x = in.nextInt();
dfs(0);
System.out.println(ans);
}
static int ans = 0,n = 9,x;
static int A[] = new int[] {1,2,3,4,5,6,7,8,9};
static void dfs(int m) {
if(m>=9) {
for(int i=1;i<n;i++) {// x = a + b/c x-a =b/c (x-a)*c=b
int a=0;
for(int k=0;k<i;k++)
a = 10*a + A[k];
if(a>x)
break;
for(int j=i+1;j<n;j++) {
int b=0,c=0;
for(int k=i;k<j;k++)
b = 10*b + A[k];
for(int k=j;k<n;k++)
c = 10*c + A[k];
if((x-a)*c==b)
ans++;
}
}
return;
}
for(int i=m;i<n;i++) {
swap(i,m);
dfs(m+1);
swap(i,m);
}
}
private static void swap(int i, int j) {
int t = A[i];
A[i] = A[j];
A[j] = t;
}
}连号区间数
import java.util.Scanner;
/**
* 小明这些天一直在思考这样一个奇怪而有趣的问题：
*
* 在1~N的某个全排列中有多少个连号区间呢？这里所说的连号区间的定义是：
*
* 如果区间[L, R] 里的所有元素（即此排列的第L个到第R个元素）递增排序后能得到一个长度为R-L+1的“连续”数列，则称这个区间连号区间。
*
* 当N很小的时候，小明可以很快地算出答案，但是当N变大的时候，问题就不是那么简单了，现在小明需要你的帮助。
*
* 输入格式：
* 第一行是一个正整数N (1 <= N <= 50000), 表示全排列的规模。
* 第二行是N个不同的数字Pi(1 <= Pi <= N)， 表示这N个数字的某一全排列。
*
* 输出格式：
* 输出一个整数，表示不同连号区间的数目。
*
* 示例：
* 用户输入：
* 4
* 3 2 4 1
*
* 程序应输出：
* 7
*
* 用户输入：
* 5
* 3 4 2 5 1
*
* 程序应输出：
* 9
*
* 解释：
* 第一个用例中，有7个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [2,2], [3,3], [4,4]
* 第二个用例中，有9个连号区间分别是：[1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [3,3], [4,4], [5,5]
*
*
* 资源约定：
* 峰值内存消耗（含虚拟机） < 64M
* CPU消耗 < 5000ms
*
*
* 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
*
* 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
* 注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
* 注意：主类的名字必须是：Main，否则按无效代码处理。
*/
public class 连号区间数 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n+1];
// int[][] max = new int[n+1][n+1];
// int[][] min = new int[n+1][n+1];
for(int i=1;i<=n;i++)
a[i] = in.nextInt();
int ans=0;
for(int i=1;i<=n;i++) {
int max=-1,min=999999999;
for(int j=i;j<=n;j++) {
max = Math.max(max, a[j]);
min = Math.min(min, a[j]);
if(max-min<=j-i)
ans++;
}
}
System.out.println(ans);
}
}
此处评论已关闭