url:Dashboard - Codeforces Round #843 (Div. 2) - Codeforces
A1&&A2. Gardener and the Capybaras
题意:
给你一个只由$a$和$b$两个字符组成的字符串
现在要你把这个字符串分成$s1,s2,s3$三部分,要求满足下面的两个条件之一
$s2 >s1ands2 > s3$
$s2 < s1ands2 < s3$
思路:
一开始就想暴力的,但是看了看后面还有a2,所以这题一定有简单的方法
由于只有$a$和$b$两个字符,所以只要$s2$第一个字符是$b$的话,两边就很难大过$s2$
所以我们只要分为:开头的一个字母,中间的字母,最后的一个字母即可
这样的话就一定是$s2$最大
但是这是整个字符串第二个字符为$b$的情况
如果第二个字符为$a$的话
只要单独把这个$a$放到$s2$即可
代码:
void solve()
{
string s1;
cin >> s1;
if(s1[1] == 'a')
{
cout << s1[0] << " " << s1[1] << " ";
for(int i = 2;i < s1.size();i++) cout << s1[i];
cout << endl;
}
else
{
cout << s1[0] << " ";
for(int i = 1;i < s1.size() - 1;i++) cout << s1[i];
cout << " ";
cout << s1[s1.size() - 1] << endl;
}
}总结:
按照字典序来说的话
一个字符串在前面字符相同的情况下要大的话,后缀越长越好
一个字符串在前面字符相同的情况下要小的话,后缀越短越好
B. Gardener and the Array
题意:
给n个数,问是否能从这个n个数的子序列中找到两个子序列满足:
a子序列的值全部or起来 = b子序列的值全部or起来
思路:
最开始没见过这种给数据的方法(
居然还把这个数组给还原了(
后来才发现这种方式更好用
最开始的想法是找一对数,使得其中一个数的二进制性质的1包含另一个数的二进制形式的1
但是发现这样也不好搞,搞出来时间复杂度还是$O(n2)$(而且后来发现情况也没包含完整)
正确思路是先全部or起来然后看能不能找到一个数,去掉这个数以后值仍然不变
去掉那个数之后的子序列便是第二个子序列
这就要求去掉的那个数里面的每个二进制形式的1的位置都要在其他数字里面出现过
所以这里用个map来记录每个数二进制形式1的位置的数量
然后就每次扫一遍那个数的二进制形式1
看是否每个每个二进制形式的1的位置在map里面都>=2
如果是就直接YES
如果扫完了都找不到就NO
代码:
void solve()
{
map<int,int> mp;
cin >> n;
vector<int> a[n + 1];
for(int i = 1;i <= n;i++)
{
cin >> temp;
int op;
for(int j = 1;j <= temp;j++)
{
cin >> op;
a[i].pb(op);
mp[op]++;
}
}
for(int i = 1;i <= n;i++)
{
bool flag = 0;
for(auto it : a[i])
{
if(mp[it] < 2)
{
flag = 1;
break;
}
}
if(!flag)
{
YES;
return;
}
}
NO;
}总结:
如果题目给的二进制形式,那就一定要考虑位运算,并且给的什么形式就考虑什么形式
想一想题目给的条件怎么样才最容易到达
这里最开始想的去找一对数明显就思路出问题了
全部or起来是最容易产生一个子序列包含另一个子序列的情况
C. Interesting Sequence
题意:
给一个数n和一个数x
问你能不能找到一个数$m$满足$m > n$而且$(n)and (n + 1) and (n + 2) ...... m = x$
思路:
一看就是位运算题,所以先考虑把例子转化成二进制形式来看
考虑是与性质
将情况分为一下四种:
1:原位置上是0,目标位置是0
这种情况就很简单,因为根据与性质,只要有0就只会是0,所以这种情况可以直接跳过
2:原位置上是0,目标位置是1
这种情况就不可能,还是与的性质,直接退出输出-1
3:原位置上是1,目标位置是0
这种就要求在不断的与运算的时候,这一位上出现过0即可
咋个才能找到最小的并且这一位出现过0呢(因为要最小,所以肯定就是这一位第一次是0的时候)
就直接先提取出这一位以及前面的位,用$n / (1 << i)即可$
然后将这个二进制数加一
由于原位置的数字是1,加一以后进位变成0
所以就刚好满足了条件
然后再用0补全二进制形式,用$* (1 << i)$即可
这里肯定是最小的,因为是该位进位变成0
解释一下这个操作
众所周知在二进制位运算中 * 2就相当于二进制形式多个0, / 2就相当于去掉后面的一位
这里$1 << i$就代表当前是哪一位,然后用原数除去,就相当于去掉了后面的位数
补0操作同理
4:原位置上是1,目标位置是1
这种情况就必须要在累于的时候这一位一直是1才行
所以就是求一个最大的数满足这一位是1
所以操作同样是提取出这一位以及前面的位数,然后+1然后补0
然后这里要-1来保证这一位以及后面的位数全是1
这样就是最大的
最后就求出一个最大值和一个最小值,如果最大值小于了最小值就输出-1,否则就输出最小值
代码:
void solve()
{
cin >> n >> m;
bitset<64> x(n),y(m);
int l = 0,r = 4e18;
if(m > n)
{
cout << -1 << endl;
return;
}
else if(m == n)
{
cout << n << endl;
return;
}
for(int i = 63;i >= 0;i--)
{
if(x[i] == 0&&y[i] == 0) continue;
else if(x[i] == 1&&y[i] == 0)
{
l = max(l,(n / (1ll << i) + 1ll) * (1ll << i));
}
else if(x[i] == 0&&y[i] == 1)
{
cout << -1 << endl;
return;
}
else
{
r = min(r,((n / (1ll << i) + 1ll) * (1ll << i)) - 1ll);
}
}
if(l > r) cout << -1 << endl;
else cout << l << endl;
// cout << l << " " << r << endl;
}总结:
位运算问题考虑用bitset来解决,非常方便
对于这种数字比较大的运算,数字要加ll
E. The Human Equation
题意:
给n个数字,你能选择一个序列进行奇数位+1偶数位-1或者奇数位-1偶数位+1的操作
要求最后数字全为0,问最少要多少次操作
思路:
最开始想的是一正一负这种最优,但是具体咋个整不会(
然后又想到for+while循环逆序去找前面的数字配对,感觉这样会超时
所以正确思路就是用两个变量来记录就行了
由于操作的是序列,也就是非连续的,那么就相当于随便选
那么每个数字在操作过后都能带给后面减少次数的机会
用两个数字来记录这种机会
每个正数在操作时会先考虑前面有多少"正数机会",并且给后面提供"负数机会"
每个负数在操作时会先考虑前面有多少"负数机会",并且给后面提供"正数机会"
代码:
void solve()
{
cin >> n;
int cnt1 = 0,cnt2 = 0,ans = 0;
vector<int> a(n + 1);
for(int i = 1;i <= n;i++) cin >> a[i];
for(int i = 1;i <= n;i++)
{
// cout << cnt1 << " " << cnt2 << endl;
if(a[i] > 0)
{
temp = a[i];
a[i] = max(0ll,a[i] - cnt1);
cnt1 = max(0ll,cnt1 - temp);
ans += a[i];
cnt2 += temp;
}
else
{
a[i] *= -1;
temp = a[i];
a[i] = max(0ll,a[i] - cnt2);
cnt2 = max(0ll,cnt2 - temp);
ans += a[i];
cnt1 += temp;
}
}
cout << ans << endl;
}总结:
由于序列是无序的,所以相当于随便选,所以这种就很容易传递
并且不用for循环与while循环去判断
就直接用两个变量即可模拟传递过程
标签：A1A2BCE,843,temp,二进制,待补,s2,位置,int,序列 From： https://www.cnblogs.com/rickly233/p/17051038.html