[转载] 2007南京赛区总结 by mmd

发表评论14次阅读2007.10.28 23:36 作者：Felicia　编辑

[阅读更多]

这是我们队的mmd写的总结，发布在珞珈山水bbs上，转载过来。


今天我们做的并不是很顺利，前面出题太慢，我状态不是很好，导致罚时也比较多。

拿到题目，我们三个人都有点晕。觉得题目有点难。三个人的身体状况也并不是很好，都
有点小感冒，cz还在发烧， 我鼻子不通气。不过我们的心态还都不错。
我们在把题目几乎看完之后，没有找到简单题。但是我一直觉得F是一个可以水的题目。在
跟feli商量了几句之后，我去提交了F，在还没有返回结果的时候我就发现我交错了文件。
改之，得到了期望中的tle，然后我还知道一种要用到后缀数组的做法，不过太麻烦，所以
我在求速度的情况下，去提交了两个for循环，看看结果是tle还是wa，结果居然还是tle。
这时候我跟cz和feli他们俩个说，这是我已知的最好做法了，不可能有更快的，肯定有别
的问题。先放一下这道题。

这个时候cz跟我说j题是一个比较麻烦的搜索，让我想一下可不可以做，我按cz的思路想了
一下，觉得处理起来比较麻烦，所以我们两个决定先放一下，这时候feli看了一下board，
然后发现已经有两个队伍ac了j题。我们三个于是意识到了我们想复杂了，还好feli马上想
到是一个简单的dp，他去写这题。交上去之后，回来一个wa，feli想了一下，发现是题意
理解错误，改之，得到了第一个ac。

这个时候已经一个多小时了，而且很明显我们的成绩不是特别好。不过我们倒也没觉得什
么，因为平时比赛我们队就总会出现这种情况。罚时比较多，出题比较慢。

cz在看了f题之后，跟我说了f题的trie树做法，这时我才想到我想的做法，全想反了，所
以才会得出来此题非常难的结论。由于手头也没有trie树的模版，我也就只能硬着头皮现
写了，所以这个题出的比较慢，中间还差点写头晕，总感觉写的有问题。还好算是ac了。


此时我们二题，要出第三道题的话，就只有出g题了。g题是一个经典题，题目就是求最长
重复子串，但是题目里面并没有说明子串是不是可以重叠的。苦于，我没有带后缀数组的
论文，所以里面最关键的一部分求h函数，我忘记是怎么求的了，这才是最郁闷的，比赛之
前我还在那里念叨忘记带论文。我在那里郁闷的推了半天，推出来的时候交上去ac了。虽
然此时我们三题，但是时间比较靠后。

此时我们三个人都没有题做，然后我们大体商量了一下，我们决定放弃其它题，去做a和d
。
我和cz去做a，feli和cz去做d。
结果证明这并不是一个不太明智的选择，因为最后a和d也就才三四支队过。而i题有十几支
队伍ac，我们却连想都没有想。
i题数据太弱，如果数据强的话，是一个我们比赛之前就讨论过了非常经典的难题（最小外
接圆），队内没人会做。我们完全没有往数据太弱那方面想。事实上可以通过凸包+枚举a
c。郁闷的是天大他们就是这样ac了，而且因为罚时比较少，所以在我们前面。

feli在比赛还剩50分钟的时候，rp暴发把d题ac了。我们就这样四题了，剩下50分钟，他们
把时间全放在了我写的a上面，不过我状态比较差，一直wa到最后。此时board已经封掉了
，在还剩20分钟的时候feli无聊去看了一下气球，说只有6支队伍过了四题。

其实在很早的时候，cz就已经把h题的贪心想好了，但是他觉得没有完全证明，所以没有敢
去写这个题。我觉得这也是比赛失败的地方之一，华科他们就是贪心过掉了，我觉得cz也
肯定可以ac，因为这类的题，他赛前做过非常多的研究。

整体上来说，我们最后成绩虽然不差，但是比赛的遗憾还是非常多的，我相信我们在下一
站的吉林可以做的更好。

标签 | 日志分类：ACM/ICPC纪事, 转载

