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();}
}
