oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
共4页: 1 2 3 4 
re: SRM388 oyjpart 2008-01-17 23:08
恩,我的意思是表面上看起来是2^n*2^k次而不知最终的复杂度,最好是通过均摊分析的思想来得知是3^n的复杂度。呵呵~~ :) 加油考研哦~
re: 闲来切题 呵呵 oyjpart 2008-01-07 17:53
贴下代码,可能容易理解些~
#include <algorithm>
using namespace std;
const int N = 10010;
int x[N], y[N];

int main() {
//freopen("t.in", "r", stdin);
int n, i;
scanf("%d", &n);
for(i = 0; i< n; i++)
scanf("%d%d", &x[i], &y[i]);
sort(x, x+n);
sort(y, y+n);
for(i = 0; i<n; i++)
x[i] -= i;
sort(x, x+n);
int ans = 0;
for(i = 0; i <n; i++)
ans += abs(x[i] - x[n/2]) + abs(y[i] - y[n/2]);
printf("%d\n", ans);
return 0;
}
re: SRM382 晕头转向 oyjpart 2008-01-06 15:45
...记错了...不好意思...
re: 一诀成都,金牌! oyjpart 2007-12-12 12:39
ACM-ICPC比赛介绍

ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest – ACM-ICPC)由国际计算机学界著名的ACM学会(Association for Computer Machinery)主办,是世界上规模最大、水平最高的国际大学生程序竞赛。每年举办一次。ACM成立于计算机诞生次年,是目前计算机学界中历史最悠久、最具权威性的组织。
re: 一诀成都,金牌! oyjpart 2007-12-11 11:51
恩 好的
re: Too Late to Apologize[未登录] oyjpArt 2007-12-09 23:10

已更正,THX
给定一个线段集,要求选择其中一个最小的子集来覆盖整个区域。
要求选定的子集是按照题目给的序来覆盖。
re: 说题~[未登录] oyjpArt 2007-11-16 19:50
29void solve() {
30 int beg = 0, end = 0, i, j, k;
31 for(i = 1; i < nA; ++i) {
32 if(A[i].w != A[i-1].w) { //某一个相同w的段
33 for(j = beg; j <= end; ++j) //段的开始何结束的2重枚举
34 for(k = j+1; k <= end; ++k)
35 if((A[j].mask&A[k].mask) == 0) //如果没有相同的数
36 cnt[A[j].mask|A[k].mask]++; //计数器增加
37 beg = end = i;
38 }
39 else
40 end = i;
41 }
42 int ans = 0;
43 for(i = 0; i < two(16); ++i) {
44 if(cnt[i] != 0 && cnt[(two(16)-1)^i] != 0) //如果某些数字的集合的计数>0 并且他的补集也>0,就是都用上了
45 ans += cnt[i] * cnt[(two(16)-1)^i];
46 }
47 printf("%d\n", ans/2);
48}
re: 我有一只小颖睿 oyjpart 2007-11-15 00:40
you guessed it!~
re: 说题~ oyjpart 2007-11-11 23:19
请问你的24是什么?
还有你的循环是43680*43680*24*24的,不出意外的话就超时了:)
re: 说题~ oyjpart 2007-11-11 13:17
那你觉得怎么写呢?
re: 被点名了~ oyjpart 2007-11-04 00:19
恩 呵呵
记得一起溜冰的时候 呵呵

