USACO Shopping Offers

USACO 上给出了两种模型，第一种是最短路，第二种是完全背包问题。其实他们的实质是一样。
个人认为完全背包更易于实现和调试，平均情况下效率更高。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #include <limits.h>
05
06 struct node
07 {
08     int add[5];
09     int p;
10 }offer[100+10] = {};
11 //also regard one item as an offer
12
13 int s,t;
14 int map[1000];  //code to index
15 int need[6];
16 int best[6][6][6][6][6];
17
18 void init()
19 {
20     scanf("%d",&s);
21     int i,j;
22     int cnt = 0;
23     int code,num,n;
24     for(i = 0;i < 1000;i ++)
25         map[i] = -1;
26     for(i = 0;i < s;i ++)
27     {
28         scanf("%d",&n);
29         for(j = 0;j < n;j ++)
30         {
31             scanf("%d%d",&code,&num);
32             if(map[code] == -1)
33                 map[code] = cnt ++;
34             offer[i].add[map[code]] = num;
35         }
36         scanf("%d",&offer[i].p);
37     }
38     scanf("%d",&t);
39     for(i = s;i < s + t;i ++)
40     {
41         scanf("%d%d%d",&code,&num,&offer[i].p);
42         if(map[code] == -1)
43             map[code] = cnt ++;
44         offer[i].add[map[code]] = 1;
45         need[map[code]] = num;
46     }
47 }
48
49 void solve()
50 {
51     int i,a,b,c,d,e;
52     for(a = 0;a < 6;a ++)
53     for(b = 0;b < 6;b ++)
54     for(c = 0;c < 6;c ++)
55     for(d = 0;d < 6;d ++)
56     for(e = 0;e < 6;e ++)
57         best[a][b][c][d][e] = INT_MAX;
58     best[0][0][0][0][0] = 0;
59
60     for(a = 0;a <= need[0];a ++)
61     {
62         for(b = 0;b <= need[1];b ++)
63         {
64             for(c = 0;c <= need[2];c ++)
65                 for(d = 0;d <= need[3];d ++)
66                     for (e = 0;e <= need[4];e ++)
67                     {
68                         for(i = 0;i < t + s;i ++)
69                         {
70                             if(a + offer[i].add[0] <= need[0] && b + offer[i].add[1] <= need[1] && c + offer[i].add[2] <= need[2] && d + offer[i].add[3] <= need[3] && e + offer[i].add[4] <= need[4])
71                                 if(best[a][b][c][d][e] < INT_MAX && best[a + offer[i].add[0]][b + offer[i].add[1]][c + offer[i].add[2]][d + offer[i].add[3]][e + offer[i].add[4]] > (best[a][b][c][d][e] + offer[i].p))
72                                 {
73                                     best[a + offer[i].add[0]][b + offer[i].add[1]][c + offer[i].add[2]][d + offer[i].add[3]][e + offer[i].add[4]] = best[a][b][c][d][e] + offer[i].p;
74                                 }
75                         }
76                     }
77         }
78     }
79     printf("%d\n",best[need[0]][need[1]][need[2]][need[3]][need[4]]);
80 }
81
82 int main()
83 {
84     freopen("shopping.in","r",stdin);
85     freopen("shopping.out","w",stdout);
86     init();
87     solve();
88     return 0;
89 }

NOIP 2011 聪明的质检员

容易知道Y(W)是关于随W的增大而递减的，因此可以想到用二分W使得Y逐步逼近S，由于题目要求绝对值最小，因此比较保险的方法是使用两次二分，分别求出恰好大于S的Y值和恰好小于S的Y值，然后输出距离S最近的即可。

然而，即使使用了二分，程序依然不能通过所有数据。因为我们忘了题目中的一个条件——区间总数上限是200000，而不同区间可能重合或相互重叠，所以，如果我们仅仅按照题目描述的方式计算每个区间上的Yi，那么在最坏情况仅仅计算所有区间上的Y就会超时，因此，需要一个更巧妙的方法——前缀和，实现方式请看代码。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MXN 200000+1

long cnt[MXN];
unsigned long long sum[MXN],s;
long w[MXN],v[MXN];
long m,n;
long range_l[MXN],range_r[MXN];

long long calc_range(long l,long r)
{
    return (cnt[r] - cnt[l - 1]) * (sum[r] - sum[l - 1]);
}

long long calc_tot(long lim)
{
    long long res = 0;
    long i;
        //空间换时间
    cnt[0] = 0;
    sum[0] = 0;
    for(i = 1;i <= n;i ++)
    {
        cnt[i] = cnt[i - 1];
        sum[i] = sum[i - 1];
        if(w[i] >= lim)
        {cnt[i] += 1;sum[i] += v[i];}
    }
    for(i = 0;i < m;i ++)
        res += calc_range(range_l[i],range_r[i]);
    return res;
}

