Report for SZUCPC2012

Posted on May 9, 2012 by swrdlgc

首先挂出本次比赛的获奖情况
一等奖：黄凛凛
二等奖：叶德颖、杨浩、戴瑞康
三等奖：张佳楠、谢宝刚、刘卓德、罗凯恒、黎启航

最佳奋斗奖：杨浩
战斗机奖：谢宝刚
勤奋女生：吴文冰
ACM…: 不知道什么东西

恭喜他们…
以上同学均可获得参加即将到来的金山杯珠海赛的资格..

感谢学生会信息部全体成员的配合~
感谢腾讯俱乐部的资金支持~
感谢益旺和星星的出题~

本次比赛题目难度略小于去年的比赛(校赛以及冬季赛)
另：已经以网络赛形式呈现，比赛id：113，SZU_OJ
有兴趣可以再刷刷…

解题啦….

Problem A Find the Dragon
**
第一题，有点见龙在田的味道…

给出一个长串，问它的2^n个子串里面是不是有”dragon”这个单词…
显然不能生成子集..
可以先找到字符d，然后r….，看看最终能不能找完所有字符…
一遍扫过去就好，不必回退，复杂度O(n)…

Problem B Rectangular Cuboid Checking
***
勉强算计算几何题…

给出3d空间内8个点，问能否构成长方体的8个顶点….
因为无序，8个点一共8！种情况，暴力枚举就好…

暴力方式：
一种做法，dfs生成全排列
一种做法，stl的next_permutation函数…

可以考虑对称性，减掉一半左右…
但其实本题代码已经不是很好敲了，建议不考虑…

复杂度：O(8!*每次判断)

Problem C The Biggest Number
*****
欧拉回路…

给n个数，如果数a的最后一位数字与数b的第一位数字相同可以连接…
求连接到的

将每个数字当做一条边，端点是头尾两个数字，一共0-9十个顶点
判断每个点的入度出度，三种情况
1、都相同：从最后一个点开始dfs
2、有两个点不同(而且都是相差1)：从出度>入度的那个点开始dfs
3、其他：构不成回路，输出-1

dfs需要注意：
贪心的从最大的数字开始走，这样保证结果最大
判断最终走过的节点是不是n个，这样保证图是连通的..

复杂度：O(n)

Problem D Cutting the Number
****
大数+dp

给出一个很长的字符串，切割成很多小串
要求后面的小串里面数字比前面的大
求切割能得到的所有小串最小和…

dp是很显然的，但是代码有点难敲
dp[i][j]表示到i，最后一个小串是j-i能得到的最大，那么
dp[i][j] = min{dp[j-1][k]+s[j~i]} k 不能java， 需要模拟大数的比较 和 大数加法….

状态n*n，转移n，复杂度：O(n*n*n)

Problem E Alec’s Game
**
很好玩的一个题目…

三种颜色：三基色，颜色叠加之后会发生变化
三种命令：喷、吸、查询
开始时，盘子内没有颜色..
然后执行n条命令，对每次查询输出当前盘子内颜色

直接模拟就好..
可以用3个位代表三种颜色
那么，喷颜色就等于把那个位变成1，反之变成0，
预先关联好各种颜色与数组下标…
代码很好敲…

Problem F Delete Comments
**
坑人题…

给出一段代码，消除//注释
怎么找都行，stl的find，或者直接找…

这题估计会n多pe的…
最后别输出回车….

Problem G The Second Shortest Path
*****
次短路

给双向图，求单源次短路…
与一般题目不同的是要求次短必须严格小于最短…

Djs改进…
将每个点拆成两个点，更新完第一个点得到最短路
更新完第二个点得到次短路
因为严格小于，注意更新方式…

复杂度，邻接阵：O(N*N)
邻接表：O(N*N), 实际比邻接阵优很多
堆优化+邻接表：O(MlgN)

Problem H Recite Vocabulary
**
日期处理

给出两个合法日期(两个端点也算)，求出它们之间的天数
得到平均每天的单词数目..

注意闰年的判断即可..

Problem I Love In WenShanLake
*
水题

这个题目是后来换上去的，因为大一的小朋友有一半左右…
本次比赛中最简单的题，也是个有爱题，正如题…

给出两个用细管连通的长方体的底面积和水面高度
求打开开关之后的水面高度
求出总体积然后除以总的底面积即可…
证明，连通器原理，因为大气压相等什么的…

注意输出舍入到整数位，可以%.lf，也可以+0.5之后%d处理

可惜了我原来的一个计数的题目
二维平面n个点，得到2^n个子集，问有多少对子集关于其中某个点对称
先去掉重复点，然后hash+公式…
数据出了两个小时，里面有线状、米字、格子的点…
还特意打表塞了个AC在里面…

