T1:disease

题意：有n头奶牛，k种细菌（k<=15）,给你每头奶牛携带的细菌种类，问：若让选出所有奶牛携带细菌少于d种，最多选几头奶牛？

思路：上手就用了动归，可能是昨天打积木那题，自己信心爆棚。然后……神奇的22.2分出炉啦！之后，我痛定思痛，发现动归真的是伪得快。

正解：反正k小，把可能情况枚举一下，最多也没几种。不就是$C_k^d$种吗？然后比较打擂台就可以了。

见代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans,d,k,inf=-0x3f3f3f,flag[16],use[16]; 
bool a[1001][16];
void dfs(int x)
{
    for(int i=use[x-1]+1;i<=d;i++)
    {
        if(flag[i]==0)
        {
            flag[i]=1;
            use[x]=i;
            if(x==k)
            {
                for(int j=1;j<=n;j++)
                {
                       for(int i=1;i<=d;i++)
                    {
                        if(a[j][i]==true&&flag[i]==0)
                          {
                        ans--;
                        break;
                        }
                    }
                }
                if(ans>inf)
                inf=ans;
                ans=n;
            }
            else
            dfs(x+1);    
            flag[i]=0;
            use[x]=0;
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&d,&k);
    ans=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[0][0]);
        for(int j=1;j<=a[0][0];j++)
        {
            scanf("%d",&a[0][1]);
            a[i][a[0][1]]=true;
        }
    }
    dfs(1);
    printf("%d",inf);
    return 0;
}

注意事项：

要开一个数组，依次向后走，去记录，万万不能从1到k来回搞，不然就不是$C_d^k$而是C!了。

好题哉！！！

T2: jumpcow

题意：有一个序列，你可以选择其中任意个数组成一个子序列，其中有个弹跳值，弹跳值为子序列奇数项的和乘上偶数项的和，问：弹跳值最大为多少？

思路：熟悉的操作，熟悉的味道——动归！一开始在考场上，把奇偶混在一起，没有分开奇数项和偶数项，只有10分。

正解：奇偶分开是什么意思呢？很简单。就是设一个二维数组：a[n][2]，其中第二维为1表示此项做奇数项是的情况，第二维为0表示此项是偶数项的情况。

转移方程：a[n][1]=max(a[n-1][0]+a[n][1],a[n-1][1])这个意思就是：如果不选此项就是前一个奇数项，然后依次向后转移。若选此项就是前一项为偶数项那就加上。

同理：a[n][0]=max(a[n-1][1]-a[n][0],a[n-1][0])。

神奇的O(n)算法！

见代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,max1=-0x3f3f3f,max2=-0x3f3f3f,inf=-0x3f3f3f;
int a[150001][2];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i][1]);    
    }
    for(int i=2;i<=n;i++)
    {
        max1=-0x3f3f3f;
        max2=-0x3f3f3f;
        for(int j=1;j<i;j++)
        {
            if(a[j][1]>max1)
            max1=a[j][1];
            if(a[j][0]>max2)
            max2=a[j][0];
        }
        a[i][0]=max1-a[i][1];
        a[i][1]+=max2;    
    }
    for(int i=1;i<=n;i++)
    {
        if(inf<a[i][0])
        inf=a[i][0];
        if(inf<a[i][1])
        inf=a[i][1];
    }
    printf("%d",inf);
    return 0;
}

好题哉！！！

T3:town

题意：有一个被水淹没小镇，给你小镇每块地的高度，每块地上的水可以流到上、下、左、右当中不高于它高度的格子里，可以在任何格子里安装一台水泵，水泵可以抽走无限量的水。问：最少需要安装几台水泵可以抽走所有的水？

正解：宽搜。先找到最低的格子，然后向高处拓展标记，如果没有抽完就找第二小的格子继续搜，以此类推。用一个变量记录一下次数即可。

见代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,k,head,ans,tail=1;
int h1[2501],l1[2501],p[5]={0,-1,1,0,0},y[5]={0,0,0,-1,1};
char a[51][51];
bool flag[51][51];
void bfs(int h,int l)
{ 
    head=0;
    tail=1;
    h1[1]=h;
    l1[1]=l;
    flag[h][l]=true;
    while(head!=tail)
    {
        head++;
        for(int i=1;i<=4;i++)
        {
            if(a[h1[head]+p[i]][l1[head]+y[i]]>0&&flag[h1[head]+p[i]][l1[head]+y[i]]==false&&a[h1[head]+p[i]][l1[head]+y[i]]>=a[h1[head]][l1[head]])
            {
                tail++;
                h1[tail]=h1[head]+p[i];
                l1[tail]=l1[head]+y[i];
                flag[h1[tail]][l1[tail]]=true;
            }
        }
    }
}
int main()
{
    scanf("%d",&k);
    for(int q=1;q<=k;q++)
    {
        ans=0;
        memset(a,-1,sizeof(a));
        memset(flag,false,sizeof(flag));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            cin>>a[i][j];
        }
        while(1)
        {
            bool flag2=false;
            int min=0x3f3f3f,minh=0,minl=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                {
                    if(a[i][j]<min&&flag[i][j]==false)
                    {
                        min=a[i][j];
                        minh=i;
                        minl=j;
                        flag2=true;
                    }
                }
            if(flag2==false)
            break;
            bfs(minh,minl);
            ans++;    
        }
        printf("%d
",ans);
    }
    return 0;
}

好题哉！！！

T4:cowtract

最大生成树模板题：没啥好讲的，博主也不会讲，上网搜呗。

见代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ans,ans1,fa[20001],flag;
struct cow{
    int father,son,cost;
};
cow tree[20001];
bool cmp(cow x,cow y)
{
    return x.cost>y.cost;
}
int find(int x)
{
    if(fa[x]==x)
    return x;
    else
    return fa[x]=find(fa[x]);
}
void add(int x,int y)
{
    fa[fa[x]]=fa[y];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&tree[i].father,&tree[i].son,&tree[i].cost);
    }
    sort(tree+1,tree+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(tree[i].father)!=find(tree[i].son))
        {   
            ans1++;
            add(tree[i].father,tree[i].son);
            ans+=tree[i].cost;
        }    
    }
    if(ans1==n-1)
    {
        printf("%d",ans);
        return 0;
    }
    else
    printf("-1");
    return 0;
}