A题
题意：
给定一个长度为n的升序序列a，Alice和Bob 轮流操作，每次取走序列中的一个数，直到所有的数都被拿完，游戏结束。若游戏结束时，如果Alice拿到的数的总数严格大于Bob所拿到的数的总数，则Alice获胜，否则Bob 获胜。
思路：
Alice每一次都拿最大的数，直到游戏结束。
当序列长度为奇数，Alice比Bob多拿了一个数，因此，一定是Alice胜利。
当序列长度为偶数时，由于序列按升序排序，因此Alice拿的数的下标一定是偶数，将Alice拿到的数的总和与Bob拿到的数的总和计算出即可得出结果。
代码：
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}
#define ONLINE_JUDGE
int t,n;
int a[110];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin>>t;
while(t--)
{
cin>>n;
int l=0,r=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i%2)
{
l+=a[i];
}
else
{
r+=a[i];
}
}
if(n%2)
{
cout<<"Alice\n";
}
else
{
if(r>l)
{
cout<<"Alice\n";
}
else
{
cout<<"Bob\n";
}
}
}
return 0;
}
B题
题意：
给定一个长度为n的序列a，可以进行至多一次如下操作：
选择一段区间 [l,r]，满足(1≤l≤r≤n),且区间长度严格小于n，将数组a的[l,r]这段区间按非降序排序。
问是否能通过执行最多一次操作使得数组a按非降序排列。
思路：
因为区间长度严格小于n，所以区间长度最大为n-1，因此仅需检查a[1]是否为最小值，a[n]是否最大值即可。
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}
#define ONLINE_JUDGE
const int N=2e5+10;
int t,n;
int a[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin>>t;
while(t--)
{
cin>>n;
int maxx=0,minn=INT_MAX;
for(int i=1;i<=n;i++)
{
cin>>a[i];
maxx=max(maxx,a[i]);
minn=min(minn,a[i]);
}
if(a[1]!=minn&&a[n]!=maxx)
{
cout<<"NO\n";
}
else
{
cout<<"YES\n";
}
}
return 0;
}
C题
链接：https://ac.nowcoder.com/acm/contest/73854/C
思路：
使用两个栈分别存贮光标前的字符与光标后的字符，用栈的弹出操作模拟题目的两种操作。
代码：
#include <bits/stdc++.h>
#define ios \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
int add(int x, int y) { return x ? add((x & y) << 1, x ^ y) : y; }
#define ONLINE_JUDGE
int n, k;
string s;
stack<char> qf, qb;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin >> n >> k;
cin >> s;
for (int i = 0; i < s.length(); i++)
{
if (s[i] != 'I')
{
qf.push(s[i]);
}
else
{
break;
}
}
for (int i = s.length() - 1; i >= 0; i--)
{
if (s[i] != 'I')
{
qb.push(s[i]);
}
else
{
break;
}
}
string s1;
for (int i = 1; i <= k; i++)
{
cin >> s1;
if (s1[0] == 'b')
{
if (!qf.empty())
{
char cf = qf.top();
qf.pop();
if (!qb.empty())
{
char cb = qb.top();
if (cf == '(' && cb == ')')
{
qb.pop();
}
}
}
}
else
{
if (!qb.empty())
{
qb.pop();
}
}
}
string res = "";
while (!qf.empty())
{
res += qf.top();
qf.pop();
}
reverse(res.begin(), res.end());
res+='I';
while (!qb.empty())
{
res += qb.top();
qb.pop();
}
cout << res << "\n";
return 0;
}
D题
链接：https://ac.nowcoder.com/acm/contest/73854/D
思路：
使用两个栈分别存贮光标前的字符与光标后的字符，用栈的弹出操作模拟backspace与delete，而光标的左右移动可以视为将栈顶元素转移至另一个栈中。
代码：
#include <bits/stdc++.h>
#define ios \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
using namespace std;
int add(int x, int y) { return x ? add((x & y) << 1, x ^ y) : y; }
#define ONLINE_JUDGE
int n, k;
string s;
stack<char> qf, qb;
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin >> n >> k;
cin >> s;
for (int i = 0; i < s.length(); i++)
{
if (s[i] != 'I')
{
qf.push(s[i]);
}
else
{
break;
}
}
for (int i = s.length() - 1; i >= 0; i--)
{
if (s[i] != 'I')
{
qb.push(s[i]);
}
else
{
break;
}
}
string s1;
for (int i = 1; i <= k; i++)
{
cin >> s1;
if (s1[0] == 'b')
{
if (!qf.empty())
{
char cf = qf.top();
qf.pop();
if (!qb.empty())
{
char cb = qb.top();
if (cf == '(' && cb == ')')
{
qb.pop();
}
}
}
}
else if (s1[0] == 'd')
{
if (!qb.empty())
{
qb.pop();
}
}
else if (s1[0] == '<')
{
if (!qf.empty())
{
char c = qf.top();
qf.pop();
qb.push(c);
}
}
else if (s1[0] == '-')
{
if (!qb.empty())
{
char c = qb.top();
qb.pop();
qf.push(c);
}
}
}
string res = "";
while (!qf.empty())
{
res += qf.top();
qf.pop();
}
reverse(res.begin(), res.end());
res += 'I';
while (!qb.empty())
{
res += qb.top();
qb.pop();
}
cout << res << "\n";
return 0;
}
E题
链接：https://ac.nowcoder.com/acm/contest/73854/E
思路：
res代表当前位置之前的最大值，对于每一个小于前一个数的a[i]将其加至res，同时每次更新res的大小即可保证最小化数组b的极差。
代码：
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}
#define ONLINE_JUDGE
typedef long long ll;
const int N=2e5+10;
int n;
ll a[N],b[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ll res=-2e9;
for(int i=1;i<=n;i++)
{
if(a[i]<res)
{
b[i]=res-a[i];
}
res=max(res,a[i]);
}
for(int i=1;i<=n;i++)
{
cout<<b[i]<<" \n"[i==n];
}
return 0;
}
F题
链接：https://ac.nowcoder.com/acm/contest/73854/F
思路：
或运算的特性：(a|b)>=max(a,b)
与运算的特性：（a&b）<=min(a,b)
根据与运算的特性，与运算的区间越小越好，因此与运算的区间为1最优，但此时不保证区间为1是全局最优解。
根据或运算的特性，或运算的区间越大越好，而与运算区间之前就是或运算，因此可以确定与运算的区间为1，值为a[n]。
异或运算与或运算的最优区间大小可以通过枚举来进行计算，时间复杂度O(n)，本题数据大小为2e5，可以通过。
但每枚举一个位置计算一边异或运算与或运算肯定超时，因此需要通过预处理将异或运算与或运算计算一遍。
代码：
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int add(int x, int y){return x ? add((x & y) << 1, x ^ y): y;}
#define ONLINE_JUDGE
typedef long long ll;
const int N=2e5+10;
int n;
ll a[N],res[N],ans[N];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
res[i]=res[i-1]^a[i];
}
for(int i=n-1;i>=1;i--)
{
ans[i]=ans[i+1]|a[i];
}
ll sum=0;
for(int i=1;i<=n-2;i++)
{
sum=max(sum,res[i]+ans[i+1]+a[n]);
}
cout<<sum<<"\n";
return 0;
}