● 8.4@pku的LonTianCheng比赛的详细分析 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: ACMICPC
标  题: 8.4@pku的LonTianCheng比赛的详细分析
发信站: 荔园晨风BBS站 (Thu Aug  5 17:40:05 2004), 站内信件

A:Connected Graph
算法：数学方法(反演)+动态规划
详细介绍：集合划分在加细关系下是一个格。
时间复杂度：O(N^3*K^2)-K为高精度系数
//当然用table很容易，我的数据就是1-50。
相信肯定存在更好的算法，由于本题过的人很多，这里就不具体介绍
难度：简单
第一个通过：136638 zwdant A Accepted     C++   2004-08-04 13:01:43

B:An Old Stone Game
算法：贪心(经典问题)，开始N个圆物品，每次合并两个和最小的且中间没有圆形

物品的物品，变成一个方的物品。
详细介绍：本题我想到4种比较好的数据结构：
          (1)fib堆 O(NLogN)
          (2)二项堆 O(NLogN)
          (3)左偏树 O(NLogN)
          (4)普通堆+启发式合并 O(N(LogN)^2)
        编程复杂度从难到易为(1)(2)(3)(4)，出题者实现了(2)(3)(4)三种方法

，程序运行速度从快到慢为(3)(2)(4)
//单纯的贪心肯定是有问题的，例如N=4,个数分别为：5,3,4,5。
时间复杂度：O(NLogN)
难度：有一定难度
没有人通过。

C:Tony's Tour
算法：带集合的动态规划
详细介绍：使用Hash表和一些预处理可以大大提高程序效率。
//本题和hnoi04-day1的一题很像，但是有障碍，复杂一些。而且搜索很难通过。

时间复杂度：O(M!*N)
难度：有一定难度
没有人通过。

D:A New Stone Game
算法：博弈问题
详细介绍：本题和xor没有任何关系，通过猜想或者推导可以得到一个很简单的平

衡状态：每种个数的石子堆出现的次数都是偶数。
时间复杂度：O(N)
难度：简单
第一个通过：136624 lin D Accepted     C++   2004-08-04 12:58:21

E:Tree
算法：二分
详细介绍：对于一个树，去掉一个结点，最分散的每颗子树分别求解，然后用
O(NLogN)的方法合并结果。
时间复杂度：O(N(LogN)^2)，用基数排序可以做到O(NLogN)
//此题的时间比较紧，用pascal比较吃亏，但是第一个通过的是用pascal的。
难度：中等
第一个通过：137783 geworm E Accepted     Pascal   2004-08-04 16:46:18

F:Coins
算法：动态规划
详细介绍：一道类似的问题在WinterCamp2004上考虑过。
          我提出了一种合并Coins的方法，例如：15个1和1,2,4,8是等价的。时

间复杂度是O(N*M*LogC/32)。
          还有ysy的方法。时间复杂度是O(N*M)。
时间复杂度：O(N*M*LogC/32)或O(N*M)
//O(N*M)如果写得好是可以通过的。
//此题的时间比较紧，用pascal很吃亏，但是第一个通过的也是用pascal的。曾经

把时限放到5s，很多人都AC了，然后又缩短到3s，几乎又都超时了。其实用C，时

间是很宽松的。
难度：有一定难度
第一个通过：137156 hdfzhb F Accepted     Pascal   2004-08-04 15:11:42
*****************f.cpp*******************
#include <stdio.h>
#include <string.h>

const int maxn=100+10;
const int maxm=100000+10;

int n,m,a[maxn],c[maxn],size;
unsigned int f[maxm/32+1],t[maxm/32+1];
int countbit[65536];

void init()
{
        size=m/32;
        int i;
        for (i=1;i<=n;i++)
                scanf("%d",&a[i]);
        for (i=1;i<=n;i++)
                scanf("%d",&c[i]);
}
void addnode(int v)
{
        int v1=v/32;
        int v2=v%32;
        int i,m2=32-v2;
        memcpy(t,f,(size+1)*sizeof(int));
        for (i=v1;i<=size;i++)
                f[i]|=(t[i-v1]<<v2);
        if (v2>0)
                for (i=(++v1);i<=size;i++)
                        f[i]|=(t[i-v1]>>m2);
}
void solve()
{
        int i,t,answer=-1;
        memset(f,0,(size+1)*sizeof(int));
        f[0]=1;
        for (i=1;i<=n;i++)
        {
                for (t=1;t<c[i];c[i]-=t,t*=2)
                        addnode(a[i]*t);
                addnode(a[i]*c[i]);
        }
        for (i=0;i<size;i++)
                answer+=countbit[f[i]/65536]+countbit[f[i]%65536];
        for (i=0;i<=m%32;i++)
                answer+=(f[size]>>i)%2;
        printf("%d\n",answer);
}
int main()
{
        countbit[0]=0;
        for (int i=1;i<65536;i++)
                countbit[i]=1+countbit[i-((i^(i-1))&i)];
        while (scanf("%d%d",&n,&m)!=-1)
        {
                if (n==0)
                        break;
                init();
                solve();
        }
        return 0;
}
*****************************************

G:Musical Theme
算法：后缀树+并查集
详细介绍：本题源于USACO1.5.6的一题，标准算法是O(N^2)的，实在比较慢。
          先令B[i]=A[i+1]-A[i]，这样求B的最长重复串L，但是要求开始位置距

离在L以上。将所有后缀排序之后，利用LCP的性质容易想到算法。
          另外用后缀数组实现可以降低编程复杂度，但时间复杂度为O(NLogN)。

时间复杂度：O(N)
难度：中等
第一个通过：137433 ijk G Accepted     C++   2004-08-04 16:13:53

H:Elevator Stopping Plan
算法：二分+贪心
详细介绍：本题源于ACM广州赛区的一题，标准算法是O(N^4)的，实在太慢。
          先二分答案，然后其实只要把电梯尽可能往上开就可以了，实现非常简单。
时间复杂度：O(N*Log(30000*20))=O(N)
//很多人都有ACM广州赛区的数据，使得本题的正确率比较高。
难度：简单
第一个通过：136541 Aladdin H Accepted     C++(GCC)   2004-08-04 12:34:
04

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

--
※ 修改:·huhaiming 於 Aug  5 18:01:00 修改本文·[FROM: 210.21.224.234]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.21.224.234]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店