image frame

听寒's Blog

CCF2018-12-1 小明上学

编程练习

题目说明

题目背景

　　小明是汉东省政法大学附属中学的一名学生，他每天都要骑自行车往返于家和学校。为了能尽可能充足地睡眠，他希望能够预计自己上学所需要的时间。他上学需要经过数段道路，相邻两段道路之间设有至多一盏红绿灯。
　　京州市的红绿灯是这样工作的：每盏红绿灯有红、黄、绿三盏灯和一个能够显示倒计时的显示牌。假设红绿灯被设定为红灯 r 秒，黄灯 y 秒，绿灯 g 秒，那么从 0 时刻起，[0,r) 秒内亮红灯，车辆不许通过；[r, r+g) 秒内亮绿灯，车辆允许通过；[r+g, r+g+y) 秒内亮黄灯，车辆不许通过，然后依次循环。倒计时的显示牌上显示的数字 l（l > 0）是指距离下一次信号灯变化的秒数。

问题描述

　　一次上学的路上，小明记录下了经过每段路的时间，和各个红绿灯在小明到达路口时的颜色和倒计时秒数。希望你帮忙计算此次小明上学所用的时间。

输入格式

　　输入的第一行包含空格分隔的三个正整数 r、y、g，表示红绿灯的设置。这三个数均不超过 106。
　　输入的第二行包含一个正整数 n（n ≤ 100），表示小明总共经过的道路段数和看到的红绿灯数目。
　　接下来的 n 行，每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路，耗时 t 秒，此处 t 不超过 10^6；k=1、2、3 时，分别表示看到了一个红灯、黄灯、绿灯，且倒计时显示牌上显示的数字是 t，此处 t 分别不会超过 r、y、g。

输出格式

　　输出一个数字，表示此次小明上学所用的时间。

测试用例

样例输入
30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

样例输出
70

样例说明
　　小明先经过第一段道路，用时 10 秒，然后等待 5 秒的红灯，再经过第二段道路，用时 11 秒，然后等待 2 秒的黄灯和 30 秒的红灯，再经过第三段、第四段道路，分别用时6、3秒，然后通过绿灯，再经过最后一段道路，用时 3 秒。共计 10 + 5 + 11 + 2 + 30 + 6 + 3 + 3=70 秒。

评测用例规模与约定

　　测试点 1, 2 中不存在任何信号灯。
　　测试点 3, 4 中所有的信号灯在被观察时均为绿灯。
　　测试点 5, 6 中所有的信号灯在被观察时均为红灯。
　　测试点 7, 8 中所有的信号灯在被观察时均为黄灯。
　　测试点 9, 10 中将出现各种可能的情况。

解题要点

模拟题，非常简单，模拟情况即可。分析数据规模可知int即可表示所有情况。

注意，黄灯时间结束后还要等红灯结束，才是绿灯可通行。
因此遇到黄灯需要为消耗时间加上 黄灯剩余时间+红灯时间。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;

