首页 > ACM题库 > HDU-杭电 > HDU 1153 Magic Bitstrings -字符串-[解题报告] C++
2013
12-03

HDU 1153 Magic Bitstrings -字符串-[解题报告] C++

Magic Bitstrings

问题描述 :

A bitstring, whose length is one less than a prime, might be magic. 1001 is one such string. In order to see the magic in the string let us append a non-bit x to it, regard the new thingy as a cyclic string, and make this square matrix of bits

each bit 1001
every 2nd bit 0110
every 3rd bit 0110
every 4th bit 1001

This matrix has the same number of rows as the length of the original bitstring. The m-th row of the matrix has every m-th bit of the original string starting with the m-th bit. Because the enlarged thingy has prime length, the appended x never gets used.

If each row of the matrix is either the original bitstring or its complement, the original bitstring is magic.

Each line of input (except last) contains a prime number p ≤ 100000. The last line contains 0 and this line should not be processed. For each prime number from the input produce one line of output containing the lexicographically smallest, non-constant magic bitstring of length p-1, if such a string exists, otherwise output Impossible.

样例输入:

5
3
17
47
2
79
0

样例输出:

0110
01
0010111001110100
0000100001101010001101100100111010100111101111
Impossible
001001100001011010000001001111001110101010100011000011011111101001011110011011

#include <iostream>

using namespace std;
long long p;
int a[100010];
int main()
{
    while(cin >> p)
    {
        if(p==0)break;
        if(p==2)cout << "Impossible" << endl;
        else
        {
            for(int i=1;i<p;i++)a[i]=1;
            for(long long i=1;i<p;i++)a[i*i%p]=0;//用int,RE一次
            for(int i=1;i<p;i++)cout << a[i];
            cout << endl;
        }
    }
    return 0;
}

思路:必须承认这道题目是看了网上的解题报告,才知道怎么做的。

a[1%n], a[2%n], a[3%n], …, a[n-1]               (1)

a[2%n], a[4%n], a[6%n], …, a[2(n-1)%n]     (2)

若a[1%n]=a[2%n],则原字符串或者补字符串(complement)第1,2位都是相等的,所以(2)式中a[2%n]=a[4%n](题目中说每一行不是原字符串就是补字符串:If each row of the matrix is either the original bitstring or its complement, the original bitstring is magic. 这句话很关键)

同理若a[1%n]!=a[2%n],则a[2%n]!=a[4%n]

由上可知a[1%n]=a[4%n],同理可推出a[1%n]=a[4%n]=a[9%n]=…=a[i*i%n] (*)

令(*)=0,其他位置为1,即可得到答案。

因为(*)包含a[1]所以要想字典序最小则必须为零

其他位置必须为1的理由如下:

若a[1%n]=a[2%n],则a[2%n]=a[4%n],则a[4%n]=a[8%n],a[3%n]=a[6%n],a[4%n]=a[6%n]…

最终会导致整个矩阵都为零,与题目要求non-constant magic bitstring不符。


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  3. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。