题目大意
给定一个长度为n的数组，然后给定一个操作：每次选择一个区间l，r使得a[l] = a[l]&a[r], a[l + 1] = a[l + 1] & a[r - 1]…以此类推，你可以对此操作执行任意次，求最终数组中最大值的最小值
主要思路
我们思考如何得到最小值
- &操作不会使数变大，只会使数变小，那么我们能得到的最小值就是把数组中的所有数&起来，那么如何才能让这个值成为答案呢
- 首先我们取l，r为整个数组，其次取l，mid和mid + 1, 然后继续二分区间直到最后数组中的每个数就为将原序列都&起来的那个最小值
所以答案就是把数组中所有数都&起来即可
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010;
int n, a[N];
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
int res = a[0];
for(int i = 1; i < n; i++) res &= a[i];
cout << res << endl;
}
return 0;
}
题目大意
给定一个字符串让你把字符串中的？改为R或者B，问该串最少有多少对相邻且相同的字符
主要思路
贪心即可，让R周围的？是B，B周围的？是R
我是用队列实现的，应该有更简单的写法
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010;
int n, a[N];
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
string s;
cin >> s;
queue<int> q;
int len = s.size();
for(int i = 0; i < s.size(); i++) if(s[i] != '?') q.push(i);
if(q.size() == 0)
{
s[0] = 'R';
q.push(0);
}
while(q.size())
{
int t = q.front();
q.pop();
if(t - 1 >= 0 && t - 1 < len && s[t - 1] == '?')
{
if(s[t] == 'R') s[t - 1] = 'B';
else s[t - 1] = 'R';
q.push(t - 1);
}
if(t + 1 >= 0 && t + 1 < len && s[t + 1] == '?')
{
if(s[t] == 'R') s[t + 1] = 'B';
else s[t + 1] = 'R';
q.push(t + 1);
}
}
cout << s << "\n";
}
return 0;
}
题目大意
给定一个图，问能否找到一条路径使得能不重复的走遍所有点
主要思路
- 首先当a[1]为1时，路径为 n + 1 -> 1 -> 2 … -> n
- 然后当a[n]为0时，路径为 1 -> 2 -> 3 …-> n -> n + 1
- 然后当给定的数组中出现0 1序列时，一定会有 1 -> … -> i -> n + 1 -> i + 1 -> … -> n，接下来判断什么时候会出现0 1序列，当a[1]不为1且a[n]不为0时(因为已经特判)，数组中一定会出现0 1序列，所以找到该序列即可，不存在无解情况
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010;
int n, a[N];
signed main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while(T--)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
if(a[1] == 1)
{
cout << n + 1 << ' ';
for(int i = 1; i <= n; i++) cout << i << ' ';
cout << "\n";
}
else if(a[n] == 0)
{
for(int i = 1; i <= n + 1; i++) cout << i << ' ';
cout << "\n";
}
else
{
int cnt = -1;
for(int i = 2; i <= n; i++)
{
if(a[i - 1] == 0 && a[i] == 1)
{
cnt = i;
break;
}
}
for(int i = 1; i < cnt; i++)
{
cout << i << ' ';
}
cout << n + 1 << ' ';
for(int i = cnt; i <= n; i++)
{
cout << i << ' ';
}
cout << "\n";
}
}
return 0;
}
题目大意
给定两个森林，问给左边森林加一条边的同时也必须在右边的森林加一条边(两条边必须都未连接过)，且连接后两边还是森林，问最多能连几条边
主要思路
我们用并查集维护两个森林，由于n范围为1000，所以暴力枚举所有边，判断是否能连接即可，改边能连接的条件是，两个点在两个森林中都在不同的树上
AC代码
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl;
#define x first
#define y second
typedef long long ll;
const int N = 200010;
int n, m1, m2;
int p1[N], p2[N];
int ans;
pair<int, int> p[N];
int find(int x, int p[])
{
if (p[x] != x) p[x] = find(p[x], p);
return p[x];
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
T = 1;
while(T--)
{
cin >> n >> m1 >> m2;
for (int i = 1; i <= n; i ++ ) p1[i] = i;
for (int i = 1; i <= n; i ++ ) p2[i] = i;
for(int i = 0; i < m1; i++)
{
int a, b;
cin >> a >> b;
int t1 = find(a, p1);
int t2 = find(b, p1);
if(t1 != t2)
{
p1[t2] = t1;
}
}
for(int i = 0; i < m2; i++)
{
int a, b;
cin >> a >> b;
int t1 = find(a, p2);
int t2 = find(b, p2);
if(t1 != t2)
{
p2[t2] = t1;
}
}
for(int i = 1; i <= n; i++)
{
int t1 = find(i, p1);
int r1 = find(i, p2);
for(int j = 1; j <= n; j++)
{
if(i == j) continue;
int t2 = find(j, p1);
int r2 = find(j, p2);
if(t1 != t2 && r1 != r2)
{
p[ans++] = {i, j};
p1[t2] = t1;
p2[r2] = r1;
}
}
}
cout << ans << endl;
for(int i = 0; i < ans; i++)
{
cout << p[i].x << ' ' << p[i].y << endl;
}
}
return 0;
}
|