题目链接（密码hpuacm）：https://vjudge.net/contest/243307
八成都是水题。
A题猴子吃桃太水。
B题疯狂的母牛，分别用三个变量保存一年，二年和三年龄的牛。第四年时三年龄的牛就要生小牛了。 注意一点就是，第一年只有一头三年龄的母牛。
C题 2的n-k次方
D题 贪心，把线段按照起点的从小到大排序，起点一样按终点小的排在前面。然后循环一边，每次取相邻两个线段的重叠长度，和与之前已经得到的重叠长度的最大值。
#include <stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 50000+10;
struct node{
LL x1, x2;
};
struct node p[MAXN];
bool cmp(struct node p1, struct node p2)
{
if( p1.x1 == p2.x1 )
return p1.x2 < p2.x2;
return p1.x1 < p2.x1;
}
int main()
{
int n;
while( cin >> n )
{
for( int i=0; i<n; i++ )
scanf("%lld %lld", &p[i].x1, &p[i].x2 );
sort(p, p+n, cmp);
LL ans = 0;
struct node temp = p[0]; // 表示前一条线段
for( int i=1; i<n; i++ )
{
if( p[i].x2 <= temp.x2) //线段i在线段i-1内
{
ans = max(ans, p[i].x2 - p[i].x1);
}
else if(p[i].x1 <= temp.x2 && p[i].x2 >= temp.x2)
{
ans = max(ans, temp.x2 - p[i].x1);
temp = p[i]; //选择最靠后的线段
}
}
cout<< ans <<endl;
}
return 0;
} 我也有一点不够明白，为什么每次要都取的是相邻的两个线段呢，举个例子
现在有五条线段用 s0,s1,s2,s3,s4来表示
编号 起点x1 终点x2
s0 1 5
s1 2 4
s2 2 6
s3 4 9
s4 7 9
那么我们可以看到最长的重叠度应该是 s0 与 s2 重叠长度是 5-2 = 3 。
那么如果按AC代码来算的话
首先一个 int ans = 0;
然后是一个 struct node temp = s0;
循环是 for( int i=1; i<5; i++ )
之后判断如果是后一条线段是否完全在前一条线段之内
如果是 ans = max(ans, s[i].x2 - s[i].x1);
如果不是 ans = max(ans, temp.x2 - s[i].x1);
然后temp = s[i];
那么ans的值得变化是
起始： ans = 0;
i = 1, temp = s0 ans = max(0, 4-2) = 2;
i = 2, temp = s1 ans = max(2, 4-2) = 2;
i = 3, temp = s2 ans = max(2, 6-4) = 2;
i = 4, temp = s3 ans = max(2, 9-7) = 2;
最终的结果就是 ans = 2;
但是我们明显知道的是 最长的重叠是s0与s2的重叠长度 5 - 2 = 3;
即最终的结果应该是3才对。
也很可能是我太菜，想不明白，还请留言帮忙指出错误 我刚写这道题的时候就考虑到这一点了但是写出的代码提交在第十二个test就错了，
我的想法就是把每一条线段和它之后的有重叠的线段，把他们的重叠长度都求出来，然后用一个动态数组保存，最后用sort排序一下，那么数组中最后一个数就是最大的重叠长度。
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 60000+10;
struct node{
LL x1, x2;
};
struct node p[MAXN];
bool cmp( struct node p1, struct node p2 )
{
if( p1.x1 == p2.x1 )
return p1.x2 < p2.x2;
return p1.x1 < p2.x1;
}
vector<LL> ve;
int main()
{
int n;
int ans = 0;
while( ~scanf("%d", &n ) )
{
ve.clear();
for( int i=0; i<n; i++ )
scanf("%lld %lld", &p[i].x1, &p[i].x2 );
sort(p, p+n, cmp);
LL temp = 0;
for( int i=0; i<n; i++ )
{
for( int j=i+1; i<n; j++ )
{
if( p[i].x2 >= p[j].x2 )
{
temp = p[j].x2 - p[j].x1;
ve.push_back(temp);
}
else if( p[i].x2 >= p[j].x1 && p[i].x2 < p[j].x1 )
{
temp = p[i].x2 - p[j].x1;
ve.push_back(temp);
}
else
break;
}
}
sort(ve.begin(), ve.end());
if( ve.empty() )
printf("0\n");
else
printf("%lld\n", ve[ve.size()-1] );
}
return 0;
} E题 贪心，先从大到小排序，每次最大的和最小的能一起走就一起走，不能就大的自己走。
F题 用了一个很巧妙的方法，直接看代码，很易懂
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+10;
int num[MAXN];
int main()
{
int n;
while( scanf("%d", &n) != EOF )
{
for( int i=0; i<n; i++ )
scanf("%d", &num[i] );
int ans = 0;
if( num[0] == 0 )
ans ++;
for( int i=1; i<n; i++ )
{
switch (num[i])
{
case 0:
{
ans++;
break;
}
case 1:
{
if( num[i-1] == 1 )
ans ++, num[i] = 0;
break;
}
case 2:
{
if( num[i-1] == 2 )
ans ++, num[i] = 0 ;
break;
}
case 3:
{
if(num[i-1] == 1)
num[i] = 2;
else if(num[i-1] == 2 )
num[i] = 1;
break;
}
}
}
printf("%d\n", ans );
}
return 0;
} G题的方法有些想不到。先求前一个的gcd并存到数组，然后是前两个，前三个，一直到最后一个。 然后逆序的再把这个数列的gcd求一遍，并放入一个新的数组。然后取正序求得gcd中的倒数第二个，倒序中正数第二个两者的最大值。这样得到的是去掉数列中第一个或者最后一个剩下的数的最大公约数。然后开一个循环，具体看代码，这个循环求得每次都是除掉数列两头的数，每次漏掉中间的一个数的最大公约数。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000+10;
int num[MAXN];
int vb[MAXN];
int ve[MAXN];
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a ;
}
int main()
{
int t;
cin >> t;
while( t-- )
{
int n;
scanf("%d", &n );
for( int i=0; i<n; i++ )
scanf("%d", &num[i]);
vb[0] = num[0];
for( int i=1; i<n; i++ )
{
vb[i] = gcd( num[i], vb[i-1] );
}
ve[n-1] = num[n-1];
for( int i = n-2; i>=0; i-- )
{
ve[i] = gcd(num[i], ve[i+1]);
// ve[i] = temp;
}
int ans = max(vb[n-2], ve[1]);
for( int i=1; i<n-1; i++ )
{
ans = max(ans, gcd(vb[i-1], ve[i+1]));
}
printf("%d\n", ans );
}
return 0;
} H题和 I 题都是直接暴力遍历一遍就行了，注意可能爆 int
J题是2011年的ACM亚洲区域赛的一道题，具体见杭电4007题。
这道题在百度上搜索一下，解法有很多种，这里只说一下我认为最简单的一种，其实也是百度了很多种解法，比较得到的
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000+10;
struct node {
int x, y;
};
struct node p[MAXN];
int arrx[MAXN]; // 便于储存筛选出的x坐标
int arry[MAXN]; // 便于储存筛选出的y坐标
bool cmp( int a, int b )
{
return a < b;
}
int main()
{
int n, r;
while( cin>> n >> r )
{
for( int i=0; i<n; i++ )
{
scanf("%d %d", &p[i].x, &p[i].y );
arry[i] = p[i].y;
}
sort(arry, arry + n, cmp);
int ans = 0;
for( int i=0; i<n; i++ )
{
int temp = arry[i]; // 搜索的正方形的下边
int cntx = 0; // 符合条件的x的个数
for( int j=0; j<n; j++ )
{
if( p[j].y >= temp && p[j].y <= temp + r )
arrx[cntx++] = p[j].x; // 筛选出符合纵坐标上条件的x
}
sort(arrx, arrx + cntx, cmp);
int edx = 0;
for( int j=0; j<n; j++ )
{ // arrx[edx] - arrx[j]得到的是当前两点的水平距离
while( edx < cntx && arrx[edx] - arrx[j] <= r )
edx ++;
ans = max(ans, edx- j);
}
}
printf("%d\n", ans );
}
return 0;
} 大概就是先用一个数组保存每个点的y坐标，然后用这个数组筛选出符合条件的x的坐标，然后在用这些符合条件的点来遍历一下，最多能有多少个点符合条件。这里说一下变量edx是什么，首先edx表示的已经找到的符合条件的点数，但是它定义在j的外面，而 arr[j] 表示的是边长为 r 的正方形的左边界，所以当然最后edx要减去 j 才得到的是当前矩形位置有多少个点符合条件。
京公网安备 11010502036488号