Qualification Round Problem A. Speaking in Tongues 简单的按规律替换字符串 Problem B. Dancing With the Googlers 忘记了具体内容了,反正要注意边界特殊情况。 Problem C. Recycled Numbers 比赛时想不明白 Case #4,于是没交大数据,后来看了 Contest Analysis 才知道有1212这种情况,会重复。比赛的时候移位是用字符串实现的。。后来才改过来。看了代码 Contest Analysis 的才知道不用数组记录数字是否出现的,只要移回原数就退出,即可避免循环节的问题。 #include <iostream> #include <cstdio> using namespace std; int a, b; long long ans; void work(int num) { int temp = num; int base = 1; [...]
练习曲 (2006)
图片来源:http://www.wretch.cc/blog/EtudeBike 评分:4/5 很像一部纪录片,没想到骑行的主人公听力不好,说话也不清楚。环岛游倒没什么特别,肯定在路上遇到一些好心人,电影后面一小段节奏有点慢。。 几个印象深刻的情节:小虫爬过地图、镜头(小女孩)透过啤酒看别人、一条鱼从天而降,貌似是从海鸥嘴里掉下来的(?)、抗议女工租车,半价优惠。 另外感觉台湾人讲话跟以前室友的闽南话确实有点像。。 === 好久没看电影,好久没看纪录片了。 以前不知道在这里发海报算不算侵权,现在觉得应该算合理使用吧。
数学建模邀请赛
从上周六到这周六,折腾一周数学建模。 两道题目,第一个是说水滴的高度和体积之间的关系,随着体积的增大高度先增大后减小,没注意具体什么问了什么。。 第二个什么条件都没给,直接问如何在城市布局 PM2.5 监测站。 完全是去打酱油,前几天每天晚上都语音好几个小时,查查论文,英文的看不懂,中文的没什么资料。大家都不怎么说话,。因为没思路。。我觉得非常非常痛苦。。后来H提出个想法,就是按风向和温度对 PM2.5 监测的影响,对上海地图拉伸两次,然后在地图里面画N个圆,要求半径相同,求出每个圆的位置,然后再把这些坐标转换到原来的上海地图上。 我就写了个凸包,让地图拉伸之后仍然是个凸多边形,不过由于我们没取几个点,其实肉眼看一下就行的…还写了一个显示这些点的程序,不过没用上,原来 MATLAB 直接就能弄。求圆的位置用的是 LINGO,貌似是线性规划,原来还有这种神奇的软件。。当然这些都不是我弄的。 最后我发的第一份pdf排版有点问题。。只好最后几分钟再发一遍。囧。。其实还有个大问题,这里就不说了= = 我们的假设是扩散快的地方少放监测站,因为这些地方的代表性不强。感觉怪怪的,不过细想还是有道理的。当然还要看环保局怎么想了,哪里有地方放设备,哪里空气质量比较好(貌似北京把一个监测站从前门挪到郊区了)。 找资料的时候还谈到了热岛效应、盛行风向、迎风坡背风坡(为啥迎风坡降水多、背风坡降水少来着?完全忘了!!)高中学地理那段时光多好啊~高中还选了地理选修课呢。。 还是对数学建模不太感兴趣。。当时想着为我们那个创新项目学点MATLAB,结果现在一点都没学,我也不想学。。 这一周大约在这上面花了多于(1号一天+3小时/天(其余天)),而且很影响心情。。好不容易有个作业这么少的假期啊。也是因为这个间接导致图形学作业没按时交。。就是不想做了。。晚了两天交,而且只写了旋转。当然很感谢两位队友~程序和论文基本都是他们写的。 以后还要不要参加数学建模呢…看到一个例子是根据客流量安排公交班次,那个倒是很好玩的。不过其他的都不好玩。 话说本来准备这周六从安亭北去苏州运转呢,结果没起来,还好没起来,否则被问到就尴尬了= = ==================== 今天 codejam 太悲剧了。。纠结了半天到底睡不睡觉,在床上躺着玩手机没睡着,于是就起来喝杯咖啡写比赛。(第一次喝这种,雀巢醇品五毛钱一袋冲出来的味道和麦当劳的一样哦!) A题想了半天才明白,大数据居然还挂了,不知道存在哪里。(输出里居然有-0.000333,难道是精度问题) B不想看 C写了一半不想写了,于是过来写blog… 于是晚上再来一次吧~重在参与。。 ==================== 晚上搞完数学建模玩了会 openBVE,没想到这么小!听说很多年了,第一次玩。画面效果不错,就是。。AI不会动,而且限速提示、停站提示不清楚。玩到九点有点头晕就算了。 ==================== 呃。。最近在看Coursera上的编译原理。。视频大约两个多小时,作业还要花一两个小时啊,有的题目有点难/tricky,有论坛,不知道以后能不能坚持下去。
USTC1305 Maximum income
来自 xw 和 wh: 维护一个递减的单调队列,因为后入队的数只有比前面所有的数小才有可能成为符合条件区间的起点,若不满足这个条件,就二分找当前最大区间。复杂度 nlogn。 === 最近好忙= = #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MAXN = 100010; int a[MAXN]; int queue[MAXN]; int day[MAXN]; int main() { int t; int n, c; int p, ans; cin >> t; while (t–) { scanf("%d%d", &n, &c); for (int i = 0; i [...]
USTC1300 Big grid
USTC1300 DP,dp[i][SAME 或 DIFF] 表示格子[0][i]和[1][i-1]相同颜色或不同颜色有多少种情况。然后就很好写了。 数学解法不会= = #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int SAME = 1; const int DIFF = 0; long long dp[10010][2]; int main() { int t,n,m,k; long long ans; cin >> t; while (t–) { memset(dp, 0, sizeof(dp)); scanf("%d%d%d", &n, &m, &k); if (n == 1) { [...]
HDU4193 Non-negative Partial Sums
HDU4193 终于知道单调队列了!其实挺简单的。搜到了这个:补缺补漏:单调队列- Blog of Felix021 – TechOnly 因为每个元素最多入队出队一次,所以复杂度是O(n)的。 这道题怎么做呢?开一个 2n 的数组,sum[i] 记录 a[1] 到 a[i] 的和。若在某个长度为 n 的区间里的最小 sum 大于等于区间左侧的 sum,也就是说区间里没有负数,答案计数加一。 // cin 会超时,不用 deque 会快一点 #include <iostream> #include <cstdio> #include <queue> using namespace std; const int MAXN = 2000010; int a[MAXN]; int main() { int n; while (scanf("%d", &n)) { if (n == 0) [...]