The 2007 ACM Asia Programming Contest – Nanjing Final Score Board

发表评论9次阅读2007.10.28 23:33 作者：Felicia　编辑

[阅读更多]

The 2007 ACM Asia Programming Contest – Nanjing
Final Score Board

RankNameSolvedTimeABCDEFGHIJTotal att/solv
1Shanghai Jiao Tong University Prime512774/2400/–3/–6/–0/–2/1315/2840/–6/2902/5228/5
2Fudan University Amethyst43491/–1/–2/–0/–0/–1/1211/522/–2/502/8612/4
3Tsinghua University Himalaya Dragoons45018/–3/–2/–12/–0/–1/963/820/–3/1673/3635/4
4Tianjin University Tju_Wizard45072/–0/–3/–0/–0/–1/1092/460/–1/2631/6910/4
5National University of Defense Technology Glory.h46812/–0/–0/–4/–0/–3/1891/1250/–2/2401/6713/4
6Wuhan University gcc47435/–0/–0/–3/2510/–6/1161/1450/–0/–2/7117/4
7East China Normal University ecnu_LSP47870/–0/–6/–0/–0/–1/1192/2600/–1/2931/9511/4
8Zhongshan(Sun Yat-sen) University ZSU_Megrez48581/–6/–0/–1/–0/–9/1961/1180/–4/2272/7724/4
9Huazhong University of Science and Technology Sellihca48640/–0/–0/–0/–0/–1/922/641/2390/–9/28913/4
10Changzhou Middle School jiangsu1411590/–2/–0/–0/–0/–4/2946/2530/–5/2841/8818/4
11Fudan University Twinkling32581/941/–2/–0/–0/–1/1163/–0/–0/–1/489/3
12Nanjing University Eureka32740/–0/–0/–1/–0/–1/881/1412/–0/–1/456/3
13Tsinghua University Coldor32862/–3/–4/–0/–0/–1/782/1564/–6/–2/1224/3
14Beijing Jiaotong University BJTU00331711/–0/–0/–0/–0/–1/572/1250/–0/–1/11515/3
15JiLin University loon33704/–0/–3/–0/–0/–1/1202/860/–0/–1/14411/3
16Zhejiang University Fire-Winged Bird34084/–3/–3/–0/–0/–1/303/2976/–0/–1/4121/3
17Zhejiang University Othello34450/–3/–2/–1/–0/–1/1152/2103/–0/–4/4016/3
18Shanghai Jiao Tong University SJTU Approximation34461/–0/–1/–0/–0/–3/15710/–0/–1/2041/4517/3
19Zhejiang University of Technology AngryHair34485/–0/–0/–2/1420/–2/870/–0/–0/–1/17910/3
20Northwestern Polytechnical University NWPU_T135331/–0/–2/–0/–0/–2/2012/890/–0/–1/2038/3
21Hefei University of Technology Necromancer35360/–0/–0/–5/–0/–1/1991/1560/–4/–3/14114/3
22Southeast University FT235475/–0/–0/–0/–0/–2/2040/–0/–2/1721/13110/3
23Changzhou Middle Schooljiang su335732/–6/–2/–0/–0/–1/2073/2610/–4/–1/6519/3
24Taiwan University puyo35832/–0/–1/–0/–0/–2/25111/–4/1790/–1/7321/3
25Fudan University Prison Break36150/–0/–1/–0/–0/–5/2533/2061/–13/–1/3624/3
26JiLin University n2o36240/–0/–0/–0/–0/–7/2391/1560/–4/–2/8914/3
27Zhongshan(Sun Yat-sen) University ZSU_Phecda367710/–0/–0/–0/–0/–8/–2/1680/–11/2621/2732/3
28Zhongshan(Sun Yat-sen) University ZSU_Alkaid38412/–0/–0/–0/–0/–2/2725/2180/–0/–4/19113/3
29Fudan University BlackScorpion2895/–0/–0/–0/–0/–1/578/–0/–0/–1/3215/2
30Shanghai Jiao Tong University Sofasquad21420/–6/–3/–0/–0/–2/1027/–0/–0/–1/2019/2
31Shanghai Jiao Tong University SJTU Kyrieh21613/–0/–5/–0/–0/–1/160/–0/–7/–3/10519/2
32Beihang University BUAA_Rivercrab21751/–0/–4/–0/–0/–2/732/–0/–0/–1/8210/2
33South China Normal University LLL22225/–1/–5/–0/–0/–1/750/–0/–8/–1/14721/2
34NUAA Coffee22330/–0/–0/–1/1760/–1/–0/–0/–0/–1/573/2
35Huazhong University of Science and Technology Abacus.22660/–0/–4/–1/–0/–2/–1/1210/–0/–2/12510/2
36Nankai University ThreeSectionedCudgel22740/–1/–0/–0/–0/–11/–1/1620/–0/–1/11214/2
37Sichuan University scu07t01228914/–10/–4/–0/–0/–1/19016/–0/–11/–3/5959/2
38South China Agricultural University SCAU_LHL23010/–0/–6/–0/–0/–1/1340/–0/–3/–2/14712/2
39Hangzhou Dianzi University RPRush23230/–0/–1/–3/–0/–11/–3/2190/–0/–1/6419/2
40Ningbo University Thunder23511/–0/–28/–5/–0/–3/12118/–0/–0/–1/19056/2
41South China University of Technology SCUT_Scintilla23540/–8/–0/–0/–0/–4/1467/–0/–4/–4/8827/2
42Tsinghua University nocomputer23610/–0/–2/–1/–0/–3/2187/–0/–0/–2/8315/2
43Shandong University SDU_Solipsist23630/–0/–5/–0/–0/–5/2350/–0/–0/–1/4811/2
44National University of Defense Technology ARTor23633/–0/–1/–0/–0/–4/2380/–0/–0/–1/659/2
45China University of Geosciences,BeijingCUGB_bbs23710/–0/–1/–0/–0/–1/21122/–0/–0/–2/14026/2
46Zhejiang University Latte23931/–0/–0/–1/–0/–5/2030/–0/–11/–2/9020/2
47Beijing University of Posts and Telecommunications LZW23930/–0/–1/–0/–0/–2/2294/–0/–0/–1/1448/2
48Xi'an Jiaotong University OurDream!24170/–0/–0/–0/–0/–5/1821/–0/–6/–1/15513/2
49Soochow University SUDA24344/1130/–0/–0/–0/–0/–0/–0/–0/–4/2018/2
50Beihang University BUAA_PSX24680/–0/–3/–0/–1/–4/2810/–0/–0/–1/1279/2
51Xidian University Origin-125010/–1/–0/–0/–0/–6/2022/–0/–1/–3/15913/2
52Hefei University of Technology RP_GAO27180/–1/–0/–0/–0/–0/–2/–0/–15/2473/15121/2
53FuZhou University Oneplus21741/–0/–0/–0/–0/–9/–0/–0/–0/–1/7411/1
54Wenzhou University wzu1840/–3/–0/–0/–0/–10/–0/–0/–0/–2/6415/1
55Huazhong Normal University AcAres1841/–0/–0/–0/–0/–3/–4/–0/–5/–1/8414/1
56Changzhou Middle School jiangsu21886/–0/–7/–1/–0/–5/–0/–0/–3/–3/4825/1
57Harbin Institute of Technology HIT_RealDream1940/–0/–0/–0/–0/–11/–2/–0/–0/–1/9414/1
58University of Science and Technology of China asdf11081/–0/–0/–0/–0/–2/–4/–0/–0/–1/1088/1
59Shanghai University Larva11170/–0/–0/–9/–0/–1/–0/–0/–0/–2/9712/1
60Harbin Engineering University HEU_acb11190/–0/–0/–0/–0/–13/–0/–0/–0/–4/5917/1
61Donghua University ResearchGhost11250/–0/–0/–0/–0/–5/–0/–0/–0/–1/1256/1
61FuZhou University just1y11250/–0/–1/–0/–0/–9/–0/–0/–0/–1/12511/1
63Beihang University BUAA_3K11320/–1/–0/–0/–0/–1/–0/–0/–0/–1/1323/1
64Beijing Normal University (zhuhai)BNUEP_Zero_Killer11360/–0/–2/–0/–0/–1/–4/–0/–0/–1/1368/1
65Renmin University of China RUC_Pacer11451/–3/–0/–0/–0/–0/–0/–0/–0/–1/1455/1
66Nanjing University of Science & Technology SunShine11460/–0/–0/–0/–0/–3/–0/–0/–3/–2/1268/1
67xihua University XHUACM211470/–0/–0/–0/–0/–0/–5/–0/–0/–1/1476/1
68Guangdong University of Technology hijo de la luna11533/–0/–0/–0/–0/–13/–11/–0/–0/–3/11330/1
69JiLin University fadrows11670/–0/–2/–0/–0/–4/–0/–0/–0/–2/1478/1
70Nanjing University of Science & Technology Polynominal11713/–0/–0/–0/–0/–3/–0/–0/–0/–2/1518/1
71Beijing University of Chemical Technology BUCTeam_NoRP11821/–0/–0/–0/–0/–15/–0/–0/–0/–3/14219/1
72Tianjin University Tju_Tornado11840/–0/–8/–0/–0/–0/–34/–0/–0/–2/16444/1
73Xiamen University Bigsea11870/–0/–6/–2/–0/–6/–8/–0/–0/–4/12726/1
74Xiangtan University Soar11905/–0/–0/–0/–0/–0/–4/–0/–0/–2/17011/1
75East China Jiaotong University ecjtu007T112090/–4/–0/–1/–0/–0/–2/1890/–4/–10/–21/1
76xihua University XHUACM112100/–0/–0/–0/–0/–0/–1/–0/–0/–1/2102/1
77Chongqing University Godsend12160/–0/–0/–0/–0/–5/–0/–0/–0/–2/1967/1
78Hangzhou Dianzi University MayDay12230/–0/–1/–0/–0/–0/–1/–0/–0/–2/2034/1
79Xidian University Just kids12280/–0/–0/–0/–0/–0/–0/–0/–4/1684/–8/1
80University of Science and Technology of ChinaHazel12582/–0/–0/–0/–0/–0/–0/–0/–0/–3/2185/1
81Ningbo institute of Technology,Zhejiang University PowerKing12710/–1/–3/–0/–0/–2/–0/–2/–0/–5/19113/1
81Xiamen University xmufish12710/–0/–2/–0/–0/–6/–0/–0/–0/–5/19113/1
83Zhejiang Sci-Tech University ZSTU12770/–0/–0/–0/–0/–0/–4/–0/–0/–4/2178/1
84Wuhan University ARBITER12790/–0/–0/–0/–0/–2/–0/–0/–0/–6/1798/1
85Nanjing University Godspeed_LCS12821/–0/–0/–0/–0/–5/2024/–0/–0/–5/–15/1
86south west University of science and Technology nicholas12850/–0/–2/–0/–0/–0/–0/–0/–3/2451/–6/1
87Hunan University HNU_footmen12880/–0/–0/–0/–0/–1/–9/–0/–0/–5/20815/1
88China University of Geosciences,WuhanFLY_KITE13000/–3/–0/–0/–0/–0/–1/–0/–0/–5/2209/1
89University of Electronic Science and Technology of China FarmerJohn13010/–0/–0/–0/–0/–3/–6/–0/–0/–4/24113/1
90Shenzhen University SZU.Butterfly13100/–3/–0/–0/–0/–4/–0/–0/–0/–5/23012/1
91Hangzhou Dianzi University TEAM III13640/–0/–1/–0/–0/–0/–0/–0/–0/–6/2647/1
92Beijing Institute of Technology bit cats001/–1/–0/–0/–0/–3/–0/–0/–0/–8/–13/0
92Civil Aviation University of China CAUC1000/–0/–0/–0/–0/–2/–5/–0/–0/–3/–10/0
92Donghua University SOS000/–0/–0/–0/–0/–5/–1/–0/–0/–0/–6/0
92East China University of Science & Technology Bluesea001/–0/–3/–4/–0/–0/–0/–0/–0/–0/–8/0
92East China University of Science & Technology stuck001/–0/–0/–0/–0/–0/–0/–0/–0/–6/–7/0
92Information College,Hangzhou Dianzi University 3.Q000/–0/–0/–0/–0/–0/–0/–0/–0/–2/–2/0
92Northeast Forestry University nefu_acm001/–29/–0/–0/–0/–0/–0/–0/–0/–0/–30/0
92PLA University of scinece and technolog ARES000/–0/–0/–0/–0/–0/–3/–0/–0/–3/–6/0
92Renmin University of ChinaRUC_Wander000/–4/–0/–1/–0/–0/–0/–0/–0/–5/–10/0
92Zhejiang Normal University Dragon9001/–0/–0/–0/–0/–0/–0/–0/–0/–2/–3/0
Submitted/1st Yes/Total Yes140/94/3108/–/0148/–/065/142/31/–/0299/16/46291/46/2725/179/2157/50/14238/12/871472/182

