蓝桥杯题库 历届试题部分（C++、Java）代码实现（31-45）

将定期更新蓝桥杯习题集的解题报告~

五、历届试题

PREV-31 小朋友排队

简记：树状数组维护
设：
f(i)=a[i]左边严格大于a[i]的元素个数。
g(i)=a[i]右边严格小于a[i]的元素个数。
则：
a[i]的不高兴度为：1+2+…+f(i) + 1+2+…+g(i);

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100052;
typedef long long int qq;
int n;
struct Data {
    int val, id;
} a[maxn];
int p[maxn], c[maxn];
qq f(qq x) { return (x + 1) * x / 2; }
bool operator<(Data x, Data y) { return x.val < y.val; }
bool cmp_id(Data x, Data y) { return x.id < y.id; }
struct Bit_tree {
    int a[maxn], size;
    int lowbit(int x) { return x & (-x); }
    void init(int x) {
        size = x;
        for (int i = 0; i <= size; i++) {
            a[i] = 0;
        }
    }
    void push(int pos, int val) {
        while (pos <= size) {
            a[pos] += val;
            pos += lowbit(pos);
        }
    }
    int ask(int pos) {
        int ret = 0;
        while (pos > 0) {
            ret += a[pos];
            pos -= lowbit(pos);
        }
        return ret;
    }
    int ask(int l, int r) {
        if (l > r) return 0;
        return ask(r) - ask(l - 1);
    }
};
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].val);
        a[i].id = i;
    }
    ///离散化
    sort(a + 1, a + 1 + n);
    int now = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i].val > a[i - 1].val) now++;
        c[i] = now;
    }
    for (int i = 1; i <= n; i++) {
        a[i].val = c[i];
    }
    ///树状数组统计 p
    sort(a + 1, a + 1 + n, cmp_id);
    memset(p, 0, sizeof(p));
    Bit_tree tr;
    tr.init(now);
    for (int i = 1; i <= n; i++) {  // a[i]左边比a[i]大的元素
        p[i] += tr.ask(a[i].val + 1, now);
        tr.push(a[i].val, 1);
    }
    tr.init(now);
    for (int i = n; i > 0; i--) {  // a[i]右边比a[i]小的元素
        p[i] += tr.ask(1, a[i].val - 1);
        tr.push(a[i].val, 1);
    }
    qq ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += f(p[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	static int N = 100010;
	static int MAX = 1000100;

	static int[] C = new int[MAX];
	static int[] S = new int[MAX];
	static int[] b = new int[N];
	static long[] total = new long[N];
	static long ans;
	static int[] num = new int[N];
	static int T, s, t, i, j;

	static int Lowbit(int x) {
		return x & (-x);
	}

	static void add(int pos, int num, int[] P) {
		while (pos <= MAX) {
			P[pos] += num;
			pos += Lowbit(pos);
		}
	}

	static int Sum(int end, int[] P) {
		int cnt = 0;
		while (end > 0) {
			cnt += P[end];
			end -= Lowbit(end);
		}
		return cnt;
	}

	static void init() {
		total[0] = 0;
		for (int i = 1; i < N; ++i) {
			total[i] = total[i - 1] + i;
		}
	}

	public static void main(String[] args) throws IOException {
		init();
		BufferedReader buf = new BufferedReader(
				new InputStreamReader(System.in));
		T = Integer.parseInt(buf.readLine());
		String[] str = buf.readLine().split(" ");
		for (int j = 0; j < T; j++) {
			num[j] = Integer.parseInt(str[j]);
			add(num[j] + 1, 1, C);
			b[j] = j - Sum(num[j], C);
										
			b[j] -= Sum(num[j] + 1, C) - Sum(num[j], C) - 1;

		}

		ans = 0;
		for (int j = T - 1; j > -1; --j) {
			add(num[j] + 1, 1, S);
			b[j] += Sum(num[j], S);

			ans += total[b[j]];
		}

		System.out.println(ans);

	}

}

PREV-32 分糖果

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int a[1100] = {0};
int n;
int num = 0;

bool is_same() {
    for (int i = 0; i < n; i++) {
        if (a[0] != a[i]) return 0;
    }
    return 1;
}

void change() {
    int b[1100] = {0};
    for (int i = 0; i < n; i++) {
        a[i] = a[i] / 2;
        b[i + 1] = a[i];
    }
    a[0] = a[0] + b[n];
    for (int i = 1; i < n; i++) {
        a[i] = a[i] + b[i];
    }
}

void add() {
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 1) {
            num++;
            a[i]++;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    while (1) {
        if (is_same()) break;
        change();
        add();
    }
    cout << num;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public  class Main
{
	static int m,n;
	public static void main(String[] args) throws IOException
	{
		int candy=0;
		BufferedReader buf;		
		String str1,str2;
		buf=new BufferedReader(new InputStreamReader(System.in));
		str1=buf.readLine();
		m=Integer.parseInt(str1);
		int b[]=new int[m];
		str2=buf.readLine();
		String a[]=str2.split(" ");
		for(int i=0;i<m;i++)
		{
			b[i]=Integer.parseInt(a[i]);
		}
		if(!equal(b))
		{
			while(true)
			{
				n=b[m-1];
				for(int i=m-1;i>0;i--)
				{
					b[i]=b[i-1]/2+b[i]/2;
				}
				b[0]=b[0]/2+n/2;
				if(equal(b))
					break;
				else
				{
					for(int i=0;i<m;i++)
					{
						if(b[i]%2!=0)
						{
							candy++;
							b[i]++;
						}
					}
				}
			}
		}
		System.out.println(candy);
		
	}
	public static boolean equal(int a[])
	{
		int num=0;
		for(int i=0;i<m-1;i++)
		{
			if(a[i]==a[i+1])
				num++;
		}
		if(num==m-1)
		{
			return true;
		}
		else 
			return false;
		
	}
}

PREV-33 兰顿蚂蚁

//简单模拟
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
int l[5] = {0, 4, 1, 2, 3};  //左转数组
int r[5] = {0, 2, 3, 4, 1};  //右转数组
int movex[5] = {0, 0, 1, 0, -1};
int movey[5] = {0, -1, 0, 1, 0};
bool color[150][150] = {0};
int x, y;  //起始坐标(x,y)
int f;

void move()  //在点(x,y)朝向f
{
    if (color[y][x] == 1)  //如果是黑砖,右转90度，将该格改为白格，并向前移一格；
    {
        f = r[f];
        color[y][x] = 0;
        x = x + movex[f];
        y = y + movey[f];

    } else  //若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。
    {
        f = l[f];
        color[y][x] = 1;
        x = x + movex[f];
        y = y + movey[f];
    }
}

int main() {
    int m, n;
    cin >> m >> n;  // m行n列
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &color[i][j]);
        }
    }
    int k;
    char s;  //上下左右分别用：U1,D3,L4,R2
    cin >> y >> x;
    scanf(" %c", &s);
    if (s == 'U') f = 1;
    if (s == 'R') f = 2;
    if (s == 'D') f = 3;
    if (s == 'L') f = 4;
    cin >> k;
    /*if(k==0)
    {
            cout<<y<<" "<<x;
            return 0;
    }
    x=x+movex[f];
    y=y+movey[f];*/
    for (int i = 0; i < k; i++) {
        move();
    }
    cout << y << " " << x;
    return 0;
}

