位运算,
输入一位, 先用B 位的掩码mask之, 得到str , 对str从A位到B位mask之, 再最前头加个1, 以免忽略前导0, 然后hash..
sort一下, 再输出..
输出很ws...小心...写得很烂...
/**//*
ID: lorelei3
TASK: contact
LANG: C++
*/
#include <fstream>
#include <algorithm>
#include <memory.h>
using namespace std;
const int MAX = 200005;
typedef struct Sequence
{
Sequence():cnt(0),value(0){}
int cnt, value;
}Seq;
Seq hash[MAX];
char str[MAX];
int A,B,p,N;
ifstream fin;
ofstream fout;
int cmp(const Seq &a , const Seq &b){
return a.cnt>b.cnt || (a.cnt==b.cnt&&a.value<b.value);
}
void my_print_bin(int value){
int tmp[100], cnt=0;
memset(tmp, 0 , sizeof(tmp));
do{
tmp[cnt++] = value & 1;
value>>=1;
}while(value);
for(int i=cnt-2; i>=0; i--)
fout<<tmp[i];
}
int main(){
int i, j;
unsigned mask, mask1, mask2;
unsigned int str=0, c;
char ch;
fin.open("contact.in");
fout.open("contact.out");
fin>>A>>B>>N;
fin.get(ch);
mask = (1<<B)-1;
while(fin.get(ch)){
if(ch=='0' || ch=='1'){
p++;
c = ch-'0';
str = ((str<<1)+c)&mask;
for(i=A; i<=B&&i<=p; ++i){
mask1 = (1<<i)-1;
mask2 = mask1+1;
unsigned int t = (str&mask1)|mask2;
hash[t].cnt++;
hash[t].value= t;
}
}
}
sort(hash, hash+MAX, cmp);
int tc=-1;
char* seq=" ";
bool flag = false;
i=0,j=0;
int count=0;
while(true){
if(hash[j].cnt == tc){
if(count==6){
seq="\n";
count=0;
}
fout<<seq;
my_print_bin(hash[j].value);
seq=" ";
count++;
}else{
if(flag)
fout<<endl;
if(hash[j].cnt==0 || ++i>N)
break;
fout<<hash[j].cnt<<endl;
my_print_bin(hash[j].value);
count = 1;
tc=hash[j].cnt;
flag =true;
}
j++;
};
return 0;
}
posted on 2010-12-18 15:52
小阮 阅读(275)
评论(0) 编辑 收藏 引用 所属分类:
USACO