[数据结构与算法]蓝桥杯竞赛训练营结营考核暨第二届“思特奇杯”编程之星算法挑战赛初赛

门牌制作

题目描述：

解题思路：

循环 取模
1 到 2020 循环，然后每次循环保存 i 的值，进入内层循环，取模 10 余 2 说明最后一位存在 2 ，存在即进行sum++，当取模 10 不为 2 时，说明最后一位不是 2 ，此时除 10，去掉最后一位，继续看倒数第二位，最后一位除掉 10 后会为 0 ，此时不满足while 执行条件会跳出循环，接着执行外层循环 ，以此类推。
代码如下：

public class Main{
    public static void main(String[] args){
        int sum =0;
        for(int i = 1; i<= 2020; i++) {
            int temp = i;
            while(temp>0) {
                if(temp%10 == 2) {
                    sum++;
                }
                temp/=10;
            }
        }
        System.out.println(sum);
    }
}

既约分数

题目描述：

解题思路：

欧几里得算法 — 辗转相除法
两个数字同时除以他们中较小的那个数，如果除出来没有余数，那么即可找到最大公约数（也就是最小的那个数字）
互质 要求判断两者最大公约数是否为 1 ，若为 1 则两个数之间互质。

代码如下：

public class Main {
	public static int num(int a, int b) {;
		if (b == 0) 
			return a;
		return num(b, a % b);
	}
	
	public static void main(String[] args) {
		int count = 0;
		for(int i = 1; i <= 2020; i++) {
			for(int j = 1; j <= 2020; j++) {
				if(num(i, j) == 1) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

蛇形填数

题目描述：

解题思路：

找规律
每一个数都是前一个数加上 4*（n-1）。

代码如下：

import java.util.Scanner;
public class Main{
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            System.out.println(sum(n));
        }

        private static int sum(int n) {
            if(n==1) {
                return 1;
            }
            return sum(n-1)+4*(n-1);
        }
}

跑步锻炼

题目描述：

解题思路：

循环 判断

代码如下：

import java.text.SimpleDateFormat;
import java.util.Calendar;

public class Main {
public static void main(String[] args) {
	int sum=2;
	Calendar c1=Calendar.getInstance();
	SimpleDateFormat a=new SimpleDateFormat("yyyyMMdd");
	c1.set(Calendar.YEAR, 2000);
	c1.set(Calendar.MONTH, 0);
	c1.set(Calendar.DAY_OF_MONTH, 1);

	for (int i = 1; i <=10000; i++) {
		c1.add(Calendar.DAY_OF_YEAR,1);
		sum++;
		String date=a.format(c1.getTime());
		char b[]=date.toCharArray();
		if (c1.get(Calendar.DAY_OF_WEEK)==Calendar.MONDAY || (b[6]=='0' && b[7]=='1'))
		 {
			sum=sum+1;
		}	
		if (date.equals("20201001")) {
			break;
		}
	}
	System.out.println(sum);
}
}

七段码

题目描述：

解题思路：

全排序
两层 for 循环全排序

代码如下：

public class Main {
	public static void main(String[] args) {
    Set<String>str=new TreeSet<String>(); 
    String a ="abcdefg";
    System.out.println(a.length());
    int count =0;
    for(int i=0;i<=a.length();i++) {
    	for(int j=i+1;j<=a.length();j++) {
    		str.add(a.substring(i, j));
    	}
    }
    System.out.println(str.size()); 
	}
}

成绩统计

题目描述：

解题思路：

循环 判断

代码如下：

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       int n=scan.nextInt();
       int []arr=new int[n];
       double pass=0,excel=0,fail=0;
        for (int i = 0; i < n; i++) {
            arr[i]=scan.nextInt();
            if(arr[i]<60)
                fail++;
            else if(arr[i]>=60&&arr[i]<85)
                pass++;
            else
                excel++;
        }
        System.out.printf("%d%%\n",Math.round(100*(pass+excel)/n));
        System.out.printf("%d%%\n",Math.round((100*excel)/n));
        scan.close();
    }
}

回文日期

题目描述：

解题思路：

循环 判断
截取用户输入的年份，把年份倒过来再拼接上去形成年月日，再来判断日期是否合法 和 是否符合ABAB 型

代码如下：

import java.util.*;
import java.text.SimpleDateFormat;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String num = Integer.toString(n);
        //
        boolean condition1 = false, condition2 = false;
        // 循环一次加一年
        for (int i = n; !condition1 || !condition2; i += 10000) {
            String date = Integer.toString(i);
            // 截取年份字符串也就是前半部分，再做反转接在后面形成回文
            StringBuffer sb = new StringBuffer(date.substring(0, 4));
            String sb2 = sb.reverse().toString();
            String string = sb.reverse().toString().concat(sb2);
            // 判断回文是否合法
            if (!condition1 && isDate(string) && string.compareTo(num) > 0) {
                System.out.println(string);
                condition1 = true;
            }
            // 加上一个判断是否ABAB型
            if (!condition2 && isDate(string) && string.compareTo(num) > 0 && string.substring(0, 2).equals(string.substring(2, 4))) {
                System.out.println(string);
                condition2 = true;
            }
        }
        scan.close();
    }

    // 判断是否合法日期
    public static boolean isDate(String date) {
        String dt = date.substring(0, 4) + "-" + date.substring(4, 6) + "-" + date.substring(6, 8);
        // 日期格式化
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        try {
            // 设为false能严格验证日期
            sdf.setLenient(false);
            // 解析生成日期 不合法就抛出异常
            sdf.parse(dt);
        } catch (Exception e) {
            return false;
        }
        return true;
    }
}

