【集合！】 20140416 && 20140417集训总结

mobius的奇怪演绎

当我第一眼看见题目中出现mobius的时候，我唯一想到的就是某科学家对于n维空间的阐述与思考，同时还提出了一个mobius环。而这道题中的环就是mobius环咯。不过其实这是一道dp。。。dp的思路还是比较神。。。左括号设为+1,右括号-1.首先前面和后面有对应的规则，那么我们就做一个四维dp(dp[i][j][m][k])i表示位置，j表示正面的左括号和右括号之和，m是背面的和的最小值的abs，k是背面的和。记录m的是因为可能出现如下情况：
__________ (mid) ________    __
+100 -200    +100
虽然l+r = 0 但是其实这是不合法的。所以dp到最后的时候就需要考虑两个条件：
1. j >= m 2. j+k == 0
转移呢？分情况讨论：
1.s[i+1] == 'S' 这种情况下肯定有dp[i+1][j+1][m][k+1] += dp[i][j][m][k];
          而上面是j + 1,而j-1取决于j是否大于0，而且这时还需要考虑k + m == 0如果为0，那么m就要更新
                  so： if（k + m == 0) dp[i+1][j-1][m+1][k-1] += dp[i][j][m][k];
                          else dp[i+1][j-1][m][k-1] +=dp[i][j][m][k];
2,s[i+1]=='D'
      如果j+1，那么k--，如上考虑k与m的关系。然后j-1只考虑j>0 方程参上或代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

int T;

ll dp[][][][];

char s[]; int n = ;

int main()

{

    freopen("mobius.in","r",stdin);

    freopen("mobius.out","w",stdout);

    scanf("%d",&T);

    getchar();

    while(T--)

    {

        n = ;

        scanf("%s",s+);

        n = strlen(s+);

        memset(dp,,sizeof(dp));

        dp[][][][n+] = ;

        for(int i = ; i < n; i++)

            for(int j = ; j <= i; j++)

                for(int  m = ; m <= i; m++)

                    for(int  k = -m+n+; k <= i+n+; k++)

                    {

                        if(dp[i][j][m][k])

                        {

                            if(s[i+] == 'S'){

                                dp[i+][j+][m][k+] += dp[i][j][m][k];

                                if(j)

                                {

                                    if(m == -(k-n-)) dp[i+][j-][m+][k-] += dp[i][j][m][k];

                                    else dp[i+][j-][m][k-] += dp[i][j][m][k];

                                }

                            }

                            else{

                                if(j) dp[i+][j-][m][k+] += dp[i][j][m][k];

                                if(m == -(k-n-)) dp[i+][j+][m+][k-] += dp[i][j][m][k];

                                else dp[i+][j+][m][k-] += dp[i][j][m][k];

                            }

                        }

                    }

        ll ans = ;

        for(int i = ; i <= n;i++)

            for(int j = ; j <= i;j++)

                ans += dp[n][i][j][-i+n+];

        printf("%lld\n",ans);

    }

    return ;

}

mobius

某不科学的多重背包

题目：Eden 的新背包问题

【问题描述】

“寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心情。能不能说给我听。”

失忆的 Eden 总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。

记忆中，她总是喜欢给 Eden 出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden 这样的一个问题：有 n 个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m 固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过 m，且价值和最大。

众所周知的，这是一个很经典的多重背包问题，Eden 很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。

这下 Eden 犯难了，不过 Eden 不希望自己被难住，你能帮帮他么？

【输入格式】

从文件 bag.in 看读入数据。

第一行一个数 n，表示有 n 个玩偶，玩偶从 0 开始编号

第二行开始后面的 n 行，每行三个数 ai, bi, ci，分别表示买一个第 i 个玩偶需要的价钱，获得的价值以及第 i 个玩偶的限购次数。

接下来的一行为 q，表示询问次数。

接下来 q 行，每行两个数 di, ei表示每个询问去掉的是哪个玩偶（注意玩偶从 0 开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立）

【输出格式】

输出到文件 bag.out 中。

输出 q 行，第 i 行输出对于第 i 个询问的答案。

【样例输入】

2 3 4

1 2 1

4 1 2

2 1 1

3 2 3

1 10

2 7

3 4

4 8

0 5

【样例输出】

【样例说明】

一共五种玩偶，分别的价钱价值和限购次数为(2,3,4)， (1,2,1)， (4,1,2)，(2,1,1)，(3,2,3)。

五个询问，以第一个询问为例。第一个询问表示的是去掉编号为 1 的玩偶，且拥有的钱数为 10 时可以获得的最大价值，则此时剩余玩偶为(2,3,4)，(4,1,2)，(2,1,1)，(3,2,3)，若把编号为 0 的玩偶买 4 个（即全买了），然后编号为 3 的玩偶买一个，则刚好把 10元全部花完，且总价值为 13。可以证明没有更优的方案了。

