MinamiMelon
0%

发表于 更新于

Sorting a Three-Valued Sequence

IOI'96 - Day 2
Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

本来打了贪心得进行模拟，后来改成了如下玄学贪心做法，十分简洁。欢迎Hack。 统计1,2,3的个数，可知放置1,2,3正确的位置，统计在各位置的数字1，2和3的个数，具体详见下。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=1000+5;
int ct[4],c[4][4];
int a[MAXN];

int main()
{
	freopen("sort3.in","r",stdin);
	freopen("sort3.out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),++ct[a[i]];
	for(int i=1;i<=ct[1];++i)
		++c[1][a[i]];
	for(int i=ct[1]+1;i<=ct[1]+ct[2];++i)
		++c[2][a[i]];
    //统计个数
	int ans=0;
	ans+=c[1][2]+c[1][3];//把1换到正确位置的最少步数
	c[2][3]+=max(0,c[2][1]-c[1][2]);//有多少3被交换到了二位置
	ans+=c[2][3];//将2,3交换到正确位置
	printf("%d\n",ans);
	return 0;
}

发表于 更新于

Arithmetic Progressions USACO1.4

An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0,1,2,3,... . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

INPUT: N (3 <= N <= 25), the length of progressions for which to search M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.
OUTPUT: If no sequence is found, a single line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.
There will be no more than 10,000 sequences.

此题目需要一些小的剪枝，详见注释。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rint register int
const int MAXN=100000+5;
int a[MAXN];
int aa[10005],bb[10005];
bool tab[MAXN];
int n,m,cnt,tot,mx;

int main()
{
	freopen("ariprog.in","r",stdin);
	freopen("ariprog.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(rint i=0;i<=m;++i)
		for(rint j=0;j<=m;++j)
			a[++cnt]=i*i+j*j,tab[a[cnt]]=1;//预处理双平方数表，快速查表
	sort(a+1,a+cnt);
	cnt=unique(a+1,a+cnt+1)-a-1;
	mx=m*m<<1;
	int r=mx/(n-1);//公差上界，最大的数除以要求的长度
	for(rint i=1;i<=r;++i)
	{
		for(rint j=1;j<=cnt;++j)
		{
			rint c=0;
			for(rint k=n-1;k>0&&a[j]+i*k<=mx;--k)//若超过max退出循环
                //从大到小枚举，不符合情况易退出
				if(!tab[a[j]+i*k]) //若有一个不符合条件即break
					break;
				else ++c;
			if(c==n-1)
			{
				aa[++tot]=a[j];
				bb[tot]=i;
			}
		}
	}
	if(tot==0)
		puts("NONE");
	else
		for(int i=1;i<=tot;++i)
			printf("%d %d\n",aa[i],bb[i]);
	return 0;
}

发表于 更新于

原题链接

经典贪心，转化为问题为，对于所有的区间，求最小的点数能使每个区间都至少有一个点。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;

const int MAXN=100000+5;
const double eps=0.000001;
struct seg
{
	double l,r;
	bool operator < (const seg& b)const
	{
		if(l==b.l)
			return r<b.r;
		return l<b.l;
	}
}e[MAXN];
int cs;

int main()
{
	int n,R;
	while(~scanf("%d%d",&n,&R))
	{
		if(n==0&&R==0)
			 break;
		int x,y;
		bool f=0;
		memset(e,0,sizeof e);
		for(int i=1;i<=n;++i)
		{
			scanf("%d%d",&x,&y);
			if(y==R)
			{
				e[i]=(seg){1.0*x,1.0*x};
			}
			else if(y<R)
			{
				double t=sqrt(R*R-y*y);
				e[i]=(seg){x-t,x+t};
			}
			else
				f=1;
		}
		int ans;
		if(f)
			ans=-1;
		else
		{
			sort(e+1,e+n+1);
			ans=1;
			double t=e[1].r;
			for(int i=2;i<=n;++i)
			{
				if(e[i].l>t)
				{
					++ans;
					t=e[i].r;
				}
				if(e[i].r<t)
					t=e[i].r;
			}
		}
		printf("Case %d: %d\n",++cs,ans);
	}
	return 0;
}

发表于 更新于

拦截导弹

题意：求最长不上升子序列长度；求一个序列最少分成几个非增子序。

第一问易求，已知序列a，令f[i]为a前i个元素的最长非增子序的长度，则有
f[i]=max{f[i],f[j]+1} (1<=j<=i-1且h[j]>=h[i]).
LIS另有nlogn做法，设g[i]为长度为i的最长不上升结尾最小是什么，二分查找更新次数组可得长度。解本题则可以倒序做LIS。
对于第二问，可以维护一个单调序列,为现有导弹拦截系统的最大高度，顺序处理序列，每次贪心的使用大于该导弹高度最小的来拦截这个导弹，显然这样比使用一个可以拦截更高的系统更优。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; 

const int INF=0x3f3f3f3f;
int a[30],f[30],g[30],n;

int main()
{
	while(~scanf("%d",&a[++n]));
	--n;
	memset(f,63,sizeof f);
	for(int i=n;i>0;--i)//倒序LIS 
	{
		int p=lower_bound(f+1,f+n+1,a[i])-f;
		f[p]=a[i];
	}
	printf("%d\n",lower_bound(f+1,f+n+1,INF)-f-1);
	memset(g,63,sizeof g);//初始时可以拦截任意高度的导弹 
	for(int i=1;i<=n;++i)
	{
		int p=lower_bound(g+1,g+n+1,a[i])-g;
		g[p]=a[i];
	}
	printf("%d\n",lower_bound(g+1,g+n+1,INF)-g-1);//找到最后一个使用过的
	return 0;
}
不难发现，第二问按照贪心的思路打出的实际上是一个nlogn的LIS。这涉及到一个定理。

Dilworth定理：对于一个偏序集，最少链划分等于最长反链长度.

也就是说把一个数列划分成最少的最长不上升子序列的数目就等于这个数列的最长不下降子序列的长度。

##零件分组 Wooden Sticks

现有一些棍状零件，每个零件都有一定的长度(Li)和重量(Wi)。现在为了加工需要，要将他们分成若干组，使每一组中的零件都能排成一个长度和重量都不下降(若i<j，则Li<=Lj，Wi<=Wj，其中i,j为在同一组中的序号)的序列。请问至少要分成几组？

先按照长度（或重量）双关键字排序，则答案序列一定是该序列的子序。则问题转化为原问题二，问未排序的那一个元素序列最少分成多少最长的非降的子序列。求这个序列的最长非增子序即可。
nlogn的非增序列处理比较复杂，（因为处理到a[i]是，要找到小于该值的最大元素，如果其最小则左移，需要从n到1处理）。可以同第一问一样转化为从右向左做LIS，也可以全部取负数做LIS（废话）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=100000+5,INF=0x3f3f3f3f;
struct elem
{
	int l,w;
	bool operator < (const elem& b)const
	{
		if(l==b.l)
			return w<b.w;
		return l<b.l;
	}
}e[MAXN];
int n,m;
int f[MAXN];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d%d",&e[i].l,&e[i].w);
	sort(e+1,e+n+1);
	memset(f,63,sizeof f);
	for(int i=1;i<=n;++i)
	{
		int p=lower_bound(f+1,f+n+1,-e[i].w)-f;
		f[p]=-e[i].w;
	}
	printf("%d",lower_bound(f+1,f+n+1,INF)-f-1);
	return 0;
}

发表于 更新于

一开始是不会的，不知道如何处理相等的情况，瞎贪心一直WA。 于是就递归处理是让相等的平局还是输掉，如下，拿到了50分。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int solve(int *a,int *b,int i,int l,int r)
{
	int ans=0;
	for(;i<=n;++i)
	{
		if(a[i]>b[l])
			ans+=2,++l;
		else if(a[i]<b[l])
			--r;
		else
		{
			ans+=max(solve(a,b,i+1,l+1,r)+1,solve(a,b,i+1,l,r-1)+(a[i]==b[r]?1:0));
			break;
		}
	}
	return ans;
}
附正解，网上的讲解已经很完善了。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN=100000+5;
int a[MAXN],b[MAXN];
int n;

int solve(int *a,int *b)
{
	int ans=0,la=1,lb=1,ra=n,rb=n;
	while(la<=ra)
	{
		if(a[la]>b[lb])
		{
			ans+=2;
			++la,++lb;
		}
		else if(a[ra]>b[rb])
		{
			ans+=2;
			--ra,--rb;
		}
		else
		{
			if(a[la]==b[rb])
				++ans;
			++la,--rb;
		}
	}
	return ans;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;++i)
		scanf("%d",&b[i]);
	sort(b+1,b+n+1);
	printf("%d %d",solve(a,b),(n<<1)-solve(b,a));
	return 0;
}

