牛客小白月赛87
A小苯的石子游戏
题目描述：
Alice和Bob又在玩石子游戏了。
具体的,现在有n堆石子,第i堆石子里面有ai个石子,且石子数量按升序排列。Alice和Bob轮流操
作,Alice先手操作,当前玩家从剩余的石子堆中任选一堆石子全部拿走,然后轮下一个玩家拿石子。直到
所有的石子都被拿完,游戏结束。
当游戏结束时,如果Alice拿到的石子总数严格大于Bob所拿到的石子总数,则Alice获胜,否则Bob
获胜。
假设 Alice和Bob都绝顶聪明,一定会以最优解拿石子,小苯想知道最终谁会成为最后的赢家,请你帮帮
他预测一下吧。
输入描述:
本题有多组测试数据。
第一行一个正整数 t(1≤t≤100),表示测试数据的组数。
每组测试数据的第一行包含一个正整数 n(1≤n≤100),表示有 n 堆石子。
每组测试数据的第二行包含 n 个正整数 a;(1≤a≤100),表示每堆石子的个数。保证石子数按升序排列,
即:对于所有的(1≤i≤n-1)都有(a≤a)。
输出描述:
输出包含 t 行,表示每个测试数据的答案。
由于输入的是升序序列，而我们要最优解，那么Alice和Bob肯定是从最大数开始拿，我们可以倒序输入将其变成一个降序序列，方便后续操作。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
while(n--){
int n,a[110];
int A=0,B=0;
cin>>n;
for(int i=n;i>=1;i--)
{
cin>>a[i];
if(i%2==1)A+=a[i];
else B+=a[i];
}
if(A>B)cout<<"Alice"<<endl;
else cout<<"Bob"<<endl;
};
return 0;
}B小苯的排序疑惑
题目描述:
小苯有一个长度为n的数组a,他可以对a进行至多一次以下操作:
●选择一段区间[l,r],满足(1≤l≤r≤n),且区间长度严格小于n,将数组a的[l,r]这段区间按非
降序排序。
换句话说,操作执行完后,区间中的值将满足:a[l≤a[l+1]≤a[l+2]≤ …. ≤a[r]。
现在小苯想知道能否通过执行最多一次操作使得数组a按非降序排列。
输入描述:
本题有多组测试用例。
第一行一个正整数 t(1≤t≤10)表示测试用例的组数。
每组数据第一行一个正整数 n(1≤n≤2×10),表示数组的长度。
每组数据第二行 n 个正整数 a(1≤a≤10),表示数组 a 的元素。
输入保证所有测试用例中的 n 总和不超过 2×10。
输出描述:
输出包含t 行,表示每组用例的答案。
如果可以使 a 有序,输出"YES",否则输出“NO”(输出不含双引号)。
因为可以选择区间长度严格小于n的区域按非降序排列，所以我们就可以选择尽可能大，也就是长度为n-1的区间。
此时我们只需要保证（第一个是最小值/最后一个是最大值）即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
ll a[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll t,n;
cin >> t;
while(t--){
cin >> n;
if(n==1){
for(int i=1;i<=n;i++){
cin >> a[i];
}
cout << "YES\n";
}else{
ll maxv=0,minv=1e10;
for(int i=1;i<=n;i++){
cin >> a[i];
maxv=max(a[i],maxv);
minv=min(a[i],minv);
}
if(maxv==a[n] || minv==a[1]){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
}
return 0;
}C小苯的IDE括号问题（easy）
题目描述:
注:此版本为本问题的easy(简单版),与hard(困难版)不同的是,easy只有两种删除操作。众所周知,通常的代码编辑器(如当前页面右侧的牛客在线编辑器)都比较智能。
如果您输入一串括号串,例如:(I)其中的I代表鼠标光标。
此时如果按下键盘中的backspace键,整个括号都会被删掉,也就是说括号串会变成I,只包含鼠标光标。
但是如果按下键盘中的delete键,那么则只会删除括号的右侧部分,也就是说括号串会变为(I。
但如果鼠标光标不处于一个匹配的括号串中间,例如:()1
此时按下backspace键,括号会变为(I。
此时按下delete键,由于光标右侧没有括号,因此括号不会发生变化。
类似的,如果括号串为:I()。
此时按下backspace键,由于鼠标光标左侧没有括号,因此括号不会发生变化。
此时按下delete键,括号会变为:I)。
问题:现在小苯给了你一个长度为n的括号串,并且保证其中恰好出现了一个I字符表示鼠标光标。他想知道,在k次
指定的删除操作后,括号串最终会是什么样子,请你帮帮他吧。
输入描述:
输入包含若干行。
第一行两个数字 n,k(1≤k≤n≤2×10),分别表示括号串的长度和操作次数。
第二行输入一行字符串表示题目所述的括号串,保证字符串仅含有:“(,),I”(大写的字母i)三种字符之一,且
I 字符出现且仅出现一次。
接下来 k 行,每行输入一个字符串代表删除操作,保证字符串一定是:delete 或 backspace。
输出描述:
输出包含一行一个字符串,表示括号串最终的样子。
这是一道简单的模拟题，只需要简单模拟即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
char ch[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,k;
ll sl,sr;
cin >> n >> k;
for(int i=0;i<n;i++){
cin >> ch[i];
if(ch[i]=='I'){
sl=i;
sr=i;
}
}
while(k--){
string sh;
cin >> sh;
if(sh=="backspace"){
if(sl-1>=0){
if(sr+1>=n){
ch[sl-1]='.';
sl--;
}else if(ch[sl-1]=='(' && ch[sr+1]==')'){
ch[sl-1]='.';
ch[sr+1]='.';
sl--;
sr++;
}else{
ch[sl-1]='.';
sl--;
}
}
}else{
if(sr+1<n){
ch[sr+1]='.';
sr++;
}
}
}
for(int i=0;i<n;i++){
if(ch[i]!='.'){
cout << ch[i];
}
}
return 0;
}D小苯的IDE括号问题（hard）
题目描述:
注:此版本为本问题的hard(困难版),与easy(简单版)不同的是,hard有四种操作。众所周知,通常的代码编辑器(如当前页面右侧的牛客在线编辑器)都比较智能。
如果您输入一串括号串,例如:(I)其中的I代表鼠标光标。
此时如果按下键盘中的backspace键,整个括号都会被删掉,也就是说括号串会变成I,只包含鼠标光标。
但是如果按下键盘中的delete键,那么则只会删除括号的右侧部分,也就是说括号串会变为(I。
但如果鼠标光标不处于一个匹配的括号串中间,例如:()I
此时按下backspace键,括号会变为(I。
此时按下delete键,由于光标右侧没有括号,因此括号不会发生变化。
类似的,如果括号串为:I()。
此时按下backspace键,由于鼠标光标左侧没有括号,因此括号不会发生变化。
此时按下delete键,括号会变为:I)。
除此之外,小苯还会按下键盘中的←和→键以移动光标。
例如括号串为(()(I),此时小苯按下左移键←一次,光标就会左移一次进而使得括号变为:(()I()。同理右移也是类似的。
但特别的,如果光标已经在括号串最左侧,此时按下左移键,括号串不会发生变化;同理如果光标位于括号串最右侧时按下右移键,括号串依然不会发生变化。
问题:现在小苯给了你一个长度为n的括号串,并且保证其中恰好出现了一个I字符表示鼠标光标。他想知道,在k次指定的操作后,括号串最终会是什么样子,请你帮帮他吧。
输入描述:
输入包含若干行。
第一行两个数字 n,k(1≤k≤n≤2×10),分别表示括号串的长度和操作次数。
第二行输入一行字符串表示题目所述的括号串,保证字符串仅含有:“(,),I"(大写的字母i)三种字符之一,且I 字符出现且
仅出现一次。
接下来k 行,每行输入一个字符串代表删除操作,保证字符串一定是:delete,backspace, <- 和->中的一种。
输出描述:
输出包含一行一个字符串,表示括号串最终的样子。
用c++中的string来模拟解决，要注意的是 “ch.erase(s+1,1);ch.erase(s-1,1);”，位置不能颠倒，如果颠倒的话先ch.erase(s-1,1);光标位置就会变成s-1，此时后面就要变成ch.erase(s,1);
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,k;
string ch;
cin >> n >> k;
cin >> ch;
int s=ch.find('I');
while(k--){
string sh;
cin >> sh;
if(sh=="backspace"){
if(s-1>=0){
if(s+1<n && ch[s-1]=='(' && ch[s+1]==')'){
ch.erase(s+1,1);
ch.erase(s-1,1);
s--;
n-=2;
}else{
ch.erase(s-1,1);
s--;
n--;
}
}
}else if(sh=="delete"){
if(s+1<n){
ch.erase(s+1,1);
n--;
}
}else if(sh=="->"){
if(s+1<n){
swap(ch[s], ch[s+1]);
s++;
}
}else{
if(s-1>=0){
swap(ch[s], ch[s-1]);
s--;
}
}
}
cout << ch;
return 0;
}E小苯的数组构造
题目描述：
大白熊给了小苯一个长度为n的数组a,他希望小苯将数组a变成有序(非递减)的。具体的,小苯需要进行如下操作:
1.任选一个数组b,长度也为n,且元素满足 :- 10≤b;≤10。
2.对于所有1≤i≤n,都执行a=a+b。
大白熊希望在执行完操作后a数组满足有序,同时要最小化数组b的极差,即使得:max(b,b, …… ,b)-min(b,b, …… ,b)最小。
请你帮小苯找出一个合法的b数组吧。
注:如有多解输出任意即可。
输入描述:
输入包含两行。
第一行一个正整数 n(1≤n≤2×10),表示 a 的长度。
第二行 n 个整数 a;(-10≤ai≤10),表示数组 a 的元素。
输出描述:
输出包含一行 n 个整数,表示构造出的b 数组(有多解输出任意即可)。
如果找不到合法的b 数组,请输出一个整数 -1。
要得到一条非降数组并且要满足b的极差最小。只需要做到非降序数组尽量不升序即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 200005
ll a[maxn],b[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i];
}
for(int i=2;i<=n;i++){
if(a[i]<a[i-1]){
b[i]=a[i-1]-a[i];
a[i]=a[i-1];
}
}
for(int i=1;i<=n;i++){
cout << b[i] << ' ';
}
return 0;
}F小苯的数组切分
题目描述:
qionghua 给了小苯一个长度为n的数组a,希望小苯将数组a分为恰好非空的三段。即:[1,l-1],[l,r],[r+1,n]这三段,其中1<l≤r<n。接着:
●第一段的所有数字做 (按位异或)运算。
● 第二段的所有数字做|(按位或)运算。
● 第三段的所有数字做 &(按位与)运算。
将这三段数字运算的结果做加法求和,作为小苯的得分。
小苯想知道他如果以最优的方案切分数组,最多能获得多少得分,请你帮他算一算吧。
输入描述:
输入包含两行。
第一行一个正整数 n(3≤n≤2×10),表示数组 a 的长度。
第二行 n 个正整数 a;(1≤ai≤10),表示数组 a 的元素。
输出描述:
输出包含一行一个正整数,表示小苯的最高得分。
因为and运算[&(按位与)]所得值一定小于原先两个值，属于越算越小的趋势，所以只需要保留最后一个给第三段即可。
对于xor 和 or，可以通过枚举进行判断应取什么边界。
#include<bits/stdc++.h>
using namespace std;
long long a[200005],b[200005];
int main()
{
long long n,ans = 0;
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i],b[i] = a[i];
for(int i = 2;i <= n-1;i++) a[i] ^= a[i-1];
for(int i = n-2;i >= 1;i--) b[i] |= b[i+1];
for(int i = 1;i <= n-2;i++) ans = max(ans,a[i]+b[i+1]);
cout << ans+a[n];
return 0;
}G小苯的逆序对
题目描述:
小苯有一个长度为n的排列p。他很想知道这个排列中有多少个逆序对满足互素。
形式化的,有多少个满足(i<j)且(a>a)且gcd(a,a)=1的(i,j)对。
输入描述:
输入包含两行。
第一行一个正整数 n(1≤n≤2×10)。表示排列的长度
第二行 n 个正整数p;(1≤p≤n)表示排列 p,保证 1 到 n 的每个正整数出现且恰好仅出现一次。
输出描述:
输出包含一行一个整数,表示排列 p 的互素逆序对个数。
考点:莫比乌斯反演,容斥,树状数组,dp。
题意:给定长为n的排列,求有多少个排列值互素的逆序对。
我们可以定义dp;表示:“所有的gcd可以是i的倍数的数字们组成的数组”的逆序对数,假设我们已经
有了这个dp数组,那么我们如何将倍数的值转为其值本身,则只需要从大到小枚举i,并执行:
dp=dp-(dp*2dp*3 …),执行了这一步后,dp;就转为了:“所有的gcd可以等于i的数”组
成数组的逆序对个数。那么显然dp1就是我们要求的答案。
接下来考虑,我们如何获得一开始的dp数组呢,也就是:“所有的gcd可以是i的倍数的数字们组成的
数组”的逆序对数。我们只需枚举i,然后对所有是i的倍数的数字们组成的数组求逆序对即可,实现上我
们可以开一个二维vector,其中vector;存了所有排列值是i的倍数的排列值,按原排列的下标顺序
存。
举个例子:如果排列是:[2,3,6,5,4,1],则vector1=[2,3,6,5,4,1],vector2=[2,6,4]。
接着我们只需要对所有的vector;都求一遍逆序对,就得到了初始的dpi。而一个数组内求逆序对这一
过程我们可以使用树状数组做到n·logn的时间复杂度,其中n是数组长度。
得到初始的dp后再做上述的容斥,我们就解决了本问题。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5 + 10;
int n;
int a[N], c[N];
ll dp[N];
void add(int u,int v)
{
while(u)
{
c[u]+=v;
u-=u&-u;
}
}
int ask(int u)
{
int res=0;
while(u<=n)
{
res+=c[u];
u+=u&-u;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i=1;i<=n;++i)
{
int tem;
cin >> tem;
a[tem]=i;
}
for(int i=n;i>=1;--i)
{
for(int j=i;j<=n;j+=i)
{
dp[i]+=ask(a[j]);
add(a[j],1);
}
for(int j = i; j <= n; j += i)
{
add(a[j],-1);
if(j!=i)
dp[i]-=dp[j];
}
}
cout<<dp[1]<<endl;
return 0;
}
