首页 > ACM题库 > HDU-杭电 > HDU 3828-A + B problem[解题报告]HOJ
2015
04-13

HDU 3828-A + B problem[解题报告]HOJ

A + B problem

问题描述 :

QQ and OO always play the game of A + B. QQ gives tow decimal number A and B, and OO answers the sum at once. But to do the same things too often is boring. So, today they are fed up with the easy game, and they come up with new rules of the game.
Rule1: When add A and B we use the binary system string of A and B.
Rule2: We can overlap the same suffix of A and prefix of B.
Rule3: If the binary system string of B is a substring of A we can use A to overlap B.
The Killers of Two Kingdoms

To make the problem more interesting, QQ gives n numbers, OO should use every one of them and every one once, then give the smallest of the sum. Now OO have no time to do it and need your help. You’re a talented programmer you can do it.

输入:

There are several tests, every test begin with n followed with n (0 < n < 16) lines, each line is a decimal number ai(0 < ai < 2^64) as described above.
Process until EOF.

输出:

There are several tests, every test begin with n followed with n (0 < n < 16) lines, each line is a decimal number ai(0 < ai < 2^64) as described above.
Process until EOF.

样例输入:

2
5
3
3
245
351
107

样例输出:

11
3935

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define mod 1000000009LL
#define ll __int64
#define maxn 2000
ll next[maxn];
void GetNext(char str[])
{
 ll i = 1, len = strlen(str + 1);
 next[1] = 0;
 ll j = 0;
 while(i <= len)
 {
 if (j == 0 || str[i] == str[j])
 {
 i++;
 j++;
 next[i] = j;
 }
 else
 j = next[j];
 }
}
//-1 include 0 no x len
ll kmp(char str[], char str2[])
{
 ll i = 1, j = 1, len1 = strlen(str + 1), len2 = strlen(str2 + 1);
 while(i <= len1 && j <= len2)
 {
 if (j == 0 || str[i] == str2[j])
 {
 i++;
 j++;
 }
 else j = next[j];
 }
 if (j > len2) return -1;
 if (i > len1) return j - 1;
}
ll n, ca;
char str[20][100];
ll share[20][20], len[20];
ll dp[85536][20];
ll pre[85536][20][2];
char strtmp[maxn], strtmp2[maxn];
void getans(ll i, ll j, ll from)
{
 if (from == -1) strcpy(strtmp, str[j] + 1);
 else strcat(strtmp, str[j] + 1 + share[from][j]);
 if (pre[i][j][0] != -1 && pre[i][j][1] != -1)
 getans(pre[i][j][0], pre[i][j][1], j);
}
ll getInt(char strtmp2[])
{
 ll ans = 0;
 for(ll i = 0; i <strlen(strtmp2); i++)
 {
 if (strtmp2[i] == '1')ans=(ans<<1)+1;
 else ans=ans<<1;
 if (ans >= mod) ans %= mod;
 }
 return ans;
}
bool vst[20];
char cat[20][20][300];
int main()
{
 ca = 1;
 while(scanf("%I64d", &n) != EOF)
 {
 for(ll i = 0; i < n; i++)
 {
 unsigned ll a;
 scanf("%I64u", &a);
 char tmp[maxn], ccnt = 0;
 while(a)
 {
 if (a & 1LL) tmp[ccnt++] = '1';
 else tmp[ccnt++] = '0';
 a >>= 1LL;
 }
 for(ll j = 0, k = ccnt - 1; j < ccnt; j++, k--)
 str[i][j + 1] = tmp[k];
 str[i][1 + ccnt] = '\0';
 }
 memset(share, 0, sizeof(share));
 memset(vst, 0, sizeof(vst));
 for(ll i = 0; i < n; i++)
 for(ll j = 0; j < n; j++)
 {
 GetNext(str[i]);
 if (i != j && !vst[j] && kmp(str[j], str[i]) == -1)//i��j����
 {
 vst[i] = 1;
 break;
 }
 }
 ll cnt = 0;
 for(ll i = 0; i < n; i++)
 if (!vst[i]) strcpy(str[cnt++] + 1, str[i] + 1);
 n = cnt;
 for(ll i = 0; i < n; i++)
 {
 len[i] = strlen(str[i] + 1);
 for(ll j = 0; j < n; j++)
 {
 GetNext(str[j]);
 if(i==j)continue;
 share[i][j] = kmp(str[i], str[j]);
 if(share[j][j]==-1)share[i][j]=strlen(str[j]+1);
 }
 }
 for(ll i = 0; i < n; i++)
 for(ll j = 0; j < n; j++)
 {
 strcpy(cat[i][j], str[i] + 1);
 strcat(cat[i][j], str[j] + 1 + share[i][j]);
 }
 memset(dp, -1, sizeof(dp));
 memset(pre, -1, sizeof(pre));
 for(ll i = 0; i < n; i++)
 {
 dp[1 << i][i] = len[i];
 pre[1 << i][i][0] = -1;
 }
 for(ll i = 1; i < (1 << n); i++)
 {
 for(ll j = 0; j < n; j++)
 {
 if (dp[i][j] != -1)
 {
 for(ll k = 0; k < n; k++)
 {
 if (!(i>>k&1))
 {
 ll st = (i | (1 << k));
 ll val = dp[i][j] + len[k] - share[k][j];
 if (dp[st][k] == -1 || val < dp[st][k])
 {
 dp[st][k] = val;
 pre[st][k][0] = i;
 pre[st][k][1] = j;
 }
 else if (val == dp[st][k])
 {
 if (strcmp(cat[k][j], cat[k][pre[st][k][1]]) < 0)
 {
 pre[st][k][0] = i;
 pre[st][k][1] = j;
 }
 }
 }
 }
 }
 }
 }
 ll id = -1, mmax = 100000;
 for(ll i = 0, k = (1 << n) - 1; i < n; i++)
 {
 if (dp[k][i] < mmax)
 {
 mmax = dp[k][i];
 id = i;
 }
 else if (dp[k][i] == mmax && strcmp(str[i] + 1, str[id] + 1) < 0)
 {
 id = i;
 }
 }
 getans((1 << n) - 1, id, -1);
 printf("%I64d\n", getInt(strtmp));
 }
 return 0;
}

  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  3. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。