2017 ACM-ICPC Asia Shenyang (ICPC亚洲沈阳赛区)

F - Heron and His Triangle
HDU - 6222
题意： 给一个N，求最小的 t 使 t >=N，并且使边长为t,t-1,t+1的三角形面积为整数
题解： 可由三角形面积公式求解递推公式
以下公式来自：博客

所以使3x² (x²-1)= S²，所以需要3x² (x²-1)为平方数
令y²为该平方数，可得：x²-3y² = 1
接着用__int128搞一搞
队友的代码：

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=66;
const double eps=1e-6;

#define endl '\n'

__int128 read(){
	char ch;
	__int128 w=0,q=1;
	ch=getchar();
	while(ch<'0'&&ch>'9'&&ch!='-') ch=getchar();
	if(ch=='-') q=-1,ch=getchar();
	while(ch>='0'&&ch<='9') w=w*10+ch-'0',ch=getchar();
	return w*q; 
}

void write(__int128 x){
	if(x<0) {
		putchar('-');
		x=-x;
	}
	int a[50],cnt=0;
	while(x){
		a[cnt++]=x%10;
		x/=10;
	}
	cnt--;
	while(cnt>=0) putchar(a[cnt--]+'0');
}

ll f[N+5];

void solve(){
	f[1]=4;
	f[2]=14;
	for(int i=3;i<=N;i++) f[i]=4*f[i-1]-f[i-2];
}

int main(){
	//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cout.setf(ios::fixed),cout.precision(3);
	ll n;
	int t;
	solve();
	scanf("%d",&t);
	getchar();
	while(t--){
		n=read();
		ll x=*lower_bound(f+1,f+1+N,n);
		write(x);
		printf("\n");
	}
	return 0;
}

I - Little Boxes
HDU - 6225
题意： 给四个数，求和
题解： 给的数据可能超long long 需要用大数，__int128搞一搞

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=1e5+5;

#define endl '\n'

__int128 read(){
	char ch;
	__int128 w=0,q=1;
	ch=getchar();
	while(ch<'0'&&ch>'9'&&ch!='-') ch=getchar();
	if(ch=='-') q=-1,ch=getchar();
	while(ch>='0'&&ch<='9') w=w*10+ch-'0',ch=getchar();
	return w*q; 
}

void write(__int128 x){
	if(x==0) {
		putchar('0');
		return;
	}
	if(x<0) {
		putchar('-');
		x=-x;
	}
	int a[50],cnt=0;
	while(x){
		a[cnt++]=x%10;
		x/=10;
	}
	cnt--;
	while(cnt>=0) putchar(a[cnt--]+'0');//注意putchar()与关同步冲突
}

int main(){
	//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cout.setf(ios::fixed),cout.precision(3);
	ll a[4],sum;
	int t;
	scanf("%d",&t);
	getchar();
	while(t--){
		sum=0;
		for(int i=0;i<4;i++) a[i]=read();
		for(int i=0;i<4;i++) sum+=a[i];
		write(sum);
		printf("\n");
	}
	return 0;
}

K - Rabbits
HDU - 6227
题意： 给n只的兔子的坐标，每个兔子可以跳到两个兔子的中间，求最多可移动的次数。
题解： 仔细考虑一下可以知道，只有第一只跟最后一只兔子到他们邻近兔子的距离是不能全部跳到的（因为第一步需要第一只跟最后一只往里跳）接下来里面兔子之间都可以一步一步往里跳，所以距离可以全部求和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;

#define endl '\n'

int a[N],d[N];

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cout.setf(ios::fixed),cout.precision(3);
	int t,n,l,r,ans;
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=2;i<=n;i++) {
			d[i]=a[i]-a[i-1]-1;
		}
		ans=0;
		for(int i=2;i<=n;i++) ans+=d[i];
		ans-=min(d[2],d[n]); 
		cout<<ans<<endl;
	}
	return 0;
}

L - Tree
HDU - 6228
待补