月度归档：2018年06月

NOIP2017 普及组第三道 棋盘

发表评论

这题写的异常难受……先想着用动态规划，难受死了，才20分。然后后来再看题解，用记忆化BFS，写的也难受，主要是太难想，终于AC了。开心~

写了有6、7个钟头吧。挺羞愧的。。。我写这种题怎么能这么长时间呢……

所有测试点全部0ms。

成就感极高。

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
#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
struct qs { //Convenient for passing parameters
    int tx, ty, os, rs, sc; //destination's coordinate (x,y) :tx,ty ;previous point::original status of color,real status of color :os,rs ;previous point's score:sc.
    qs(int tx1, int ty1, int os1, int rs1, int sc1) {
        tx = tx1; ty = ty1; os = os1; rs = rs1; sc = sc1;
    } //the init of struct
};
int m, n;
int arr[105][105], f[105][105]; //arr stores the color(status) of all coordinate; f stores the least gold the person will spend
int shiftx[4] = { 1,-1,0,0 }, shifty[4] = { 0,0,1,-1 }; //shifts for the coordinate
queue<qs> q;
void execute(qs o) {
    //Calculate New Score
    //Compare Which one is smaller
    //Only when the new one is smaller one,will the program insert the queue
    int nscore = 0x7fffffff;
    if (o.rs != -1 && arr[o.tx][o.ty] != -1) { // C2C(R2R/Y2Y/R2Y/Y2R) {"C"："Color","2":"To","R":"Red","Y":"Yellow"};
        if (o.rs == arr[o.tx][o.ty])nscore = o.sc; // R2R/Y2Y
        else nscore = o.sc + 1; // R2Y/T2R
        if (nscore < f[o.tx][o.ty] || o.tx==1&&o.ty==1) { //o.tx==1&&o.ty==1 is to create an entrance for the inital queue push
            f[o.tx][o.ty] = nscore;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], arr[o.tx][o.ty], arr[o.tx][o.ty], nscore));
        }
    }
    else if (o.os != -1 && arr[o.tx][o.ty] == -1) { // C2N
        if (o.os == 0 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Red
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
        }
        else if (o.os == 1 && o.sc + 2 < f[o.tx][o.ty]) { //Assume that the temporary color of current cell is Yellow
            f[o.tx][o.ty] = nscore = o.sc + 2;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 1, nscore));
            nscore += 1;
            for (int i = 0; i < 4; i++)q.push(qs(o.tx + shiftx[i], o.ty + shifty[i], -1, 0, nscore));
        }
    }
}
int main() {
    memset(arr, -1, sizeof(arr));
    memset(f, 0x7f, sizeof(f));
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        arr[x][y] = c;
    }
    f[1][1] = 0;
    q.push(qs(1, 1, arr[1][1], arr[1][1], 0));
    while (!q.empty()) {
        qs cur = q.front();
        q.pop();
        if (cur.tx > m || cur.ty > m || cur.tx < 1 || cur.ty < 1)continue;
        execute(cur);
    }
    cout << (f[m][m] == 0x7f7f7f7f ? -1 : f[m][m]) << endl;
}

NOIP2017普及组前两道水题

发表评论

T1

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    long long re = 0.2*a + 0.3*b + 0.5*c;
    cout << re;
}

T2

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>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string s1, string s2) {
    if (s1.length() != s2.length())return s1.length() < s2.length();
    return s1 < s2;
}
int main() {
    int n, q;
    vector<string> arr;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end(), cmp);
    for (int i = 1; i <= q; i++) {
        int tmpi;
        string tmp;
        cin >> tmpi >> tmp;
        bool flag = false;
        for (vector<string>::iterator ptr = arr.begin(); ptr != arr.end(); ptr++) {
            if (ptr->length() - tmp.length() <=1e9 && ptr->substr(ptr->length() - tmp.length()) == tmp) {
                flag = true;
                cout << (*ptr) << endl;
                break;
            }
        }
        if (!flag)cout << "-1" << endl;
    }
}