Problem J Survival Game
***
BFS
脑筋急转弯的感觉…

给个类似迷宫的东西，里面有一个KEY，n多人，n多门…
问逃离迷宫的最少时间

从KEY处BFS最短路就好…
BFS到第一个人，第一个门，它们之和-1就是答案..

部分代码请访问：

http://blog.csdn.net/swrdlgc/article/details/7547550

有疑问请发邮件ahzlsd@gmail.com,
或至实验室227(马上就466啦)咨询…
谢谢阅读到此！
by ACM实验室

Posted in 解题报告 | 1 Comment

《NOTICE》深圳大学第十届腾讯杯ACM程序设计大赛现已开始接受报名

Posted on April 20, 2012 by swrdlgc

为了激发同学们对计算机技术和应用的学习兴趣，发挥同学们在计算机方面的特长，提高大学生的程序设计水平，计算机与软件学院特举办深圳大学第十届ACM程序设计大赛。大赛致力于为广大同学创造一个相互交流、共同提高计算机程序设计水平的平台，发掘编程人才，让有这方面专长的同学一展所长。
欢迎在校学生踊跃报名。

一、竞赛时间： 2012年5月6日（星期日）
二、竞赛地点： 办公楼235实验室
三、主办单位：深圳大学ACM实验室
承办单位：计算机与软件学院学生会信息部
特别鸣谢：深圳大学腾讯创新俱乐部
四、参赛对象： 深圳大学在校全日制本科生
五、报名时间： 即日起至4月28日24点
六、报名方式：
1、网上报名： 登陆http:// acm.szu.edu.cn报名系统填写报名信息
2、邮箱报名： 发送姓名+学号+学院+手机号到cssexxb@gmail.com
3、短信报名：发送“姓名+学号+学院+年级+手机长号+深大短号+邮箱”到
13760204692
4、由于机房空间有限，报名从速，超出100位的报名者可能取消参赛资格
七、比赛方式：
1、以个人为单位参赛；竞赛时间为五小时；试题为英文，10题；
2、比赛全部为上机操作；
3、重点考察选手的算法和程序设计能力，不考察任何Windows/Linux编程知识；
4、选手可携带任何非电子类资料，包括书籍和打印出来的程序等；
5、在竞赛过程中选手可以随时通过网络提交程序；
6、竞赛平台为深圳大学在线程序评测系统。
八、 奖项设置：
一等奖 （1个）：奖金400元
二等奖 （3个）：奖金200元
三等奖 （5个）：奖金100元

最佳奋斗奖（1人）：last accepted
战斗机奖（1人）：first accepted
勤奋女生奖（1人）：the most accepted one among the girls
ACM微博幸运儿（1人）：just for fun..

具体信息请联系: 仲甄翔 623792/13692183244

荣誉可兼得，奖品不可兼得。另外，所有参赛者均可获得一份纪念品。

计算机与软件学院
2012年4月20 日

本通知解释权归程序设计实验室所有。。。

Posted in 比赛通知 | 2 Comments

选拔赛解题报告

Posted on April 5, 2012 by swrdlgc

首先说一下这次选拔的结果，在实验做题的有效
第一队：黄凛凛、罗益旺、张良
第二队：董倩、叶德颖、张佳楠
其中黄凛凛搞定了F题，全场唯一。。

请大家注意校赛已经接受报名

http://acm.szu.edu.cn/blog/?page_id=66

*表示个人觉得题目的难度，题意请以原题为主
解答有可能有错误，请发邮件，zlsd.cn@qq.com
其它的不说了，解题吧

*
ProA: Test Problem
题意：给定N，求1到N之间所有整数的和
标签：水题
解法： 1.公式，n>0,(n+1)*n/2; n<=0,-(n+1)*(n-2)/2.
2.暴力求和.
备注：本来没有这题，但实在不忍心一题不过，算是爱心题吧

**
ProB: Scrabble
题意：给一些单词，问给定的Scrabble能拼凑成的单词数
Scrabble的下划线可代替任意字符
标签：计数题
解法：直接数出Scarbble各种字符的个数，分别与每个单词对比，
最终判断下划线的数目是否超过不能匹配的字符数
备注：关键词，arrange，排列，就是字符可以乱排

*****
ProC: Convex area
题意：三维凸包的面积
标签：几何
解法：(不很确定)不求凸包，直接求面积,枚举三点构成面，
对每个面判断是不是所有点都在同一边，发现不在就退出，
两点只可能参与凸包两个面，理论复杂度：O(n4)
因为参与凸包的面很少，所以实际应该比这个低~
备注：没有验证

