专栏首页饶文津的专栏【USACO 3.1】Contact(01子串按出现次数排序)

【USACO 3.1】Contact(01子串按出现次数排序)

题意:给你一个01字符串,将长度为a到b之间(包含a、b)的子串按照出现次数排序。注意输入输出格式

题解:01子串对应一个二进制,为了区别11和011这样的不同子串,我们把长度也记录下来,官方题解是在子串前加上1来区别。然后按次数排序。为了方便,我将字符串代表的二进制转化为int整数,输出时再转化为字符串。

http://train.usaco.org/usacoprob2?a=F1brtx4Sr2b&S=contact

/*
TASK:contact
LANG:C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int time[20][5000];
int a,b,n;
char s[200005];
int cnt;
int toB(int be,int len){
    int ans=0;
    for(int i=0;i<len;i++)
        ans=ans*2+(s[be+i]=='1');
    return ans;
}
struct node{
    int time,v,len;
}e[100000];
bool cmp(node a,node b){
    return a.time>b.time||a.time==b.time&&(a.len<b.len||a.len==b.len&&a.v<b.v);
}
void toS(int v,int len){
    char s[20]="";
    for(int i=len-1;i>=0;i--){
        s[i]=v%2+'0';
        v/=2;
    }
    printf("%s",s);
}
int main(){
    freopen("contact.in","r",stdin);
    freopen("contact.out","w",stdout);
    scanf("%d%d%d",&a,&b,&n);
    while(~scanf("%s",s+strlen(s)));
    int l=strlen(s);
    for(int i=0;i<l-a+1;i++)
        for(int j=a;j<=b&&i+j<=l;j++)
            time[j][toB(i,j)]++;//长度j的值为toB的子串出现次数++

    for(int i=a;i<=b;i++)
        for(int j=0;j<1<<i;j++)
            if(time[i][j])e[cnt++]=(node){time[i][j],j,i};//出现次数不为0的子串放入e中
    sort(e,e+cnt,cmp);//按出现次数排序
    int num;
    for(int i=0,j=0;i<cnt;i++){
        if(!i||e[i].time!=e[i-1].time){//如果和上一个子串次数不同
            j++;
            if(j>n)break;//只输出前n大的。
            printf("%d\n",e[i].time);
            num=0;
        }
        toS(e[i].v,e[i].len);
        num++;
        if(e[i].time==e[i+1].time && num%6)
            printf(" ");
        else//下一个子串和当前子串的出现次数不同或者是第6个了,就要换行
            puts("");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【USACO 3.2】Sweet Butter(最短路)

    枚举到的某点,然后优先队列优化的dijkstra求最短路,把给定的点到其的最短路加起来,更新最小值。复杂度是

    饶文津
  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • 【Mutual Training for Wannafly Union #1 】

    题意:过隧道,每次人可以先向前一格,然后向上或向下或不动,然后车都向左2格。问能否到达隧道终点。

    饶文津
  • 【USACO 3.2】Sweet Butter(最短路)

    枚举到的某点,然后优先队列优化的dijkstra求最短路,把给定的点到其的最短路加起来,更新最小值。复杂度是

    饶文津
  • LeetCode 139 Word Break

    ShenduCC
  • 04:围棋

    总时间限制: 1000ms内存限制: 65536kB描述围棋的棋盘上有19*19条线交织成的361个交点,黑棋和白棋可以下在交点上。我们称这些交点为“目”。 一...

    attack
  • 【奇技淫巧】-- 走地图的不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    看、未来
  • 【(图) 旅游规划 (25 分)】【Dijkstra算法】

    _DIY
  • 【AtCoder - 2300】Snuke Line(树状数组)

    每隔d站停一次的列车,一定能买到购买区间的长度≥d的纪念品。 长度比d小但包含了d的倍数的纪念品也可以买到。 所以,如果按长度给纪念品排序,用树状数组维护长...

    饶文津
  • 修理牛棚 Barn Repair

    分析:贪心,取对间隔进行排序,按照贪心思想取间隔最大着为空隙,当前所需木板数+1,要注意的是一旦选出空隙总长要加一,因为你分裂了线段少算了末端,木板数用完了就得...

    glm233

扫码关注云+社区

领取腾讯云代金券