Day12

2018-08-21

字数统计: 2.1k字 | 阅读时长: 10min

Problem(problem.pas/c/cpp)

题目描述
众所周知， Pb 是位大神犇，时不时就去 BZOJ 啊 codeforces 啊什么的玩玩，
这次无聊刷(nue)题的时候看到了一道奇怪的题目：
给你一个数 n 和有 n 个非负整数的数组 a ， 求
Max{(j- i+1)*Min{a[k]| (i<=k<= j)}| (1<=i<=n,i<= j<=n)}
题目如此简短， Pb 神犇很快就看完了，看完之后大呼一声：“水题！”不出 5min就把这题给秒了，于是对出题人说：“快来秒这道水题！”
然而出题人是个 SB，显然没有 Pb 那么神，完全做不出，所以请你来帮忙咯。

输入格式
一个整数 n。
接下来一行，共 n 个非负整数，代表 a 数组。

输出格式
输出应该只有一个非负整数，代表答案。

样例输入
1 3

样例输出
3

数据范围
对于 10%的数据， 1<=n<=2000
对于 20%的数据， 1<=n<=500000
对于另 30%的数据， n=4000000，保证 a 数组是非严格递增或非严格递减
对于 100%的数据， 1<=n<=4000000， 0<a[i]<=1000000000