洛谷 P1120 小木棍 ［数据加强版］

发表评论

写的很绝望……看了三遍所有题解仍然69……

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
#include<bits/stdc++.h>
using namespace std;
int n, sum = 0;
int lens[100] = { 0 };
bool visited[100] = { false };
int sums[100] = { 0 };
int o_min = 0, o_max;
vector<int> divisors;
int min_len;
inline bool dfs(int curpos, int curvalue, int groups){
    if (curvalue == min_len){
        if (groups == sum / min_len - 1)return true;
        else{
            int i;
            for (i = 1; i <= n; i++){
                if (!visited[i])break;
            }
            assert(i != n + 1);
            visited[i] = true;
            bool flag = dfs(i, lens[i], groups + 1);
            visited[i] = false;
            return flag;
        }
    }
    bool flag_finished = false;
    for (int i = curpos + 1; i <= n; i++){
        if (curvalue + lens[n] > min_len || curvalue + sums[i]<min_len)break;
        if (visited[i] || curvalue + lens[i] > min_len)continue;
        visited[i] = true;
        if (dfs(i, curvalue + lens[i], groups))flag_finished = true;
        visited[i] = false;
        if (flag_finished)return true;
        for (int j = i + 1; j <= n; j++){
            if (lens[j] != lens[i]){
                i = j - 1;
                break;
            }
        }
    }
    return false;
}
inline bool process(int min_length){
    min_len = min_length;
    visited[1] = true;
    bool flag = dfs(1, lens[1], 0);
    visited[1] = false;
    return flag;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> lens[i];
        if (lens[i] > 50){
            i--;
            n--;
        }
    }
    sort(lens + 1, lens + n + 1, greater<int>());
    for (int i = 1; i <= n; i++){
        o_min = max(o_min, lens[i]);
        sum += lens[i];
    }
    for (int i = n; i >= 1; i--){
        sums[i] = sums[i + 1] + lens[i];
    }
    o_max = sum;
    for (int i = o_min; i <= o_max / 2; i++){
        if (o_max%i == 0)divisors.push_back(i);
    }
    divisors.push_back(o_max);
    for (int i = 0; i < divisors.size(); i++){
        if (process(divisors[i])){
            cout << divisors[i];
            break;
        }
    }
}

