UOJ143 万圣节的数列 构造
2024-10-13 19:02:56
做过这道题,然后这道题告诉你怎么构造数据……
一种可行的构造方式是:将奇数和偶数分成两半,奇数放在偶数前面,然后除以2,再递归下去处理。
构造的正确性是显然的:如果存在“奇数偶数奇数”或者“偶数奇数偶数”的等差子序列,会在当前层被分离,否则除以2之后,“奇数奇数奇数”和”偶数偶数偶数“的等差子序列的公差会/2,那么这些等差子序列在递归到某一时刻也会变为”奇数偶数奇数“或者”偶数奇数偶数“的等差子序列。
不难发现上面的构造方式相当于对二进制翻转之后排序输出。
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
while(!isdigit(c))
c = getchar();
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return a;
}
int reverse(int x){
int sum = 0;
for(int i = 0 ; i < 30 ; ++i)
sum |= ((x >> i) & 1) << (30 - i);
return sum;
}
#define PII pair < int , int >
vector < PII > rev;
int main(){
#ifndef ONLINE_JUDGE
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
#endif
int N = read();
for(int i = 1 ; i <= N ; ++i)
rev.push_back(PII(reverse(read()) , i));
sort(rev.begin() , rev.end());
for(auto t : rev) printf("%d " , t.second);
return 0;
}
最新文章
- Shell练习
- Pushlet浏览器长连接通讯
- transfer between javabean and map
- Nginx 笔记与总结(15)nginx 实现反向代理 ( nginx + apache 动静分离)
- android 中 listview 设置自动匹配高度
- 关于使用dotnetbar开发winform程序在用户电脑上部署时问题
- 传说中的WCF(10):消息拦截与篡改
- python各种类型转换-int,str,char,float,ord,hex,oct等
- C# DataGridView绑定数据源的几种常见方式
- This Android SDK requires Android Developer Toolkit version 23.0.0 or above
- android .9.png ”点九” 图片制作方法
- java中遍历MAP,嵌套map的几种方法
- Facebook Hacker Cup 2015 Round 1--Corporate Gifting(树动态规划)
- java集合(3)- Java中的equals和hashCode方法详解
- 防止系统锁屏-python、C++实现
- oracle 11g rac asm磁盘组增加硬盘
- anaconda安装tensorflow
- 数据标准化+网格搜索+交叉验证+预测(Python)
- PHP设计模式之观察者模式(转)
- C++零散知识点