Hairaa's Blog

Record

0%

Posted on Edited on

2019程序设计能力实训第二次机考题解

题目链接：题目还没有公开

机考环境：CodeBlocks

编程语言：C++

#A. 点对

描述：从输入的偶数个数字里面两两选择，使得所有数对内部差的和为最小。

思路：排序后相邻的数差值总是最小的，所以只需排序并两两选择相邻数字即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

typedef long long int ll;

using namespace std;

int main()
{
    ll num,nums[100005] = {}, sum = 0;
    cin>>num;
    for(ll i = 0;i < num;i++){
        cin>>nums[i];
    }
    sort(nums,nums+num);
    for(ll i = 0;i < num;i+=2){
        sum += nums[i + 1] - nums[i];
    }
    cout<<sum<<endl;
}
#B. QR Code

描述：

​ 比较繁琐的字符串与进制处理题。

​ 提供一个十进制表示的字符串s，将其按每3位转换为10位的二进制串，最后若剩余1位或2位则转换为4位或7位二进制字符串，叠加得到字符串res。

​ 最后的输出：”0001”+输入的s的长度对应的10位二进制字符串+res。

相关方法：

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
56
57
#include <iostream>
#include <string>
using namespace std;

int StrtoDec(string temp){		//十进制字符串转十进制数
    int Dec = 0, weight = 1;
    for(int i = temp.size() - 1;i>=0;i--){
        Dec+=weight*int(temp[i]-'0');
        weight*=10;
    }
    return Dec;
}

string DectoBin(int Dec,int num){	//十进制数转二进制
    string bin = "";
    int index = num - 1;
    for(int i = 0;i<num;i++){
        bin+='0';
    }
    while(Dec){
        if(Dec%2){
            bin[index]='1';
        }
        Dec /= 2;
        index--;
    }
    return bin;
}

int main()
{
    string s, temp, res = "";
    int tag = 0,length = s.size(),index; //index指向末尾不成3个一组的一组数字的开头
    cin>>s;
    index = s.size()-s.size()%3;
    for(int i = 0;i<index;i++){		//先处理三个一组的位
        temp += s[i];
        if(i % 3 == 2){		//每三位生成一个10位二进制串
            int Dec = StrtoDec(temp);
            res+=DectoBin(Dec,10);
            temp = "";
        }
    }
    for(int i = index;i<s.size();i++){	//如果剩下1、2位则加到temp上
        temp+=s[i];
    }
    if(temp.size()==1){	//处理末尾1位的情况
        int Dec = StrtoDec(temp);
        res+=DectoBin(Dec,4);
    }
    else if (temp.size()==2){	//处理末尾2位的情况
        int Dec = StrtoDec(temp);
        res+=DectoBin(Dec,7);
    }
    cout<<"0001"<<DectoBin(s.size(),10)<<res<<endl;
    return 0;
}
#C. 浮点数加法

描述：实现输入所要求精度的浮点数加法。输入的字符串可能会省略小数点、小数点前后的0。末尾四舍五入。

思路：

​ 首先需要做字符串处理，注意没有小数点、省略小数点前后的0的情形。

​ 随后，按精度对小数点后的位数进行分割或补充，原位数>精度时截取精度+1位（原因是末尾需要四舍五入，要多算一位），原位数<精度时补0）。

​ 分别用大整数方法加整数部和小数部。首先处理小数部末尾的进位，其次处理小数部头部的进位（看位数是否是精度+1，如果大于精度+1则说明有进位）。如进位则将小数部的头部（[0]索引）加到整数部上并输出头部后的尾部（别忘了输出时删除用于四舍五入的末尾）。如无进位则输出小数部并剔除用于四舍五入的末位。

​ 还有一些暗坑没有发现，目前可以A过91分。

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <string>
#include <regex>
using namespace std;

string add(string s1, string s2) {	//大整数加法
    string s;
    int len1 = s1.size(), len2 = s2.size();
    if (len1 < len2) {
        for (int i = 1;i <= len2 - len1;++i) {
            s1 = "0" + s1;
        }
    }
    else {
        for (int i = 1; i <= len1 - len2;++i) {
            s2 = "0" + s2;
        }
    }
    len1 = s1.size();
    int Plus = 0, tmp;
    for (int i = len1 - 1;i >= 0;--i) {
        tmp = s1[i] - '0' + s2[i] - '0' + Plus;
        Plus = tmp / 10;
        tmp %= 10;
        s = char(tmp + '0') + s;
    }
    if (Plus) {
        s = char(Plus + '0') + s;
    }
    return s;
}

string split_int(string a,int index) {  //从字符串中分割出整数部
    string integer = "";
    if(index == -1){       //省略小数点的情形
        return a;
    }
    else if (index == 0){   //省略整数的情形
        return "0";
    }
    else{
        for(int i = 0;i<index;i++){
            integer+=a[i];
        }
    }
    return integer;
}

