 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
POJ Contest算法简介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
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