20180811日更新：已经AC。
这题真的很麻烦，之前做过一回，69分放弃了，今天又重新做，改到了78AC22TLE，又看题解里的优化终于改到了AC。
题解：https://www.luogu.org/blog/complexity/solution-p1120
https://www.luogu.org/blog/cm-nanyi2018/solution-p1120
https://www.luogu.org/blog/ogawa/solution-p1120

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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<functional>
using namespace std;
int n,lens[70],curLen,totSum=0;
int bucket[60],lst[60],lstPtr=0;
vector<int> possibleLen;
inline int check(){
    int i;
    for(i=1;i<=lstPtr;i++)if(bucket[lst[i]]!=0)return i;
    return i;
}
inline bool dfs(int lstPos,int len){//have already added lst[lstPos] before entering this recursive function
    if(len==totSum||len==totSum-curLen)return true;
    if(len%curLen==0){
        int i=check();
        bucket[lst[i]]--;
        bool flag=dfs(i,len+lst[i]);
        bucket[lst[i]]++;
        return flag;
    }
    int curRemain=curLen-len%curLen;
    for(int i=lstPos;i<=lstPtr;i++){
        if(lst[i]>curRemain||bucket[lst[i]]==0)continue;
        bucket[lst[i]]--;
        if(dfs(i,len+lst[i])){
            bucket[lst[i]]++;
            return true;
        }
        bucket[lst[i]]++;
        if(curRemain==lst[i])return false;
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int maxV=0;
    for(int i=1;i<=n;i++){
        cin>>lens[i];
        if(lens[i]>50){
            i--;n--;
            continue;
        }
        bucket[lens[i]]++;
        maxV=max(maxV,lens[i]);
    }
    for(int i=50;i>=1;i--)if(bucket[i]!=0)lst[++lstPtr]=i;
    for(int i=1;i<=n;i++)totSum+=lens[i];
    for(int i=maxV;i<=totSum/2;i++)if(totSum%i==0)possibleLen.push_back(i);
    possibleLen.push_back(totSum);
    bucket[lst[1]]--;
    for(int i=0;i<possibleLen.size();i++){
        curLen=possibleLen[i];
        if(dfs(1,lst[1])){
            cout<<curLen;
            return 0;
        }
    }
}

[USACO1.2]命名那个数字 Name That Number

发表评论
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
#include<bits/stdc++.h>
using namespace std;
vector<string> Dict; //用Dict存放所有字典中的名字
string str; //给定的编号
const char * str_trans = "2223334445556667 77888999"; //使用该C-风格字符串来存放A-Z(除去Q和Z这24个字母所对应的数字)
int main(){
    ios::sync_with_stdio(false); //只用cin/cout加快IO速度
    cin >> str;
    string tmp;
    while (cin >> tmp){ //将后面所有的字符串循环读入到tmp中，再放到Vector尾，(cin>>tmp)即可以起到读入字符串的作用，也可以起到判断文件是否到达末尾。详情请阅读C++ Primer Plus。
        Dict.push_back(tmp);
    }
    int len = str.length();
    bool global_flag = false;
    for (int i = 0; i < Dict.size(); i++){ //遍历所有字典元素，因为字典元素少
        if (len != Dict[i].length())continue; //剪枝，如果字符串位数不一样就没有必要比较。
        bool flag = true;
        for (int j = 0; j < len; j++){
            if (str_trans[Dict[i][j] - 'A'] != str[j]){ //比对字典中每个字符对应的数字是否与输入的每个数字相同
                flag = false; //不相同直接跳出循环
                break;
            }
        }
        if (flag){ //相同则输出该单词
            cout << Dict[i] << endl;
            global_flag = true;
        }
    }
    if (!global_flag){ //如果没有一个单词符合要求，就输出NONE。
        cout << "NONE" << endl;
    }
}

简易python socket通信

发表评论

Server:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#coding=utf-8
import socket
HOST='127.0.0.1'
PORT=52314
s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
s.bind((HOST,PORT))
s.listen(1)
while 1:
    conn,addr=s.accept()
    print 'The client on %s is connecting the server.' % str(addr)
    while 1:
        data=conn.recv(1024)
        if data=="\q":
            print 'The client is going to offline.'
            conn.close()
            break
        else:
            print data
conn.close()
s.close()

Client:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#coding=utf-8
import socket
HOST = '127.0.0.1'
PORT = 52314
try:
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect((HOST, PORT))
    while 1:
        cmd = raw_input()
        if cmd == "quit":
            print 'Bye!'
            s.sendall("\q")
            break
        s.sendall(cmd)
finally:
    s.sendall("\q")
    s.close()

说说用树莓派配置NAS的过程

发表评论

主要是给自己留个参考。
用的树莓派是B+，原来有无线网卡，和一块160G的SATA硬盘，网上买了个SATA转USB的绿联硬盘盒。然后就开工了。
烧好SD卡。在/boot引导里新建文件ssh，开启ssh连接。默认用户名密码：pi raspberry。然后把debian源换成aliyun。然后apt update。装个frp内网穿透、nginx提供http服务、vsftpd提供ftp服务。就OK了。下面列几个不好配置的点。将来如果再配置就不用麻烦半天了。

1、frp想要搞成开机启动，必须在/etc/rc.local中frp启动之前加上sleep 60好让网卡等外围设备初始化完毕，否则连不上网frp自动退出，就要人工手动了。
2、vsftpd的配置文件列一下：

listen_ipv6=YES
local_enable=YES
write_enable=YES
secure_chroot_dir=/var/run/vsftpd/empty
pam_service_name=ftp
rsa_cert_file=/etc/ssl/certs/ssl-cert-snakeoil.pem
rsa_private_key_file=/etc/ssl/private/ssl-cert-snakeoil.key
ssl_enable=NO
userlist_enable=YES
userlist_deny=NO
userlist_file=/etc/vsftpd.allowed_users
ftpd_banner=Welcome to NAS service.
local_root=/var/www/DISK
use_localtime=yes
pasv_enable=yes
pasv_min_port=5000
pasv_max_port=5050
anonymous_enable=NO
chroot_local_user=NO
chroot_list_enable=YES
chroot_list_file=/etc/vsftpd.chroot_list
allow_writeable_chroot=YES

/etc/vsftpd.chroot_list和/etc/vsftpd.allowed_users都写ftp用户名就可以了。然后添加ftp用户需要useradd -d /var/www/DISK -s /sbin/nologin。就是这样。

高中三年总结

2条回复

想写什么，但又仿佛没什么话可写。还有一些内容由于我个人的表达问题或是其他原因没有充分展现出来，希望谅解。下面一些地方所写的感悟与思考都是一些个人的浅见，如有错误恳请批评指正。
谨以此文献给各位帮助过我的老师，各位同学和自己
时光荏苒，高中生活真可谓转瞬即逝。我们常说“十年弹指一挥间”，只不过是大段时间度过后，我们现在看起来过去的时间不值一提了而已，而非真的弹指一挥间就过去了。就像我经常和父母开的玩笑一样：“我都弹了十个响指了，怎么还没过去十年啊？”高中三年，是我们青春时光中最美好的三年，也是最值得我们珍重的三年。每个人都有着自己美好的回忆，也有痛苦的过往。无论你是如何对待、度过这三年的，这三年终将成为你毕生难忘的经历。
回望这三年，我的文化课之路一直走的基本上可以说是没有大风大浪。最好的时候考过年级前十，最差的时候年级一百多。到了高三成绩就稳定在年级20-40名之间。我个人对于这几科的学习可谓是不喜不厌（也许高一高二不喜欢语文，但高三有所转变），只是跟着老师的进度走，只是完成老师平时的作业，上课认真听讲。高中基本上就没报过文化课的课外辅导课程。所以我还算差不多的成绩就全拜我们几位好老师所赐。我在此真诚的感谢各位老师（给各位老师一个热烈的拥抱٩(๑^o^๑)۶）。语文贾老师和我讨论、辩论问题，使我的思想境界得到提高。可谓是“拔除了草地里资本(自由)主义的大毒草”。数学老师赵老师和曾经的班主任白老师，认真的指导我们问题，安慰我们的小情绪。现在的英语班主任李老师，认真为我们准备各种英语考试材料，为我们准备各种非常管用的作文套路，在我NOIP2017出师不利时加以安慰。物理老师赵老师，作为我们的年纪主任，除处理年级工作之外，还认真备好两个实验班的物理课程，耐心回答我们的问题。化学夏老师，看部分同学的化学理综选择题差，特意为我们出了N套化学卷子选择题；除此之外，有问题找夏老师倾诉时，夏老师的安慰让自己有了坚强的后盾。生物王老师，平时上课风趣幽默，课下还给我们小零食吃(^v^)。正是因为有这几位老师，我们两个班的全体同学才能够取得更好的成绩。我再一次向各位用心教育我们的老师表示感谢。
三年来，同样让我获益匪浅的还有是我所热爱的计算机专业。它不仅提供了我一种在紧张时消遣压力的途径，给我带来了成就感，也给我带来了至关重要的副产品——计算机比赛得奖。最重要的两种比赛奖励可谓是可遇而不可求：全国中小学生电脑制作比赛一等奖和信息学奥赛省级二等奖。有了它们便有了一份自主招生初审的保障，使我可能有机会更进一步进入更好的大学进行深造。在此特别感谢帮助过我的原计算机老师赵老师和八十中的竞赛老师贾老师、北京理工大学的罗老师，有了你们我的计算机之路才走的更加顺畅！
三年转瞬即逝，一下子就来到了高考，你是否在高考之前紧张过？坦诚的说，我是。而且这焦虑一直持续在两天之中。一直想的都是高考结束以后有多好多好，恨不得时间加速，立马跳到高考之后。考试过去之后大部分人都会发现好像变得特别空虚，不知道该做什么好了。其实这种现象对我来说还并不严重吧，毕竟我还有自己的方向。各位同学又是怎么样的呢？其实高考早一点晚一点都无所谓的，晚一点，就算是晚了一年，复习的不就更充分一点，不是吗？没有高考的同学，明年高考，加油！
当下我们已经步入“后高考时代”，希望每个解放的同学都能够放下高考的枷锁，重新开始一个崭新的自己，勇敢的面对未来！
在此，最后，我斗胆发一些”傻白甜”的自己的亲身感悟，我自认为可以算得上是对同学以后人生之路的建议。同学如果认为我说的有道理，可以汲取，如果没有也可完全不理。欢迎以客观理性的态度同我进行讨论！
1，不忘初心：初心是最重要的，遍观整个世界，有多少人是由于失去初心而走上违法犯罪道路的，又有多少人是由于被社会抹去了棱角，而丢失了自己的初心的。”不忘初心，方得始终。”衷心希望大家都能够保持自己纯洁良好的品性，让自己到达成功的彼岸！
2，做好最棒的自己：做任何一件你想要做好的事情，一定要尽全力完成，这样你一定不会后悔。若不尽全力，将来就有可能后悔。
3，注意大语文观，关心政治：这条其实是我最想说的一条。前两条大家鸡汤早就喝够了，有可能根本不需要。这一条可以算是我自己个人在高三阶段总结出来的吧。高一高二语文学的不是很好，高三在努力之中在意识到了语文的重要性。我所说的”大语文”范围泛指、涵盖了语文科目本身、政治、历史以及地理最次之。语文语言文字除了满足日常需要之外，本身有可能没有什么可学的，但是最重要的是古文、小说其中所蕴含的做人的道理，以及其中任何与我们现实生活相通的东西。对于硬生生的考阅读运用了什么写作手法等这种问题，我是比较不以为然的。真正有真情实感的作家写作时从未想着我要在文章中使用任何写作手法，一切东西都是真情实感的流露，只不过是语言学家把它们强硬加以分类并运用到语文试卷中用来拉开差距的吧。语文，政治，历史是有机的结合在一起的，它们相辅相成互相影响，这也就是为什么说文科生不担心语文的原因了。因为它们相辅相成，是相通的。我们应该去探求与了解的是文字背后的做人之理，而非浮于表面的什么写作修辞手法，我感觉我是记不住的。而当前大语文观最应注重的则是政治，就像今年高考写作题目”新时代新青年——谈在祖国发展中成长”，你不懂点政治都不会写。在各种媒体声音日益交杂的今天，各方主流媒体代表的势力观点并不相同，自媒体获取眼球吸引焦点的情况也不在少数。作为新一代青年的我们如果想要努力奋进，奋发向上，一定要具有独立思考的能力，不为任何派别的媒体所迷惑，思考事物的本质。开阔眼界，去外面看一看，对于自己的思想，要把握好两个底线：我们的中国是不容诋毁的，权利是不能受到侵犯的；相信政策的制定者是基于善意制定的，出现的错误是执行者所犯。能够掌握好这两条，再去筛选信息，关注信息的真实性，并加以思考，就非常好了。
在本篇文章的最后，祝还要参加自主招生考试的各位同学接下来的考试一帆风顺。再一次对所有帮助过我的老师表示衷心的感谢。
几张个人照片和老师的合照，毕业照等照片：
密码提示：学校(两个汉字的拼音)+班级(阿拉伯数字)+博主姓名拼音