发表于 更新于

题目链接

考虑正序去除点去掉其所有连边十分复杂，可以倒序离线处理，每次新建一个点，连接其连边，用并查集统计联通块的个数。 附代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=400000+5;
int ans[MAXN],fa[MAXN],rnk[MAXN],hd[MAXN],des[MAXN];
int ff[MAXN],tt[MAXN];
int to[MAXN<<1],nxt[MAXN<<1];
bool used[MAXN];
int cnt,n,m;

inline void build(int f,int t)
{
    to[++cnt]=t;
    nxt[cnt]=hd[f];
    hd[f]=cnt;
}

int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

bool unite(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y) return 0;
    if(rnk[x]==rnk[y])
        fa[x]=y,++rnk[y];
    else if(rnk[x]>rnk[y])
        fa[y]=x;
    else
        fa[x]=y;
    return 1;
}

int main()
{
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&ff[i],&tt[i]);
        build(ff[i],tt[i]);
        build(tt[i],ff[i]);
    }
    int k;
    scanf("%d",&k);
    for(int i=1;i<=k;++i)
        scanf("%d",&des[i]),
        used[des[i]]=1;
    int ansn=n-k;
    for(int i=1;i<=m;++i)
    {
        if(!used[ff[i]]&&!used[tt[i]])
        {
            if(unite(ff[i],tt[i]))
                --ansn;
        }
    }
    for(int j=k;j>=1;--j)
    {
        ans[j]=ansn;
        ++ansn;
        int u=des[j];
        used[u]=0;
        for(int i=hd[u];i;i=nxt[i])
        {
            int v=to[i];
            if(used[v]) continue;
            if(unite(u,v))
                --ansn;
        }
    }
    printf("%d\n",ansn);
    for(int i=1;i<=k;++i)
        printf("%d\n",ans[i]);
    return 0;
}