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;
}
05-11 13:32