#include<bits/stdc++.h>
using namespace std;
template <class T> inline void read(T&a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){a=a*10+(s-'0');s=getchar();}
	a*=f;
} 
long long ans;
int n,s[4100000],a[4100000],l[4100000],p[4100000],top; 
int main()
{
	freopen("problem.in","r",stdin);
	freopen("problem.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(a[i]);
	a[++n]=0;
	//the first element's position in the s[] which is less than a[i]
	l[1]=0;
	//position
	p[1]=1;
	//stack
	s[++top]=a[1];
	for(int i=2;i<=n;i++)
	{
		while(top&&a[i]<s[top])
		{
			ans=max((long long)s[top]*(i-l[top]-1),ans);
			top--;
		}
		s[++top]=a[i];p[top]=i;l[top]=p[top-1];
	}
	printf("%lld\n",ans);
	return 0;
}

题解：

用单调栈来维护一个单调上升序列，每当当前元素小于栈顶元素，更新答案并弹出栈顶。

Tents(tents.pas/c/cpp)

问题描述
Pb 去郊游啦！他来到一块空地打算在这里搭一个帐篷。
但是,帐篷的四个支撑点不能在落在任何位置上,而只能落在一些固定点上。
现在,他找到地面上有 N 个点可以支撑帐篷。（四个支撑点必须围成一个矩形）
他想知道依次每加多一个点，搭帐篷的方法数。

输入格式
第 1 行：一个整数 N
第 2 行至 N +1 行：每行有两个整数的 x， y 作为一个点的坐标。 

输出格式
共 N 行： 第 i 行表示当前加入第 i 个点后可以搭帐篷的方案数。 

样例输入
8
1 2
1 -2
2 1
2 -1
-1 2
-1 -2
-2 1
-2 -1

样例输出
0
0
0
0
0
1
3
6

样例解释
最后的答案是（ 1,2,6,5），（1,3,6,8），（1,4,6,7），（ 2,3,5,8），（2,4,5,7），（ 3,4,8,7）
数据范围
对于 50%的数据 4<=N<=100.
对于 100%的数据 4<=N<=1,000.
所有的 x,y 都不会超过 16,000。所有点都是不同的。

#include<bits/stdc++.h>
using namespace std;
const int mod = 4e6+7;
int x[1100],y[1100];
int xx[4000000],yy[4000000],len[4000000],t;
int cnt[4000000];
int hash[4000000],tot;
int main()
{
	freopen("tents.in","r",stdin);
	freopen("tents.out","w",stdout);
	int n;
	int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d %d",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			int a=x[i]+x[j],b=y[i]+y[j],c=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
			t=(a*233+b*1017+c*3017)%mod;
			while(hash[t]!=0&&(xx[hash[t]]!=a||yy[hash[t]]!=b||len[hash[t]]!=c))
				t=(t+5903)%mod;
			if(hash[t]!=0)
			{
				ans+=cnt[hash[t]];
				cnt[hash[t]]++;
			}
			else
			{
				hash[t]=++tot;
				xx[tot]=a;
				yy[tot]=b;
				len[tot]=c;
				cnt[hash[t]]++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
```    

#### 题解：
	首先四维暴力可拿70分。（四个for分别枚举矩形四个顶点）。
    而正解是o(n^2)的。可以构成矩形的两条边有以下性质：
    1. x1+x3=x2+x4;
    2. y1+y3=y2+y4;
    3. (x1-x3)*(x1-x3)+(y1-y3)*(y1-y3)=(x2-x4)*(x2-x4)+(y2-y4)*(y2-y4).
    将这三个当做一条边的三个元素，然后进行hash，计数，判重。然后就过了。
    
# Clannad(clannad.pas/c/cpp)
    问题描述
    Pb 有 n 种不同颜色的团子，每种团子的个数一定,总数为 m， pb 要将这些团
    子排成一排，且相同颜色的团子不能相邻。
    
    输入格式
    第 1 行：一个整数 n 表示有 n 种颜色的团子
    第 2 行有 n 个整数，表示第 i 种颜色团子的个数
    
    输出格式
    对于每个测试点，输出字典序最小得满分，输出任意一种可行方案得一半分
    数。
    如果没有可行方案输出-1.
    
    样例输入
    3
    2 3 3
    
    样例输出
    1 2 3 2 3 2 3 1（ 一半分数）
    或者
    1 2 1 3 2 3 2 3 （ 满分）
    
    数据范围
    对于 20%的数据， n<=5, m<=10
    对于 50%的数据， n<=1000, m<=1000
    对于另外 20%的数据,n<=20, m<=100000
    对于 100%的数据,n<=100000,m<=100000

## 题解用的是set来实现的，如下：
```cpp
#include <iostream>
#include <set>
using namespace std;

int a[100000]; 
int tree[400000]; 

int main(){
//	freopen("clannad.in", "r",stdin);
//	freopen("clannad.out", "w", stdout); 
    int n, m = 0;   cin >> n; 
    set<pair<int, int> > S;
    for (int i = 0; i < n; i++){
    	cin >> a[i]; 
	m += a[i]; 
	S.insert(make_pair(a[i], i));
    }
    int last = -1; //上一个输出的数组a下标。 
    int low = 0; //最小的下标。 
    while (!a[low]) low++; 
    int up = low + 1; 
    while (!a[up])	up++;//
    while (m)
	{
    	set<pair<int, int> >::iterator toloc = S.end();
    	toloc--;
		int loc = toloc->second; 
		if (a[loc] > ((m + 1) >> 1))
		{
		    cout << -1; 
		    break; 
		}
		if (m % 2 && a[loc] == ((m >> 1) + 1))
		{
//		    if (loc == last)	cout << "GG"; 
		    set<pair<int, int> >::iterator it = S.find(make_pair(a[loc], loc));
		    a[loc]--; 
		    S.erase(it);
		    S.insert(make_pair(a[loc], loc));
		    last = loc; 
		    while (!a[low]) low++; 
		    if (up == low)  up++; //
		    while (!a[up])	up++; //
		} 
		else if (low == last)
		{
		    set<pair<int, int> >::iterator it = S.find(make_pair(a[up], up));
		    a[up]--; 
		    S.erase(it);
		    S.insert(make_pair(a[up], up));
		    last = up; 
		    while (!a[up])  up++; 
		} 
		else
		{
		    set<pair<int, int> >::iterator it = S.find(make_pair(a[low], low));
		    a[low]--; 
		    S.erase(it);
		    S.insert(make_pair(a[low], low));
		    last = low; 
		    while (!a[low]) low++; 
		    if (low == up)  up++; 
		    while (!a[up])	up++; 
		}
		cout << last + 1 << ' '; 
		m--; 
    }
}

但是本蒟蒻实在不会用迭代器，于是用大根堆去实现了一遍

#include<bits/stdc++.h>
using namespace std;
int a[100010],n,maxx,m;
priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > >q1;
int main()
{
//	freopen("clannad.in","r",stdin);
//	freopen("clannad.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        maxx=max(maxx,a[i]); 
        m+=a[i];
        q1.push(make_pair(a[i],i));
    }
    if(maxx>m/2)
    {
        printf("-1\n");
        return 0;
    }
    int last,low=0,up;
    while(!a[low]) low++;
    up=low+1;
    while(!a[up]) up++;
    while(m)
    {
        int c=q1.top().first,b=q1.top().second;
        while(c!=a[b])
        {
            q1.pop();
            q1.push(make_pair(a[b],b));
            c=q1.top().first,b=q1.top().second;
        }
        if(2*c>m)
        {
            printf("%d ",b);
            last=b;
            a[b]--;
            m--;
            while(!a[low]) low++;
            if(up==low) up++;
            while(!a[up]) up++;		
        }
        else if(low==last)
        {
            printf("%d ",up);
            last=up;
            a[up]--;
            while(!a[up]) up++;
            m--;
        }
        else
        {
            printf("%d ",low);
            last=low;
            a[low]--;
            while(!a[low]) low++;
            if(up==low) up++;
            while(!a[up]) up++;
            m--;
        } 
    } 
    return 0;
}

题解：

其实无论是set还是qriority_queue，解这道题的思路都是一样的。只要a[1~n]中，有一个值大于m/2，就无解，否者有解，一有大于m/2，就输出，其他保证输出最小的数即可。
用三个变量last,low,up分别记录上一个输出，最小可用，以及紧挨着low的可用值。分三种情况讨论输出。

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/bd619c1f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！