[TopCoder] SRM370 Div2

发表评论73次阅读2007.10.10 9:07 作者：Felicia　编辑

[阅读更多]

这是我第一次做SRM
比赛之前先下了一个插件，装上，感觉还不错。250分的题很简单，仔细想一下就知道只要把第一个数组相加，减去第二个数组相加即可。但我比较笨，直接按照题目意思模拟，写得慢了，又不习惯环境，最后交的时候才197分，垃圾。500分的题也很简单，是Div1的250分题。只需要按照样例3的描述暴力搞即可。交了个442分的。1000分的题是个DP，一开始状态想错了，写了一会儿发现不妙，赶紧修改状态，然后越改越乱，就没心情写了……最后没交。Challenge的时候我心情很差，就看了几个代码，也不想cha他们。然后就是等System Test，等他完了我的寝室就要关门了……所以就直接回去了。
今天起来看一下Rating，发现有1300+，还是蓝名，不错。又看Summary，是Room第4。
Sherlock和Lzx也做了这个比赛。

标签, | 日志分类：Topcoder SRM

[动态规划] pku1338 技巧

发表评论1次阅读2007.10.09 21:53 作者：Felicia　编辑

[阅读更多]

非常经典的递推计算。基本思想是设3个指针，分别表示3个素数乘到哪了，然后通过比较3个指针位置的递推结果来确定下一个数是什么。
具体实现见代码。

下面是我的代码

下载: pku1338.cpp
#include <stdio.h>
int u[2000],i,n,p2,p3,p5;
int main() {
    p2=p3=p5=u[1]=1;
    for (i=2;i<=1500;i++) {
        if (u[p2]*2<u[p3]*3 && u[p2]*2<u[p5]*5) u[i]=u[p2++]*2;
        else if (u[p3]*3<u[p2]*2 && u[p3]*3<u[p5]*5) u[i]=u[p3++]*3;
        else if (u[p5]*5<u[p2]*2 && u[p5]*5<u[p3]*3) u[i]=u[p5++]*5;
        else if (u[p2]*2==u[p3]*3 && u[p2]*2<u[p5]*5) u[i]=u[p2++]*2,p3++;
        else if (u[p2]*2==u[p5]*5 && u[p2]*2<u[p3]*3) u[i]=u[p2++]*2,p5++;
        else if (u[p3]*3==u[p5]*5 && u[p3]*3<u[p2]*2) u[i]=u[p3++]*3,p5++;
        else if (u[p2]*2==u[p3]*3 && u[p3]*3==u[p5]*5) u[i]=u[p2++]*2,p3++,p5++;
    }
    while (scanf("%d",&n),n!=0) printf("%d\n",u[n]);
    return 0;
}
标签, | 日志分类：动态规划

[动态规划] pku3420 状态压缩+快速矩阵乘法

发表评论91次阅读2007.10.08 9:19 作者：Felicia　编辑

[阅读更多]

经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有231。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。

下面是我的代码

下载: pku3420.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-6 11:05:55
File Name: pku3420.cpp
Description:
**********************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
 
int g[16][16];
int M;
 
void dfs(int old_state, int now, int new_state)
{
    if (now > 3)
    {
        g[old_state][new_state]++;
        return;
    }
    if (old_state & (1 << now))
        dfs(old_state, now + 1, new_state);
    if (now <= 2)
    {
        if ((old_state & (1 << now)) == 0 && (old_state & (1 << (now + 1))) == 0)
            dfs(old_state, now + 2, new_state);
    }
    if ((old_state & (1 << now)) == 0)
        dfs(old_state, now + 1, new_state | (1 << now));
}
 
void mul(int a[16][16], int b[16][16], int c[16][16])
{
    for (int i = 0; i < 16; i++)
        for (int j = 0; j < 16; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < 16; k++)
                c[i][j] += a[i][k] * b[k][j];
            c[i][j] %= M;
        }
}
 
