Codeforces Round #830 (Div. 2)
A. Bestie
题目描述：
n个数字，你需要通过进行若干次如下操作使得
，操作如下：
- 选择一个下标
i，使得,花费是 n-i+1问最小花费是多少
思路：
显然尽可能选靠后的
i进行操作最好我们最多只需要操作两次，就能使得数组的gcd=1，方法就是操作任意两个相邻的
i
- 所以我们只需要对第
n位进行一次判断，如果gcd=1，就输出1- 如果不行，就对第
n-1位，如果gcd=1，就输出2- 否则输出
3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int ar[100];
ll gcd(ll a, ll b){
if(b) return gcd(b, a % b);
else return a;
}
int main(){
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> ar[i];
}
int g = ar[1];
for(int i = 2; i <= n; ++i){
g = gcd(g, ar[i]);
}
if(g == 1){
cout << 0 << endl;
}
else{
int ans = 3;
for(int i = n - 1; i <= n; ++i){
int x = gcd(i, ar[i]);
for(int j = 1; j <= n; ++j){
if(i == j)continue;
x = gcd(x, ar[j]);
}
if(x == 1)
ans = min(ans, n-i+1);
}
cout << ans << endl;
}
}
return 0;
}
B. Ugu
题目描述：
给出一个01字符串
你可以进行若干次下面的操作：
- 选择一个下标
i，使得i<=j<=n的所有字符都取反问最少要进行多少次操作，才能使得字符串前面部分全是0，后面全是1
思路：
显然相邻的相同的字符可以忽略掉，这样我们统计出来01交换的次数
如果第一位是0，则给数量减1后输出
如果第一位是1，则直接输出
#include <bits/stdc++.h>
using namespace std;
int n, m, k, x;
char ar[200050];
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;cin >> t;while(t--){
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> ar[i];
int fuck = 0;
for(int i = 1; i < n; ++i){
if(ar[i] != ar[i + 1])++fuck;
}
if(ar[1] == '0')--fuck;
cout << max(0, fuck) << endl;
}
return 0;
}
C1. Sheikh (Easy version)
题目描述：
给定一个数组
a[i]，你需要从1到n找到一个子区间，使得区间和-区间异或和最大，如果存在多种答案的话，请输出最小长度的区间
思路：
我们假设
sum[i]为前缀和，suf[i]为前缀异或和显然加上数字
x，异或最多增加x，也就是说sum[i]-suf[i]是不下降的一组数，所以最大值肯定是sum[n] - suf[n]，我们要做的是缩小区间长度我们可以二分区间长度
check的时候就暴力枚举每个区间，判断值是否等于
sum[n]-suf[n]求出最短区间后，就从头开始枚举起点
l，找到那个区间就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define int long long
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
int sum[MAX];
int mul[MAX];
int ans;
bool judge(int mid){
for(int i = 1; i + mid - 1 <= n; ++i){
if(sum[i+mid-1] - sum[i-1] - (mul[i+mid-1]^mul[i-1]) >= ans)return true;
}
return false;
}
void work(){
cin >> n >> m;
ans = 0;
for(int i = 0; i <= n; ++i)sum[i] = mul[i] = 0;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
sum[i] = sum[i - 1] + tr[i];
mul[i] = mul[i - 1] ^ tr[i];
}
ans = sum[n] - mul[n];
int l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
if(judge(mid))r = mid - 1;
else l = mid + 1;
}
int al = 1, ar = 1;
for(int i = 1; i + l - 1 <= n; ++i){
if(sum[i+l-1]-sum[i-1] - (mul[i+l-1]^mul[i-1]) >= ans){
al = i; ar = i + l - 1;
break;
}
}
cin >> x >> x;
cout << al << ' ' << ar << endl;
}
signed main(){
io;
int t;cin>>t;while(t--)
work();
return 0;
}
C2. Sheikh (Hard Version)
题目描述：
加强版的问题是
Q次询问，每次询问都是问l到r,输出每个区间对应的答案
思路：
根据上面的思路，最大的数值肯定是
sum[r]-sum[l-1]-suf[r]^suf[l-1],我们要做的就是其实就是将l和r往里移动，假设最终答案是al, ar那什么样的数可以删掉呢？
就是区间的数字和等于异或和时，即区间内数字在2进制上没有交集，比如：1 2 4 8这样的
根据鸽巢原理，假设数字最多30位，则最多只需要31个非0的数字就一定会存在2进制上存在交集的情况
再可以发现区间和和区间异或和与数字的顺序毫无关系，而且需要删除的数字必须放一起考虑，所以我们可以将要删除的
a[l]-a[al-1]和a[r+1]-a[ar]放在一起，左边加上右边一共最多需要删除32位，所以我们可以枚举左边删多少位，右边删多少位，然后暴力判断求解就行比较坑的是存在0的情况，我们需要用类似并查集的东西来跳过0的元素
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
ll tr[MAX];
ll sum[MAX], fuck[MAX];
int suf[MAX];
int pre[MAX];
int x, y;
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
sum[i] = sum[i - 1] + tr[i];
fuck[i] = fuck[i - 1] ^ tr[i];
}
pre[1] = 0;
for(int i = 2; i <= n; ++i){
if(tr[i - 1] == 0)pre[i] = pre[i - 1];
else pre[i] = i - 1;
}
suf[n] = n + 1;
for(int i = n - 1; i >= 1; --i){
if(tr[i + 1] == 0)suf[i] = suf[i + 1];
else suf[i] = i + 1;
}
while(m--){
cin >> x >> y;
ll ans = sum[y] - sum[x - 1] - (fuck[y] ^ fuck[x - 1]);
if(ans == 0){
cout << x << ' ' << x << endl;
continue;
}
int len = inf, al = 0, ar = 0;
for(int i = x, a = 0; i <= y && a <= 31; i = suf[i], ++a){
for(int j = y, b = 0; j >= i && b <= 31; j = pre[j], ++b){
if(sum[j] - sum[i-1] - (fuck[j]^fuck[i-1]) == ans && j - i + 1 < len){
len = j - i + 1;
al = i;ar = j;
}
}
}
cout << al << ' ' << ar << endl;
}
}
int main(){
io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
work();
}
return 0;
}
D1. Balance (Easy version)
题目描述：
存在一个空的集合，有两种操作
+ x，将x插入到集合中去? k，询问k的最小未出现的倍数
思路：
暴力
我们开一个
map<ll, ll>mp,记录上次询问这个数字x的答案，即上一次询问x的最小未出现的倍数，开一个set<ll>记录数字是否出现，对于每次查询，我们暴力跑他的倍数，直到找到第一个没出现过的倍数输出就行，并更新一下map
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll x;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n;
set<ll>s;
map<ll, ll>mp;
char p;
for(int i = 1; i <= n; ++i){
cin >> p >> x;
if(p == '+'){
s.insert(x);
}
else{
ll fuck = mp.count(x) ? mp[x] : x;
while(s.count(fuck)){
fuck += x;
}
mp[x] = fuck;
cout << fuck << endl;
}
}
return 0;
}
D2. Balance (Hard version)
题目描述：
比D1多一个删除操作
- x，从集合中删除掉x
思路：
我们考虑一种最简单的求存在删除操作的mex的方法
即开一个
set,初始将1-MAX的数字全放进去对于每个添加操作，我们只需要从set中删除这个数字
对于每个删除操作，我们只需要从set中添加这个数字
对于每个查询操作，我们只需要输出set中最小的数字
对于这个题，我们思考一下上一个做法不可行的原因：删除一个数字，则他出现所有因子的答案都可能会发生改变，所以不能暴力更新
首先还是需要一个
set<ll>vis;来标记这个数字是否在集合中，map<ll, ll>ans,记录上一次的答案我们需要考虑开一个
map<ll, vector<ll>>v;的容器存一下上面出现的那个问题，即v[x]的vector对应的是如果删除x，会受到影响的那些数字，正常来说是所有因子都会受到影响，但是我们其实只需要存之前出现过的，且是x因子的那些数字就行比如说：查询
x的时候要进行数字的跳跃，去找每个x的倍数y，如果y存在于数字集合中的话，我们需要跳到下一个x的倍数，但是对于此时的y，如果把y删掉，是会对x的答案产生影响的，所以需要我们往v[x]中塞入y,作为标记此外，我们还需要对每一个数字
x，都开一个set，即map<ll, set<ll>>mp,意义和最简单的求带删除操作的mex的set 差不多，但是他其实只是维护的被删除的元素产生的影响，他不需要进行集合的初始化，即不需要像普通集合一样初始的时候塞进1-MAX,而且是在总集合删除元素的时候会进行集合的元素的塞入（为什么是塞入已经在上面介绍简单的mex中讲过了），同样的移除的时候是在总集合增加元素的时候进行的。其实，
mp[x]记录的是x到mp[x]中被删除的x的倍数的集合，所以对于一次查询x，我们首先看他的mp[x]是否存在元素，如果存在的话就表示由于删除过x的小倍数，导致当前的ans[x]不是最小的mex，我们就需要用mp[x]中找答案，答案就是mp[x]中数字最小的元素。如果mp[x]不存在元素，则我们需要暴力去从mp[x]往上跑x的倍数，直到找到第一个没出现过的x的倍数,这个过程就跟D1一样了
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, x;
char p;
void work(){
cin >> n;
map<ll, bool>vis;
map<ll, ll>ans;
map<ll, set<ll>>mp;
map<ll, vector<ll>>v;
while(n--){
cin >> p >> x;
if(p == '+'){
vis[x] = 1;
for(auto u : v[x])mp[u].erase(x);
}
else if(p == '-'){
vis[x] = 0;
for(auto u : v[x])mp[u].insert(x);
}
else {
if(!ans.count(x))ans[x] = x;
if(mp[x].size())cout << *mp[x].begin() << endl;
else{
while(vis[ans[x]]){
v[ans[x]].push_back(x);
ans[x] += x;
}
cout << ans[x] << endl;
}
}
}
}
int main(){
io;
work();
return 0;
}