string split_flout(string a,int index) {	//从字符串中分割出小数部
    string flout = "";
    if(index == -1){
        return "0";
    }
    else if (index == a.size()-1){     //省略小数部分的情形
        return "0";
    }
    else{
        for(int i = index + 1; i<a.size();i++){
            flout+= a[i];
        }
        return flout;
    }
}

int find_index(string s){
    for(int i = 0;i<s.size();i++){
        if(s[i]=='.'){
            return i;
        }
    }
    return -1;
}

string format_flout(string s, int n) {      //规范化小数位
    int len = s.size();
    if (n >= len) {      //精度>原小数位数，补零
        for (int i = 0;i < (n - len + 1);i++) {
            s += "0";
        }
    }
    else {       //精度<=原小数位数，截断为长度为精度+1的字串
        string temp = "";
        for (int i = 0;i < n + 1;i++) {
            temp += s[i];
        }
        s = temp;
    }
    return s;
}

int main()
{
    string a, b, int_a, int_b, flout_a, flout_b, sum_flout, sum_int, sum = "", Plus = "";
    int n, index_a, index_b;
    cin >> a >> b >> n;

    index_a = find_index(a);    //记录小数点位置
    index_b = find_index(b);

    int_a = split_int(a,index_a);	//a的整数部
    flout_a = format_flout(split_flout(a,index_a), n);	//a的小数部

    int_b = split_int(b,index_b);	//b的整数部
    flout_b = format_flout(split_flout(b,index_b),n);	//b的小数部

    sum_flout = add(flout_a, flout_b);
    sum_int = add(int_a, int_b);

    if (sum_flout[sum_flout.size() - 1] > '4') {		//末尾>4则四舍五入
        sum_flout = add(sum_flout, "10");
    }

    int sum_flout_len = sum_flout.size();
    if (sum_flout_len > n + 1) {	//如果小数部长度大于精度+1则有进位
        Plus += sum_flout[0];       //标记进位
        sum_int = add(sum_int, Plus);   //把小数部溢出的进位加给整数部
        for (int i = 1;i < n + 1;i++) { //从第二位开始输出（第一位溢出进位了）
            sum += sum_flout[i];
        }
    }
    else {
        for (int i = 0;i < n;i++) {
            sum += sum_flout[i];
        }
    }
    if(sum_int[0]=='0'&&sum_int.size()>1){  //sum_int有前导零
        string temp = "";
        for(int i = 0;i<sum_int.size();i++){
            if(sum_int[i]!='0'){
                temp+= sum_int[i];
            }
        }
        sum_int = temp;
    }
    cout << sum_int << "." << sum << endl;
}
#D. 计算步数

描述：这道题目前还不会。

#E. 挑数字

描述：在 n 个正整数中挑选 m 个数。要使这 m 个数与其中最大的一个数之间的差值之和最小化。

思路：跟2018年实训第一次考试的圆柱体排序那道题原理一样。还有10分是数组超大了，还不知道怎么解决。

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
#include <iostream>
#include <algorithm>
typedef long long int ll;

using namespace std;

int main()
{
    ll n,m,nums[100005],min_num;
    cin>>n>>m;
    for(ll i = 0;i < n;i++){
        cin>>nums[i];
    }
    sort(nums,nums+n);
    min_num = (m-1)*nums[m-1];  //随便初始化一个
    for(ll i = 0;i < n-m+1;i++)
    {
        ll sum = (m-1)*nums[i+m-1];
        for(ll j = 0;j < m-1;j++){
            sum-=nums[j + i];
        }
        if(sum < min_num)
        {
            min_num = sum;
        }
    }
    cout<<min_num<<endl;
}

Posted on

控制玩手机的第一周！（7/19-7/25）

​ 虽然终于开始放暑假了，但是由于大量课程需要返校考试的缘故仍然需要控制手机的使用时间，以达到较好的学习效果。

​ 实际上，控制屏幕使用时间也并非应该是期末周或是需要集中学习时才采取的策略。为了平日里能够更加专注于自我提升或者娱乐，减少手机的使用时间是必要的。

​ 然而，为什么说减少手机使用时间可以更加专注于娱乐？在观察了过去三周的手机屏幕使用数据后，得出了以下的结论：

​ 每周的总使用时间达58-69小时，日均8-10小时。占据比例最大的是社交类软件（57%-62%），总屏幕使用时间占据每周总时间（7*24h）的近34%-41%。

​ 可以认为一周除去睡觉的时间外大部分时间都在使用手机，而大部分时间都用在了浏览社交软件上，实际上这并不能达到良好的娱乐体验，只是在无意义地刷新与浏览碎片化的信息。

在这里插入图片描述

​ 出于上述的背景和原因，我对手机使用时间进行了控制。具体的措施是：社交软件使用时间限制在3小时/每天之内，12：30-7：00之间禁用手机。（这一功能可以通过iOS系统中的“屏幕使用时间”功能来实现）

​ 成果如下图所示，由于控制使用时间的举措从周二开始，因此社交类软件总使用时间并未能够降至24小时之内。但较其上周已经有了显著的降低，总时间降幅达42%。