int calc(int n)
{
    int p[16][16];
    memcpy(p, g, sizeof(p));
    
    int ans[16][16], tmp[16][16];
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i < 16; i++)
        ans[i][i] = 1;
 
    while (n)
    {
        if (n & 1)
        {
            mul(ans, p, tmp);
            memcpy(ans, tmp, sizeof(tmp));
        }
        n >>= 1;
        mul(p, p, tmp);
        memcpy(p, tmp, sizeof(tmp));
    }
    return ans[0][0];
}
 
int main()
{
    memset(g, 0, sizeof(g));
    for (int i = 0; i < 16; i++)
        dfs(i, 0, 0);
    
    int n;
    while (scanf("%d%d", &n, &M), n + M != 0)
    {
        printf("%d\n", calc(n));
    }
    return 0;
}
标签, | 日志分类：动态规划

[动态规划] pku1191 三维DP

发表评论22次阅读2007.10.08 9:12 作者：Felicia　编辑

[阅读更多]

不错的DP题。状态f[i][x1][y1][x2][y2]表示要把(x1,y1) — (x2, y2) 分割成i块所得到的最小平方和（平方和指的是每块矩形的和的平方和）。然后根据水平和竖直切割进行状态转移。这样计算出f[n][1][1][8][8]得到整个棋盘分割成n块得到的最小平方和，然后代入均方差公式算得结果。

下面是我的代码

下载: pku1191.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-1 19:01:11
File Name: pku1191.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
 
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
 
int n;
int a[9][9], g[9][9];
int f[16][9][9][9][9];
 
inline int sum(int x1, int y1, int x2, int y2)
{
    return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1])
        * (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
}
 
int dp(int k, int x1, int y1, int x2, int y2)
{
    if (f[k][x1][y1][x2][y2] != maxint)
        return f[k][x1][y1][x2][y2];
    if (k == 1)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    if (x1 == x2 && y1 == y2)
        return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
    int ret = maxint;
    for (int i = x1; i < x2; i++)
    {
        ret <?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
        ret <?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
    }
    for (int i = y1; i < y2; i++)
    {
        ret <?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
        ret <?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
    }
    return f[k][x1][y1][x2][y2] = ret;
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            scanf("%d", &a[i][j]);
    memset(g, 0, sizeof(g));
 
    for (int i = 0; i <= 8; i++)
        for (int j = 0; j <= 8; j++)
            g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + a[i][j];
    
    for (int k = 0; k <= 15; k++)
        for (int x1 = 1; x1 <= 8; x1++)
            for (int y1 = 1; y1 <= 8; y1++)
                for (int x2 = 1; x2 <= 8; x2++)
                    for (int y2 = 1; y2 <= 8; y2++)
                        f[k][x1][y1][x2][y2] = maxint;
    
    double sum = 0.0;
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            sum += a[i][j];
    sum /= n;
    sum *= sum;
 
    printf("%.3lf\n", sqrt(dp(n, 1, 1, 8, 8) / double(n) - sum));
    return 0;
}
标签, | 日志分类：动态规划

[图论] pku3417 树上的统计

1个评论42次阅读2007.10.06 20:53 作者：Felicia　编辑

[阅读更多]

我的做法是，对于每条新边，记录树中与之对应的路径。然后对于每条树边，统计被对应的次数。最后记录每个点到树根的路径上，有多少个1（设为q[i]）。对于新边(x,y)，它对答案的贡献就是q[x] + q[y] – 2q[lca(x,y)]。除了这些，答案还应加上树中0边的数量 * m。

下面是我的代码