int main()
{
    long i;
    long long a,b;
    scanf("%ld%ld%lld",&n,&m,&s);
    for(i = 1;i <= n;i ++)
        scanf("%ld%ld",&w[i],&v[i]);
    for(i = 0;i < m;i ++)
        scanf("%ld%ld",&range_l[i],&range_r[i]);

    long l,r,mid;
        //分别从两个方向逼近S
    l = 0;r = 10e6 + 1;
    while(l < r)
    {
        mid = (l + r) / 2;
        if(calc_tot(mid) <= s)
            r = mid;
        else
            l = mid + 1;
    }
    a = llabs(calc_tot(l) - s);

    l = 0;r = 10e6 + 1;
        //其实这里的l，r没有必要开这么大，读者可以自行分析
    while(l < r)
    {
        mid = (l + r + 1) / 2;
        if(calc_tot(mid) >= s)
            l = mid;
        else r = mid - 1;
    }
    b = llabs(calc_tot(l) - s);

    if(a < b)    printf("%lld\n",a);
    else printf("%lld\n",b);
    return 0;
}

NOIP 2011 参赛感言

比赛结束后我发现数学还是很重要的，选择客栈，聪明的质检员，观光公交都有涉及到一部分数学知识，而计算系数这题直接就是二项式定理的应用。

下面分析一下各个题目的主要思想：

选择客栈：动态规划，加法原理
mayan游戏：DFS，剪枝
质检员：二分，空间换时间
观光公交：贪心算法（我还没有研究出来是怎么贪心的）

其中，mayan游戏对选手的语言实现能力有较高要求，本人考试时用了一个多小时最终还是没有折腾出来。

选择客栈，质检员考察了选手的基本技能——当然，也是优秀程序员必备的素质——用空间换时间，详细题解见下面的连接：

安排客栈

聪明的质检员

NOIP2011 Day1 安排客栈

首先，对题目进行一个数学上的描述：
有color[],price[]两个数组，求满足条件
color[i] == color[j](i < j) 且 存在i<=k<=j满足price[k]<=limit(即题目描述中的p)
的的个数。

显然，如果使用最朴素的办法，可以用两个for嵌套，即：

for(i = 1;i <= n;i ++)
   for(j = i + 1;j <= n;j ++)
       if(check(i,j))  tot ++;

可是，题目中n的上限是200000。即使check可以在O(1)时间内完成，算法复杂度也是n^2的，所以我们需要一个更巧妙的方法：用空间换取时间。

具体思路是这样的。如果price[i]<=limit,那么j的取值就可以是i其后所有颜色与i相同的客栈，因此，我们需要一个数组cnt[i][k]来记录从第i个开始,颜色为k的客栈的数量（具体实现见代码）。 可是，如果price[i]>limit,那又会是什么情况呢？

这个时候，如果我们可以在i后面找到一个m满足price[m]<=limit,那么j可以取从m开始颜色和i相同的所有客栈编号（具体实现见代码）。由于i显然是递增的，因此不会出现重复计数的情况。至此，问题成功解决。
 

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <time.h>
04 #define MAX_HOTEL (200000 + 10)
05 #define MAX_COLOR (50 + 5)
06 #include <string.h>
07
08 long cnt[MAX_HOTEL][MAX_COLOR];
09 long next[MAX_HOTEL];
10 long n;
11 int k,limit;
12 int color[MAX_HOTEL];
13 int price[MAX_HOTEL];
14
15 int solve()
16 {
17     long i,j;
18     long long ans = 0;
19     scanf("%ld%d%d",&n,&k,&limit);
20     for(i = 0;i < n;i ++)
21         scanf("%d%d",&color[i],&price[i]);
22        
23     for(i = 0;i < k;i ++)
24         cnt[n][i] = 0;
25     for(i = n - 1;i >= 0;i --)
26     {
27         for(j = 0;j < k;j ++)
28             cnt[i][j] = cnt[i + 1][j];
29         cnt[i][color[i]] ++;
30     }
31    
32     next[n] = -1;  //-1表示不存在
33     for(i = n - 1;i >= 0;i --)
34     {
35         if(price[i] <= limit)
36             next[i] = i;
37         else    next[i] = next[i + 1];
38     }
39        
40     for(i = 0;i < n;i ++)
41     {
42         if(price[i] <= limit)    ans += cnt[i][color[i]] - 1;
43         else if(next[i] != -1)
44         {
45             ans += cnt[next[i]][color[i]];
46         }
47         else break;  //如果i后面已经没有price小于limit的客栈了，可以直接跳出。
48     }
49     printf("%lld\n",ans);
50     return 0;
51 }
52
53 void test()  //测试用
54 {
55     char input[1000];
56     char printstdans[1000];
57     clock_t start,end;
58     int i;
59     for(i = 1;i <= 10;i ++)
60     {
61         sprintf(input,"hotel%d.in",i);
62         sprintf(printstdans,"cat hotel%d.ans",i);
63         freopen(input,"r",stdin);
64         printf("%d:\n",i);
65         memset(next,0,sizeof(next));
66         memset(cnt,0,sizeof(cnt));
67         start = clock();
68         solve();
69         end = clock();
70         system(printstdans);
71         printf("%.2f secs\n",(float)(end - start) / CLOCKS_PER_SEC);
72     }
73 }
74
75 int main()
76 {
77     test();
78     return 0;
79 }

