Problem Set
1000
高精度
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
System.out.println(sc.nextBigInteger().add(sc.nextBigInteger()));
}
}
}1001
位运算防爆 1000题的阴影
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
long num= sc.nextLong();
System.out.println((1+num)*num>>>1);
}
}
}1002
还是开大数
记得输出没有空格
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
long cnt=1;
long n= sc.nextLong();
for (long i = 0; i < n; i++) {
BigInteger b1=sc.nextBigInteger();
BigInteger b2=sc.nextBigInteger();
System.out.println("Case"+cnt+":");
System.out.println(b1+"+"+b2+"="+b1.add(b2));
cnt++;
}
}
}1003
将双层for循环替换成剪枝 还是没过
线性遍历过了 时间复杂度为O(2n)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int cnt = 1;
long t = sc.nextLong();
for (long i = 0; i < t; i++) {
int n = sc.nextInt();
long arr[] = new long[n + 1];
long ans[] = new long[n + 1];
for (int i1 = 1; i1 <= n; i1++) {
arr[i1] = sc.nextLong();
ans[i1] = arr[i1] + ans[i1 - 1];
}
long max = Integer.MIN_VALUE;
int left = -1;
int right = -1;
long min = 0;
for (int i1 = 1; i1 <= n; i1++) {
if (ans[i1] - min > max) {
max = ans[i1] - min;
right = i1;
left = findLeftIndex(ans, min, i1);
}
min = Math.min(min, ans[i1]);
}
System.out.println("Case " + cnt + ":");
System.out.println(max + " " + left + " " + right);
cnt++;
}
}
private static int findLeftIndex(long[] ans, long min, int endIndex) {
for (int i = 0; i < endIndex; i++) {
if (ans[i] == min) {
return i + 1;
}
}
return -1;
}
}
1004
用java特有双列集合
默认开哈希 速度快
最后再遍历一次即可 时间复杂度O(n)
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while (sc.hasNext()){
long n= sc.nextLong();
if(n==0)return;
//双列集合存储
Map<String,Long>map=new HashMap<>();
for (long i = 0; i < n; i++) {
//输入键
String str= sc.next();
//如果集合有键 把键对应的数值拿出来 加1 再放回去
if(map.containsKey(str)){
long num=map.get(str);
num++;
map.put(str,num);
}
//如果集合里没有键 把（键，1）放到集合里面去
else map.put(str,1L);
}
//把键放到一个单列集合里
Set<String> set=map.keySet();
String s="";
long ans=0;
//遍历单列集合 找到值最大的键 记录
for (String str : set) {
if(map.get(str)>ans){
s=str;
ans=map.get(str);
}
}
System.out.println(s);
}
}
}1005
有取余必出现周期
对7取余就只能出现0到7
第三个数由第一个和第二个决定
两两组合 7*7 周期为49
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
long a = sc.nextLong();
long b = sc.nextLong();
long n = sc.nextLong();
if (a == 0 && b == 0 && n == 0) return;
//最大周期为49
n %= 49;
long ans1=1;
long ans2=1;
long ans3=1;
if(n==1) System.out.println(1);
else if(n==2) System.out.println(1);
else {
for (long i = 0; i < n - 2; i++) {
ans3=(a*ans2+b*ans1)%7;
ans1=ans2;
ans2=ans3;
}
System.out.println(ans3);
}
}
}
}1006
数学题 恶心人
import java.util.Scanner;
public class Main {
// 定义常量
static final int maxn = 12 * 60 * 60;
static double hm, hs, ms;
static double T_hm, T_hs, T_ms;
// 初始化函数
static void init() {
double h = 1.0 / 120;
double m = 1.0 / 10;
double s = 6;
hm = m - h;
hs = s - h;
ms = s - m;
T_hm = 360 / hm;
T_hs = 360 / hs;
T_ms = 360 / ms;
}
// 最大值函数
static double max(double a, double b, double c) {
return Math.max(Math.max(a, b), c);
}
// 最小值函数
static double min(double a, double b, double c) {
return Math.min(Math.min(a, b), c);
}
// 主函数
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
init();
while (scanner.hasNext()) {
double n = scanner.nextDouble();
if (n == -1) break;
double[] a = new double[6];
a[0] = n / hm;
a[1] = n / hs;
a[2] = n / ms;
a[3] = (360 - n) / hm;
a[4] = (360 - n) / hs;
a[5] = (360 - n) / ms;
double ans = 0;
for (double i = 0; i <= maxn; i += T_hm) {
for (double j = 0; j <= maxn; j += T_hs) {
if (j + a[1] > i + a[3]) break;
if (i + a[0] > j + a[4]) continue;
for (double k = 0; k <= maxn; k += T_ms) {
if (k + a[2] > i + a[3] || k + a[2] > j + a[4]) break;
if (i + a[0] > k + a[5] || j + a[1] > k + a[5]) continue;
double p = max(i + a[0], j + a[1], k + a[2]);
double q = min(i + a[3], j + a[4], k + a[5]);
if (q > p) {
ans += q - p;
}
}
}
}
double percentage = 100.0 * ans / maxn;
System.out.printf("%.3f\n", percentage);
}
scanner.close();
}
}
1007
不会
而且没看懂题解
分治算法是什么玩意
1008
枚举吧
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n= sc.nextInt();
if(n==0)return;
int ans=0;
int sum=0;
for (int i = 0; i < n; i++) {
int temp= sc.nextInt();
if(temp>ans){
sum+=(temp-ans)*6;
}
else if(temp<ans){
sum+=(ans-temp)*4;
}
ans=temp;
sum+=5;
}
System.out.println(sum);
}
}
}1009
贪心
先解性价比最高的做法
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while (sc.hasNext()){
int n= sc.nextInt();
int m= sc.nextInt();
if(n==-1&&m==-1)return;
int arr1[]=new int[m];
int arr2[]=new int[m];
double arr3[]=new double[m];
for (int i = 0; i < m; i++) {
arr1[i]= sc.nextInt();
arr2[i]= sc.nextInt();
arr3[i]=arr1[i]*1.0/arr2[i];
}
double max=0;//性价比
int ans=0;//记录最大值
double sum=0;
while (n>0){
for (int i = 0; i < m; i++) {
if(arr3[i]>max){
max=arr3[i];
ans=i;
}
}
if(max==0)break;
if(n>arr2[ans]){
sum+=arr1[ans];
arr3[ans]=0;
n-=arr2[ans];
}
else {
sum+=arr3[ans]*n*1.0;
n=0;
}
max=0;
}
System.out.println(String.format("%.3f",sum));
}
}
}