import java.io.*;

public class Main {
	static int n, m;
	static int s, e;
	static char[] chs = { 'L', 'U', 'R', 'D', 'L' };
	static int count = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1[] = br.readLine().split(" ");
		n = Integer.parseInt(s1[0]);
		m = Integer.parseInt(s1[1]);

		int[][] arr = new int[n][m];
		for (int a = 0; a < n; a++) {
			String str[] = br.readLine().split(" ");
			for (int b = 0; b < m; b++) {
				arr[a][b] = Integer.parseInt(str[b]);
			}
		}

		int x, y;
		String s2[] = br.readLine().split(" ");
		x = Integer.parseInt(s2[0]);
		y = Integer.parseInt(s2[1]);

		char dec = s2[2].charAt(0);

		int z;
		z = Integer.parseInt(s2[3]);

		s = x;
		e = y;
		while (count < z) {
			if (arr[s][e] == 1) {
				for (int i = 0; i < chs.length; i++) {
					if (dec == chs[i]) {
						dec = chs[i + 1];
						break;
					}
				}
				arr[s][e] = 0;
				func(dec, s, e);

			}

			if (arr[s][e] == 0) {
				for (int j = 1; j < chs.length; j++) {
					if (dec == chs[j]) {
						dec = chs[j - 1];
						break;
					}
				}
				arr[s][e] = 1;
				func(dec, s, e);

			}
		}
		System.out.print(s + " " + e);
	}

	public static void func(char dec, int x, int y) {
		if (dec == 'L') {
			e -= 1;
			count++;
		}
		if (dec == 'U') {
			s -= 1;
			count++;
		}
		if (dec == 'R') {
			e += 1;
			count++;
		}
		if (dec == 'D') {
			s += 1;
			count++;
		}
	}
}

PREV-34 矩阵翻硬币

