再见了,ACM-ICPC

终于还是来到了这一天,当双手在键盘上敲下这些文字的时候,竟有些颤抖。尽管曾经不止一次的思考过退役后的场景,也做足了充分的思想准备,但当这一刻真的到来,却有些不知所措。看着 ACM 交流群里热烈的讨论,关上窗口,退出该群;将 ACM 资料小心翼翼的放置在移动硬盘的角落,不小心瞥见 NOIP 退役时存放的资料,记忆一下子席卷而来。在算法竞赛的道路上跌跌撞撞的行走了将近五年,从 NOIP 到 ICPC,是时候说再见了。 此时的我,依然记得多年前第一次提交 A+B 时的激动,记得思索半天推导出 Segment Tree 时的满足,记得苦思冥想理解 Dancing Links 时的欣喜,记得写完几本草...

2016年4月5日 · 3 分钟 · 1224 字 · Kai Wang

记 2015 ACM-ICPC亚洲区域赛(长春站、北京站)

细细想来,已经有近四个月没有更新过博客,上一次还是在 7 月份。既然这样,那就从那时候讲起吧。 整个暑假,绝大部分时间在参加 ACM 训练,除此之外,还参加了全国大学生电子设计竞赛,拿了个一般的奖项;去英国走了一遭,体会了不同的风土人情。一直想好好记录这两件事情,但总是由于各种各样的原因搁置了。 这学期自从开学以来就一直非常的忙,刚开始备战 ACM,上个月在长春拿了一块铜牌,上星期在北京拿了一块银牌,周三刚刚把 FPGA 设计邀请赛的作品完成,明天一大早赶往上海交通大学参加微软 Hackthon 大赛,下周需要提交全国移动互联网开发大赛的作...

2015年11月20日 · 5 分钟 · 2125 字 · Kai Wang

SGU 144 - Meeting

Description Two of the three members of the winning team of one of the ACM regional contests are going to meet in order to train for the upcoming World Finals. They decided that they will meet sometime between $X$ o’clock and $Y$ o’clock. Because they never get anywhere on time (they were late even on the day of the regional contest), they did not set an exact time when they will meet. However, they decided that the one who gets first at the meeting point will not wait more than $Z$ minutes for the other one (they calculated that, if the other one will not come within $Z$ minutes from the arrival of the first of them, then it is very probable that he will not show up at all). Knowing that, in the end, both of them will show up at some time between $X$ o’clock and $Y$ o’clock (not necessarily after an integer number of minutes), compute which is the probability that they will actually meet. Input The input will contain 2 integer numbers $X$ and $Y$ ($0\leq X < Y\leq 24$) and one real number $Z$ ($0 < Z\leq 60(Y-X)$). Output You should output the required probability with 7 decimal digits (rounded according to the 8th decimal digit). Sample Input 11 12 20.0 Sample Output 0.5555556 Analysis 这是一道纯粹的数学概率题,我们可以进行公式推导。首先我们需要...

2015年7月22日 · 1 分钟 · 464 字 · Kai Wang

The Freshman Grind

