枚举
1443. 拍照
题目大意：
给定b数组，其中$b_i=a_{i−1}+a_i$
求a数组的可能解中的字典序最小的解
其中a要满足1-n中取值且不能重复
思路：
对每个a[1]，都能唯一确定整个a数组
只需要在求a数组的过程中判断每个数是否满足：不重复且范围在1-n
因为要字典序最小，所以在给a[1]赋值的时候从小到大赋值，求到第一个可以的a数组即是答案
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int a[N], b[N];
bool st[N];
bool check(int a1)
{
memset(st, 0, sizeof st);
a[1] = a1;
st[a1] = true;
for (int i = 2; i <= n; i ++ )
{
a[i] = b[i - 1] - a[i - 1];
if (a[i] < 1 || a[i] > n) return false;
if (st[a[i]]) return false;
st[a[i]] = true;
}
for (int i = 1; i <= n; i ++ )
cout << a[i] << ' ';
return true;
}
int main()
{
cin >> n;
for (int i = 1; i < n; i ++ ) cin >> b[i];
for (int i = 1; i <= n; i ++ )
if (check(i))
break;
return 0;
}
3347. 菊花链
题目大意：
有多少个区间，其中存在整个区间的平均数
思路：
区间内是否存在某个数字：hash set
有时候需要用到快慢指针，本题不需要
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N = 110;
int n;
int p[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> p[i];
int res = 0;
for (int i = 0; i < n; i ++ )
{
unordered_set<int> hash;
for (int j = i, s = 0; j < n; j ++ )
{
s += p[j];
hash.insert(p[j]);
int cnt = j - i + 1;
if (s % cnt == 0 && hash.count(s / cnt))
res ++ ;
}
}
cout << res << endl;
return 0;
}
1789. 牛为什么过马路 II
题目大意：
给一个长度为52的字符串，26个字母每个出现2次，表示一个环，把相同的字母连线，问有几个字母发生了交叉？
思路：
发生交叉：有且仅有一个字母在两个相同字母中间
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> p[26];
int main()
{
string s;
cin >> s;
for (int i = 0; i < s.size(); i ++ )
p[s[i] - 'A'].push_back(i);
int res = 0;
for (int i = 0; i < 26; i ++ )
for (int j = i + 1; j < 26; j ++ )
{
int cnt = 0;
for (auto y: p[j])
if (p[i][0] < y && y < p[i][1])
cnt ++ ;
if (cnt == 1) res ++ ;
}
cout << res << endl;
return 0;
}
1875. 贝茜的报复
题目大意：
多少种给变量赋值的方法可以使得表达式的计算结果为偶数
思路：
二进制枚举，每位代表一个数
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
int main()
{
int n;
cin >> n;
//存储每种字母取奇数和偶数分别有几种情况，例如 cnt[0]['B'] = 3 代表B字母取偶数有3中情况
unordered_map<char,int> cnt[2];
while(n --){
char c;
int x;
cin >> c >> x;
cnt[abs(x) % 2][c] ++;
}
char str[] = "BESIGOM";
int res = 0;
//记录在某种情况下某个字母是取奇数还是偶数，例如 v['B'] = 1代表当前情况B取奇数
unordered_map<char,int> v;
//枚举每一种情况，用一个二进制数来表示 i = 1110000 表示： BES取奇数，IGOM取偶数
for(int i = 0; i < 1 << 7; i ++){
//检验i的每一位是0还是1，代表每个字母是取奇数还是偶数
for(int j = 0; j < 7; j ++){
v[str[j]] = i >> j & 1;
}
if((v['B'] + v['I']) * (v['G'] + v['O'] + v['E'] + v['S']) * v['M'] % 2 == 0)
{
int sum = 1;
for(int j = 0; j < 7; j ++){
sum *= cnt[i >> j & 1][str[j]];
}
res += sum;
}
}
cout << res << endl;
return 0;
}
1855. 愤怒的奶牛
题目大意：
每次爆炸，会引爆周围的草，并使下一次的爆炸半径+1，问能够引爆的干草捆最大数量
思路：
枚举第一次引爆的牛，计算引爆干草的数量
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, INF = 2e9;
int n;
int p[N];
int main()
{
cin >> n;
p[0] = -INF, p[n + 1] = INF;
for (int i = 1; i <= n; i ++ )cin >> p[i];
sort(p + 1, p + n + 1);
int res = 0;
for (int i = 1; i <= n; i ++ ){
//l 代表当前向左爆炸的半径,开始是1，每移动一次a则l + 1，r代表当前向又爆炸的范围
int l = 1, r = 1, a = i, b = i;
//当可以进行下一次引爆
while (p[a] - p[a - 1] <= l)
{
//找到下一次可以引爆的最左边的地方
int k = a - 1;
//当a能够到k左边一个位置，则将k--
while (p[a] - p[k - 1] <= l) k -- ;
a = k;
l ++ ;
}
while (p[b + 1] - p[b] <= r)
{
int k = b + 1;
while (p[k + 1] - p[b] <= r) k ++ ;
b = k;
r ++ ;
}
res = max(res, b - a + 1);
}
cout << res << endl;
return 0;
}
1826. 农田缩减
题目大意：
二维平面，给了一堆点的坐标，问去掉那个点后，剩下的坐标用矩形框起来，这个矩形面积最小
思路：
枚举每个点被删除，看被删除的点是不是最大值或是最小值，是的话就赋值为次小次大，不是的话就赋值为最小最大
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
int x[N], y[N], a[N], b[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d%d", &x[i], &y[i]);
a[i] = x[i], b[i] = y[i];
}
sort(a, a + n);
sort(b, b + n);
int res = 2e9;
//枚举每个点被删除
for (int i = 0; i < n; i ++ )
{
//分别记录x的最小，最大，y的最小，最大
int x1, x2, y1, y2;
//看被删除的点是不是最大值或是最小值
//是的话就赋值为次小次大，不是的话就赋值为最小最大
x1 = x[i] == a[0] ? a[1] : a[0];
x2 = x[i] == a[n - 1] ? a[n - 2] : a[n - 1];
y1 = y[i] == b[0] ? b[1] : b[0];
y2 = y[i] == b[n - 1] ? b[n - 2] : b[n - 1];
res = min(res, (x2 - x1) * (y2 - y1));
}
printf("%d\n", res);
return 0;
}
1913. 公平摄影
题目大意：
两种牛，站成一排，照片中要么只出现一种牛，要么两种牛的数量一样，问照片的尺寸(最左边的牛和最右边的牛的坐标之差)最大是多少
思路：
设两种牛分别是1和-1，则区间[i,j]内两种牛的数量一样等价于该区间的区间和为0,即$S_j - S_{i - 1} = 0$即$S_j=S_{i-1}$
记$S^_i=S_{i-1},则S_j=S^_{i}$,记录每个$S^`_i$第一次出现的位置，当该数值之后再出现的时候，用新的位置减去第一次出现的位置
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
PII q[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
int x;
char str[2];
scanf("%d%s", &x, str);
if (*str == 'G') q[i] = {x, 1};
else q[i] = {x, -1};
}
sort(q + 1, q + n + 1);
unordered_map<int, int> hash;
int res = 0, sum = 0, last;
for (int i = 1; i <= n; i ++ )
{
//记录每个S`i第一次出现的位置（sum没加q[i].y，则sum为S`i）
if (!hash.count(sum)) hash[sum] = q[i].x;
sum += q[i].y;
//如果当前sum以前出现过，则用当前位置减去第一次出现的位置
if (hash.count(sum)) res = max(res, q[i].x - hash[sum]);
//计算最长的全是1或-1的区间的长度，如果当前点和上一个点不一样，则当前点是下一个区间的起点
if (i == 1 || q[i].y != q[i - 1].y) last = q[i].x;
res = max(res, q[i].x - last);
}
printf("%d\n", res);
return 0;
}
1978. 奶牛过马路
题目大意：
一群牛过马路，第i头牛从ai点走到对面的bi点，问有几头牛的路线和别的牛的路线都没有交叉
思路：
如果第i头牛和别的牛没有交叉，保证：$max(b_1,b_2…b_{i-1}) < b_i$,$min(b_{i+1}…b_n)>b_i$
即：b[i]的前缀最大值小于b[i]，b[i]的后缀最小值小于b[i]
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010, INF = 1e8;
int n;
PII q[N];
int smax[N], smin[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &q[i].x, &q[i].y);
sort(q + 1, q + n + 1);
smax[0] = -INF, smin[n + 1] = INF;
for (int i = 1; i <= n; i ++ ) smax[i] = max(smax[i - 1], q[i].y);
for (int i = n; i; i -- ) smin[i] = min(smin[i + 1], q[i].y);
int res = 0;
for (int i = 1; i <= n; i ++ )
if (smax[i - 1] < q[i].y && smin[i + 1] > q[i].y)
res ++ ;
printf("%d\n", res);
return 0;
}
1969. 品种邻近
题目大意：
一排牛，每只牛有一个品种ID。
如果两头牛的品种ID相同，且距离小于k,则这叫一个拥挤奶牛对
问拥挤奶牛对中品种ID最大的是多少。
思路：
判断某个ID在之前出现的位置：
法一：用一个map存储每个id最后出现的位置
法二：将当前牛的前k个位置放入一个队列中，并用一个数组记录队列中的每个元素出现的次数，若当前牛的品种ID出现在队列中，则这是一个拥挤奶牛对
代码：
法一：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int M = 1000010;
int cnt[M];
map<int,int> m;
int main()
{
int n;
int k;
cin >> n >> k;
int res = -1;
for(int i = 0; i < n; i ++){
int id;
cin >> id;
if(m.count(id)){
if(i - m[id] <= k)res = max(res, id);
}
m[id] = i;
}
cout << res << endl;
return 0;
}
法二：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int M = 1000010;
int cnt[M];
queue<int> q;
int main()
{
int n;
int k;
cin >> n >> k;
int res = -1;
for(int i = 0; i < n; i ++){
int id;
cin >> id;
if(cnt[id])res = max(res, id);
q.push(id);
cnt[id] ++;
if(q.size() > k){
cnt[q.front()] --;
q.pop();
}
}
cout << res << endl;
return 0;
}
1960. 闪烁
题目大意：
农夫约翰对牛棚里昏暗的灯光感到不满，刚刚安装了一个新吊灯。
新吊灯由 N 个灯泡组成，这 N 个灯泡围成一圈，编号为 0∼N−1。
奶牛对这个新吊灯非常着迷，并且喜欢玩以下游戏：
对于第 i 个灯泡，如果在 T−1 时刻，它左侧的灯泡（当 i>0 时，为第 i−1个灯泡；当 i=0 时，为第 N−1 个灯泡）是开着，那么在 T 时刻，就切换这个灯泡的状态。
这个游戏将持续 B 单位时间。
给定灯泡的初始状态，请确定在 B 单位时间后，它们的最终状态。
思路：
用一个数state的每一位表示某个灯的亮灭
记录从当前到每个state的走的步数
如果走到了之前走到的state，则说明走到了环的入口
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1 << 16;
int n;
LL m;
//p数组表示某一种状态从原点走几步走到
int p[N];
int update(int state){
int res = 0;
for(int i = 0; i < n;i ++){
int j = (i - 1 + n) % n;
//x是原来的第i位，y是原来的第i - 1位
int x = state >> i & 1, y = state >> j & 1;
//如果y是1，则把新的状态(res)的第i位置为与x相反
if(y) {
if(x) res |= 0 << i;
else res |= 1 << i;
}
//否则，res的第i位即x
else{
res |= x << i;
}
// res |= (x ^ y) << i;
// 等价于 res |= (x ^ y) << i;
}
return res;
}
void print(int state)
{
for (int i = 0; i < n; i ++ )
cout << (state >> i & 1) << endl;
}
int main()
{
cin >> n >> m;
//state的二进制表示形式表示每一位的灯是亮还是灭
int state = 0;
//逐位设置每个灯是亮还是灭
for(int i = 0; i < n; i ++){
int x;
cin >> x;
state |= x << i;
}
memset(p, -1, sizeof(p));
p[state] = 0;
for(int i = 1;;i ++){
//update函数返回接下来一步的状态
state = update(state);
//走到了最后一步，则输出
if(i == m){
print(state);
break;
}
//新的一步在之前没走过，则记录从源点走到该状态所需的步数i，p[state] = i;
else if(p[state] == -1)p[state] = i;
//新的一步在之前出现过，说明走到了循环的入口，state即循环入口的状态
else{
//循环的长度，即当前的步数减去从源点走到循环入口的长度
int len = i - p[state];
int r = (m - i) % len;
while(r --)state = update(state);
print(state);
break;
}
}
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com