简记：
思路：m*n的方格，ans = sqrt(m)*sqrt(n); 向下取整floor。大数据，二分求根号。
注：模拟十进制只能90分，压万进制可以满分

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
const int bit = 10000;
struct Bnum {
    int a[maxn / 4], len;
    void input() {
        memset(a, 0, sizeof(a));
        char temp[maxn / 2];
        scanf("%s", temp);
        len = strlen(temp);
        for (int i = 0, j = len - 1; j >= 0; i++, j -= 4) {
            a[i] += (temp[j] - '0');
            if (j - 1 >= 0) a[i] += (temp[j - 1] - '0') * 10;
            if (j - 2 >= 0) a[i] += (temp[j - 2] - '0') * 100;
            if (j - 3 >= 0) a[i] += (temp[j - 3] - '0') * 1000;
        }
        len = (len - 1) / 4 + 1;
    }
    void print() {
        for (int i = len - 1; i >= 0; i--) {
            if (i == len - 1)
                printf("%d", a[i]);
            else
                printf("%04d", a[i]);
        }
        printf("\n");
    }
} e, o;
void init() {
    memset(e.a, 0, sizeof(e.a));
    e.len = 1;
    e.a[0] = 1;
    memset(o.a, 0, sizeof(o.a));
    o.len = 1;
}
bool operator<=(Bnum x, Bnum y) {
    if (x.len != y.len) return x.len < y.len;
    int pos = x.len - 1;
    while (pos >= 0) {
        if (x.a[pos] == y.a[pos]) {
            pos--;
            continue;
        }
        return x.a[pos] <= y.a[pos];
    }
    return 1;
}
Bnum operator+(Bnum x, Bnum y) {
    Bnum ret = o;
    ret.len = max(x.len, y.len);
    for (int i = 0; i < ret.len; i++) {
        ret.a[i] = x.a[i] + y.a[i];
    }
    for (int i = 0; i < ret.len; i++) {
        ret.a[i + 1] += ret.a[i] / bit;
        ret.a[i] %= bit;
    }
    if (ret.a[ret.len] != 0) ret.len++;
    return ret;
}
Bnum operator+(Bnum x, int y) {  //+1
    Bnum ret = x;
    ret.a[0] += y;
    int p = 0;
    for (int i = 0; i < ret.len; i++) {
        if (ret.a[i] / bit == 0) break;
        ret.a[i + 1] += ret.a[i] / bit;
        ret.a[i] %= bit;
    }
    if (ret.a[ret.len] != 0) ret.len++;
    return ret;
}
Bnum operator-(Bnum x, int y) {  //-1
    Bnum ret = x;
    ret.a[0] -= y;
    for (int i = 0; i < ret.len; i++) {
        if (ret.a[i] >= 0) break;
        ret.a[i + 1]--;
        ret.a[i] += bit;
    }
    if (ret.a[ret.len - 1] == 0) ret.len--;
    if (ret.len == 0) ret.len++;
    return ret;
}
Bnum operator*(Bnum x, Bnum y) {
    Bnum ret = o;
    for (int i = 0; i < x.len; i++) {
        for (int j = 0; j < y.len; j++) {
            ret.a[i + j] += x.a[i] * y.a[j];
        }
    }
    ret.len = x.len + y.len - 1;
    for (int i = 0; i < ret.len; i++) {
        ret.a[i + 1] += ret.a[i] / bit;
        ret.a[i] %= bit;
    }
    if (ret.a[ret.len] != 0) ret.len++;
    return ret;
}
Bnum operator/(Bnum x, int k) {  //除2下取整
    Bnum ret = x;
    for (int i = ret.len - 1; i >= 0; i--) {
        if (i != 0) ret.a[i - 1] += bit * (ret.a[i] & 1);
        ret.a[i] >>= 1;
    }
    if (ret.a[ret.len - 1] == 0) ret.len--;
    return ret;
}
Bnum sqrt(Bnum x) {
    Bnum l = e, r = x, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        // printf("l=");   l.print();
        // printf("r=");   r.print();
        // printf("mid="); mid.print();
        if ((mid * mid) <= x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l - 1;
}
void test() {
    Bnum x;
    long long int y;
    x.input();
    x.print();
    scanf("%lld", &y);
    printf("%lld\n", (long long int)sqrt(y));
    x = sqrt(x);
    x.print();
    x = x * x;
    x.print();
}
int main() {
    init();
    // while(1)test();
    Bnum x, y;
    x.input();
    y.input();
    Bnum ans = sqrt(x) * sqrt(y);
    ans.print();
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {


	public static void main(String[] args) throws Exception {
		/*n = Reader_09.nextInt();
		m = Reader_09.nextInt();*/
		
		//由于数目很大,所以不能用netxInt() 所以用String 最后转换成bigInteger
		String n = Reader_10.next();
		String m = Reader_10.next();
		
		System.out.println(sqrt(n).multiply(sqrt(m)));
		
	}

	private static BigInteger sqrt(String s) {
		
		//存一下数字的长度
		int length = s.length();
		//操作的位数
		int len = 0;
		//偶数
		if (length % 2 == 0) {
			len=length/2;
		}else {
			len=length/2+1;
		}
		char[] sArr = new char[len];
		//将字符数组默认位数上的数都填充为0
		Arrays.fill(sArr, '0');
		//转换成大整数
		BigInteger target = new BigInteger(s);
		for (int pos = 0; pos < len; pos++) {
			//从1~9开始尝试
			for (char c = '1'; c <= '9'; c++) {
				sArr[pos] = c;//在pos这个位置上尝试
				//转换成字符串,填入biginteger ,并用bigInteger的性质平方
				BigInteger pow = new BigInteger(String.valueOf(sArr)).pow(2);
				//大整数的比较方法
				if (pow.compareTo(target) == 1) {
					//如果用2超出了,就填1,如果8超出了,就填7
					sArr[pos] -= 1;
					break;
				}
			}
		}
		
		
		return new BigInteger(String.valueOf(sArr));
		
		
	}

}
class Reader_10 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(
			System.in));
	static StringTokenizer tokenizer = new StringTokenizer("");

	static String next() throws Exception {
		while (!tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(br.readLine());
		}
		return tokenizer.nextToken();
	}

	static int nextInt() throws Exception {
		return Integer.parseInt(next());
	}

}

PREV-35 正则问题

简记：
对于解决带括号的表达式求解问题，递归比较方便。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
char s[maxn];
int f(int &l, int r) {
    int ret = 0;
    while (l < r) {
        // printf("%d %c %d\n",l,s[l],ret);
        if (s[l] == 'x') {
            l++;
            ret++;
        }
        if (s[l] == '(') {
            l++;
            ret += f(l, r);
        }
        if (s[l] == '|') {
            l++;
            return max(ret, f(l, r));
        }
        if (s[l] == ')') {
            l++;
            return ret;
        }
    }
    return ret;
}
int main() {
    scanf("%s", s);
    int x = 0;
    printf("%d\n", f(x, strlen(s)));
    return 0;
}

import java.util.Scanner;
public class Main {

