CF#345 div2 A\B\C题

A题：

贪心水题，注意1，1这组数据，坑了不少人

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

	int a1,a2;

	while(cin>>a1>>a2)

	{

		int i=0;

		int b = max(a1,a2);

		int s = min(a1,a2);

		if(b==1 && s==1) {

			cout<<0<<endl;

			continue;

		}

		for(i = 1;i <= 10000;i++)

		{

			b -= 2;

			s += 1;

			if(!b || !s) break;

			if(s > b) {

				int tmp = b;

				b = s;

				s = tmp;

			}

		}

		cout<<i<<endl;

	}

	return 0;

}

---

B题：

首先给数组排序，然后问题就可以抽象成找到一个有序数组的上升子序列的最大个数，实现方法有点笨拙（我宁愿称之为巧妙：））

#include <iostream>

#include <cstring>

#include <algorithm>

#define INF 99999

using namespace std;

int num[1007][1007];

int main(){

	int n;

	int a[1007];

	while(cin>>n)

	{

		int ans = 0;

		memset(num,0,sizeof(num));

		for(int i = 1;i <= n;i++)

			cin>>a[i];

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

		//初始化第一个

		int cnt = 0;

		int Min = INF;

		num[1][++cnt]++;

		int tmp = a[1];

		for(int i = 2;i <= n;i++)

		{

			if(a[i] == tmp) num[1][cnt]++;

			else {

				tmp = a[i];

				num[1][++cnt]++;

			}

		}

		for(int i = 1;i <= cnt;i++)

			Min = min(Min,num[1][i]);

		int y = 1;

		while(cnt) {

			ans += (cnt-1)*Min;

			int tcount = 0;

			for(int i = 1;i <= cnt;i++)

			{

				num[y][i] -= Min;

				if(num[y][i])

					num[y+1][++tcount] = num[y][i];

			}

			cnt = tcount;

			y++;

			Min = INF;

			for(int i = 1;i <= cnt;i++)

				Min = min(Min,num[y][i]);

		}

		cout<<ans<<endl;

	}

	return 0;

}

---

C题：

将二者的计算公式稍作推导就可以发现任意两点要符合要求，只要xy两个坐标只要满足(x||y)的复合命题为真即可。然后至于数组的大小，这里引用了特殊的数据结构来存储大量的数据，然后注意x或y坐标相同有n个点，而ans是要加或减n*(n-1)/2的

#include <iostream>

#include <map>

#include <cstdio>

#define ll long long

using namespace std;

map<ll,ll> num_x;

map<ll,ll> num_y;

map<pair<ll,ll>,ll> num_s;

ll tx,ty;

int main()

{

	int n;

	while(cin>>n)

	{

		ll ans = 0;

		num_x.clear();

		num_y.clear();

		num_s.clear();

		for(int i = 1;i <= n;i++)

		{

			scanf("%I64d%I64d",&tx,&ty);

			num_x[tx]++;

			num_y[ty]++;

			num_s[make_pair(tx,ty)]++;

		}

		map<ll,ll>::iterator it1;

		map<pair<ll,ll>,ll>::iterator it2;

		for(it1 = num_x.begin();it1 != num_x.end();it1++)

			ans += it1->second*(it1->second-1)/2;

		for(it1 = num_y.begin();it1 != num_y.end();it1++)

			ans += it1->second*(it1->second-1)/2;

		for(it2 = num_s.begin();it2 != num_s.end();it2++)

			ans -= it2->second*(it2->second-1)/2;

		printf("%I64d\n",ans);

	}

	return 0;

}