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

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)

posts - 224, comments - 694, trackbacks - 0, articles - 6

re: SRM388 oyjpart 2008-01-17 23:08

恩，我的意思是表面上看起来是2^n*2^k次而不知最终的复杂度，最好是通过均摊分析的思想来得知是3^n的复杂度。呵呵~~ :) 加油考研哦~

re: JAVA常用设计模式2 MVC [ Model-View-Controller ] oyjpart 2008-01-17 18:52

呃...

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: pku1769 新写的线段树(点树)模版 oyjpart 2007-12-05 11:47

给定一个线段集，要求选择其中一个最小的子集来覆盖整个区域。
要求选定的子集是按照题目给的序来覆盖。

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

恩呵呵
记得一起溜冰的时候呵呵

喝酒也好

re: 我的金山我来书写[未登录] oyjpArt 2007-10-27 22:44

枚举的带宽实际上是有限制的，也就是说只需要枚举数据中给出的带宽（100＊100）个就可以了。然后每个机器都选择在这个带宽之上的最小费用。也就是枚举之后每个机器需要遍历厂商一次，所以总复杂度是100＊100＊100＊100，的却会超时。但是可以对上述算法做一些简单的优化。就是说，枚举带宽的时候，其实要保证带宽对于每个机器都是又相应的厂商的，也就是说如果枚举之前可以先去掉相当多不需要枚举的带宽。也就是说每句的带宽的下界变成了每个机器在不同厂商下的最小带宽的最大带宽，上界也有类似的变化。这个时间复杂度下的却可能超时，不过你可以试验下这个优化的效果。

re: 我的金山我来书写[未登录] oyjpArt 2007-10-27 19:44

你可以枚举那个Mininum 带宽然后把其他的排序选择比较小的呵呵
如果需要代码我可以发邮件给你

re: Psytopic性格测试+职业导向 oyjpart 2007-10-22 09:54

点链接阿

re: HNU contest oyjpart 2007-10-12 20:27

....这题不是我做的...alpc117

re: 2007年度ACM/ICPC World Final 排名 oyjpart 2007-10-07 22:59

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-09-03 23:23

豪兄好猛阿哈哈

re: 再说几道题 oyjpart 2007-08-28 09:09

一共有11个珠子用11个2进制位来表示是否已经加入到当前的串中，即供需要2^11 = 2048来表示

re: 计算几何入门题（更新中……） oyjpart 2007-08-23 11:37

凸包的o(n^2)算法，即卷包心菜。
哈哈
太有创意了。。。

re: 说几道题目 oyjpart 2007-08-22 20:56

哦 wy大牛啊~

re: 动态规划题集锦 oyjpart 2007-08-22 17:32

LSM太猛了！
呵呵
赞~

re: PKU1037 A decorative fence DP+分段统计 oyjpart 2007-08-19 11:05

恩是的