	static int position =0;
	static char [] a;
	public static void main(String[] args) {
		
		
			Scanner in =new Scanner (System.in);
			String str=in.nextLine();
			a=str.toCharArray();
			in.close();
			System.out.println(read());
		
		
	}
	static int  read() {
		int max=0;
		int temp=0;
		while(position<a.length) {
			if(a[position]=='(') {position++;max+=read();continue;}
			
			if(a[position]=='x') {position++;max++;continue;}
			if(a[position]=='|') {position++;temp=max(max,temp);max=0;continue;}
			if(a[position]==')') {position++;return max(max,temp);}
			
			
			
		}
		return max(max,temp);
			
			
			
	}
	private static int max(int max, int temp) {
		if(max>=temp)return max;
		else return temp;
	}	
}

PREV-36 包子凑数

简记：数论常识+打表找规律

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int a[maxn], n;
bool vis[maxn * maxn];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int gcd = a[0];
    for (int i = 1; i < n; i++) {
        gcd = __gcd(gcd, a[i]);
    }
    if (gcd != 1) {
        printf("INF\n");
    } else {
        vis[0] = 1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < maxn * maxn; j++) {
                if (j - a[i] >= 0) {
                    vis[j] = max(vis[j], vis[j - a[i]]);
                }
            }
        }
        bool first = 1;
        for (int i = 0; i < maxn * maxn; i++) {
            if (!vis[i]) {
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n =in.nextInt();//有几个笼子
        int[] a = new int[n];//存储每个笼子能够装多少包子
        int[] number=new int[10001];//存储能够凑齐的包子数量
        int count=0;
        for (int i=0;i<n;i++){
            a[i]=in.nextInt();
            number[a[i]]=1;
        }
        int g=a[0];
        for (int i =1;i<a.length;i++){
            g=gcd(g,a[i]);
        }
        if (g!=1){
            System.out.println("INF");
        }else {
            for (int i=0;i<a.length;i++){
                for (int j=0;j+a[i]<10001;j++){
                    if (number[j]==1) number[j+a[i]]=1;
                }
            }
            for (int i=0;i<10001;i++){
                if (number[i]==0) count++;
            }
            System.out.println(count-1);//减去number[0]的情况
        }
    }

    //求最大公约数
    public  static  int  gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}

PREV-37 分巧克力

简记：整体二分答案

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
typedef long long int qq;
struct choc {
    qq h, w;
} a[maxn];
int n;
qq k;
qq f(int x, choc p) { return (p.h / x) * (p.w / x); }
bool is_ok(int x) {
    qq ans = 0;
    for (int i = 0; i < n; i++) {
        ans += f(x, a[i]);
    }
    return ans >= k;
}
int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld", &a[i].w, &a[i].h);
    }
    int l = 1, r = 1e5;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (is_ok(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%d\n", l - 1);
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static class InputReader{
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		
		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream),32768);
			tokenizer = null;
		}
		
		public String next() {
			while(tokenizer == null || !tokenizer.hasMoreElements()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				}catch(IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
	public static void main(String[] args) {
		InputReader s = new InputReader(System.in);
		int n = s.nextInt();
		int k = s.nextInt();
		int h[] = new int[n];
		int w[] = new int[n];
		for(int i=0;i<n;i++) {
			h[i] = s.nextInt();
			w[i] = s.nextInt();
		}
		int l=1,r=100000,ans=1;
		while(l<=r) {
			int mid = (l+r)/2;
			int t = 0;
			for(int i=0;i<n;i++) {
				t+=(h[i]/mid)*(w[i]/mid);
				if(t>=k) {
					l = mid+1;
					ans = mid;
					continue;
				}
			}
			if(t<k) {
				r = mid-1;
			}
		}
		System.out.println(ans);
		
	}
}

PREV-38 油漆面积

简记：本来是线段树扫描线的，暴力冲过去了

#include<bits/stdc++.h>
using namespace std;
bool book[10005][10005];
int main(int argc,char **argv)
{
	int cnt,sum=0;
	scanf("%d",&cnt);
	while(cnt--)
	{
		int x1,x2,y1,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		int i,j;
		for(i=x1;i<x2;i++)
			for(j=y1;j<y2;j++)
			{
				if(book[i][j]==false)
				{
					book[i][j]=true;
					sum++;
				}
			}
	}
	printf("%d\n",sum);
	return 0;
}

PREV-39 日期问题

简记：模拟

#include <bits/stdc++.h>
using namespace std;
struct data {
    int y, m, d;
    void print() { printf("%d-%02d-%02d\n", y, m, d); }
} s, t;
int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool is_run(int x) {
    if (x % 100 == 0) {
        return x % 400 == 0;
    }
    return x % 4 == 0;
}
data operator+(data x, int ppp) {  //+1
    data ret = x;
    ret.d++;
    if (ret.d > day[ret.m] + (ret.m == 2 && is_run(ret.y))) {
        ret.d = 1;
        ret.m++;
        if (ret.m == 13) {
            ret.m = 1;
            ret.y++;
        }
    }
    return ret;
}
bool operator==(data l, data r) {
    return l.y == r.y && l.m == r.m && l.d == r.d;
}
bool operator<=(data l, data r) {
    if (l.y != r.y) {
        return l.y < r.y;
    }
    if (l.m != r.m) {
        return l.m < r.m;
    }
    return l.d <= r.d;
}
void init() {
    s.y = 1960;
    s.m = 1;
    s.d = 1;
    t.y = 2059;
    t.m = 12;
    t.d = 31;
}
int a, b, c;
bool is_ok(data x) {
    if (x.y % 100 == a && x.m == b && x.d == c) return 1;
    if (x.y % 100 == c && x.m == a && x.d == b) return 1;
    if (x.y % 100 == c && x.m == b && x.d == a) return 1;
    return 0;
}
int main() {
    init();
    scanf("%d/%d/%d", &a, &b, &c);
    for (data i = s; i <= t; i = i + 1) {
        if (is_ok(i)) i.print();
    }
    return 0;
}

import java.util.Scanner;
import java.util.TreeSet;


public class Main {

	/**
	 * @param args
	 * @return 
	 */
	public static java.lang.String rq(int a, int b, int c){
		if(a>=0 && a<=59) a = a + 2000;
		else if(a>=60 && a<=99) a = a + 1900;
		else
			return "";
		
		if(b<1 || b>12)
			return "";
		if(c<1 || c>31)
			return "";
		switch(b){
			case 2:
				boolean temp = run(a);
				if(temp){
					if(c>29) return "";}
				else
					if(c>28) 
						return "";
				break;
			case 4:
				if(c>30) return "";
				break;
			case 6:
				if(c>30) return "";
				break;
			case 9:
				if(c>30) return "";
				break;
			case 11:
				if(c>30) return "";
				break;
			
		}
		String _a,_b,_c;
		_a = String.valueOf(a);
		_b = String.valueOf(b);
		_c = String.valueOf(c);
		if(_b.length() == 1)
			_b = "0"+_b;
		if(_c.length() == 1)
			_c = "0"+_c;
		
		return _a+"-"+_b+"-"+_c;
			
	}
	public static boolean run(int a){
		if((a%4==0 && a%100!=0) || a%400==0)
			return true;
		else
			return false;
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner reader = new Scanner(System.in);
		String s = reader.next();
		String _a,_b,_c;
		_a = s.substring(0, 2);
		_b = s.substring(3, 5);
		_c = s.substring(6, 8);
		int a,b,c;
		a = Integer.parseInt(_a);
		b = Integer.parseInt(_b);
		c = Integer.parseInt(_c);
		_a=rq(a,b,c);
		_b=rq(c,a,b);
		_c=rq(c,b,a);
		TreeSet<String> ss = new TreeSet<String>();
		if(_a.length()!=0) ss.add(_a);
		if(_b.length()!=0) ss.add(_b);
		if(_c.length()!=0) ss.add(_c);
		for(String sss : ss){
			System.out.println(sss);
		}
	}
	

}

PREV-40 k倍区间

简记：简单维护思想

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
typedef long long int qq;
int n, a[maxn], c[maxn], s[maxn], k;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        s[i] = (s[i - 1] + a[i]) % k;
        c[s[i]]++;
    }
    qq ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += c[s[i - 1]];
        c[s[i]]--;
    }
    printf("%lld\n", ans);
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

