CQUPT 2017.5.15 (注释待补。。。

题解

poj 1112 team them up
题意：
把一群人分成两个组，满足4个条件：
1.每个人都属于其中一个组。
2.每个组都至少有一个成员。
3.每一个组中任意两个人都认识。
4.每个组的大小尽量接近。

思路：
如果我们把认识的人相互连边，那么就很不好想。
如果把不认识的人相互连边，那么互相认识的人之间就不会有边，就相当于一个二分图。即把一个图用染色法判断，有很多个连通分量。我们就从每个连通分量的二分图中，选择一个部分，这个时候就要用到dp了。

代码：

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
int mabs(int x)
{
    return x >= 0 ? x : -x;
}
int n;
bool ft[105][105];
bool zt[105][105];
int cor[105];
bool dp[105][105];
int ans[105][105][105];
vector<int> v0[105],v1[105];
vector<int> r1,r2;
int cnt = 0;
bool dfs(int x,int c)
{
    cor[x] = c;
    if (c == 0) v0[cnt].push_back(x);
    else v1[cnt].push_back(x);
    for (int i =  1;i <= n;i++)
    {
        if (i == x) continue;
        if (ft[x][i])
        {
            if (cor[i] != -1)
            {
                if (cor[i] == cor[x]) return false;
            }
            else
            {
                if (!dfs(i,!c)) return false;
            }
        }
    }
    return true;
}
int main()
{
    memset(cor,-1,sizeof(cor));
    memset(v1,0,sizeof(v1));
    memset(v0,0,sizeof(v0));
    memset(ans,-1,sizeof(ans));
    r1.clear(),r2.clear();
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
    {
        int t;
        while (scanf("%d",&t) != EOF)
        {
            if (!t) break;
            zt[i][t] = 1;
        }
    }
    for (int i = 1;i <= n;i++)
        for (int j = i+1;j <= n;j++)
    {
        if (!(zt[i][j] && zt[j][i]))
        {
            ft[i][j] = ft[j][i] = 1;
        }
    }
    bool flag = 0;
    for (int i  = 1;i <= n;i++)
    {
        if (cor[i] == -1)
        {
            if (!dfs(i,0))
            {
                flag = 1;
                break;
            }
            cnt++;
        }
    }
    if (flag)
    {
        printf("No solution\n");
        return 0;
    }
    //printf("%d$$$\n",cnt);
    //for (int i = 0;i < cnt;i++)
        //printf("%d ** %d",(int)v0[i].size(),(int)v1[i].size());
    dp[0][0] = 1;
    for (int k = 0;k < cnt;k++)
        for (int i = 0;i <= n;i++)
        for (int j = 0;j <= n;j++)
    {
        if (dp[i][j] && ans[i][j][k] == -1)
        {
            int a = v0[k].size(),b = v1[k].size();
            if (!dp[i+a][j+b] && ans[i+a][j+b][k] == -1)
            {
                dp[i+a][j+b] = 1;
                ans[i+a][j+b][k] = 0;
                for (int t = 0;t < k;t++)
                    ans[i+a][j+b][t] = ans[i][j][t];
            }
            if (!dp[i+b][j+a] && ans[i+b][j+a][k] == -1)
            {
                dp[i+b][j+a] = 1;
                ans[i+b][j+a][k] = 1;
                for (int t = 0;t < k;t++)
                    ans[i+b][j+a][t] = ans[i][j][t];
            }
        }
    }
    int res = 10000;
    int s1 = 0,s2 = 0;
    for (int i = n / 2;i >= 1;i--)
    {
        int j = n - i;
        if (dp[i][j])
        {
            //printf("%d***\n",i,j);
            if (res > mabs(i-j))
            {
                res = mabs(i-j);
                s1 = i,s2 = j;
            }
        }
    }
    //printf("%d**\n",res);
    for (int i = 0;i < cnt;i++)
    {
        if (ans[s1][s2][i] == 0)
        {
            for (int j = 0;j < v0[i].size();j++)
                r1.push_back(v0[i][j]);
            for (int j = 0;j < v1[i].size();j++)
                r2.push_back(v1[i][j]);
        }
        else
        {
            for (int j = 0;j < v1[i].size();j++)
                r1.push_back(v1[i][j]);
            for (int j = 0;j < v0[i].size();j++)
                r2.push_back(v0[i][j]);
        }
    }
    printf("%d",(int)r1.size());
    for (int i = 0;i < r1.size();i++)
    {
        printf(" %d",r1[i]);
    }
    printf("\n");
    printf("%d",(int)r2.size());
    for (int i = 0;i < r2.size();i++)
    {
        printf(" %d",r2[i]);
    }
    printf("\n");
    return 0;
}

HDU 4352 : xhxj lis
题意：
找一个区间之中lis为k的数字的个数。
思路：
数位dp，其中找lis的时候用到了状态压缩的思想，以及lis的二分做法。
代码 :

#include <stdio.h>
#include <string.h>
int k;
int dig[15];
long long dp[25][1 << 11][15];
int get_k(int st)
{
    int res = 0;
    while (st)
    {
        if (st & 1) res++;
        st >>= 1;
    }
    return res;
}
int get_num(int st,int x)
{
    for (int i = x;i <= 9;i++)
    {
        if (st & (1 << i)) return (st ^ (1 << i) | (1 << x));
    }
    return st | (1 << x);
}
long long dfs(int pos,int ze,int lim,int st)
{
    if (pos == -1) return get_k(st) == k;
    if (!lim && dp[pos][st][k] != -1) return dp[pos][st][k];
    int up = lim ? dig[pos] : 9;
    long long ans = 0;
    for (int i = 0;i <= up;i++)
    {
        ans += dfs(pos - 1,(ze && i == 0),lim && i == up,(ze && i == 0) ? 0 : get_num(st,i));
    }
    if (!lim) dp[pos][st][k] = ans;
    return ans;
}
long long solve(long long n)
{
    int pos = 0;
    while (n)
    {
        dig[pos++] = n % 10;
        n /= 10;
    }
    return dfs(pos-1,1,1,0);
}
int main()
{
    int t;
    int cas = 0;
    scanf("%d",&t);
    memset(dp,-1,sizeof(dp));
    for (cas = 1;cas <= t;cas++)
    {
        memset(dig,0,sizeof(dig));
        long long l,r;
        scanf("%I64d%I64d%d",&l,&r,&k);
        printf("Case #%d: %I64d\n",cas,solve(r)-solve(l-1));
    }
    return 0;
}

poj 1114 brackets sequence
题意：
给出一个括号序列，输出一个最短的合法的序列使给出的序列是这个序列的子序列。
思路：
动态规划，dp[i][j]表示从i到j需要添加的最小的括号数。然后输出的时候用递归的方式输出。
代码：

#include <stdio.h>
#include <string.h>
char a[120];
int dp[120][120];
int v[120][120];
void println(int i,int j)
{
    if (i > j) return;
    if (i == j)
    {
        if (a[i] == '(' || a[i] == ')') printf("()");
        else printf("[]");
    }
    else if (v[i][j] == -1)
    {
        printf("%c",a[i]);
        println(i+1,j-1);
        printf("%c",a[j]);
    }
    else
    {
        println(i,v[i][j]);
        println(v[i][j]+1,j);
    }
}
int main()
{
    scanf("%s",a);
    memset(dp,0,sizeof(dp));
    memset(v,-1,sizeof(v));
    int len = strlen(a);
    for (int i = 0;i < len;i++) dp[i][i] = 1;
    for (int m = 1;m < len;m++)
        for (int i = 0;i + m < len;i++)
    {
        int j = i + m;
        dp[i][j] = 1000000;
        if ((a[i] == '(' && a[j] == ')') || (a[i] == '[' && a[j] == ']'))
        {
            dp[i][j] = dp[i+1][j-1];
            v[i][j] = -1;
        }
        for (int k = i;k < j;k++)
        {
            if (dp[i][j] > dp[i][k] + dp[k+1][j])
            {
                dp[i][j] = dp[i][k] + dp[k+1][j];
                v[i][j] = k;
            }
        }
    }
    println(0,len-1);
    printf("\n");
    return 0;
}

cf 258b lucky number:
题意：
给出一个数，使得从1到这个数的区间内选择7个数，使得其一个数的幸运数字的个数大于其他六个数的幸运数字个数之和，问有多少种方案。
思路：
首先，用数位dp计算出含0，1，2，。。。，9个幸运数字的数字的个数。之后运用乘法原理计算出方法数。
代码 ：

#include <stdio.h>
#include <string.h>
long long dp[12][12];
long long dig[12];
long long luc[12];
const long long inf = 1e9 + 7;
long long Ans = 0;
int cnt = 0;
void cal(int lm,int ma,int num,long long res)
{
    if (lm >= ma) return;
    if (num == 7)
    {
        Ans = (Ans + res) % inf;
        return;
    }
    for (int i = 0;i <= cnt;i++)
    {
        if (luc[i])
        {
            luc[i]--;
            cal(lm + i,ma,num + 1,res * (luc[i] + 1) % inf);
            luc[i]++;
        }
    }
}
long long dfs(int pos,int num,bool lim)
{
    if (pos == 0) return num == 0;
    if (!lim && dp[pos][num] != -1) return dp[pos][num];
    int up = lim ? dig[pos] : 9;
    long long ans = 0;
    for (int i = 0;i <= up;i++)
    {
        ans += dfs(pos-1,num - (i == 4 || i == 7),lim && i == up);
    }
    if (!lim) dp[pos][num] = ans;
    return ans;
}
void solve(long long m)
{
    while (m)
    {
        dig[++cnt] = m % 10;
        m /= 10;
    }
    for (int i = 0;i <= cnt;i++)
        luc[i] = dfs(cnt,i,1);
    luc[0]--;
    for (int i = 1;i <= cnt;i++)
        cal(0,i,1,luc[i]);
    printf("%I64d\n",Ans);
}
int main()
{
    long long m;
    scanf("%I64d",&m);
    memset(dp,-1,sizeof(dp));
    solve(m);
    return 0;
}

poj 2411 M's dream
题意：
用1 * 2的长方形填充m * n的长方形，问有多少种填法。
思路：
状态压缩dp，一个数字代表当前一行的状态，之后进行判断就ok。
代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int h,w;
const int sta = (1 << 11) + 10;
long long dp[12][sta];
long long ans[12][12];
bool init(int k)
{
    for (int i = 0;i < w; )
    {
        //printf("*****\n");
        if (k & (1 << i))
        {
            if (i == w - 1) return false;
            else if (k & (1 <<(i + 1))) i += 2;
            else return false;
        }
        else
            i++;
    }
    return true;
}
bool ok(int now,int pre)
{
    for (int i = 0;i < w; )
    {
        if (now & (1 << i))
        {
            if (pre & (1 << i))
            {
                if (i == w - 1) return false;
                if ((now & (1 << (i + 1))) && (pre & (1 << (i + 1)))) i += 2;
                else return false;
            }
            else
            {
                i++;
            }
        }
        else
        {
            if (pre & (1 << i)) i++;
            else return false;
        }
    }
    return true;
}
void solve(void)
{
    int maxn = (1 << w) - 1;
    for (int i = 0;i <= maxn;i++)
    {
        if (init(i)) dp[1][i] = 1;
    }
    for (int i = 2;i <= h;i++)
    {
        for (int j = 0;j <= maxn;j++)
            for (int k = 0;k <= maxn;k++)
        {
            if (ok(j,k)) dp[i][j] += dp[i-1][k];
        }
    }
    printf("%lld\n",ans[h][w] = ans[w][h] = dp[h][maxn]);
}
int main()
{
    memset(ans,-1,sizeof(ans));
    while ((scanf("%d%d",&h,&w) != EOF) && h * w)
    {
        if (h < w) swap(h,w);
        if (ans[h][w] != -1)
        {
            printf("%lld\n",ans[h][w]);
            continue;
        }
        if (h * w & 1)
        {
            ans[h][w] = 0;
            printf("0\n");
        }
        else
        {
            memset(dp,0,sizeof(dp));
            solve();
        }
    }
    return 0;
}