在这里插入图片描述

​ 实际上，要想做到社交软件限制在每天3小时内是有一定难度的。在AppStore中，微信、小红书、微博、知乎等软件都被归类于社交软件。

​ 作为一名新晋追星族，此前从未下载过的小红书与微博成为了我近期了解偶像动态必备的App。尤其是微博，每天会数次访问以查看快乐女士李斯丹妮的微博及衍生言论、图片等。在控制时间之前，我常常会仔细浏览粉丝群（目前已经是一个3000人的大群了，消息频率极高）中的消息，查看Timeline上的小视频、微博等碎片化信息。

​ 微信已经是现代人难以离开的社交软件，许多人（俺）因为担心错过消息而频繁检查微信消息，顺便浏览公众号、朋友圈等。为了控制手机的使用，我再次关闭了朋友圈。（此前在正式学期期间常常会关闭朋友圈数周之久以专注于学习。）

​ 知乎上新奇的知识与讨论常能让人沉迷其中，但在我意识到知乎会让人不断浏览无用的知识后，知乎App在我的手机中已经近3年没有长期留存过了。（刚放假想轻松几天时可能会下载）

​ 在设定了手机使用时间的限制之后，最大的难题就是将社交软件使用时间限制在3小时之内。无意识地浏览信息会让使用时间在不知不觉中骤增，导致在下午或傍晚时手机就提醒你只剩5分钟可以使用社交软件，然而剩余的时间并不足以维系当日正常的社交活动。

​ 为了达到社交<3小时的目标，我选择每次拿起手机后急促地处理微信未读消息、简单浏览微博（只看快乐女士李斯丹妮本人的微博是否更新，不关心衍生话题与粉丝群）、关闭朋友圈。这样的举措使得我的手机使用时间大大减少，同时在一定范围内限制了我熬夜的恶习。

​ 当然，手机上设定的限制只需要简单操作就可以取消，要完全借助外力戒除手机的滥用是非常困难的。

​ 如果你也想控制手机的使用的话，不妨想一想你为什么要这样做？应该如何行动，又如何能够保持自律不打破自己设定的规则呢？

​ 对我而言，原因和行动已在前文中阐释。而自律的方法，或许就是保持规则的神圣感，在任何情况下都不试图去打破它。

Posted on

EOJ-2017程序设计能力实训题解-1（1001-1005）

题目链接：https://acm.ecnu.edu.cn/contest/43/

本次更新的题目主要涉及到的知识点有语言练习、排序和表达式。难度在该题集中都为naive。

由于题目难度不算太高，本期题解将会对题目进行简要讲解。

本地测试环境：Visual Studio 2019

编程语言：C++

#1001. A+B Problem

描述：最基础的语言题。

难点：可能在于如何在不知道行数的情况下输入，使用下面的语句即可实现。

1
while(cin>>a>>b)
#1002. 几位数？

描述：常规的做法应该是循环整数求位数，在本例中可以直接使用获取字符串长度的方法。
相关方法：

1
2
string str;
int length = str.size();	//获取字符串长度的方法
#1003. 计算a的n次方

描述：虽然在本题中常规方法并不会导致超时，但常规方法时间复杂度较高。因此将以快速幂方法来实现。

讲解：

在这里插入图片描述

​ 通过上述公式可知，当$n$为偶数时其规模可以降至一半。结合递归方法与位运算，可写出快速幂代码。

​ 其中，通过位与运算来实现判断奇偶，右移操作来实现除2可以提升性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long int ll;

ll pow(ll a, ll n) {
	if (n == 0) {
		return 1;
	}
	if (n & 1) {	//n为奇数时
		return (a * pow(a, n - 1));
	}
	else {
		return (pow(a, n >> 1) * pow(a, n >> 1));
	}
}
#1004. 值班

描述：只需判断是否有30条记录，简单的计数题。

#1005. SQUINT

描述：求平方根，同时需要向上取整。

讲解：

​ 0.取整方法：ceil()向上取整，floor()向下取整。

​ 1.使用库函数sqrt求平方根，需要math.h头文件。

​ 2.使用二分法求平方根。

1
2
3
4
5
6
7
8
9
while(max-min>0.1){	//精度
        if (mid * mid > num) {
            max = mid;
        }
        else {
            min = mid;
        }
        mid = (max + min) / 2;
    }

​ 3.使用牛顿迭代法求平方根

在这里插入图片描述

在这里插入图片描述

img

​ 详细求解过程与代码稍后更新。（先update一个版本再说哈哈）

​ LaTex公式总是渲染失败，尝试了网上的方法也没有用(⊙﹏⊙)，只好把公式截图发出来啦。

Posted on

Hello Hairaaa！

1
print("Hello Hairaaa!")

在拖延了很长时间之后，终于决定开通自己的博客啦。

不定期更新，内容可能包括技术&美食&五花八门的经验分享。

加油，共勉！(ง •_•)ง