专栏首页饶文津的专栏【kAriOJ】离散数学 构造群码 极大似然法解码

【kAriOJ】离散数学 构造群码 极大似然法解码

A. 编程题1 构造群码

时间限制 1000 ms 内存限制 65536 KB

题目描述

针对给定H,计算群码编码函数eH,并计算给定字的码字。

输入格式

第一行输入两个整数m,n;(m < n ,n < 10)

第二行输入m × (n - m) 个0或1,也就是矩阵H的上半部分,下半部分单位矩阵自行生成;

第三行输入m比特的字;

输出格式

第一行输出该编码函数能检测到的错误位数;

第二行输出给定字的码字;

输入样例

2 5
1 1 0 0 1 1
1 1

输出样例

2
11101

能检测到的错误位数,就是0~2^m-1生成的编码和0的非零距离的最小值-1。

编码就直接乘上[I|H],有个地方害我一直wa的,就是int k=0; if(g&(1<<j))k=1; bn[i]^=k&h[m-j][i];我写成了 bn[i]^=g&(1<<j)&h[m-j][i];

/*
TASK:构造群码
LANG:C++
URL:http://code.bupt.edu.cn/problem/contest/491/problem/A/
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 30
#define ll long long
using namespace std;
int n,m,h[N][N];
int bm[N],bn[N];
//计算n长度的a的权
int weight(int *a){
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=a[i];
    return ans;
}
//计算最多检测的错误
int getk(){
    int ans=100;
    //g的二进制即生成的Bm
    for(ll g=1;g<1<<m;g++){
        memset(bn,0,sizeof bn);
        for(int i=1;i<=n;i++)
            for(int j=m-1;j>=0;j--){
                int k=0;
                if(g&(1<<j))k=1;
                bn[i]^=k&h[m-j][i];
            }
        int w=weight(bn);
        if(w)ans=min(ans,weight(bn));
    }
    return ans-1;
}
int main() {
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=m+1;j<=n;j++)
            scanf("%d",&h[i][j]);
        h[i][i]=1;
    }
    printf("%d\n",getk());
     
    for(int i=1;i<=m;i++)
        scanf("%d",&bm[i]);
    //将bm编码成bn
    for(int i=1;i<=n;i++){
        bn[i]=0;
        for(int j=1;j<=m;j++)
            bn[i]^=bm[j]&h[j][i];
    }
    for(int i=1;i<=n;i++)printf("%d",bn[i]);
     
    return 0;
}

A. 编程题2 极大似然法解码

时间限制 1000 ms 内存限制 65536 KB

题目描述

给定群码(m,n)的编码函数e的H,采用极大似然法进行解码 (n<=20)

输入格式

第一行输入两个整数m,n;

第二行输入m × (n - m) 个0或1,也就是矩阵H的上半部分,下半部分单位矩阵自行生成;

第三行输入n比特的字;

输出格式

第一行:输出与e相关的极大似然法能纠错的比特数

第二行:采用极大似然法对给定的字解码后的字

输入样例

3 6
1 1 0 1 0 1 0 1 1
001110

输出样例

1
011

在所有编码和0的距离时,把编出来的码记录起来,然后解码时遍历所有编码,找到距离最近的,就是答案了。

/*
TASK:极大似然法解码
LANG:C++
URL:http://code.bupt.edu.cn/problem/contest/492/problem/A/
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 50
#define ll long long
using namespace std;
int n,m,h[N][N];
int bm[N];
ll bn[2000][N];
int tmp[N];
//计算n长度的a的权
int weight(ll a[N]){
    int ans=0;
    for(int i=1;i<=n;i++)
        ans+=a[i];
    return ans;
}
//计算最多检测的错误,同时计算得到所有的对应编码
int getk(){
    int ans=100;
    //g的二进制即生成的Bm
    for(ll g=1;g<1<<m;g++){
        for(int i=1;i<=n;i++)
            for(int j=m-1;j>=0;j--){
                int k=0;
                if(g&(1<<j))k=1;
                bn[g][i]^=k&h[m-j][i];
            }
        int w=weight(bn[g]);
        if(w)ans=min(ans,w);
    }
    return (ans-1)/2;
}
int getn(){
    int mi=100,ans=0;
    for(ll g=0;g<1<<m;g++){
        int dif=0;
        for(int i=1;i<=n;i++){
            if(bn[g][i]!=tmp[i])dif++;
        }
        if(mi>dif){
            mi=dif;
            ans=g;
        }
    }
    return ans;
}
int main() {
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=m+1;j<=n;j++)
            scanf("%d",&h[i][j]);
        h[i][i]=1;
    }
    printf("%d\n",getk());
     
    for(int i=1;i<=n;i++){
        char c;
        scanf(" %c",&c);
        tmp[i]=c-'0';
    }
    int ans=getn();
    for(int i=m-1;i>=0;i--)
        printf("%d",(1<<i)&ans?1:0);
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

    饶文津
  • 【奶昔队ROUND#1】

    模拟,不过我做的时候不是模拟,是计算...(写了好久,还wa了几次),现在看了别人的代码写过一份。

    饶文津
  • 【Gym 100947I】What a Mess

    饶文津
  • AtCoder Beginner Contest 118题解报告

    海天一树
  • LIS + Problem

    让我们举个例子:求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

    AngelNH
  • 河北工业大学ACM集训队日常训练day1030

    emmm.昨天刚到青岛.今天热身赛结束.非常想记录的一点就是.这个酒店太豪了.早餐特别豪.还有浴池.orz.要加油努力赚钱买大房子呀.补了一下题.记录一下. ...

    xiaohejun
  • 2018年全国多校算法寒假训练营练习比赛(第二场)

     背包问题,只是特殊处理一下h为0和不为0的情况就行  若h=0,卡不了bug,就是正常的o-1背包  若h不等于0,可以卡bug,假设第i件武器是卡b...

    mathor
  • Codeforces Round #627 (Div. 3) 题解

    A.Yet Another Tetris Problem 题意:看白了其实就是让你看看是否都为偶数,或者奇数,是的话输出YES,否则输出NO。

    用户7727433
  • 2491 玉蟾宫

    2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description   有一天...

    attack
  • floyd算法

     floyd算法解决的问题是在图中找到从i号结点到j号结点最短路径值(边的权值)的问题,核心代码就下面四行

    mathor

扫码关注云+社区

领取腾讯云代金券