public class Main {

	private static long ans = 0L;
	private static int num;

	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n = (int) in.nval;
		in.nextToken();
		int k = (int) in.nval;
		ans = 0;		
	
		int[] sum = new int[100005];
	
		int[] cnt = new int[100005];
		cnt[0] = 1;
		for (int i = 1; i <= n; i++) {
			in.nextToken();
			int t = (int) in.nval;
			sum[i] = (sum[i - 1] + t) % k;
			ans += cnt[sum[i]];
			cnt[sum[i]]++;
		}
		out.println(ans);
		out.flush();
	}

}

PREV-41 Excel地址

简记：进制知识

#include <bits/stdc++.h>
using namespace std;
typedef long long int qq;
int a[100];
int main() {
    qq n;
    while (scanf("%lld", &n) != EOF) {
        int cnt = 0;
        while (n) {
            if (n % 26 == 0) {
                a[cnt++] = 26;
                n /= 26;
                n--;
            } else {
                a[cnt++] = n % 26;
                n /= 26;
            }
        }
        for (int i = cnt - 1; i >= 0; i--) {
            char c = 'A' + a[i] - 1;
            printf("%c", c);
        }
        printf("\n");
    }
    return 0;
}

import java.util.Scanner;

public class Main {
	
	
	public static void main(String[] args){
		
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		char[] c = new char[100];
		int cnt = 0;
		
		while(n!=0){//500
			if(n%26==0){
				c[cnt++]=26+64;
				n/=26;//19 // 0
				n--;//18 //-1
			}else{
				c[cnt++]=(char) (n%26+64);//
				n/=26;//n=1
			}
			
		}
		for(int i=cnt-1;i>=0;i--)
			System.out.print(c[i]);
		
	}

}

PREV-42 九宫幻方

简记：dfs暴力搜索即可