Created by CSUS PC^2 8.7 20051115 04
http://www.ecs.csus.edu/pc2/
Last updated Sun Oct 28 14:19:05 CST 2007

标签 | 日志分类：ACM/ICPC纪事

Wish myself

发表评论4次阅读2007.10.25 10:03 作者：Felicia　编辑

[阅读更多]

今晚8点的火车
开始长途旅行啦
我们将默默地离开
带上给自己默默的祝福

标签 | 日志分类：心情日记

[TopCoder] SRM373 Div1

发表评论25次阅读2007.10.24 14:02 作者：Felicia　编辑

[阅读更多]

今天早上早起到机房做SRM，250分的比较简单，500分的题比较奇怪，以前都没做过这种题。想了挺久的，没想出来。可能我比较笨吧。1000分的题是个计算几何，来不及看了。今天做的人很少，rating到了1490。

标签, | 日志分类：Topcoder SRM

[计算几何] pku3293 技巧

发表评论17次阅读2007.10.22 14:06 作者：Felicia　编辑

[阅读更多]

先按规则连。规则是隔一段连一个。比如一条直线上有6个点，就1-2，3-4，5-6，这么连。如果只有奇数个点，就不行。然后再判有没有洞。
方法是任选一个点，走一圈，看看是否遍历所有的点。