int main()
{
	int r, y, g; cin >> r >> y >> g;
	int n; cin >> n;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		// clog << "当前时间点：" << ans << endl;
		int k, t; cin >> k >> t;
		if (k == 0) {
			ans += t;
			continue;
		}
		// clog << "状态：" << k << " " << t << endl;
		switch (k)
		{
		case 1: // R
			ans += t;
			break;
		case 2: // Y
			ans += t + r;
			break;
		case 3: // G
			ans += 0;
			break;
		default:
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

关于软件工程过度设计的一点感想

随笔

代码架构设计的复杂性就像一个左右摇摆的天平。
过于简单，则越有可能产生不好的代码，增大代码修改的难度（需要理解原有不良代码），降低代码维护性。
过于复杂，则产生无用的抽象层，增大代码修改的复杂度（需要理解原有抽象设计并保持），同样会降低代码维护性。
过度设计，其实就是把维护烂代码吃的屎，转成了维护烂设计吃的屎。

有个关键的问题：对于一个设计，想让它被使用起来越爽，相应要去维护它也越累。
我们有时常常无视了设计带来的维护复杂度，只看到了它的使用便利性。我们为软件工程的各种设计而兴奋，梦想着在良好设计的代码库中高效工作而兴奋。

实际上，天下没有白吃的午餐。必须认识到维护设计也有成本，势必会有人为此承担债务，但不代表软件设计就毫无用处，适当的设计可以使使用便利性的好处高于维护复杂性的坏处。

业务代码在设计上要更多地权衡利弊，因为使用者和维护者是同一主体，两者此消彼长，但却也不是等额增减。争取设计带来的使用便利性大于维护复杂性。如果两者相等，设计便是无用的。如果使用便利性小于维护复杂度，那这个起反作用的过度设计应当尽快被移除。
特别地，对于基础通用类库，与业务代码不同，抽象设计的使用者和维护者不是同一批人，值得在设计的天平上，比业务代码更多地倾向良好设计。基础类库的维护者可以通过好设计，将广大使用者的债务负担，转移至维护者一次性解决或削减。

博客重建说明

旧博客的源文件已经完全丢失，故重建博客。

关于旧文章

原博客迁移至域名old.blog.moew.xyz，继续保留开放，但是无意外不会再做修改。

有价值的文章后续会转移过来，这边也会陆续完善。

关于友情链接

已知需要更新的友情链接，已经全部更新完毕。

有几个站无法访问，又联系不到人，只好撤除链接。
如果站点还在需要重新添加，可以联系我。

转换罗马数字

学习记录

基本思路：
由于最大单位为由M表示的1000，所以千、百、十、个的各个数值均有有限的固定组合且数量不大。
进而1000以下的组合可通过查表拼接完成转换，1000以上部分可通过动态生成重复M的拼接。

首先通过取余循环分离各位数字，而后计算索引值并查表取出对应字符串进行拼接，最后返回结果

JS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
    function convert(num) {
      var rest = num;
      var numArr = [];
      var table = {
        0:'',
        
        1:'I', 2:'II', 3:'III', 4:'IV', 5:'V',
        6:'VI', 7:'VII', 8:'VIII', 9:'IX', 
        
        10: 'X', 20:'XX', 30:'XXX', 40:'XL', 50:'L',
        60:'LX', 70:'LXX', 80: 'LXXX', 90: 'XC',
        
        100:'C', 200: 'CC', 300:'CCC', 400: 'CD', 500:'D',
        600:'DC', 700:'DCC', 800: 'DCCC', 900: 'CM',
     
        1000:'M'
      };
      //分离各位数字
      while(rest > 0){
        numArr.push(Math.floor(rest % 10));
        rest = Math.floor(rest / 10);
      }
      console.log(numArr);
     var result = numArr.reduce(function(str, val, index){
       //index代表原始数据从个位起索引
       if (index < 3){
        //1000以下部分查表转换并拼接
    	return table[val*Math.pow(10,index)] + str;
       }else{
        //1000以上部分动态生成
    	var unit = table[1000].repeat(Math.pow(10,index-3));
    	return unit.repeat(val) + str;
    	}
     }, '');
     console.log(result);
     return result;
    }
    
    //test case
    console.assert(convert(2)==="II");
    console.assert(convert(9)==="IX");
    console.assert(convert(12)==="XII");
    console.assert(convert(29)==="XXIX");
    console.assert(convert(500)==="D");
    console.assert(convert(501)==="DI");
    console.assert(convert(649)==="DCXLIX");
    console.assert(convert(891)==="DCCCXCI");
    console.assert(convert(999)==="CMXCIX");
    console.assert(convert(1000)==="M");
    console.assert(convert(1004)==="MIV");
    console.assert(convert(2017)==="MMXVII");
    console.assert(convert(3999)==="MMMCMXCIX");
    console.assert(convert(10000)==="MMMMMMMMMM");
    console.assert(convert(16234)==="MMMMMMMMMMMMMMMMCCXXXIV");
console.assert(convert(316234)==="MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMCCXXXIV");

参考资料：Roman Numerals

【20170710】C++ 初学踩过的一些坑总结

学习记录

关于double与float

字面值默认是double, 加f才是float
如124412.0是double。124412.0f才是float
没特殊需要只用double（现代CPU可直接运算，性能与存储速度不比float慢），特殊情况考虑float和long double等

类型转换

1 / 2 = 0 // both int
1.0 /2 = 0.5 // double and int
1 / 2.0 = 0.5 // int and double

io流操作符setw()

setw()只对紧随其后的输出起作用，其他的操作如setfill()对随后的所有输出起作用。
如

cout << setfill('0')<< setw(5) << 233 << 666;

将输出

00233666

关于类的数据成员初始化代码位置问题

有且只有static成员可以且必须在类外初始化，非staitc只能在类内初始化。

非const不可以直接在声明后写初值
const数据成员不可以在构造函数体中赋值。
函数实现不管是否staitc/const可以在任何地方写函数体，但在类内会默认当做inline函数

乱七八糟的……画了个流程图结合下面示例看一下吧

流程图包含4种位置（类外初始化、声明处初始化、构造函数初始化列表处初始化、构造函数体赋值），没有出现的即为不可以。

其中构造函数体中代码，严格来讲不是初始化而是赋值，但是对于一些内置类型来说也相差无几。

关于类的数据成员初始化代码位置问题

类外初始化示例：

class c
{
private:
     static int x_;
public: 
     c(){}; 
};
static int c::x_ = 666; // correct

类内声明处初始化示例：

class c
{
private:
     const int x_ = 666; // correct
public: 
     c(){}; 
};

初始化列表示例：

class c
{
private:
     const int x_; 
public: 
     c():x_(666){}; // correct
};

函数体示例：

class c
{
private:
     int x_; 
public: 
     c():{
        this->x_ = 666; // correct
     }; 
};

堆上动态分配的类数据成员

应该定义拷贝构造函数与赋值运算符函数，否则按编译器默认行为可能造成出错（默认浅拷贝行为）

myClass(const myClass& anotherObject)
{
     // run when constructing object (this is still uninitialized)……
}

myClass& operator=(const myClass& anotherObject)
{
    // run when be assigned (this is already initialized)……
}

const对象与非const对象可以相互转换

 const int a =0;
 int b;
 b = a; //correct
 const int c = b; //correct

对于类来说，非const对象可以直接转换为const对象，而const对象转换为非const对象则需要对应的接收const对象的复制构造函数（默认会有一个，但是如果已有复制构造函数但不接收const对象则会导致无法转换）

友元函数

声明友元函数时，即使并在头文件中不使用具体类型，也要include具体文件以引入具体类型声明。

类继承体系

非虚函数不要在子类中重定义
原因：如果需要重定义，那么就不应该继承，子类与基类不构成is-a关系
非虚函数静态联编，使基类引用总调用基类函数，即使这个基类引用实际引用了一个派生类对象

从基类继承的带默认参数的函数，不要重定义其参数

重载函数注意事项

重载类构造函数

派生类永远在初始化列表中显式调用基类构造函数
复制构造函数还要注意参数要接收const对象以提供const对象到非const对象的转换

重载类型转换函数

没有返回值，且必须是非静态成员函数

//correct
myClass::operator double()
{
    return this.toDouble();
}

//error
static myClass::operator double()
{
    //……
}

//error
operator double(const myClass &object)
{
    return object.toDouble();
}

重载赋值运算符

永远应该返回*this以便使用于连续赋值
永远应该检查到自身的赋值以防错误
派生类永远显示调用基类赋值运算符，若基类没有重载赋值运算符，则应 static_cast<base_class>(*this)=rhs;
参数要接收const对象以提供const对象到非const对象的转换

const myClass& operator=(const myClass& rhs)
{
    base_class::operator=(rhs); // or static_cast<base_class>(*this)=rhs;
    if(this != &rhs)
    {
         // do something
    }
    return *this;
}
myClass c1,c2,c3;
c1 = c2 = c3;

运算符==与!=重载

总应该同时重载两者，且执行结果相反。

重载数组下标运算符

返回值类型需为非const引用类型，以便进行c[i]=xxx;的赋值操作

重载&& || ,

不要试图重载&& || ,
重载后他们便成为了普通函数，无法保证从左到右求值，&&和||使用的短路求值也无法保证。

异常处理

避免在构造函数中抛出异常
因为不会调用析构函数，而可能导致已经分配的资源无法释放，造成内存泄漏。
如果一定要抛出也要保证会安全释放，譬如使用智能指针。

catch类型最好是引用类型
对于类对象来说，引用不仅节约了拷贝对象的时间，而且防止可能异常对象会复制失败。
同时可以利用多态，而防止对象截断。

dynamic_cast操作的对象是类指针
bad_cast只有在无法相互转换的类进行dynamic_cast时才会抛出，如同级的互相转换。
如指向派生类对象的基类指针试图转换到另一派生类的指针，即试图向下类型转换（从父类转换为子类）失败，则会返回空指针而不会抛出bad_cast。

STL中异常基类及一系列派生类在<exception>中定义，而runtime_error与logic_erro还需要<stdexcept>

函数模板

在试图进行类型匹配时，不会进行类型转换。
即(T a, T b)只匹配(int, int)(double, double)等相同类型，而不会进行类型转换以匹配(int, double)
模板参数只接受编译期可确定的常量值

template <typename T>
void func(T a, T b)
{}
func(1, 2); //legal
func(1.0, 2.0); //legal
func(1.0, 2); //illegal

若为类成员函数，则需将定义放在头文件.h中以编译期实例化。

类模板

默认类型参数

可以为类模板指定默认类型参数

template <typename T = int>

但不能在函数模板中使用默认类型参数。

继承限制

类模板可以继承普通类。
类模板可以继承类模板。
普通类可以继承类模板的特化。
普通类不可以继承类模板。
总结：若子类为已实例化的类，则基类必须已实例化。

静态成员

每个模板实例类都有一份静态数据成员

嵌套类型

一个模板中的依赖于模板参数的名字被称为依赖名字。
当一个 依赖名字 嵌套在一个类的内部时，我称它为 嵌套依赖名字。
嵌套依赖名字必须显式使用typename关键字声明其为类型，否则将不被认为是类型而可能导致编译错误。

例如：

template<typename T> void f() {
    T::c* x;
 　 ...
}

这里没有使用typename声明，我们想表达的是：定义一个指针变量x，指向的数据类型是类T中的c类型。
然而编译器将认为是T中的静态成员变量c与已存在的变量x进行*运算相乘，此时编译出错。

如果要声明x为C内的nested dependent name（嵌套依赖名字），必须显式使用typename：

template<typename T> void f() {
    typename T::c* x;
 　 ...
}

Song - 「Last Of The Wilds」 - Nightwish

转载分享

[player url=’//static.moew.xyz/usr/uploads/music/Nightwish/Last Of The Wilds.mp3’ title=”Last Of The Wilds” artist=’Nightwish’ origin=’http://music.163.com/#/m/song?id=4208408']
[/player]

[player url=’//static.moew.xyz/usr/uploads/music/Nightwish/Eramaan Viimeinen.mp3’ title=”Eramaan Viimeinen” artist=’Nightwish / Jonsu from Indica’ origin=’http://music.163.com/#/m/song?id=4208408']
[lrc]
[00:01.50]Erämaan viimeinen(Jonsu)
[00:51.40]Nukkuu korpi, ja nyt 荒野沉睡依旧
[00:53.78]aatoksissain minä matkaa teen 我穿行于思绪之中
[00:56.25]Yli metsien, uinuvan veen 穿越丛林，趟过静水
[00:58.73]Kuutar taivaan yön valaisee 月之女神指引着星空
[01:01.75]Maalaa maiseman, pohjoisen siimeksen 点缀北绿荫下的万物
[01:05.76]Unta onko tää 这是梦境吗?

[01:07.71]Vai kuolema jossa palata sinne saan missä 还是死亡 那片我向往回归的地方
[01:12.14]hiillos jo luovuttaa lumen alla 星火放弃希望 甘愿被冰雪埋葬
[01:15.33]Kun astun maailmaan, erämaan aikaan 当我踏足此地 如今的荒野……
[01:21.37]Ensilumi satoi kahdesti 初雪再次降临
[01:23.82]Maalasi sieluni taulun 散落在我灵魂的画卷上

[01:26.21]Tää jylhä kauneus ja ääretön yksinäisyys 这份狂放的美好与无尽的孤独
[01:31.21]Lapsuuteni metsän, taivaan 属于我儿时的森林和天空
[01:33.22]Kaikuu se haikeus halki tän matkan 那份美好贯穿整个旅途
[01:36.48]Aamun tullen yö tarinansa kertoo 当黎明破晓 黑夜诉说着它的传奇
[01:39.96]Jylhä on kauneus ja ääretön yksinäisyyteni 狂放即美好 无尽的孤独
[01:44.74]Sitä henkeensä halajaa 正是对灵魂的渴望
[01:47.13]Kehtoni hauta, hautani paikka 我摇篮中的坟墓 埋葬我的地方
[01:50.41]Erämaan viimeinen on 是荒野的最后一隅

[02:00.90]Minne katosivat muut 生机都到哪里去了？
[02:02.95]Suon noidat, neidontornit 沼泽女巫和她们的塔楼
[02:04.78]Ja varjoissa havisevat puut 还有那幽影笼罩的针叶林
[02:08.31]Kielon istutin ikihankeen 我在冰封中埋下铃兰的种子
[02:11.77]Ja hiljaisuuden tultua luotin tulevaan 当寂静降临 我只能企盼未来
[02:16.98]Ensilumi satoi kahdesti 初雪再次降临
[02:18.71]Maalasi sieluni taulun 散落在我灵魂的画卷上

[02:21.79]Tää jylhä kauneus ja ääretön yksinäisyys 这份狂放的美好与无尽的孤独
[02:25.77]Lapsuuteni metsän, taivaan 属于我儿时的森林和天空
[02:28.77]Kaikuu se haikeus halki tän matkan 那份美好贯穿整个旅途
[02:32.21]Aamun tullen yö tarinansa kertoo 当黎明破晓 黑夜诉说着它的传奇
[02:35.55]Jylhä on kauneus ja ääretön yksinäisyyteni 狂放即美好 无尽的孤独
[02:40.46]Sitä henkeensä halajaa 正是对灵魂的渴望
[02:42.66]Kehtoni hauta, hautani paikka 我摇篮中的坟墓 埋葬我的地方
[02:46.04]Erämaan viimeinen on 是荒野的最后一隅

[03:59.54]Tää jylhä kauneus ja ääretön yksinäisyys 这份狂放的美好与无尽的孤独
[04:03.33]Lapsuuteni metsän, taivaan 属于我儿时的森林和天空
[04:05.96]Kaikuu se haikeus halki tän matkan 那份美好贯穿整个旅途
[04:09.57]Aamun tullen yö tarinansa kertoo 当黎明破晓 黑夜诉说着它的传奇
[04:13.04]Jylhä on kauneus ja ääretön yksinäisyyteni 狂放即美好 无尽的孤独
[04:17.81]Sitä henkeensä halajaa 正是对灵魂的渴望
[04:20.07]Kehtoni hauta, hautani paikka 我摇篮中的坟墓 埋葬我的地方
[04:23.49]Erämaan viimeinen on 是荒野的最后一隅
[04:27.29]Tää jylhä kauneus ja ääretön yksinäisyys 这份狂放的美好与无尽的孤独
[04:30.91]Lapsuuteni metsän, taivaan 属于我儿时的森林和天空
[04:33.88]Kaikuu se haikeus halki tän matkan 那份美好贯穿整个旅途
[04:37.40]Aamun tullen yö tarinansa kertoo 当黎明破晓 黑夜诉说着它的传奇
[04:40.88]Jylhä on kauneus ja ääretön yksinäisyyteni 狂放即美好 无尽的孤独
[04:44.78]Sitä henkeensä halajaa 正是对灵魂的渴望
[04:49.08]Kehtoni hauta, hautani paikka 我摇篮中的坟墓 埋葬我的地方
[04:52.03]Erämaan viimeinen on 是荒野的最后一隅
[/lrc]
[/player]

[player url=’//static.moew.xyz/usr/uploads/music/如我西沉.mp3’ title=”如我西沉” artist=’满汉全席’ origin=’http://music.163.com/#/m/song?id=450532474']
[/player]

请我喝杯咖啡吧~

支付宝
微信