***
ProD: Nim
题意：N堆石头，每次可以从一堆中拿走>=1个，问获胜的拿法种数
标签：博弈题
解法：异或为0则为必胜状态
备注：黑书上的Nim例题

***
ProE: Dropping tests
题意：给n个分数，求丢掉k个以后的分子分母比最大值
标签：0/1分数规划
解法：二分答案ans，然后将ai-bi*ans排序，取最大的m-k个
备注：暴力也可以搞，由1个最大递推到n-k个最大，O(n*n)

****
ProF: Box walking
题意：从(0,0,0)点沿着长方体(‘x,’y,’z)的面走到(x,y,z)点的最小值
标签：数学
解法：首先，两点之间直线最短，将长方体展开之后，
就可以发现有三种情况，两点在同一面，两点在相邻两个面，
两点在不相邻两个面(这时候两点之间直线跨三个面，需要用叉积判断是否满足)。
然后勾股定理就好。
备注：by hll

****
ProG: Colored stones
题意：给定一个颜色序列，移掉最小个数保证相同颜色之间没有其它颜色，颜色种数<=5
标签：状态压缩dp
解法：dp[k][set][color]表示前k个以color结尾具有颜色集合为set的最大值
其中set是一个int数，int的第i个位表示第i中颜色在不在集合里面
初始：dp[0][1《color[0]][color[0]]=1，其它为0
到k+1个时，如果第k+1个的颜色(c)没有出现，可以放在最后面
转移：dp[k+1][set|1《c]=max(dp[k][set|1《c]+1, dp[k+1][set|1《c]);
如果第k+1个的颜色(c)已经出现，到第k个结尾为c的集合可以+1
转移：dp[k+1][set]=max(dp[k][set]+1, dp[k+1][set]);
其它颜色结尾情况直接拷贝即可
转移：dp[k+1][set][!c]=max(dp[k][set][!c], dp[k+1][set][!c]);
备注：

*****
ProH: RSI
题意：给出0-9十个数字，以及一些规则，求按一串数字的最少时间
标签：dp
解法：
备注：还不是很清楚，求救！！【已有更新，见最下面的comments】

**
ProI: Do it!
题意：每个人做100, 速度是r. 求完成任务的最小总时间
听到doit之后n+速度变r+2, n-速度变r-1, n0不变.
标签：暴力
解法：直接计算doit次数为0,1,2,..的总时间(<34次),求得最小即可
备注：

Posted in 解题报告 | 1 Comment

关于省赛选拔的通知

Posted on March 30, 2012 by admin

鉴于省赛将在4月21日进行

现决定对全校想参加省赛的同学进行选拔

原定校赛推迟到省赛之后，具体时间另行通知

选拔赛相关信息如下：

1、比赛时间：4月4日12：00-17：00

2、比赛地点：ACM程序设计实验室（办公楼227）

3、要求：自备比赛所需，包括纸质资料、可以无线上网的PC等

4、其它信息：当天来到比赛地点时通知

程序设计创新基地
2012年3月30日

PS: 谢谢各位师兄师姐对此次比赛的建议~
特别感谢小六仔师兄、老卢师兄、红豆师兄、jq等的帮助

Posted in 比赛通知 | 2 Comments

实验室可上外网列表

Posted on March 30, 2012 by admin

实验室上不了外网，只能上深大内部网及以下的网站

PKU 北大OJ
ZJU 浙大OJ
HDU 杭电OJ
SOJ 中大OJ
FZU 福大OJ
UVA
USACO
CF
TC
HUST
UESTC
WOJ
watashi.ws

在实验室上网建议：

目前实验室的网络只能上内部网及一系列OJ，故可以在实验室更好地做题学习
如果想上其他外部网站可以通过设置代理的方式上网，或者可以远程到自己宿舍的电脑上网

因各种原因（技术的和物理的），目前只能这样解决。

Posted in 实验室相关 | Leave a comment

Hello world! Hello ACMCPC!

Posted on March 4, 2012 by admin 
#include <stdio.h>
int main()
{
    printf("Hello world!");
    return 0;
}

#include <iostream>
using namespaces std;
int main()
{
    cout << "Hello world!" << endl;
    return 0;
}

#include <stdio.h>
int main()
{
    int a, b, t;
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%d", &a, &b);
        printf("%d\n", a+b);
    }
    return 0;
}

#include <iostream>
using namespaces std;
int main()
{
    int a, b, t;
    cin >> t;
    while( t-- )
    {
        cin >> a >> b;
        cout << a+b <<endl;
    }
    return 0;
}
Posted in 未分类 | 1 Comment