#include <bits/stdc++.h>
using namespace std;
int a[3][3], ans[3][3];
int vis[10], num = 0;
bool is_ok() {
    int e = (1 + 9) * 9 / 2;
    e /= 3;
    for (int i = 0; i < 3; i++) {
        int s1 = 0, s2 = 0;
        for (int j = 0; j < 3; j++) {
            s1 += a[i][j];
            s2 += a[j][i];
        }
        if (s1 != e || s2 != e) return 0;
    }
    if (a[0][0] + a[1][1] + a[2][2] != e) return 0;
    if (a[0][2] + a[1][1] + a[2][0] != e) return 0;
    return 1;
}
void out() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    printf("-----\n");
}
void dfs(int dep) {
    if (num == 2) return;
    if (dep == 9) {
        // out();
        if (is_ok()) {
            num++;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++) {
                    ans[i][j] = a[i][j];
                }
        }
        return;
    }
    int x = dep % 3, y = dep / 3;
    // printf("dep=%d (%d,%d)=%d \n",dep,x,y,a[x][y]);
    if (a[x][y] != 0)
        dfs(dep + 1);
    else {
        for (int i = 1; i <= 9; i++) {
            if (vis[i]) continue;
            a[x][y] = i;
            vis[i] = 1;
            dfs(dep + 1);
            a[x][y] = 0;
            vis[i] = 0;
        }
    }
}
int main() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &a[i][j]);
            vis[a[i][j]]++;
        }
    }
    dfs(0);
    if (num == 1) {
        for (int i = 0; i < 9; i++) {
            printf("%d", ans[i / 3][i % 3]);
            if (i % 3 == 2)
                printf("\n");
            else
                printf(" ");
        }
    } else {
        printf("Too Many\n");
    }
    return 0;
}

PREV-43 拉马车

#include <stdio.h>
#include <string.h>
void StartGame(char *HandCardA, char *HandCardB, char *TableCard);
int CheckCard(char TableCard[]);
void GetCard(char *GettedString, int keyStay, char *TableCard);
int EndGame(char EndString[]);
void GetCardRealHand(char *ChangedString);
int NumberCard;
int main() {
    char HandCardA[30];           // A手中的牌
    char HandCardB[30];           // B手中的牌
    char TableCard[60] = {'\0'};  //桌面上的牌

    gets(HandCardA);  //获取A的手牌
    gets(HandCardB);  //获取B的手牌

    NumberCard = strlen(HandCardA) +
                 strlen(HandCardB);  //获取总牌数（作为一种程序结束条件）

    StartGame(HandCardA, HandCardB, TableCard);  // Strat Game
}

void StartGame(char *HandCardA, char *HandCardB, char *TableCard) {
    int HandSortOrder = 0;  //用于判断出牌顺序
    while (1) {
        if (HandSortOrder % 2 == 0)  // turn:A   (:first)
        {
            strncat(TableCard, HandCardA, 1);
            GetCardRealHand(HandCardA);
            HandSortOrder += 1;
            if (CheckCard(TableCard) >= 0) {
                GetCard(HandCardA, CheckCard(TableCard), TableCard);
                HandSortOrder += 1;
            }
            if (EndGame(HandCardA) == 1) {
                puts(HandCardA);
                break;
            } else if (EndGame(HandCardA) == 2) {
                puts(HandCardB);
                break;
            }

        } else  // turn B
        {
            strncat(TableCard, HandCardB, 1);
            GetCardRealHand(HandCardB);
            HandSortOrder += 1;
            if (CheckCard(TableCard) >= 0) {
                GetCard(HandCardB, CheckCard(TableCard), TableCard);
                HandSortOrder += 1;
            }
            if (EndGame(HandCardB) == 1) {
                puts(HandCardB);
                break;
            } else if (EndGame(HandCardB) == 2) {
                puts(HandCardA);
                break;
            }
        }
    }
}

int CheckCard(char TableCard[])  //查询是否有与之前相同的牌，并返回牌的下表
{
    int LenTableCard = strlen(TableCard), i;
    for (i = 0; i < LenTableCard - 1; i++) {
        if (TableCard[LenTableCard - 1] == TableCard[i]) {
            return i;
        }
    }
    return -1;
}

void GetCard(char *GettedString, int keyStay, char *TableCard)  //从桌面上获取牌
{
    int LenTableCard = strlen(TableCard), i;
    // strncat(GettedString, TableCard + keyStay, LenTableCard - keyStay);
    for (i = LenTableCard - 1; i >= keyStay; i--) {
        strncat(GettedString, TableCard + i, 1);
    }
    TableCard[keyStay] = '\0';
}

int EndGame(char EndString[])  //是否达到结束游戏的条件（1.全部牌集中在一个人手中
                               //2.一人没有手牌）
{
    if (strlen(EndString) == NumberCard) {
        return 1;
    }
    if (strlen(EndString) == 0) {
        return 2;
    }
    return 0;
}

void GetCardRealHand(
    char *
        ChangedString)  //每个人出牌后的手牌
                        //PS:我没找到C语言中没有相关剪切的库函数调用，所以需要复制后，自己删除
{
    int LenChangeString = strlen(ChangedString), i;
    for (i = 0; i < LenChangeString - 1; i++) {
        ChangedString[i] = ChangedString[i + 1];
    }
    ChangedString[LenChangeString - 1] = '\0';
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String strA = br.readLine();
		String strB = br.readLine();
		br.close();
		game(strA,strB);
		
	}

	private static void game(String strA, String strB) {
		Stack<String> stack = new Stack<>();
		while(true) {
			while(true){
				String a = strA.substring(0,1);
				strA = strA.substring(1);
				String temp = isWin(stack, a, strA);
				if (temp.equals(strA)) {
					break;
				}else {
					strA = temp;
				}
			}
			if (strA.length() == 0) {
				break;
			}
			while(true) {
				String b = strB.substring(0, 1);
				strB = strB.substring(1);
				String temp = isWin(stack, b, strB);
				if (temp.equals(strB)) {
					break;
				}else {
					strB = temp;
				}
			}
			if (strB.length() == 0) {
				break;
			}
		}
		if (strA.length() > strB.length()) {
			System.out.println(strA);
		}else {
			System.out.println(strB);
		}
	}

	private static String isWin(Stack<String> stack, String a, String str) {
		if (stack.search(a) > 0) {
			str += a;
			while (true) {
				String temp = (String)stack.pop();
				str += temp;
				if (temp.equals(a)) {
					break;
				}
			}
		}else {
			stack.push(a);
		}
		return str;
	}

}