下载: pku3417.cpp
/**********************************************************************
Author: WHU_GCC
Created Time: 2007-10-6 12:45:53
File Name: pku3417.cpp
Description:
**********************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
 
const int maxn = 100010;
 
struct node_t
{
    int father;
    int value;
    int pre;
};
 
struct tmp_t
{
    int v;
    tmp_t *next;
};
 
int n, m;
node_t p[maxn];
tmp_t *u[maxn];
int edge_u[maxn];
int edge_v[maxn];
int edge_lca[maxn];
int *d[20][200010];
int euler[maxn * 2];
int a[maxn * 2];
int high[maxn];
int stt[maxn];
int tim;
int *mmin(int *a, int *b)
{
    if (*a < *b)
        return a;
    return b;
}
void make_rmq(int n)
{
    int i, j;
    for (i = 1; i <= n; i++)
         d[0][i] = &a[i];
    for (j = 1; j <= log((double)n) / log (2.0);j++)
        for (i = 1; i + (1 << j) - 1 <= n; i++)
            d[j][i] = mmin (d[j - 1][i], d[j - 1][i + (1 << (j - 1))]);
}
int *rmq(int i,int j)
{
    if (i > j)
        swap (i, j);
    int k = (int)(log (j - i + 1.) / log (2.0));
    return mmin (d[k][i], d[k][j - (1 << k) + 1]);
}
void mmd (int f, int v, int h)
{
    euler[++tim] = v;
    high[v] = h;
    tmp_t *pt;
    for (pt = u[v]; pt; pt = pt->next)
        if (pt->v != f)
        {
            mmd (v, pt->v, h + 1);
            euler[++tim] = v;
        }
}
 
void build ()
{
    tim = 0;
    mmd (1, 1, 1);
    memset (stt, 0, sizeof (stt));
    int i;
    for (i = 1; i <= tim; ++i)
    {
        if (stt[euler[i]] == 0)
            stt[euler[i]] = i;
        a[i] = high[euler[i]];
    }
    make_rmq (tim);
}
int lca (int u, int v)
{
    return euler[rmq (stt[u], stt[v]) - a];
}
 
int f[maxn];
int g[maxn];
int q[maxn];
 
int dfs(int father, int now)
{
    int ret = 0;
    tmp_t *t;
    for (t = u[now]; t; t = t->next)
        if (t->v != father)
            ret += dfs(now, t->v);
    return g[now] = ret + f[now];
}
 
void dfs1(int father, int now, int sum)
{
    q[now] = sum + (g[now] == 1);
    tmp_t *t;
    for (t = u[now]; t; t = t->next)
        if (t->v != father)
            dfs1(now, t->v, sum + (g[now] == 1));
}
 
int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        memset(u, 0, sizeof(u));
        int i;
        for (i = 0; i < n - 1; i++)
        {
            int t1, t2;
            scanf("%d%d", &t1, &t2);
            tmp_t *p = new tmp_t;
            p->v = t2;
            p->next = u[t1];
            u[t1] = p;
            
            p = new tmp_t;
            p->v = t1;
            p->next = u[t2];
            u[t2] = p;
        }
        memset(p, 0, sizeof(p));
        for (i = 1; i <= n; i++)
            p[i].pre = i;
        build();
        memset(f, 0, sizeof(f));
        for (i = 0; i < m; i++)
        {
            int t1, t2;
            scanf("%d%d", &t1, &t2);
            edge_u[i] = t1;
            edge_v[i] = t2;
            int t = lca(t1, t2);
            edge_lca[i] = t;
            f[t1]++;
            f[t2]++;
            f[t] -= 2;
        }
        memset(g, 0, sizeof(g));
        dfs(1, 1);
        memset(q, 0, sizeof(q));
        dfs1(1, 1, 0);
        int sum = 0;
        for (i = 2; i <= n; i++)
            if (g[i] == 0)
                sum++;
        int ans = 0;
        for (i = 0; i < m; i++)
            ans += q[edge_u[i]] + q[edge_v[i]] - 2 * q[edge_lca[i]];
        printf("%d\n", ans + sum * m);
    }
    return 0;
}
标签, | 日志分类：图论
« Older Entries
Newer Entries »