喝酒也好
枚举的带宽实际上是有限制的,也就是说只需要枚举数据中给出的带宽(100*100)个就可以了。然后每个机器都选择在这个带宽之上的最小费用。也就是枚举之后每个机器需要遍历厂商一次,所以总复杂度是100*100*100*100,的却会超时。但是可以对上述算法做一些简单的优化。就是说,枚举带宽的时候,其实要保证带宽对于每个机器都是又相应的厂商的,也就是说如果枚举之前可以先去掉相当多不需要枚举的带宽。也就是说每句的带宽的下界变成了每个机器在不同厂商下的最小带宽的最大带宽,上界也有类似的变化。这个时间复杂度下的却可能超时,不过你可以试验下这个优化的效果。
你可以枚举那个Mininum 带宽 然后把其他的排序 选择比较小的 呵呵
如果需要代码我可以发邮件给你
re: Psytopic性格测试+职业导向 oyjpart 2007-10-22 09:54
点链接阿
re: HNU contest oyjpart 2007-10-12 20:27
....这题不是我做的...alpc117
solved problems
re: MCM2007 oyjpart 2007-09-28 01:45
byron还参加了数模阿,真是全才,ACM,MCM,科研,还有学业,还有MM!
re: 肖申克的救赎 oyjpart 2007-09-07 19:45
Thanks.
re: 再说几道题[未登录] oyjpArt 2007-09-03 23:29
不好意思 没说清楚
dp[2048][8][8]中的第一维是代表当前那些珠子已经加入到串中。
比如如果1,2,4颗珠子加入 则第一维为(00000001011)B
所谓加入 就是这颗珠子是否已经使用
后面2维分别代表连续的珠串中最左端和最右端的珠子是什么颜色的(一共8种颜色)
之所以这样设置DP 是因为在不断加入珠子的过程中始终成为一连串,而决定一个状态的只有左右两个珠子的颜色。所以这样设置DP之后就可以达到无后效性。
豪兄好猛阿 哈哈
re: 再说几道题 oyjpart 2007-08-28 09:09
一共有11个珠子 用11个2进制位来表示是否已经加入到当前的串中,即供需要2^11 = 2048来表示
凸包的o(n^2)算法,即卷包心菜。
哈哈
太有创意了。。。
re: 说几道题目 oyjpart 2007-08-22 20:56
哦 wy大牛啊~
re: 动态规划题集锦 oyjpart 2007-08-22 17:32
LSM太猛了!
呵呵
赞~
恩 是的
真的么?
那你怎么写的呢?
re: 扩展欧几里德有感 oyjpart 2007-08-15 10:08
哦 好的
就是因为凸多边形是凸的 所以如果你确定两点移第三点会出现先增后减
re: 推荐-好题(转贴) oyjpart 2007-08-12 16:13
Lsm全切了 哈哈!
re: 扩展欧几里德有感 oyjpart 2007-08-11 08:09
可以阿。呵呵 当然
re: pku3268 dij+heap oyjpart 2007-07-27 08:41
终于更新blog了。。。
是网络流中我们自己确定的2个特殊节点。
如果对网络流算法比较陌生 我觉得看一下相关书籍比较好 :)
呵呵 没事啦
re: PKU1733 URAL1003 Parity game oyjpart 2007-07-04 17:05
Yes :)
2283654 alpc12 1733 Accepted 416K 514MS G++ 1412B 2007-06-23 23:01:56

what's your test case?
re: 被点名了~ oyjpart 2007-06-30 11:39
晕 你是我的偶像啊...
re: 有一类程序员 oyjpart 2007-06-27 01:34
很多这种人啊 真讨厌
re: 家 oyjpart 2007-06-18 00:49
不知不觉已经是第一百篇随笔了~ 纪念一下
re: 发现自己土了 oyjpart 2007-06-12 16:00
哈哈 发现我更土
re: 自己太弱 要学的太多 oyjpart 2007-06-11 00:35
谢谢啊 呵呵
我的理解很粗浅哎 我觉得就是对于平面内离散的点集S
凸包就是S的一个子集S1形成的一个凸多边形 使所有的点都包含在这个凸包C或在C的边上
为什么是速度最快呢?
re: 真理只有一个 oyjpart 2007-06-05 12:34
谢谢。。。
呵呵!~~
re: 蓝人 oyjpart 2007-06-04 13:55
呵呵~~
原来真的如此
re: 2900 不灭的回忆 oyjpart 2007-05-29 00:58
RPWT...
哈哈
呵呵 确实好玩 不过我不是很懂。。呵呵~~
不管他 开静态的二维数组满足题目最大顶点数即可
如果题目没有说明而且你熟悉stl的话 你就用二维vector
共4页: 1 2 3 4