下面是我的代码

下载: pku3293.cpp
#include <iostream>
 
using namespace std;
 
const int MAXN=100010;
 
typedef struct {
    int x,y,id;
} point_t;
 
int cmp_x(const point_t &a,const point_t &b) {
    return a.x<b.x || a.x==b.x && a.y<b.y;
}
 
int cmp_y(const point_t &a,const point_t &b) {
    return a.y<b.y || a.y==b.y && a.x<b.x;
}
 
point_t p[MAXN];
int c[MAXN][2];
 
int main() {
    int ca,n,i;
    for (scanf("%d",&ca);ca--;) {
        scanf("%d",&n);
        for (i=0;i<n;i++) {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].id=i;
        }
        
        int ans=0,flag=1;
        
        sort(p,p+n,cmp_x);
        int cnt=1;
        for (i=1;i<n;i++) {
            if (p[i].x!=p[i-1].x) {
                if (cnt&1) flag=0;
                cnt=1;
            }
            else {
                cnt++;
                if ((cnt&1)==0) {
                    ans+=p[i].y-p[i-1].y;
                    c[p[i].id][0]=p[i-1].id;
                    c[p[i-1].id][0]=p[i].id;
                }
            }
        }
        
        sort(p,p+n,cmp_y);
        cnt=1;
        for (i=1;i<n;i++) {
            if (p[i].y!=p[i-1].y) {
                if (cnt&1) flag=0;
                cnt=1;
            }
            else {
                cnt++;
                if ((cnt&1)==0) {
                    ans+=p[i].x-p[i-1].x;
                    c[p[i].id][1]=p[i-1].id;
                    c[p[i-1].id][1]=p[i].id;
                }
            }
        }
        
        //check connect
        int p=1,x=0,cc=0;
        do {
            x=c[x][p];
            p=1-p;
            cc++;
        } while (x!=0);
        if (cc!=n) flag=0;
        
        if (!flag) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}
标签, | 日志分类：计算几何
« Older Entries