PREV-44 青蛙跳杯子

简记：bfs

#include <bits/stdc++.h>
using namespace std;
const int bas = 15;
int mov[6] = {-3, -2, -1, 1, 2, 3}, len;
struct state {
    int a[bas], pos, step, hast = -1;
    int hash() {
        // if(hast!=-1)return hast;
        int ret = 0;
        for (int i = 0; i < len; i++) {
            ret = ret * 3 + a[i];
            // printf("ret=%d\n",ret);
        }
        return ret;
    }
    void input(char *s, int n) {
        for (int i = 0; i < n; i++) {
            if (s[i] == '*') {
                a[i] = 0;
                pos = i;
            }
            if (s[i] == 'W') a[i] = 1;
            if (s[i] == 'B') a[i] = 2;
        }
    }
    void print() {
        printf("%d  ", step);
        for (int i = 0; i < len; i++) {
            printf("%d", a[i]);
        }
        printf("\n");
    }
};
bool vis[15000000];
queue<state> q;
int bfs(state s, state t, int n) {
    len = n;
    memset(vis, 0, sizeof(vis));
    vis[s.hash()] = 1;
    s.step = 0;
    q.push(s);
    int e = t.hash();
    while (!q.empty()) {
        // q.front().print();
        if (q.front().hash() == t.hash()) return q.front().step;
        state now = q.front();
        now.step++;
        for (int i = 0; i < 6; i++) {
            if (now.pos + mov[i] < 0 || now.pos + mov[i] >= len) continue;
            int t = now.a[now.pos];
            now.a[now.pos] = now.a[now.pos + mov[i]];
            now.a[now.pos + mov[i]] = t;
            now.pos += mov[i];
            now.hast = -1;

            int add = now.hash();
            if (vis[add]) {
                t = now.a[now.pos];
                now.a[now.pos] = now.a[now.pos - mov[i]];
                now.a[now.pos - mov[i]] = t;
                now.pos -= mov[i];
                now.hast = -1;
                continue;
            }
            vis[add] = 1;
            q.push(now);
            // printf("step=%d\n",now.step);
            // printf("@1 ");now.print();

            t = now.a[now.pos];
            now.a[now.pos] = now.a[now.pos - mov[i]];
            now.a[now.pos - mov[i]] = t;
            now.pos -= mov[i];
            now.hast = -1;

            // printf("@2 ");now.print();
        }
        q.pop();
    }
}
int main() {
    // printf("%lf\n",pow(3,15));
    char temp[100];
    state s, t;
    scanf("%s", temp);
    s.input(temp, strlen(temp));
    scanf("%s", temp);
    t.input(temp, strlen(temp));
    printf("%d\n", bfs(s, t, strlen(temp)));
    return 0;
}

import java.util.*;


public class Main {
    static class Fron {
        String now;
        int step;
        int pos;

        Fron(String now, int step, int pos) {
            this.now = now;
            this.pos = pos;
            this.step = step;
        }
    }