虽然本人在考场上头脑发热只得了40分，个人认为这道题还是很不错的，带有一点动态规划的味道。

NOIP2011 Day2 计算系数

这道题和数学有密切关系，涉及到一个叫做二项式定理的东西（维基百科）。不过，即使不了解上面那个所谓的定理，我们也可以手工列举几个m,n,k模拟一下，就会发现系数和组合数的关系了。

#include <stdio.h>
#include <stdlib.h>

long long f[1010][1010];

long long times(long long a,int e)
{
    long long res = 1;
    while(e > 0)
    {
        res = (res * a) % 10007;
        e --;
    }
    return res;
}

void combination()
{
    int i,j;
    for(i = 0;i < 1010;i ++)
    {
        f[i][0] = 1;
        for(j = 1;j <= i;j ++)
        {
            f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % 10007;
        }
    }
}

int main()
{
    long a,b,k,m,n;
    scanf("%ld%ld%ld%ld%ld",&a,&b,&k,&n,&m);
    combination();
    printf("%lld\n",((f[k][m] * times(a,n)) % 10007) * times(b,m) % 10007);
    return 0;
}

不过考试的时候这道题我只得了60分，也许是因为没有使用long long型吧。

Magic Square 解题报告

本题是BFS的经典题目，因为只有8个数字，每个都在1～8之间，因此可以使用一个32bit整型描述状态，使用bitwise改变状态。

需要注意散列函数，要使用unsigned long，或者给返回值加上labs()，否则散列值（在某些机器上）可能是负数，造成数组越界。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define SEED 10007

struct element
{
    unsigned long s;
    char op;
    long prev;
}queue[41000] = {};

struct HNode
{
    unsigned long s;
    struct HNode *next;
}*hashtable[SEED] = {};

long head,tail;
long target = 0;

void enqueue(struct element a)
{
    queue[tail ++] = a;
}

struct element dequeue()
{
    return queue[head ++];
}

void getarget()
{
    int i;
    long t;
    for(i = 7;i >= 0;i --)
    {
        scanf("%ld",&t);
        target |= t << (i * 4);
    }
}

unsigned long h(unsigned long s)
{
    return (s % (unsigned long)SEED);
}

long transA(long s)
{
    long t;
    t = ((s & 0xF) << 28) | ((s & 0xF0) << 20) | ((s & 0xF00) << 12) | ((s & 0xF000) << 4);
    t |= ((s & 0xF0000) >> 4) | ((s & 0xF00000) >> 12) | ((s & 0xF000000) >> 20) | ((s & 0xF0000000) >> 28);
    return t;
}

long transB(long s)
{
    long t;
    t = ((s & 0xFFF00000) >> 4) + ((s & 0xFFF) << 4) + ((s & 0xF0000) << 12) + ((s & 0xF000) >> 12);
    return t;
}

long transC(long s)
{
    long t;
    t = s & 0xF00FF00F;
    t |= (s & 0xF0) << 20 | (s & 0xF00) >> 4 | (s & 0xF00000) >> 12 | (s & 0xF000000) >> 4;
    return t;
}

void pt(struct element p)
{
    char str[70];
    int i;
    for(i = 0;i < 60 && p.op != 0;p = queue[p.prev],i ++)
    {
        str[i] = p.op;
    }
    printf("%d\n",i);
    for(i --;i >= 0;i --)
    {
        printf("%c",str[i]);
    }
    printf("\n");
}

int find(long s)
{
    struct HNode *p;
    for(p = hashtable[h(s)];p != NULL;p = p->next)
        if(p->s == s)   return 1;
    return 0;
}

void insert(long s)
{
    struct HNode *p;
    p = malloc(sizeof(struct HNode));
    p->s = s;
    p->next = hashtable[h(s)];
    //fprintf(stderr,"%ld\n",h(s));
    hashtable[h(s)] = p;
}

int main()
{
    freopen("msquare.out","w",stdout);
    freopen("msquare.in","r",stdin);
    struct element now,next;
    long tmp;
    head = tail = 0;
    getarget();
    now.s = 0x12345678;
    now.prev = 0;
    now.op = 0;
    insert(0x12345678);
    enqueue(now);
    while(head < tail)
    {
        now = dequeue();
        if(now.s == target) break;
        tmp = transA(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'A';
            enqueue(next);
        }
        tmp = transB(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'B';
            enqueue(next);
        }
        tmp = transC(now.s);
        if(!find(tmp))
        {
            insert(tmp);
            next.s = tmp;
            next.prev = head - 1;
            next.op = 'C';
            enqueue(next);
        }
    }
    pt(now);
    return 0;
}

此外，USACO的题解给出了一种更适用与本题的方法，即把每个状态与一个数字相对应，只要用8！个数字就可以描述所有状态。并且从目标向初始状态搜索，输出结果时就没有必要反过来了。