Colin's blog

A football fan,an English lover and a coder


  • 首页

  • 分类

  • 关于

  • 归档

  • 标签

Font Size

发表于 2017-05-06   |   分类于 acm
原题:Font Size 原题大意史蒂文喜欢看书。他现在读的这本书由N个段落组成,第i个段落包含ai个字符。现在他决定增加字符的字体大小。但史蒂文手机屏幕的尺寸有限。其宽度为W,高度为H。因此,如果字符的字体大小为S,则只能在一行中显示⌊W/S⌋个字符,并在页面中显示⌊H/S⌋行。(⌊x⌋是不大于x的最大整数)所以这里的问题是,如果史蒂文想控制页数不超过P,他可以设置的最大字体大小是多少?请注意,段落必须以新行开头,段落之间没有空行。 算法分析二分,但是二分有几种写法: 规定范围里的最大值(如果连续两个数,偏向右边的数)m = l+(r-l+1)/2; if(check(m)) l = m; else r = m-1; 规定范围里的最小值(如果连续两个数,偏向左边的数)m = l+(r-l)/2; if(check(m)) l = m+1; else r = m; 小于一个精度while(r-l < 1e-5){ m = (l+r)/2; if(check(m)) l = m; else r= m; } 程序代码#include <bits/stdc ...
阅读全文 »

Atcoder 073

发表于 2017-05-03   |   分类于 acm
Sentou原题:Sentou 原题大意一个水龙头,按一次开关会流T秒,再次按开关会刷新它的时间。给出n次按开关的时刻,问总共会流多少秒。 算法分析水题,用一个数组记录两次开关的时间差,并判断前一个时刻加上水流的时间能否到达下次按开关的时刻,如果能则加上时间差,否则加上水流时间。 程序代码#include <cstdio> #include <cstring> #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 200000+5; typedef long long ll; ll sen[maxn], a[maxn]; ll sum = 0; int n; ll t; int main(){ scanf("%lld%lld",&n, &t); for(int i = 0; i < n; i++) { scanf("%lld", &sen[i]); ...
阅读全文 »

迷宫转弯问题

发表于 2017-04-29   |   分类于 acm
走迷宫问题是图搜索的经典问题,这里给出两个和转弯有关的题。 Laser原题:Laser 原题大意有一个n×m的区域,有一个激光和一个传感器,其中有一些障碍,我们的目标就是在空白的区域放一些镜子,并且希望用最少数量的镜子,能够使激关经过反射后到达传感器。<>^v箭头指向激光的方向,C表示传感器,#表示障碍, . 表示空白区域。 算法分析暴力模拟当前光线在何处时,放置了哪种镜子,搜下去就行了。光线通过的路径也被视作’#’,其实这个条件是没有意义的。假若光线产生了回路,对于最优解来说与其花费更多镜子去产生回路,不如只放置一面镜子就使得方向偏转,而我们bfs出的结果一定是最优的。需要注意镜子不能摆放在起点,终点和’#’处。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long LL; int t; int n, m; char s[222][222]; int walk[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int vis[222][222 ...
阅读全文 »

Choreographer Problem

发表于 2017-04-26   |   分类于 acm
原题:Choreographer Problem 原题大意艺术团中,有n个舞者,i舞者和(i-1)舞者、(i+1)舞者相似,(i-1)和(i+1)舞者并不相似。如果n> 1,那么第一个舞者只有相似的舞者,最后一个舞者只有相似的舞者,所有其他舞者都有两个相似的舞者。舞蹈开始和结束在一个空荡荡的舞台。舞蹈舞蹈不应该是空的。每一分钟,以下变化之一发生在舞台上: 1.一个舞者(目前不在舞台上)出现; 2.一个舞者(目前在舞台上)离开舞台; 3.一个舞者代替另一个类似于他/她的舞者(基于舞者的切换-一个舞者离开舞台,而舞台上出现一个类似的舞者)同时,舞台上不能有超过k个舞者。 现在编舞师正在考虑安排舞蹈,使得每一个不包含k个舞者的舞者都会在舞台上出现一次。你的工作是编写一个程序来帮助编舞。 输出:+i表示i舞者出现在舞台上,-i表示i舞者离开舞台;++i表示i舞者离开舞台,同时(i+1)舞者出现在舞台上;–i表示i舞者离开舞台,同时(i-1)舞者出现在舞台上 算法分析题目要我们生成组合 && 相邻的两个组合必须很接近由这点,我们可以想到Gray码。 注意到台上的人数不能超过 ...
阅读全文 »

Hamiltonian Hypercube

发表于 2017-04-26   |   分类于 acm
原题:Hamiltonian Hypercube 原题大意n维哈密尔顿超立方体 想知道a到b之间的顶点数,1 <= n <= 60;a,b都出现在n位格雷码中; 算法分析求出两个格雷码对应的二进制数的十进制表示做差即可。 有关格雷码的模板: 1. 二进制 -> Gray LL to_gray(LL x) { return x ^= (x>>1);//返回结果为Gray码的十进制表示。 } 2. Gray-二进制 LL to_bin(LL x) { LL y = x; while(x>>=1) { y ^= x; } return y; } 3. 构造长度为n的格雷码 vector<int> G; for(int i=0;i<(1<<n);i++) { G.push_back(to_gray(i)); } 程序代码#include <cstdio> using namespace std; typedef long lon ...
阅读全文 »
1…121314…23
Shen Hao

Shen Hao

Colin's blog | acm |c++

114 日志
6 分类
71 标签
GitHub
© 2017 Shen Hao
由 Hexo 强力驱动
主题 - NexT.Muse