T1
题目描述
给出一个长为的排列，请你把它排序。排序方法是：定义一种操作表示交换，先找到所有逆序对满足，任意排成一个排列，使得按照这个顺序操作以后是单调递增的。如果有多种排列，输出任意一种。
输入格式
第一行输入，第二行输入数组。保证是排列。
输出格式
如果不存在答案，输出。
否则，第一行输出表示逆序对数量，接下来行每行输出两个数，表示一次操作，需要满足（是没有经过操作的数组）。
样例
样例输入1
3
3 1 2
样例输出1
2
1 3
1 2
设 \(b[i]\) 意思为 \(i\) 位置应该放的数应该放数是 \(b[i]\) 的数
\(b[1]\) 表示第 \(1\) 个位置应该放的数在原数列里的下标是 \(2\)
\(b[2]\) 表示第 \(2\) 个位置应该放的数在原数列里的下标是 \(3\)
\(b[3]\) 表示第 \(3\) 个位置应该放的数在原数列里的下标是 \(1\)
怎么用冒泡排序做这道题呢？
冒泡排序都是比较相邻的两个元素，所以我们将这道题构造成比较不相邻的逆序对
\(b[i]\) 的最终状态是升序排列的，这样就能第 \(i\) 个位置应该放的数是 \(b[i]\)（即为 \(i\)）
\(b[i]\) 有几个性质
1.当交换 \(a[b[u]]\) 和 \(a[b[y]]\) 的时候， \(b[u]\) 和 \(b[y]\) 也会交换
假设想让 \(a\) 升序排列，交换 \(a[1]\) 和 \(a[3]\),那么 \(b[2]\) 和 \(b[3]\) 也会交换
2.如果 \(b[u]>b[y]\) 且 \(u<y\) 那么\(a[b[u]]\) 和 \(a[b[y]]\) 互为逆序对
\(b[2]\) 和 \(b[3]\) 为例子
\(b[2]=3\) 说明2位置（2）应该放一个下标比较大的数，但是3位置（3）要放一个下标比较小的数，这样就满足了逆序对的定义，即下标较小的位置反而大
这样的话我们求出 \(b[i]\) 数组：\(b[a[i]]=i\) 然后对 \(b\) 冒泡排序成有序，就能求出交换的是那些下标
而且因为交换 \(b\) 中的逆序对对应 \(a\) 中的逆序对，所以将 \(b\) 排到升序，\(a\) 也意味着排到升序，而且不会对其他逆序对造成影响，因为交换的是 \((b[i],b[i+1])\)
同时冒泡排序保证了交换的次数就等于逆序对的个数
nt代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void Write(int x){
if(x>9) Write(x/10);
putchar(x%10+48);
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
Write(x);
putchar(' ');
}
}
using namespace Testify;
const int N=1005;
int n,a[N],Tempestissimo,b[N],c[N];
int op[N],cnt(0);
signed main(void){
n=read();
for(register int i=1;i<=n;i++){
a[i]=b[i]=read();
// c[i]=i;
}
sort(b+1,b+n+1);
int cnt=unique(b+1,b+n+1)-b-1;
for(register int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
}
for(register int i=1;i<=n;i++){
b[a[i]]=i;
}
for(register int i=1;i<=n;i++){
for(register int j=i+1;j<=n;j++){
if(a[i]>a[j]){
Tempestissimo++;
}
}
}
Write(Tempestissimo),puts("");
if(!Tempestissimo) return 0;
for(register int i=1;i<n;i++){
for(register int j=1;j<n;j++){
if(b[j+1]<b[j]){
printf("%lld %lld\n",b[j+1],b[j]);
// swap(a[i+1],a[i]);
swap(b[j+1],b[j]);
}
}
}
// for(register int i=1;i<=n;i++){
// cerr<<a[i]<<" ";
// }
return 0;
}
二.B. Xorum
题目描述
你有一块黑板，只写着一个奇数。你可以往黑板上写数，目标是写下1。你可以使用两种操作：选择两个已经写在黑板上的数，写下它们的和或异或和。要求写数字不超过 次且上的数字不超过 。
输入格式
一个奇数。
输出格式
第一行输出操作数，接下来每行输出一个操作，表示写下，表示写下。
样例
样例输入1
3
样例输出1
5
1 3 3
2 3 6
1 3 5
1 3 6
2 8 9
样例输入2
123
样例输出2
10
1 123 123
2 123 246
1 141 123
1 246 123
2 264 369
1 121 246
2 367 369
1 30 30
1 60 60
2 120 121
使用按位计算
因为给定 \(x\) 是奇数，所以他可以表示为 \(1???????????1\)
\[y=1???????????100000000 \]\[z=x\oplus y=1???????????0???????????1 \]\[c=z+y=1???????????01???????????1 \]\[d=c\oplus x=1???????????0000000000 \]\[e=y<<1=1???????????10000000000000 \]\[f=d\oplus e=10 000000000000000 \]然后根据 \(x\) \(y\) \(f\) 解出1
将\(y\)不断左移和\(x\)做异或运算将y化简到 \(100000000000000\)
然后在和 \(x\) 异或将最靠前的1消去，不断循环这个过程就能得到1
代码
点击抄袭代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
inline int read(){
int f(1),x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f*x;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
}
using namespace Testify;
int n;
int x,y,z,c,d,e,f,h;
int sum;
inline int popcount(int s){
int res=0;
while(s){
res++;
s-=(s&(-s));
}
return res;
}
inline int geth(int s){
int res=0;
while(s){
res++;
s>>=1;
}
return res;
}
inline int POP(int s,int t){
return (s>>t)&1;
}
int cnt(0);
struct node{
int opt,a,b;
}ans[100005];
signed main(void){
// cerr<<POP(4,2);
x=read();
while(x!=1){
y=x;
h=geth(x);
for(register int i=1;i<h;i++){
// printf("1 %lld %lld\n",y,y);
ans[++cnt]=node{1,y,y};
y<<=1;
}
// printf("2 %lld %lld\n",x,y);
ans[++cnt]=node{2,x,y};
z=(x^y);
ans[++cnt]=node{1,z,y};
// printf("1 %lld %lld\n",z,y);
c=(z+y);
ans[++cnt]=node{2,c,x};
// printf("2 %lld %lld\n",c,x);
d=(c^x);
ans[++cnt]=node{1,y,y};
// printf("1 %lld %lld\n",y,y);
e=(y<<1);
ans[++cnt]=node{2,d,e};
// printf("2 %lld %lld\n",d,e);
f=(d^e);
int op=popcount(x);
for(register int i=1;i<op;i++){
while(!POP(y,h++)){
ans[++cnt]=node{1,f,f};
// printf("1 %lld %lld\n",f,f);
f<<=1;
}
ans[++cnt]=node{2,y,f};
// printf("2 %lld %lld\n",y,f);
y^=f;
ans[++cnt]=node{1,f,f};
// printf("1 %lld %lld\n",f,f);
f<<=1;
}
ans[++cnt]=node{2,x,y};
x^=y;
}
write(cnt),putchar('\n');
for(register int i=1;i<=cnt;i++){
printf("%lld ",ans[i].a);
if(ans[i].opt==1){
putchar('+');
}else{
putchar('^');
}
printf(" %lld\n",ans[i].b);
}
return 0;
}