A小苯的石子游戏
本题贪心模拟即可
B 小苯的排序疑惑
考虑到最简单的操作把n-1个数排好，最后一个看能否有序。即：a[1]<=min(a[2],a[3],a[4]..,a[n])|| a[n]>=max(a[1],a[2],a[3]....,a[n-1])满足条件，反之易得不可能
C&D 小苯的IDE括号问题
本题考察题意理解，简单版本我们可以只关注逻辑删除，hard需要我们物理删除，所以简单版本可以用双指针扫描，最后拼接，而hard版本因为指针是线性移动无法判断是否删除，所以hard版本用vector模拟队列即可 要注意的是可能需要翻转
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
vector<char> l;
vector<char> r;
int flag=0;
for(int i=0;s[i];i++){
if(s[i]=='I'){
flag=1;
continue;
}
if(flag) r.push_back(s[i]);
else l.push_back(s[i]);
}
reverse(r.begin(),r.end());
string ans;
while(k--){
string d;
cin>>d;
if(d[0]=='b'){
if(l.empty()) continue;
if(!r.empty()&&r.back()==')'&&l.back()=='('){
l.pop_back();
r.pop_back();
}
else l.pop_back();
}
else if(d[0]=='d'){
if(r.empty()) continue;
r.pop_back();
}
else if(d[0]=='<'){
if(l.empty()) continue;
r.push_back(l.back());
l.pop_back();
}
else{
if(r.empty()) continue;
l.push_back(r.back());
r.pop_back();
}
}
for(auto d:l) ans+=d;
ans+='I';
reverse(r.begin(),r.end());
for(auto d:r) ans+=d;
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solved();
}
}
E 小苯的数组构造
首先考察 如果a[i]< a[i-1] 那么我们可以把a[i]变成a[i-1]可以发现,前缀a[i]的值都会变成前缀最大值，所以b[i]=前缀最大-a[i], 考虑最大的b[i]，如果极差小于b[i]，可以证明无法满足单调，故,max bi为最大值.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{
int n;
cin>>n;
vector<int> a(n+1);
vector<int> b(n+1);
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]<<" ";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solved();
}
}
F 小苯的数组切分
本题考察位运算性质,首先一点 and 操作 只减不增，能维持a[n] 都算不错，所以把r固定在n,一定没有问题，考虑枚举l即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{
int n;
cin>>n;
vector<int> f(n+1),g(n+1),a(n+1);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=n-1;i>=2;i--) f[i]=f[i+1]|a[i];
for(int i=1;i<=n;i++) g[i]=g[i-1]^a[i];
int ans=0;
for(int i=1;i<=n-1;i++){
ans=max(ans,f[i+1]+g[i]+a[n]);
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solved();
}
}
G 小苯的逆序对
此题比较缝合考察了逆序对以及数论容斥的一些知识。考虑gcd(i,j)=x的逆序对，那么怎么求呢？
设g[x] 表示 x|gcd(i,j)的逆序对个数 那么 f[x]=g[x]-f[2x]-f[3x]-f[4x].....。 所以我们对每个x单独求，答案就是f[1].
求逆序对，我们要怎么样保证 x|gcd(i,j) 呢？ 很简单，把x的倍数全部单独划分一个数组求逆序对即可，我是用值域树状数组求的，要考虑树状数组的清空，那么每次我们映射的时候就映射x的多少倍即可，这样方便清空降低时间复杂度。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
const int N=2e5+10;
int tree[N];
void updata(int idx,int k,int n){
while(idx<=n){
tree[idx]+=k;
idx+=(idx)&(-idx);
}
}
int query(int idx){
int res=0;
while(idx){
res+=tree[idx];
idx-=(idx)&(-idx);
}
return res;
}
void solved()
{
int n;
cin>>n;
vector<int> b(n+1);
vector<int> a[n+1];
vector<int> d[n+1];
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i) a[j].push_back(i);
}
for(int i=1;i<=n;i++){
for(auto &k:a[b[i]]){
d[k].push_back(b[i]/k);
}
}
auto cal=[&](int k){
int res=0;
//cout<<k<<":";
for(int i=0;i<d[k].size();i++){
//cout<<d[k][i]<<" ";
res+=(i-query(d[k][i]));
updata(d[k][i],1,d[k].size()+1);
}
// cout<<res<<endl;
for(int i=0;i<=d[k].size()+1;i++) tree[i]=0;
return res;
};
vector<int> f(n+1);
for(int i=n;i>=1;i--){
f[i]=cal(i);
for(int j=i+i;j<=n;j+=i) f[i]-=f[j];
}
cout<<f[1]<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--)
{
solved();
}
}