2018 Benelux Algorithm Programming Contest 解题报告

A

温暖的签到题。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

const int N=1e5+7;

ll a[N],x;

int main(){
	int n=input();x=input();
	for(int i=1;i<=n;i++){
		a[i]=input();
	}

	sort(a+1,a+1+n);

	int Ans=1;

	for(int i=2;i<=n;i++){
		if(a[i]+a[i-1]<=x) Ans=i;
		else break;
	}

	printf("%d\n",Ans);
}

C

oeis题,oeis:A075777

import math

def cubestepdown(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0)))
    minSA = -1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:
            s1 = s1 - 1
        s1quot = int(n/s1)
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))
            SA = 2*(s1*s2 + s1*s3 + s2*s3)
            if minSA==-1:
                minSA = SA
            else:
                if SA<minSA:
                    minSA = SA
            s2 = s2 - 1
        s1 = s1 - 1
    return minSA

n = int(input())
print(cubestepdown(n))


J

数学题,婆罗摩笈多公式(Brahmagupta's formula):

\[A=\sqrt{(s-a)(s-b)(s-c)(s-d)} \\ 其中a、b、c、d为四边形的周长,s=\frac{a+b+c+d}{2} \]

带入公式即可算出最大面积。有关婆罗摩笈多公式的推导

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

double a,b,c,d,s;

int main(){
	a=input(),b=input(),c=input(),d=input();
	s=(a+b+c+d)/2;

	double Ans=sqrt((s-a)*(s-b)*(s-c)*(s-d));

	printf("%.12lf\n",Ans);
}

B

恶心模拟题,给每个日期排序,计算最大日期间隔,如果有相同需要分类讨论,如果当前日期小于10-28则计算与去年的10-28的距离,如果大于则计算与今年10-28的距离,选择与10-28距离最小的日期就是答案。

#include <bits/stdc++.h>

using namespace std;

#define ll long long
ll input(){
	ll x=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return f? -x:x;
}

#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair

const int N=107;

PII a[N];
int day[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int cal(PII a,PII b){
	if(a>b) swap(a,b);
	if(a.fr==b.fr) return b.sc-a.sc;
	int res=day[a.fr]-a.sc+b.sc;
	for(int i=a.fr+1;i<b.fr;i++){
		res+=day[i];
	}
	return res;
}

PII getAns(PII a){
	PII res;
	if(a.sc-1==0){
		res.fr=a.fr-1;
		res.sc=day[a.fr-1];
	}else res.fr=a.fr,res.sc=a.sc-1;
	if(res.fr==0) res.fr=12,res.sc=31;
	return res;
}

int main(){
	int n=input();

	for(int i=1;i<=n;i++){
		a[i].fr=input(),a[i].sc=input();
	}

	sort(a+1,a+1+n);

	ll mx=0,pos;

	for(int i=1;i<=n;i++){
		if(i==1){
			if(mx<cal(mp(1,1),a[1])+cal(a[n],mp(12,31))+1){
				mx=cal(mp(1,1),a[1])+cal(a[n],mp(12,31))+1;
				pos=i;
			}
		}else if(mx<cal(a[i-1],a[i])){
			mx=cal(a[i-1],a[i]);
			pos=i;
		}else if(mx==cal(a[i-1],a[i])){
			PII t1=getAns(a[i]),t3=getAns(a[pos]),t2,t4;
			if(t1<mp(10,28)) t2=mp(1,1);
			else t2=mp(10,28);
			if(t3<mp(10,28)) t4=mp(1,1);
			else t4=mp(10,28);
			int tt1,tt2;
			if(t2==mp(1,1)) tt1=cal(mp(10,28),mp(1,1))+cal(t1,t2);
			else tt1=cal(t1,t2);
			if(t4==mp(1,1)) tt2=cal(mp(10,28),mp(1,1))+cal(t3,t4);
			else tt2=cal(t3,t4);
			if(tt1<tt2) pos=i;
		}
	}

	PII Ans=getAns(a[pos]);

	if(Ans.fr<10) printf("0%d-",Ans.fr);
	else printf("%d-",Ans.fr);
	if(Ans.sc<10) printf("0%d\n",Ans.sc);
	else printf("%d\n",Ans.sc);
}

F

二分答案,二分最小的天数计算总收益减去成本,剩下的钱跟\(m\)比较大小,判断二分方向,即可。但是不知道为啥我写c++总是爆ll,所以用pythonAC了。

上一篇:Day——06


下一篇:C Programming Test And Answer 07