注意买某种玩偶不一定要买光。

【数据规模与约定】

10%数据满足 1 ≤ n ≤ 10；

另 20%数据满足 1 ≤ n ≤ 100, ci = 1, 1 ≤ q ≤ 100；

另 20%数据满足 1 ≤ n ≤ 100, 1 ≤ q ≤ 100；

另 30%数据满足 ci = 1；

100%数据满足 1 ≤ n ≤ 1000, 1 ≤ q ≤ 3*105,1 ≤ ai、bi、ci ≤ 100, 0 ≤ di < n, 0 ≤ ei ≤ 1000。

为什么一开始要贴题目呢？因为这道题原来bzoj上面有，现在被他们封权限了，要交钱才能看。so，以后看方便（bzoj丧心病狂，原来的良心呢?)
贴这道题主要是因为几点启示：
1.一定要注意空间的问题，并且c++ 如果开小了有可能不会re。。坑！
2.看到如此的询问，直接考虑预处理吧。这道题利用只有一个物品会被ban掉，所以就预处理出1-i，容量为j的最大价值和i-n，容量为j的最大价值。注意这里是可以递推的。f[i][j] = f[i-1][j] 然后在在现在的i物品上dp，减少计算量。不减少——手测比暴力还低。。。
3.注意编号问题！

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 int n,q;

 int num[],w[],v[];

 int f[][];

 int g[][];

 int main()

 {

     freopen("bag.in","r",stdin);

     freopen("bag.out","w",stdout);

     scanf("%d",&n);

     memset(f,,sizeof(f));

     memset(g,,sizeof(g));

     memset(num,,sizeof(num));

     memset(w,,sizeof(w));

     memset(v,,sizeof(v));

     for(int i = ; i <= n; i++)

         scanf("%d%d%d",&w[i],&v[i],&num[i]);

     for(int i = ; i <= n; i++)

     {

         for(int j = ; j <= ; j++)

             f[i][j] = f[i-][j];

         for(int k = ;k <= num[i];k++)

             for(int t = ;t >= ; t--)

                 if(t >= w[i]) f[i][t] = max(f[i][t],f[i][t-w[i]]+v[i]);

     }

     for(int i = n;i >;i--)

     {

         for(int j = ; j <= ; j++)

             g[i][j] = g[i+][j];

         for(int k = ; k <= num[i];k++)

             for(int t = ; t >= ; t--)

                 if(t >= w[i]) g[i][t] = max(g[i][t],g[i][t-w[i]]+v[i]);

     }

     scanf("%d",&q);

     while(q--)

     {

         int t,mark;

         scanf("%d%d",&mark,&t);

         mark ++;

         if(mark == ) printf("%d\n",g[][t]);

         else if(mark == n) printf("%d\n",f[n-][t]);

         else{

             int ans = ;

             for(int j = ; j <= t;j++)

                 ans = max(ans,f[mark-][j]+g[mark+][t-j]);

             printf("%d\n",ans);

         }

     }

     return ;

 }

bag

bzoj 刷题路

