2018HDU多校训练1

题目链接：https://cn.vjudge.net/contest/298618

A - Maximum Multiple

题意：给定一个n，找n的约数x,y,z，满足x+y+z=n，求 x ∗ y ∗ z x*y*z x∗y∗z的最大值 题解：转化一下，n=ax=by=cz，那么 x = n / a x=n/a x=n/a， y = n / b y=n/b y=n/b， z = n / c z=n/c z=n/c 原式转化为已知 1 / a + 1 / b + 1 / c = 1 1/a+1/b+1/c=1 1/a+1/b+1/c=1，求 n 3 / ( a ∗ b ∗ c ) n^3/(a*b*c) n3/(a∗b∗c)的最大值 由于满足 1 / a + 1 / b + 1 / c = 1 1/a+1/b+1/c=1 1/a+1/b+1/c=1的整数对只有{2,2,4} {3,3,3} {2,3,6}我们只需求这几种情况的值即可

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn=100010;

int n;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		ll ans=-1;
		if(n%3==0){
			ans=max(ans,1LL*n*n*n/27);
		}
		if(n%4==0){
			ans=max(ans,1LL*n*n*n/32);
		}
		if(n%6==0){
			ans=max(ans,1LL*n*n*n/36);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

B - Balanced Sequence(贪心）

HDU - 6299 题解转载自：https://blog.csdn.net/ACTerminate/article/details/81171799 题意： 给你n个包含’(‘与’)’的字符串，可以将这些字符串任意排序，求所有排序中，子序列是正规括号序列的最大长度。

题解： 首先我们对所有的字符串找到通过stack找到所有的串内正规括号子序列，之后剩下的串只有三种可能:

1. 只包含’(’
2. 先是一串’)’然后再是一串’(’
3. 只包含’)’ 然后，按照第一类，第二类，第三类的顺序放置串。对于第二类内的排序，首先按照’(‘个数贡献正负排序,’)’个数小于’(‘个数则贡献为正，贡献是正的则排前面。然后正贡献的串，我们按照’)’个数从小到大排。负贡献的串，我们按照’(‘个数从大到小排。对于排序完的串，我们从前往后模拟记录一下即可。

#include
#include
#include
#include
#include
#include
using namespace std;
const int MAXN=(int)1e5+10;
struct node
{
    int a,b;
}p[MAXN];
char str[MAXN];
stacks;
vectorv1,v2,v3;
bool cmp(node x,node y){
    if(x.a+x.b>=0&&y.a+y.b>=0)return x.a>y.a;
    else if(x.a+x.b>=0)return 1;
    else if(y.a+y.b>=0)return 0;
    else return x.b>y.b;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        while(!s.empty())s.pop();
        v1.clear();v2.clear();v3.clear();
        int step=0,n,ans=0;
        scanf("%d",&n);
        for(int i=1;i