The 2017 ACM-ICPC Asia Shenyang Regional Contest [Cloned]

The 2017 ACM-ICPC Asia Shenyang Regional Contest [Cloned]

A-BBP Formula

B-Bridge

C-Empty Convex Polygons

D-Defense of the Ancients

E-Five-round Show Hand

F-Heron and His Triangle

题意：

给你一个n，让你求出满足t-1,t,t+1边长，并且面积是整数的三角形的最小的t

solution：

打表，找规律
打表程序

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;

int main()
{
   
    for(int i=1;i<=1000;i++)
    {
   
        ll x=1ll*3*i*i*(i*i-4);
        ll y=sqrt(x);
        if(y*y!=x||y%8!=0)continue;
        if(i==2)continue;
        printf("%d\n",i);
    }
    return 0;
}

该题代码。

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main{
   
	public static void main (String[] args) {
   
		Scanner in=new Scanner(System.in);
		int t;t=in.nextInt();
		BigInteger []res=new BigInteger[55];
		res[0]=BigInteger.valueOf(4);res[1]=BigInteger.valueOf(14);
		for(int i=2;i<55;i++)
			res[i]=res[i-1].multiply(BigInteger.valueOf(4)).subtract(res[i-2]);
		while(t>0) {
   
			t--;
			BigInteger n=in.nextBigInteger();
			for(int i=0;i<55;i++) {
   
				if(n.compareTo(res[i])<=0) {
   
					System.out.println(res[i]);
					break;
				}
			}
		}
	}
}

G-Infinite Fraction Path

H-Legends of the Three Kingdoms

I-Little Boxes

题意：

给了四个盒子的数量，求总和。坑点：会爆unsigned long long

import java.math.BigInteger;
import java.util.Scanner;
import java.util.Stack;
public class Main{
   
	public static void main(String[] args) {
   
		Scanner in=new Scanner(System.in);
		int t=in.nextInt();
		while(t>0) {
   
			t--;
			BigInteger a,b,c,d;
			a=in.nextBigInteger();
			b=in.nextBigInteger();
			c=in.nextBigInteger();
			d=in.nextBigInteger();
			BigInteger sum=a.add(b).add(c).add(d);
			System.out.println(sum);
		}
	}
}

J-New Self-describing Sequence

K-Rabbits

题意：

给了你n只兔子，他们占据不同的数字，最外面的兔子能跳到任意两只兔子中间，问他们能玩多久。

solution：

贪心，我们知道最优解就是尽可能将最外层两只兔子中间的还未被占据的地方都占据一遍，但是又由于有一只兔子要跳到两只兔子之间这个条件的限制，所以就要去掉最外层相邻两个兔子的距离的一个，所以就去掉少的那个就行。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int t,n;
int a[505];
int vis[10005];
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
   
            scanf("%d",&a[i]);
            vis[a[i]]=1;
        }
        sort(a,a+n);
        int res=0,l,r;
        if(a[1]-a[0]<a[n-1]-a[n-2])
            l=a[1],r=a[n-1];
        else
            l=a[0],r=a[n-2];
        while(l<r)
        {
   
            while(l<r&&vis[l])l++;
            if(l>=r)break;
            vis[l]=1;
            res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

精简代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int t,n;
int a[505];
int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        int res=max(a[n-1]-a[1],a[n-2]-a[0])-n+2;
        printf("%d\n",res);
    }
    return 0;
}

L-Tree

M-Wandering Robots