捕获

时间限制:3000MS
内存限制:589824KB

题目描述

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。
敌人的位置将被一个二维坐标(x, y)所描述。
小美有一个全屏技能,该技能能一次性将若干敌人一次性捕获。
捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。
现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述

第一行三个整数N,A,B,表示共有N个敌人,小美的全屏技能的参数A和参数B。
接下来N行,每行两个数字x,y,描述一个敌人所在的坐标。
1≤N≤500，1≤A,B≤1000,1≤x,y≤1000。

输出描述

一行,一个整数表示小美使用技能单次所可以捕获的最多数量。

样例输入

3 1 1
1 1
1 2
1 3

样例愉出

2

思路：这道题如果直接在二维数组中标点并进行统计的话，由于图坐标范围比较大，因此不太可靠，同时点数相对二维图的大小来说过于少了。换个思路，其实只需要对每个点统计这个点作为左上、左下、右上、右下点时包含的数量即可，每次加入第i个点的时候，和前面i-1个点计算一下并维护一下各自的四个值。举例来说，如果一个点i作为左上角时包含一个点t，那么t作为右下角时一定也会包含点i，当然值得注意的是这个不能说明点i作为左上角和点t作为右下角对应的矩形是相同的，只能说各自在对方的包含域里而已。

#include
#include
using namespace std;struct Point{int x, y, left_up_num, left_down_num, right_up_num, right_down_num;
};const int maxn = 5e2 + 5;
Point points[maxn];int main(){int N, A, B, x, y, idx, pre_idx, max_num = 0, diff_x, diff_y;cin >> N >> A >> B;for(idx = 0; idx < N; ++ idx){cin >> x >> y;points[idx] = Point{x, y, 1, 1, 1, 1};for(pre_idx = 0; pre_idx < idx; ++ pre_idx){diff_x = points[idx].x - points[pre_idx].x;diff_y = points[idx].y - points[pre_idx].y;if(abs(diff_x) > A || abs(diff_y) > B){continue;}//由于存在共线即diff_x = 0或diff_y = 0的情况 因此不能直接else  if(diff_x <= 0 && diff_y <= 0){// 当前点作为左上角  对应点作为右下角 //cout << "(" << points[idx].x << "," << points[idx].y << ")" << "作为左上角 包含(" << points[pre_idx].x << "," << points[pre_idx].y << ")" << endl;++ points[idx].left_up_num;++ points[pre_idx].right_down_num;max_num = max(max_num, max(points[idx].left_up_num, points[pre_idx].right_down_num));}if(diff_x >= 0 && diff_y <= 0){// 当前点作为左下角  对应点作为右上角 //cout << "(" << points[idx].x << "," << points[idx].y << ")" << "作为左下角 包含(" << points[pre_idx].x << "," << points[pre_idx].y << ")" << endl;++ points[idx].left_down_num;++ points[pre_idx].right_up_num;max_num = max(max_num, max(points[idx].left_down_num, points[pre_idx].right_up_num));}if(diff_x <= 0 && diff_y >= 0){// 当前点作为右下角  对应点作为左下角 //cout << "(" << points[idx].x << "," << points[idx].y << ")" << "作为右下角 包含(" << points[pre_idx].x << "," << points[pre_idx].y << ")" << endl;++ points[idx].right_down_num;++ points[pre_idx].left_up_num;max_num = max(max_num, max(points[idx].right_down_num, points[pre_idx].left_up_num));}if(diff_x >= 0 && diff_y >= 0){// 当前点作为右上角  对应点作为左下角 //cout << "(" << points[idx].x << "," << points[idx].y << ")" << "作为右上角 包含(" << points[pre_idx].x << "," << points[pre_idx].y << ")" << endl;++ points[idx].right_up_num;++ points[pre_idx].left_down_num;max_num = max(max_num, max(points[idx].right_up_num, points[pre_idx].left_down_num));}}//cout << "左上 左下 右上 右下" << endl;for(pre_idx = 0; pre_idx <= idx; ++ pre_idx){cout << "  " << points[idx].left_up_num << "    " << points[idx].left_down_num << "    " << points[idx].right_up_num << "    " << points[idx].right_down_num << endl;}}cout << max_num; 
}

彩带

时间限制:3000MS

内存限制:589824KB

题目描述

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。
因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。
显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。
你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

输入描述

第一行两个整数N,K,以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。
接下来一行N个整数，每个整数表示一种色彩,相同的整数表示相同的色彩。1≤N,K<5000，彩带上的颜色数字介于[1,2000]之间。

输出描述

一行，一个整数，表示选取的彩带的最大长度。

样例输入

8 3
1 2 3 2 1 4 5 1

样例输出

5

思路：我们对于每一种颜色记录该颜色上一次出现的位置，初始的时候，所有颜色的上一次出现位置为0。我们每次读取一个新的颜色，并判断当前颜色是否在已包含的颜色集合里，如果不存在，则增加一个颜色数量，同时判断数量是否超过K，如果超过，则在已有颜色里找到上一次出现位置最靠前的踢出集合，并将区间左端点(彩带最左端的前一个位置)移动到该位置，同时维护答案。

#include
#include

回文串

时间限制:3000MS
内存限制:589824KB

题目描述

现在小美获得了一个字符串。小羊想要使得这个字符串是回文串。
小美找到了你。你可以将字符串中至多两个位置改为任意小与英文字符'a'-'z'。
你的任务是帮助小美在当前制约下,获得字典序最小的回文字符串。
数据保证能在题目限制下形成回文字符串。
注:回文字符串:即一个字符串从前向后和从后向前是完全一致的字符串。
例如字符串ababa, aaaa,acca都是回文字符串。字符串abed, acea都不是回文字符串

输入描述

一行,一个字符串,字符串中仅由小写英文字符构成。
保证字符串不会是空字符串。
字符串长度介于[1, 100000]之间。

输出描述

一行,一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例输入

acca

样例输出

aaaa

思路：字符串，扫一遍看多少个位置不同

        A、如果没有位置不同，从头开始尝试变a，如果头已经是a，就考虑下一个，以此类推。

        B、如果只有一个位置不同，考虑前面部分的是不是a

                1、如果前面的是a，把后面的变a；现在还剩一次改动机会，需要考虑串的字符数是奇数还是偶数。如果是奇数，考虑把中心字符改为a；如果为偶数，则没法动，因为如果想把下一位改a，由于它们已经回文，要么本来就是a无需更改，要么两个相等且不为a，要同时改两个。

                2、如果前面的不是a，把前面的改为a后，若后面对应位置的也不为a，则后面的也改为a，用完两次机会。否则在为奇数串的情况下改中心字符为a。 

                总结来说：优先把不同的位置都变为a，如果有多余的机会，看是否可以改中心。

        C、如果有两个位置不同，对于每个不同的位置，考虑把字典序大的改成小的，因为如果前面的字典序大，改小更好，如果前面的字典序小，那只能选择把后面的改小。

#include
#include
#include
using namespace std;
int main(){string str;cin >> str;int str_len = str.length(), left = 0, right = str_len - 1, not_equal_num = 0, idx;vector not_equal_idx;while(left < right){if(str[left] != str[right]){++ not_equal_num;not_equal_idx.push_back(left);	not_equal_idx.push_back(right);} ++ left;-- right;}if(not_equal_num == 0){//没有不同 left = 0, right = str_len - 1;while(left < right){if(str[left] != 'a'){str[left] = str[right] = 'a';break;} ++ left;-- right;} }else if(not_equal_num == 1){//1个不同 left = not_equal_idx[0];right = not_equal_idx[1];str[left] = str[right] = min(str[left], str[right]);if(str_len & 1){str[str_len >> 1] = 'a';}}else{//2个不同 for(idx = 0; idx <= 2; idx += 2){left = not_equal_idx[idx];right = not_equal_idx[idx + 1];str[left] = str[right] = min(str[left], str[right]);}} cout << str;return 0;
}