首先跪拜hja。
跪毕，起身说正事。今天我竟然调了一个早上的1001，然后又调了一个晚上的1002，我是不是没救了。。
第一道题，就是某周大神在2007还是08年的的某ppt中的最大最小定理解析，其中提到了s-t平面图用对偶图的方法来做，不过原理我不怎么太懂，也就是不会推导，所以只能是比较弱的记录下来。根据Symon Yang的说法，这种题的图都相当的规整，所以对于对偶面的确定一般比较简单。不过既然在标号上降低难度，那么点基本都是10^6级的了，so，想到用对偶图的边来表示割，然后跑一遍spfa或dijkstra+heap就可以了。不过由于对自己的dijkstra毫无信心，所以我还是spfa算了。那么有什么注意的呢？那就是慢慢推导编号，不要捉急，慢慢来。还有如果是spfa要开一个循环队列，只需要在下标那里mod一个点数就好。（为什么是点数呢？因为如果开小了那么又可能前面的某些没有出列的元素被覆盖掉了，导致算法出错（我会告诉你我调了一个小时吗?)其余倒没什么了。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 int n,m;

 int heng[][],shu[][],xie[][];

 struct edge{

     int t,d;

     edge* next;

 }e[],*head[];

 int ne = ;

 void addedge(int f,int t,int d)

 {

     e[ne].t = t,e[ne].d = d;

     e[ne].next = head[f];

     head[f] = e + ne++;

     e[ne].t = f,e[ne].d = d;

     e[ne].next = head[t];

     head[t] = e + ne++;

 }

 int s,t;

 int dis[];

 bool in[];

 int q[];

 int l,r;

 int spfa(int s,int t)

 {

     int ql=;

     memset(dis,0x3f3f3f3f,sizeof(dis));

     memset(in,false,sizeof(in));

     memset(q,,sizeof(q));

     in[s] = true;

     l = , r = ;

     q[r++ % ql] = s;

     dis[s] = ;

     while(l < r)

     {

         int now = q[l++ % ql];

         in[now] = false;

         for(edge* p = head[now];p;p = p->next)

             if(dis[p->t] > dis[now] + p->d){

                 dis[p->t] = dis[now] + p->d;

                 if(in[p->t] == false) {

                     q[r++ % ql] = p->t,in[p->t] = true;

                 }

             }

     }

     return dis[t];

 }

 int main()

 {

     freopen("cs.in","r",stdin);

     memset(heng,,sizeof(heng));

     memset(shu,,sizeof(shu));

     memset(head,NULL,sizeof(head));

     scanf("%d%d",&n,&m);

     if( n ==  || m == )

     {

         int k  = max(n,m);

         int ans = 0x3f3f3f3f;

         for(int i = ; i < k; i++)

         {

             int x;

             scanf("%d",&x);

             ans = min(ans,x);

         }

         printf("%d",ans);

         return ;

     }

     for(int i = ;i <= n; i++)

         for(int j = ; j < m; j++)

             scanf("%d",&heng[i][j]);

     for(int i = ; i <= n-;i++)

         for(int j = ; j <= m; j++)

             scanf("%d",&shu[i][j]);

     for(int i = ; i <= n-;i++)

         for(int j = ; j <= m-;j++)

             scanf("%d",&xie[i][j]);

     s = ;

     t = n*(m-) + m*(n-) + (m-)*(n-) - n * m + ;

     for(int  i = ; i <= n; i++)

         for(int j = ;j < m; j++)

         {

             if(i == ){addedge(t,(i-)*(m-)*+j*,heng[i][j]);}

             else if( i == n) {addedge((i-)*(m-)*+j*-,s,heng[i][j]);}

             else addedge((i-)*(m-)*+j*,(i-)*(m-)*+j*-,heng[i][j]);

         }

     for(int i = ; i < n; i++)

         for(int j = ; j <= m; j++)

         {

             if(j == ){addedge(s,(i-)*(m-)*+(j-)*+,shu[i][j]);}

             else if( j == m){addedge(t,(i-)*(m-)*+(j-)*,shu[i][j]);}

             else addedge((i-)*(m-)*+(j-)*,(i-)*(m-)*+(j-)*+,shu[i][j]);

         }

     for(int i = ; i < n; i++)

         for(int j = ; j < m;j++)

             addedge((i-)*(m-)*+(j-)*+,(i-)*(m-)*+j*,xie[i][j]);

     printf("%d\n",spfa(s,t));

     return ;

 }

注意数组一定不要开小了，我re了7次还是8次。。。

还有就是1002这道神题。这道题第一要知道递推式，然后还要写高精。像这种找规律我一般都跪了。。不过这个题找递推式的正确方法是基尔霍夫矩阵来求，有时间再探讨好了，我还是不要作死了，no zuo no die。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n;

 int a[];

 int b[];

 int len1, len2;

 void cal()

 {

     int temp[];

     memset(temp,,sizeof(temp));

     int len = ;

     for(int i = ; i < len1;i++)

     {

         temp[i] += a[i]*;

         temp[i+] += temp[i]/;

         temp[i] = temp[i]%;

     }

     if(temp[len1] != ) len = len1 + ;

     else len = len1;

     for(int i = ; i < min(len,len2);i++)

     {

         if(temp[i] < b[i]) temp[i+]--,temp[i]+= ;

         temp[i] = temp[i] - b[i];

     }

     if(temp[len-] == ) len--;

     temp[] += ;

     int now = ;

     while(temp[now] >= ){temp[now+] += , now++;temp[now-] %= ;}

     if(now == len) len++;

     int t[];

     for(int i = ; i < len1;i++)

         t[i] = a[i];

     for(int i = ; i < len;i++)

         a[i] = temp[i];

     for(int i = ; i < len1;i++)

         b[i] = t[i];

     len2 = len1;

     len1 = len;

 }

 int main()

 {

     scanf("%d",&n);

     a[] = ;

     b[] = ;

     len1 = ;

     len2 = ;

     for(int i = ; i <= n;i++)

         cal();

     for(int i = len1 - ; i >= ; i--)

         printf("%d",a[i]);

 }

高精真是写死人。。要不是省选只能用c，c++，pascal果断python，java(其实主要我不会java和python = =b。。。）
不过张老师给我说了一个dp：
对于第i个点，然后进行分割，相当于这一状态的某种情况是由某两种已知的情况拼出来的。。。。只能说。。我明天再去问问。。
再跪hja！

巴特西

【集合！】 20140416 && 20140417集训总结

最新文章

热门文章

巴特西

【集合！】 20140416 && 20140417集训 总结

最新文章

热门文章

【集合！】 20140416 && 20140417集训总结