第一场就保龄了，开门红
A. 排序
题目给出的是一个排列，所以一定会通过有限次操作来使操作有序。 （话说这题上来就搞诈骗）
由于数据范围很小，我们直接 \(O(n^2)\) 暴力枚举即可。
而你需要操作逆序对个数次，所以每次交换需要让逆序对的个数减一，所以只需要每次交换值相邻的两个就可以了。
code
#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int n,ans;
int a[M];
struct abc{
int x,y;
}da[M*M];
bool cmp(abc x,abc y){
if(x.x==y.x){
return a[x.y]>a[y.y];
}
return x.x<y.x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
for(int j=1;j<i;j++){
if(a[j]>a[i]){
ans++;
da[ans].x=j;
da[ans].y=i;
}
}
}
printf("%d\n",ans);
sort(da+1,da+ans+1,cmp);
for(int i=1;i<=ans;i++){
printf("%d %d\n",da[i].x,da[i].y);
}
return 0;
}
B. Xorum
神奇的推式子
你已知一个奇数，需要通过两种操作来得到1。也就是说，要不断地消去该奇数每一位上的1。
设你现在的一个奇数为 \(x\)。
将 \(x\) 的最后一位挪至与第一位对齐得到 \(y\)。
\(x\) 异或 \(y\) 得到 \(z\)。
\(z\) 加上 \(y\) 得到 \(n\)。
\(y\) 加上 \(y\) 得到 \(p\)。
\(n\) 异或 \(p\) 得到 \(m\)。
\(m\) 异或 \(x\) 得到 \(q\)。
然后你利用这个 \(q\) 就可以消掉 \(y\) 除最后一位上的1，也就是 \(x\) 最高位上的1，这样就可以消掉一个1，不断重复此过程即可。
\[\begin{aligned} &1------1\quad x\\ 1------&10000000000000\quad y\\ 1------&0------1\quad z=x+y\\ 1------0&1------1\quad n=z+y\\ 1------10&00000000000000\quad p=y+y\\ 1&1------1\quad m=n\oplus p\\ 1&00000000000000\quad q=m\oplus x\\ \end{aligned} \]code
#include<bits/stdc++.h>
using namespace std;
const long long M=1e5+10;
long long n,cnt;
struct abc{
long long op,x,y;
}da[M];
long long solve(long long x){
long long s=(x>>1),y=x;
while(s){
da[++cnt].op=1; da[cnt].x=y; da[cnt].y=y;
y<<=1,s>>=1;
}
long long z=(x^y);
da[++cnt].op=2; da[cnt].x=x; da[cnt].y=y;
long long t=z+y;
da[++cnt].op=1; da[cnt].x=z; da[cnt].y=y;
long long p=y+y;
da[++cnt].op=1; da[cnt].x=y; da[cnt].y=y;
long long e=(t^p);
da[++cnt].op=2; da[cnt].x=t; da[cnt].y=p;
long long q=(e^x);
da[++cnt].op=2; da[cnt].x=e; da[cnt].y=x;
while(y!=(y&(-y))){
if(y&q){
da[++cnt].op=2; da[cnt].x=y; da[cnt].y=q;
y=y^q;
}
da[++cnt].op=1; da[cnt].x=q; da[cnt].y=q;
q=q<<1;
}
da[++cnt].op=2; da[cnt].x=y; da[cnt].y=x;
return y^x;
}
int main(){
scanf("%lld",&n);
while(n!=1){
n=solve(n);
}
printf("%lld\n",cnt);
for(long long i=1;i<=cnt;i++){
printf("%lld %lld %lld\n",da[i].op,da[i].x,da[i].y);
}
return 0;
}
C. 有趣的区间问题
一个类似 \(CDQ\) 分治的做法，对于每个区间，最大值和最小值的位置可以在中点左边也可以是右边，所以一共有四种情况。
- 最大值最小值都在左边：用一个指针维护右区间的位置即可
- 最大值最小值都在右边：同上
- 最大值在左最小值在右：用一个桶存 \(popcount\) 的值，对于每一个最大值，找出右边最大值小于最小值的位置统计答案
- 最大值在右最小值在左：扩展时一个用 \(\leq\),一个用 \(<\)，其余同上
code
#include<bits/stdc++.h>
using namespace std;
const long long M=1e6+10;
struct abc{
long long id1,id2;
}da[M];
long long n,ans;
long long a[M],num[M];
long long t[70];
inline long long read(){
long long x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline long long lowbit(long long x){
return x&(-x);
}
inline long long getnum(long long x){
long long now=x,num=0;
while(now){
now-=lowbit(now);
num++;
}
return num;
}
inline void clear(){
for(int i=0;i<=65;i++){
t[i]=0;
}
return;
}
void solve(long long l,long long r){
if(l==r){
ans++;
return;
}
long long mid=l+r>>1;
solve(l,mid); solve(mid+1,r);
da[mid].id1=da[mid].id2=mid;
for(long long i=mid-1;i>=l;i--){
da[i].id1=a[da[i+1].id1]>a[i]?da[i+1].id1:i;
da[i].id2=a[da[i+1].id2]<a[i]?da[i+1].id2:i;
}
da[mid+1].id1=da[mid+1].id2=mid+1;
for(long long i=mid+2;i<=r;i++){
da[i].id1=a[da[i-1].id1]>a[i]?da[i-1].id1:i;
da[i].id2=a[da[i-1].id2]<a[i]?da[i-1].id2:i;
}
long long j=mid+1;
for(long long i=mid;i>=l;i--){
while(j<=r&&a[da[j].id2]>=a[da[i].id2]&&a[da[j].id1]<=a[da[i].id1]){
j++;
}
if(num[da[i].id1]==num[da[i].id2]){
ans+=j-1-mid;
}
}
long long i=mid;
for(long long j=mid+1;j<=r;j++){
while(i>=l&&a[da[i].id2]>=a[da[j].id2]&&a[da[i].id1]<=a[da[j].id1]){
i--;
}
if(num[da[j].id1]==num[da[j].id2]){
ans+=mid-i;
}
}
clear();
j=mid+1;
long long k=mid+1;
for(long long i=mid;i>=l;i--){
while(j<=r&&a[da[j].id1]<=a[da[i].id1]){
t[num[da[j].id2]]++;
j++;
}
while(k<j&&a[da[k].id2]>=a[da[i].id2]){
t[num[da[k].id2]]--;
k++;
}
ans+=t[num[da[i].id1]];
}
clear();
i=k=mid;
for(long long j=mid+1;j<=r;j++){
while(i>=l&&a[da[i].id1]<a[da[j].id1]){
t[num[da[i].id2]]++;
i--;
}
while(k>i&&a[da[k].id2]>a[da[j].id2]){
t[num[da[k].id2]]--;
k--;
}
ans+=t[num[da[j].id1]];
}
}
int main(){
n=read();
for(long long i=1;i<=n;i++){
a[i]=read();
num[i]=getnum(a[i]);
}
solve(1,n);
cout<<ans<<'\n';
return 0;
}
D. 无聊的卡牌问题
由于一次拿三张牌，所以我们将三个一组进行捆绑，利用一个栈实现。
可以发现，一些牌的选择是有先后顺序的，所以可以进行拓扑排序，每次拿对其他牌限制多的即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int M=210;
struct abc{
int x,y,z;
}da[M<<1];
int n,num,top,cnt1,cnt2,op;
int st[M<<3],in[M<<1],out[M<<1];
bool z[M<<3],zz[M<<1];
vector<int>h[M<<1];
priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > >p,q;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int main(){
n=read(); num=n<<1;
for(int i=1;i<=n*3;i++){
int a=read();
z[a]=1;
}
for(int i=1;i<=n*6;i++){
if(top>=2&&z[i]&&z[st[top]]&&z[st[top-1]]){
da[++cnt1]=(abc){st[top-1],st[top],i};
top-=2;
}
else if(top>=2&&!z[i]&&!z[st[top]]&&!z[st[top-1]]){
++cnt2;
da[n+cnt2]=(abc){st[top-1],st[top],i};
top-=2;
}
else {
st[++top]=i;
}
}
for(int i=1;i<=n;i++){
for(int j=n+1;j<=n+n;j++){
if(da[i].x<da[j].x&&da[j].z<da[i].z){
h[j].push_back(i);
in[i]++; out[j]++;
}
if(da[j].x<da[i].x&&da[i].z<da[j].z){
h[i].push_back(j);
in[j]++; out[i]++;
}
}
}
for(int i=1;i<=(n<<1);i++){
if(in[i]==0){
if(i<=n){
p.push(make_pair(out[i],i));
}
else {
q.push(make_pair(out[i],i));
}
}
}
while(num){
pair<int,int> x;
if(op==0){
x=p.top();
p.pop();
}
else {
x=q.top();
q.pop();
}
if(zz[x.second]){
continue;
}
zz[x.second]=1;
cout<<da[x.second].x<<' '<<da[x.second].y<<' '<<da[x.second].z<<'\n';
num--;
for(int i=0;i<h[x.second].size();i++){
int y=h[x.second][i];
in[y]--;
}
for(int i=1;i<=(n<<1);i++){
if(zz[i]==0&&in[i]==0){
if(i<=n){
p.push(make_pair(out[i],i));
}
else {
q.push(make_pair(out[i],i));
}
}
}
op=op^1;
}
return 0;
}