想来放假已经好几天了,总算抽出了一些时间来总结一下这学期的经历,虽然在期末考试期间应导师要求写过一篇《学期总结》,然而由于复习紧迫,只是草草收笔,并没有点中要处。 Grind of Courses 这学期刚开始,或许是由于上学期不错的成绩造成的盲目自信,导致了上课时间并没有特别认真的听讲,大多数时间在自己看课外书,比如《暗时间》、《浪潮之巅》等(不得不承认,这些都是不可多得的好书,前者介绍了如何高效的利用时间;后者介绍了近几十年信息技术产业作为信息产业的发展史,其中涉及了各大知名公司,例如 Apple、Microsoft、AT...

2015年7月21日 · 6 分钟 · 2512 字 · Kai Wang

SGU 116 - Index of super-prime

Description Let $P_1, P_2,\cdots ,P_N,\cdots$ be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes. Input There is a positive integer number in input. Number is not more than 10000. Output Write index $I$ for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing. Sample Input 6 Sample Output 2 3 3 Analysis 首先,我们可以根据筛法求出 10000 以内的素数,接下来我们继续利用筛法,求出这些素数中,下标为素数的超级素数,这样我们就得到了题目中所需要的超级素数。 对于寻找一个最优的组合,我们可以使用 0/1 背...

2015年7月20日 · 2 分钟 · 519 字 · Kai Wang

专题一、简单搜索 - Virtual Judge

很久以前刷完了 Virtual Judge 上的简单搜索专题,现总结如下: POJ 1321 由于题目的数据范围比较小,可以直接 dfs 暴力。读入时记录每个空位的位置,保存在 pX[] 以及 pY[] 数组中。暴力的时候统计当前处理第几个空格以及当前处理到了第几行即可。 #include <iostream> #include <memory.h> using namespace std; const int MAX = 128; long long ans; int N, K, nCnt; bool pUsed[MAX]; int pX[MAX], pY[MAX]; int pRow[MAX], pCol[MAX]; void dfs(int x, int y); int main() { char dwTmp; while(cin >> N >> K) { if(N == -1 && K == -1) { break; } nCnt = 0; ans = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= N; j++) { cin >> dwTmp; if(dwTmp == '#') { nCnt++; pX[nCnt] = i; pY[nCnt] = j; } } cin.ignore(); } memset(pRow, 0, sizeof(pRow)); memset(pCol, 0, sizeof(pCol)); memset(pUsed, false, sizeof(pUsed)); dfs(1, 0); cout << ans << endl; } return 0; } void dfs(int x, int y) { if(y == K) { ans++; } else { for(int i = x; i <= nCnt; i++) { if(!(pUsed[i] || pRow[pX[i]] || pCol[pY[i]])) { pRow[pX[i]]++; pCol[pY[i]]++; pUsed[i] = true;...

2015年6月8日 · 9 分钟 · 4250 字 · Kai Wang

记 2015 ACM-ICPC 上海大都会赛

到今天为止,距离 2015 ACM 国际大学生程序设计竞赛上海大都会赛结束已经快有一个星期了,趁着记忆中暂存的些许余温,将其记录下来。 我们从上周四开始,放下手中正在做的题目,转而准备比赛所需要的材料。由于比赛是可以携带纸质材料进场,因此我们准备了一些较为常用的算法模板,并且幻想着可能会遇到类似的题目。然而事实证明,携带的这些模板并没有什么作用,当然,这是后话。 周五晚上,我们开始整理行装。由于第二天早上需要六点半之前集合,所以便早早的入睡了。早上起来稍微打点一下,已是六点。草草地吃了一块面包,关上宿舍门便出发了。...

2015年5月30日 · 5 分钟 · 2135 字 · Kai Wang

2048 游戏制作过程(Java 描述):第五节、界面美化

这一节,我们将介绍游戏界面的美化以及游戏数据的存储。 首先创建一个 color.xml 资源文件,用来保存每个数字对应的背景色和前景色。右击 res 文件夹,选择 New,单击 Android resource file,输入 color,单击 Next 即可。 新建资源 修改代码如下: <?xml version="1.0" encoding="utf-8"?> <resources> <color name="bg2">#eee4da</color> <color name="text2">#776e65</color> <color name="bg4">#ede0c8</color> <color name="text4">#776e65</color> <color name="bg8">#f2b179</color> <color name="text8">#f9f6f2</color> <color name="bg16">#f59563</color> <color name="text16">#f9f6f2</color> <color name="bg32">#f67c5f</color> <color name="text32">#f9f6f2</color> <color name="bg64">#f65e3b</color> <color name="text64">#f9f6f2</color> <color name="bg128">#edcf72</color> <color name="text128">#f9f6f2</color> <color name="bg256">#edcc61</color> <color name="text256">#f9f6f2</color> <color name="bg512">#edc850</color> <color name="text512">#f9f6f2</color> <color name="bg1024">#edc53f</color> <color name="text1024">#f9f6f2</color> <color name="bg2048">#edc22e</color> <color name="text2048">#f9f6f2</color> <color name="bgsuper">#3c3a32</color> <color name="textsuper">#f9f6f2</color> </resources> 其中 bg 表示背景色,text 表示前景色,切换到 Card 界面,在 setNumber 中添加如下代码: switch(number) { case 0: tvNumber.setBackgroundColor(0x33FFFFFF); break; case 2: tvNumber.setTextColor(getResources().getColor(R.color.text2)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg2)); break; case 4: tvNumber.setTextColor(getResources().getColor(R.color.text4)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg4)); break; case 8: tvNumber.setTextColor(getResources().getColor(R.color.text8)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg8)); break; case 16: tvNumber.setTextColor(getResources().getColor(R.color.text16)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg16)); break; case 32: tvNumber.setTextColor(getResources().getColor(R.color.text32)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg32)); break; case 64: tvNumber.setTextColor(getResources().getColor(R.color.text64)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg64)); break; case 128: tvNumber.setTextColor(getResources().getColor(R.color.text128)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg128)); break; case 256: tvNumber.setTextColor(getResources().getColor(R.color.text256)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg256)); break; case 512: tvNumber.setTextColor(getResources().getColor(R.color.text512)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg512)); break; case 1024: tvNumber.setTextColor(getResources().getColor(R.color.text1024)); tvNumber.setBackgroundColor(getResources().getColor(R.color.bg1024)); break; case...

2015年5月17日 · 3 分钟 · 1347 字 · Kai Wang

2048 游戏制作过程(Java 描述):第四节、游戏逻辑

上一节中,我们已经成功的将卡牌添加到了游戏中,但只是显示在了界面上,并没有保存下来。我们在 GameView 中定义一个二维数组用来保存游戏界面的卡牌。 private Card[][] cardMap = new Card[4][4]; // 记录游戏 接下来,我们需要将初始化时候添加的卡片添加到 cardMap 数组中,如下图所示: private void addCards(int cardSize) { Card card; for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { card = new Card(getContext()); card.setNumber(2); addView(card, cardSzie, cardSize); cardMap[i][j] = card; // 添加卡片 } } } 这样一来,我们就将游戏界面记录下来了。 但是上一节中,我们一下子就生成了 16 张卡片,这和平时游戏的时候不一致。而且我们只能生成卡片 2。为了改进它,我们可以定义一个函数 addRandomNumbe...

2015年5月15日 · 7 分钟 · 3052 字 · Kai Wang

2048 游戏制作过程(Java 描述):第三节、创建界面

首先,我们要使得我们的程序能够判断用户的手势,一共为上、下、左、右四种。在 GameView 类中添加如下代码: private void initGameView() { setOnTouchListener(new View.OnTouchListener() { @Override public boolean onTouch(View v, MotionEvent event) { return false; } }); } 接下来,我们来分析一下如何进行手势判断。首先,用户的手势输入应该有两个数据,一个是按下的屏幕位置,一个是放开的屏幕位置。那么我们只需要计算横向和竖向坐标差的绝对值,绝对值较大的一个方向则是用户需求的方向。至于横向中的左右和竖向中的上下,我们可以通过按下和放开的位置的大小进行比较得出。 有了上面的分析,我们开始写代码: private void initGameView() { setOnTouchListener(new View.OnTouchListener() { private float startX, startY; // 起始位置 private float endX, endY; // 终了位置...

2015年5月14日 · 4 分钟 · 1539 字 · Kai Wang