    static String start, end;
    static Queue<Fron> q = new ArrayDeque<Fron>();
    static Map<String, Integer> m = new HashMap<String, Integer>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        start = sc.nextLine();
        end = sc.nextLine();
        int pos = 0;
        for (int i = 0; i < start.length(); i++) {
            if ('*' == start.charAt(i)) {
                pos = i;
                break;
            }
        }
        System.out.println(bfs(start, 0, pos));
        sc.close();
    }

    private static int bfs(String now, int step, int pos) {
        Fron f = new Fron(now, step, pos);
        q.offer(f);
        while (!q.isEmpty()) {
            Fron status = q.poll();
            if (status.now.equals(end)) {
                return status.step;
            }
            String temp;
            if (m.containsKey(status.now)) {
                continue;
            } else {
                m.put(status.now, 1);
            }
            if (status.pos + 1 < start.length()) {
                temp = status.now;
                temp = swap(status.pos, status.pos + 1, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos + 1);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
            if (status.pos + 2 < start.length()) {
                temp = status.now;
                temp = swap(status.pos, status.pos + 2, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos + 2);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
            if (status.pos + 3 < start.length()) {
                temp = status.now;
                temp = swap(status.pos, status.pos + 3, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos + 3);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
            if (status.pos - 1 > -1) {
                temp = status.now;
                temp = swap(status.pos, status.pos - 1, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos - 1);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
            if (status.pos - 2 > -1) {
                temp = status.now;
                temp = swap(status.pos, status.pos - 2, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos - 2);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
            if (status.pos - 3 > -1) {
                temp = status.now;
                temp = swap(status.pos, status.pos - 3, temp);
                Fron fNext = new Fron(temp, status.step + 1, status.pos - 3);
                if (!m.containsKey(temp)) {
                    q.offer(fNext);
                }
            }
        }
        return -1;
    }

    private static String swap(int i, int j, String now) {
        char[] c = now.toCharArray();
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;
        now = new String(c);
        return now;
    }

}

PREV-45 图形排版

#include <stdio.h>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
typedef struct {
    int a, b, sum, w, mmax;
} node;
node x[100010];
int r[100010];
int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    int sum = 0;
    int nowm = m, mmax = 0;
    for (int i = 0; i < n; i++) {
        if (nowm == 0) {
            sum += mmax;
            mmax = 0;
            nowm = m;
        }
        scanf("%d%d", &x[i].a, &x[i].b);
        int a = x[i].a, b = x[i].b;
        if (a > nowm) {
            b = nowm * b / a + ((nowm * b) % a ? 1 : 0);
            a = nowm;
        }
        x[i].mmax = mmax;
        x[i].w = nowm;
        x[i].sum = sum;
        if (b > mmax) mmax = b;
        nowm -= a;
    }
    sum += mmax;
    for (int i = n - 1; i >= 0; i--) {
        nowm = m, mmax = 0;
        int j;
        for (j = i; j < n && nowm; j++) {
            int a = x[j].a, b = x[j].b;
            if (a > nowm) {
                b = nowm * b / a + ((nowm * b) % a ? 1 : 0);
                a = nowm;
            }
            if (b > mmax) mmax = b;
            nowm -= a;
        }
        r[i] = mmax + r[j];
    }
    int ans = sum;
    for (int i = 0; i < n; i++) {
        nowm = x[i].w, mmax = x[i].mmax;
        int j;
        for (j = i + 1; j < n && nowm; j++) {
            int a = x[j].a, b = x[j].b;
            if (a > nowm) {
                b = nowm * b / a + ((nowm * b) % a ? 1 : 0);
                a = nowm;
            }
            if (b > mmax) mmax = b;
            nowm -= a;
        }
        int res = x[i].sum + mmax + r[j];
        if (res < ans) ans = res;
    }
    printf("%d\n", ans);
    return 0;
}

import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] arg) {
		new Main().solve();
	}
	
	StringTokenizer ST;
	BufferedReader BR;
	PrintWriter PW;
	
	String next() {
		while(ST == null || !ST.hasMoreTokens()) {
			try {
				ST = new StringTokenizer(BR.readLine());
			}catch (Exception e) {
				// TODO: handle exception
				throw new RuntimeException(e);
			}
		}
		return ST.nextToken();
	}
	
	int nextInt() {
		return Integer.parseInt(next());
	}
	
	void solve() {
		BR = new BufferedReader(new InputStreamReader(System.in));
		PW = new PrintWriter(System.out);
		
		int m = nextInt(), n = nextInt();
		Pair a[] = new Pair[n + 10];
		Triple cr[] = new Triple[n + 10];
		cr[0] = new Triple();
		//正向处理出加到第i块的状态，Triple记忆第i块右下坐标(x,y)和第i块缩放后的高度h
		for(int i = 1; i <= n; i++) {
			Triple tmp = new Triple(cr[i-1]);
			if(tmp.x == m) tmp.x = tmp.h = 0;
			
			a[i] = new Pair(nextInt(), nextInt());
			cr[i] = new Triple();
			
			Pair b = Change(a[i], m - tmp.x);
			cr[i].x = tmp.x + b.x;
			cr[i].h = Math.max(tmp.h, b.y);
			cr[i].y = cr[i].h + tmp.y - tmp.h;
		}
		
		Triple A[] = new Triple[m];
		Triple B[] = new Triple[m];
		for(int i = 0; i < m; i++) {
			A[i] = new Triple();
			B[i] = new Triple();
		}
		
		int ans = cr[n].y;
		for(int i = n; i >= 1; i--) {
            //处理删除第i块的答案ah
			Triple pre = cr[i-1];
			int ah;
			if(pre.x == m) {
				ah = pre.y + B[0].y;
			} else {
				ah = pre.y - pre.h + B[pre.x].y - B[pre.x].h + Math.max(pre.h, B[pre.x].h);
			}
			ans = Math.min(ans, ah);
			
			//逆向DP，处理出第i至n块从(0,j)位置开始放置
			for(int j = 0; j < m; j++) {
				Pair b = Change(a[i], m - j);
				Triple tmp;
				if(j + b.x == m) tmp = new Triple(0, B[0].y, 0);
				else tmp = new Triple(B[j + b.x]);
				
				A[j].h = Math.max(b.y, tmp.h);
				A[j].y = A[j].h + tmp.y - tmp.h;
			}
			
			for(int j = 0; j < m; j++)
				B[j] = new Triple(A[j]);
		}
		
		PW.print(ans);
 
		
		PW.close();
	}
	
	Pair Change(Pair A, int x) {
		if(A.x <= x) return new Pair(A);
		return new Pair(x, (A.y * x + A.x - 1) / A.x);
	}
}
 
 
class Pair implements Comparable<Pair> {
	int x, y;
	
	Pair() { }
	
	Pair(Pair A) { x = A.x; y = A.y; }
	
	Pair(int x, int y) {
		this.x = x; this.y = y;
	}
	
	@Override
	public int compareTo(Pair A) {
		return x == A.x ? y - A.y : x - A.x;
	}
}
 
class Triple {
	int x, y, h;
	
	Triple() {}
	
	Triple(int x, int y, int h) {
		this.x = x; this.y = y; this.h = h;
	}
	
	Triple(Triple A) {
		x = A.x; y = A.y; h = A.h;
	}
	
	@Override
	public String toString() {
		return String.valueOf(x) + " " + String.valueOf(y) + " " + String.valueOf(h);
	}
}