子串分值和

题目描述：

解题思路：

找规律
对于每一个子串的分值，只有第一次出现在内的字符才会对该子串有贡献
代码如下：

import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner cin = new Scanner(System.in);
            String str =cin.next();
            int[] a = new int[30];
            
            long ans = 0;
            int n = str.length();
            str = " " + str;
            for(int i=1;i<=n;++i) {
                ans+=(i-a[str.charAt(i)-'a'])*(long)1*(n-i+1);
                a[str.charAt(i)-'a']=i;
            }
            System.out.println(ans);
        }
}

平面切分

题目描述：

解题思路：

欧拉定理
欧拉定理结论 每增加一条直线，对平面数增加的贡献值，是其与先前直线的交点数（不包括与已有交点重合的点）+1

代码如下：

#include <iostream>
#include <set>
#include <algorithm>
#include <cstdio>
using namespace std;

long double aa[1010];
long double bb[1010];
long long  n;
set <pair <long double,long double> > s;
pair <long double,long double> p;
int main(){
    long double a,b;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a>>b;
        p.first=a;
        p.second=b;
        s.insert(p);
    }
    int y = 0;
    long long anss=2;
    for(set <pair <long double,long double> > ::iterator it=s.begin();it!=s.end();it++,y++){
        aa[y]=it -> first;
        bb[y]=it -> second;
    }
    for(int k = 1;k < s.size(); k++)
    {
        set<pair<long double, long double> > pos;
        for(int j = k-1;j >= 0; j--)
        {
                if(aa[k]==aa[j])
                        continue;
                long double a1=aa[k],b1=bb[k];
                long double a2=aa[j],b2=bb[j];
                p.first = 1.0*(b2-b1)/(a1-a2);
                p.second = 1.0*a1*((b2-b1)/(a1-a2)) + b1;
                pos.insert(p);
        }
        anss+=pos.size() + 1;
    }
    printf("%lld\n",anss);
    return 0;
}

字串排序

题目描述：

解题思路：

字典序
先确定符合条件的 最短的字符串 有多长，再获取 逆序数 与 V 相同且字典序最小的字符串

代码如下：

import java.util.Scanner;
public class Main {
	static int list[]={//存放后缀序列，这样插和删除很容易
		0,0,0,0,0,//注cccbba=1,2,3,0,……
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0,0,0,0,0,
		0
	};
	static int[] str=new int[300];//存放前缀序列
	static void reset() {//后缀序列清零
		int i=0;
		while(i<26&&list[i]!=0) {
			list[i]=0;
			++i;
		}
	}
	static int getrnum() {//计算逆序数（分三步）
		int cnt=0;
		for(int i=0;str[i]!=0;++i) {//前缀的逆序数
			for(int j=i;str[j]!=0;++j) {
				if(str[i]>str[j]) {
					++cnt;
				}
			}
		}
		for(int i=0;str[i]!=0;++i) {//前缀对后缀的逆序数
			for(int j=25;j>=0;--j) {
				if(str[i]-'a'>j) {
					cnt+=list[j];
				}
			}
		}
		int temp=0;
		for(int i=0;i<26;++i) {//后缀的逆序数
			cnt+=temp*list[i];
			temp+=list[i];
		}
		return cnt;
	}
	static int getinc(int c) {//获得最大逆序增量（特殊步骤中代替求逆序数函数用来提速）（可以认为在数字符串里有多少非c(传入的参数)字符）(也就是插入c逆序数能增加多少)
		int i=0,cnt=0;
		while(str[i]!=0) {
			if(str[i]>(c+'a')) {
				cnt++;
			}
			++i;
		}
		for(i=0;i<26;++i) {
			if(i!=c) {
				cnt+=list[i];
			}
		}
		return cnt;
	}
	static void set() {//在后部序列中插入元素，保证逆序数最大
		int max=0,temp=0,index=0;
		for(int i=0;i<26;++i) {
			list[i]++;
			if((temp=getinc(i))>max) {//找出使逆序数增得最快的字符插入（这里比用增而直接记录逆序数不影响结果，但慢一些，数据10000左右要5秒左右，会超时的，不然我也不会编这么个对于的函数。。）
				index=i;
				max=temp;
			}
			list[i]--;
		}
		list[index]++;
	}
	static void getMaxStr(int l) {//获取前缀确定且长度确定的前提下的最大逆序数字串
		reset();
		for(int i=0;str[i]!=0;++i,--l);
		while(l>0) {
			set();
			--l;
		}
	}
	static void printstr() {//打印目标字符串
		String Str="";
		int i=0;
		while(str[i]!=0) {
			Str+=(char)str[i];
			++i;
		}
		for(i=25;i>=0;--i) {//这里其实没用，既然不执行也不会影响效率，留着吧，后缀最后是空的，但曾经存在过。。。
			for(int j=0;j<list[i];++j) {
				Str+=(char)(i+'a');
			}
		}
		System.out.println(Str);
	}
	static void getans(int num,int l) {//l是字串长度
		for(int i=0;i<l;++i) {
			for(int j=0;j<26;++j) {//每个位从a开始试
				str[i]=j+'a';
				getMaxStr(l);//获取指定前缀最大逆字串
				if(getrnum()>=num) {//超了就下一个
					break;
				}
			}
		}
	}
	public static void main(String[] args){//这了很简洁了
		int num;
		Scanner sc = new Scanner(System.in);
		num=sc.nextInt();//获取输入
		sc.close();
		int l=0;
		while(getrnum()<num) {//获取最短字串长
			++l;
			getMaxStr(l);
		}
		getans(num,l);//获得目标字串
		printstr();//打印
	}
}