CCF CSP计划

本文记录CCF-CSP算法题解。

注：#include<bits/stdc++.h>包含所有的C++头文件。

2018年

12月

201812-1 小明上学

1
r, y, g = map(int, input().split())
2
n = int(input())
3
t = 0
4
# 出发
5
for i in range(n):
6
    path = list(map(int, input().split()))
7
    if path[0]==0 or path[0] == 1:  # 经过道路/等红灯
8
        t += path[1]
9
    elif path[0] == 2:  # 等黄灯（之后还要等红灯）
10
        t += path[1] + r
11
print(t)

201812-2 小明放学

1
r, y, g = map(int, input().split())
2
n = int(input())
3
total_time = 0
4
# 出发
5
for i in range(n):
6
    m_type, m_time = map(int, input().split())
7
    if m_type == 0: # 经过道路
8
        total_time += m_time
9
        continue
10
    # 转成距绿灯结束的时间
11
    if m_type == 1: # 红灯
12
        m_time += g
13
        m_type = 3
14
    if m_type == 2: # 黄灯（之后还要等红灯）
15
        m_time += (r + g)
16
        m_type = 3
17
    if m_type == 3: # 绿灯
18
        pass
19
    now_time = (m_time - total_time) % (g+r+y)  # 当前循环距绿灯结束的时间
20
    if now_time > g:  # 经过该路口时不为绿灯
21
        total_time += (now_time - g)  # 加上要等待的时间
22
print(total_time)

201812-3 CIDR合并

201812-4 数据中心

201812-5 管道清洁

9月

201809-1 卖菜

1
n = int(input())
2
p = list(map(int, input().split()))  # 0~n-1
3
o = [0]*n
4
o[0] = int((p[0]+p[1])/2)
5
o[-1] = int((p[-2]+p[-1])/2)
6
for i in range(1, n-1):
7
    o[i] = int((p[i-1]+p[i]+p[i+1])/3)
8
for i in o:
9
    print(i, end=' ')

201809-2 买菜

1
n = int(input())
2
H = []  # 小H装车时间段
3
W = []  # 小W装车时间段
4
for i in range(n):
5
    H.append(tuple(map(int, input().split())))
6
for i in range(n):
7
    W.append(tuple(map(int, input().split())))
8
tlate = max(H[-1][-1], W[-1][-1])  # 最晚时间点
9
timecnt = [0]*tlate  # 时间点计数
10
for s, e in H:
11
    for i in range(s, e):
12
        timecnt[i] += 1
13
for s, e in W:
14
    for i in range(s, e):
15
        timecnt[i] += 1
16
print(timecnt.count(2))

201809-3 元素选择器

1
n, m = map(int, input().split())  # 文档行数、待查询选择器个数
2
doc = []
3
sel = []
4
# 结构化文档内容
5
for i in range(n):
6
    doc.append(input())
7
# 待查询的选择器
8
for i in range(m):
9
    sel.append(input())
10
# 解析文档
11
cons = []
12
for i in range(n):
13
    level = doc[i].count('.')//2
14
    tag = ""
15
    tid = ""
16
    if len(doc[i].split())==1:
17
        tag = doc[i][level*2:]
18
    else:
19
        left, right = doc[i].split()
20
        tag = left[level*2:]  # 标签大小写不敏感
21
        tid = right  # id大小写敏感
22
    pline = -1
23
    for j in range(i-1, 0-1, -1):
24
        if cons[j]["level"] == level-1:
25
            pline = j + 1
26
            break
27
    cons.append({"tag":tag, "id":tid, "level":level, "pline":pline})  # 存信息为字典添加到列表
28
# 元素选择器选择
29
collection = []  # 结果保存列表
30
for i in range(m):
31
    collection.append([])
32
    if len(sel[i].split())==1:  # 选择器不含空格
33
        if sel[i][0]!='#':  # 标签选择器
34
            for j in range(n):
35
                if cons[j]["tag"].lower() == sel[i].lower():  # 标签大小写不敏感
36
                    collection[i].append(j+1)   
37
        else:  # id选择器
38
            for j in range(n):
39
                if cons[j]["id"] == sel[i]:  # id大小写敏感
40
                    collection[i].append(j+1)
41
    else:  # 后代选择器
42
        p = sel[i].split()
43
        for j in range(n):
44
            parent = j + 1
45
            k = len(p) - 1
46
            while k >= 0:  # 从后向前迭代检查是否匹配
47
                match = False
48
                if p[k][0]!='#':
49
                    if cons[parent-1]["tag"].lower() == p[k].lower():
50
                        match = True
51
                    elif parent == j+1 and k==len(p)-1:  # 第一次必须匹配上不然直接退出
52
                            break
53
                else:
54
                    if cons[parent-1]["id"] == p[k]:
55
                        match = True
56
                    elif parent==j+1 and k==len(p)-1:
57
                            break
58
                if match:
59
                    k -= 1
60
                    if k < 0:  # 匹配成功
61
                        collection[i].append(j+1)
62
                        break
63
                if cons[parent-1]["pline"]==-1:  # 没有父节点了仍未匹配成功即匹配失败
64
                    break  # 匹配失败退出
65
                parent = cons[parent-1]["pline"]  # 取父节点继续检查匹配
66
# 输出
67
for x in collection:    
68
    print(len(x), " ".join(map(str, x)))

201809-4 再卖菜

201809-5 线性递推式

3月

201803-1 跳一跳

1
//CCF 201803-1 跳一跳
2
#include <bits/stdc++.h>
3
using namespace std;
4
int jump(int &score, int &temp){
5
    int a;
6
    cin >> a;
7
    if(a == 1){
8
        score += 1;
9
        temp = 0;
10
        jump(score, temp);
11
    }
12
    else if(a == 2){
13
        temp += 2;
14
        score += temp;
15
        jump(score, temp);
16
    }
17
    return score;
18
}
19
int main(){
20
    int score = 0, temp = 0;
21
    score = jump(score, temp);
22
    cout << score << endl;
23
    return 0;
24
}

201803-2 碰撞的小球

1
//CCF 201803-2 碰撞的小球
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, L, t, i, j, k; //小球个数、线段长度、计算时刻等
6
    cin >> n >> L >> t;
7
    int A[100]; //n个小球的初始位置（都为偶数）
8
    int dirA[100]; //存放n个小球当前的运动方向：1为右、-1为左
9
    for(int i=0; i<n; i++){
10
        cin >> A[i];
11
        dirA[i] = 1; //所有小球方向初始化为右
12
    }
13
    for(int i=1; i<=t; i++){ //t秒的循环
14
        for(j=0; j<n; j++){
15
            if((A[j]==L && dirA[j]==1) || (A[j]==0 && dirA[j]==-1)) //位于两个端点
16
                dirA[j] *= -1; //掉头
17
            else
18
                for(k=0; k<n; k++)
19
                    if(A[j]==A[k] && j!=k) {//小球发生碰撞
20
                        dirA[j] *= -1;
21
                        dirA[k] *= -1;
22
                    }
23
            A[j] += dirA[j]; //更新当前位置
24
        }
25
    }
26
    for(int i=0; i<n; i++)
27
        cout << A[i] << " ";
28
    cout << endl;
29
    return 0;
30
}

201803-3 URL映射

1
//CCF 201803-3 URL映射
2
#include <bits/stdc++.h>
3
using namespace std;
4
struct reg{
5
    string name; 
6
    vector<string> regV;
7
    reg(string n, vector<string> v):name(n), regV(v){}
8
}; //规则结构体
9
vector<reg> regS; //规则向量
10
vector<string> str2regV(string str){ //字符串转化为规则向量
11
    vector<string> res;
12
    str = str.substr(1, str.size()-1); //substr: 从字符串指定位置复制指定数量的字符
13
    res.push_back("/");
14
    size_t pos = str.find("/");
15
    while(pos != string::npos){ //npos: npos表示string的结束位子
16
        res.push_back(str.substr(0, pos));
17
        res.push_back("/");
18
        str = str.substr(pos+1); //没有指定长度，从pos+1复制到字符串结尾
19
        pos = str.find("/");
20
    }
21
    if(str.size())  res.push_back(str);
22
    return res;
23
}
24
void urlMap(string str){ //完成URL映射
25
    vector<string> v = str2regV(str); //目标URL的规则向量
26
    for( size_t i=0; i<regS.size(); i++){
27
        vector<string> &r = regS[i].regV; //所有规则向量的每一项规则
28
        string res = regS[i].name; ////所有规则向量的每一项规则名称
29
        size_t lr = r.size(), lv = v.size(), j = 0, k = 0;
30
        while(j<lr && k<lv){
31
            if(r[j] == v[k]){ j++, k++; continue; }
32
            if(r[j] == "<path>"){ //路径 <path>
33
                if(v[lv-1] == "/") break;
34
                res += " ";
35
                while(k < lv)   res += v[k++];
36
                cout << res << endl;
37
                return;
38
            }else if(r[j] == "<int>"){ //整数 <int>
39
                string num;
40
                bool tag = 1;
41
                for(size_t l=0; l<v[k].size(); l++){
42
                    if(isdigit(v[k][l]))    num+= v[k][l];
43
                    else{ tag = 0; break; }
44
                }
45
                if(tag == 0)    break;
46
                size_t uz = 0;
47
                while(num[uz]=='0' && uz<num.size()-1) ++uz; //去除前导0
48
                res += " " + num.substr(uz, num.size()-uz);
49
            }else if(r[j] == "<str>"){ //字符串 <str>
50
                res += " " + v[k];
51
            }else break;
52
            j++; k++;
53
        }
54
        if(j==lr && k==lv){
55
            cout << res << endl;
56
            return;
57
        }
58
    }
59
    cout << "404" << endl; //匹配失败
60
}
61
int main(){
62
    int n, m; //规则数、URL数
63
    cin >> n >> m;
64
    for(int i=0; i<n; i++){
65
        string regStr, name; //规则字符串及其名称
66
        cin >> regStr >> name;
67
        regS.push_back(reg(name, str2regV(regStr))); //构建规则向量
68
    }
69
    while(m--){ //对每一个url依次映射
70
        string str;
71
        cin >> str;
72
        urlMap(str);
73
    }
74
    return 0;
75
}

201803-4 棋局评估

1
//CCF 201803-4 棋局评估
2
#include <bits/stdc++.h>
3
using namespace std;
4
int A[3][3]; //棋盘 空白为0
5
bool isrowsame(int i, int val) { //横向第i行都相同
6
    return A[i][0]==val && A[i][1]==val && A[i][2]==val;
7
}
8
bool iscolsame(int j, int val) { //竖向第j列都相同
9
    return A[0][j]==val && A[1][j]==val && A[2][j]==val;
10
}
11
bool isdiagsame(int val) { //斜方向的三个位置都相同
12
    return (A[0][0]==val && A[1][1]==val && A[2][2]==val) || (A[0][2]==val && A[1][1]==val && A[2][0]==val);
13
}
14
int countempty() { //计算空白格子个数
15
    int res = 0;
16
    for(int i=0; i<3; i++)
17
        for(int j=0; j<3; j++)
18
            if(A[i][j] == 0) res++;
19
    return res;
20
}
21
int iswin(int player) { //player: 1代表Alice, 2代表Bob
22
    bool r = isrowsame(0, player) || isrowsame(1, player) || isrowsame(2, player);
23
    bool c = iscolsame(0, player) || iscolsame(1, player) || iscolsame(2, player);
24
    bool d = isdiagsame(player);
25
    int w = r || c || d; //判断当前状态玩家是否胜出
26
    if(w == 0)  return 0; //未胜出，继续游戏
27
    w = countempty() + 1; //该玩家胜出，计算分数，游戏结束
28
    return player==1 ? w : -w;
29
}
30
int dfs(int player){
31
    if(countempty() == 0) return 0; //棋盘已满，平局
32
    int Min = 10, Max = -10;
33
    for(int i=0; i<3; i++)
34
        for(int j=0; j<3; j++) {
35
            if(A[i][j] == 0) {
36
                A[i][j] = player;
37
                int w = iswin(player);
38
                if(w) { //棋局结束
39
                    A[i][j] = 0;
40
                    return w>0 ? max(Max, w) : min(Min, w);
41
                }
42
                if(player == 1) Max = max(Max, dfs(2));
43
                else    Min = min(Min, dfs(1));
44
                A[i][j] = 0;
45
            }
46
        }
47
    return player==1 ? Max : Min;
48
}
49
int main() {
50
    int T; //输入数据的组数
51
    cin >> T;
52
    while(T--){  //依次处理每组数据并输出当前局面的得分
53
        for(int i=0; i<3; i++)
54
            for(int j=0; j<3; j++)
55
                cin >> A[i][j];
56
        int x = iswin(1), y = iswin(2);
57
        if(x)   cout << x << endl;
58
        else if(y)  cout << y << endl;
59
        else    cout << dfs(1) << endl;
60
    }
61
    return 0;
62
}

学习参考：

201803-5 二次求和

2017年

12月

201712-1 最小差值

1
//CCF 201712-1 最小差值
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, num[1024], minval=10000;
6
    cin >> n;
7
    for(int i=0; i<n; ++i)
8
        cin >> num[i];
9
    sort(num, num+n);
10
    for(int i=1; i<n; ++i)
11
        minval = min(minval,num[i]-num[i-1]);
12
    cout << minval <<endl;
13
    return 0;
14
}

201712-2 游戏

1
//CCF 201712-2 游戏
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, k;
6
    cin >> n >> k;
7
    vector<int> win; //剩余人序列
8
    for(int i=1; i<=n; ++i)
9
        win.push_back(i); 
10
    int num = 0; //开始报数
11
    while(win.size()>1){
12
        n = win.size();
13
        int len = 0;
14
        for(int i=0; i<n; ++i){
15
            ++num;
16
            if(num%k && num%10!=k)
17
                win[len++] = win[i];
18
        }
19
        if(len==0)  win[len++] = win.back();
20
        win.resize(len); //重置个数
21
    }
22
    cout << win[0] << endl;
23
    return 0;
24
}

201712-3 Crontab

1
// CFF 201712-3 Crontab
2
#include <bits/stdc++.h>
3
using namespace std;
4
char vMon[][4]={"","jan","feb","mar","apr","may","jun","jul","aug","sep","oct","nov","dec"};
5
char vWek[][4]={"sun","mon","tue","wed","thu","fri","sat"};
6
int mtharray[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
7
map<string,int> mMon,mWek;
8
map<string,vector<string> > mrt;
9
void buildMonAndWekMap(){ //初始化月份和工作日对应的序号
10
    for(int i=1;i<=12;++i) mMon[vMon[i]]=i;
11
    for(int i=0;i<=6;++i) mWek[vWek[i]]=i;
12
}
13
int stoi_x(const string &str){ //string转int
14
    int ans;
15
    stringstream ss(str);
16
    ss>>ans;
17
    return ans;
18
}
19
void toStandard(string &str){ //标准话：转化为小写
20
    int len=str.size();
21
    for(int i=0;i<len;++i)  str[i]=tolower(str[i]);
22
}
23
string to_string_x(int n){ //int转string
24
    stringstream ss;
25
    ss<<n;
26
    return ss.str();
27
}
28
vector<string> splitStringAndbuildVector(string &str,int TAG){ //切分string构建vector
29
    str+=",";
30
    vector<string> vret;
31
    size_t found=str.find(",");
32
    while(found!=string::npos){
33
        string x=str.substr(0,found);
34
        str=str.substr(found+1,str.size()-found-1);
35
        size_t fdx=x.find("-");
36
        if(fdx==string::npos){ //非连续值
37
            if(TAG==1&&isalpha(x[0])) x=to_string_x(mMon[x]);//是month英文缩写，转换为数字
38
            if(TAG==2&&isalpha(x[0])) x=to_string_x(mWek[x]);//是day of week英文缩写，转换为数字
39
            if(x.size()==1) x="0"+x;//添加0
40
            vret.push_back(x);
41
        }else{//连续值
42
            string L=x.substr(0,fdx),R=x.substr(fdx+1,x.size()-fdx-1);
43
            int left,right;
44
            if(TAG==0) left=stoi_x(L),right=stoi_x(R);
45
            else if(TAG==1){//month
46
                left=(isalpha(L[0]))?mMon[L]:stoi_x(L);
47
                right=(isalpha(R[0]))?mMon[R]:stoi_x(R);
48
            }else if(TAG==2){//day of week
49
                left=(isalpha(L[0]))?mWek[L]:stoi_x(L);
50
                right=(isalpha(R[0]))?mWek[R]:stoi_x(R);
51
            }
52
            while(left<=right){
53
                string num=to_string_x(left);
54
                if(num.size()==1)num="0"+num;
55
                vret.push_back(num);
56
                ++left;
57
            }
58
        }
59
        found=str.find(",");
60
    }
61
    return vret;
62
}
63
bool isleapyear(int y){ //判断是否闰年
64
    return (y%4==0&&y%100)||y%400==0;
65
}
66
string getWeekday(string year,string month,string day){ //计算星期几
67
    int y=stoi_x(year),m=stoi_x(month),d=stoi_x(day);
68
    int by=1970,countday=0;
69
    while(by<y){
70
        countday+=(isleapyear(by))?366:365;
71
        ++by;
72
    }
73
    for(int i=1;i<m;++i) countday+=mtharray[i];
74
    countday+=d-1;
75
    return "0"+to_string_x((4+countday%7)%7);
76
}
77
int main(){
78
    int n;
79
    string st,et;
80
    buildMonAndWekMap();
81
    cin>>n>>st>>et;
82
    string syy=st.substr(0,4),smm=st.substr(4,2),sdd=st.substr(6,2),sHH=st.substr(8,2),sMM=st.substr(10,2);
83
    string eyy=et.substr(0,4),emm=et.substr(4,2),edd=et.substr(6,2),eHH=et.substr(8,2),eMM=et.substr(10,2);
84
    int syInt=stoi_x(syy),eyInt=stoi_x(eyy);
85
    while(n--){
86
        vector<string> vmts,vhur,vdfm,vmth,vdfw;
87
        string minutes,hours,dofmon,month,dofwek,command;
88
        cin>>minutes>>hours>>dofmon>>month>>dofwek>>command;
89
        toStandard(month);//不区别大小写，转化为标准小写
90
        toStandard(dofwek);//不区别大小写，转化为标准小写
91
        if(minutes=="*") minutes="0-59";
92
        vmts=splitStringAndbuildVector(minutes,0);//应该执行的分钟
93
        if(hours=="*") hours="0-23";
94
        vhur=splitStringAndbuildVector(hours,0); //应该执行的小时
95
        if(dofmon=="*") dofmon="1-31";
96
        vdfm=splitStringAndbuildVector(dofmon,0);//应该执行的日期
97
        if(month=="*") month="1-12";
98
        vmth=splitStringAndbuildVector(month,1);//应该执行的月份
99
        if(dofwek=="*") dofwek="0-6";
100
        vdfw=splitStringAndbuildVector(dofwek,2);//应该周几执行
101
        set<string> wekexist;
102
        for(size_t i=0;i<vdfw.size();++i) wekexist.insert(vdfw[i]);//更快的检索当前日期（dayofweek）是不是应该执行
103
        int curyear=syInt;//从开始年份执行
104
        while(curyear<=eyInt){
105
            if(isleapyear(curyear)) mtharray[2]=29;//leapyear的2月份应该是29天
106
            else mtharray[2]=28;
107
            string year=to_string_x(curyear);//年份
108
            for(size_t mi=0;mi<vmth.size();mi++){ //month
109
                string curm=vmth[mi];//当前月份
110
                for(size_t di=0;di<vdfm.size();di++){ //day of month
111
                    string curd=vdfm[di];//当前日期
112
                    string wd=getWeekday(year,curm,curd);//该年，该月，该日是星期几
113
                    if(wekexist.count(wd)==0||stoi_x(curd)>mtharray[stoi_x(curm)])continue;
114
                    //命令行中不包含该星期或者当前天数超过当前月份的应有天数时
115
                    for(size_t Hi=0;Hi<vhur.size();++Hi) //hour
116
                        for(size_t Mi=0;Mi<vmts.size();++Mi){ //minutes
117
                            string datetime=year+curm+curd+vhur[Hi]+vmts[Mi];
118
                            if(datetime>=st&&datetime<et) mrt[datetime].push_back(command);//在当前日期时间内
119
                        }
120
                }
121
            }
122
            ++curyear;//进入下一年
123
        }
124
    }
125
    for(map<string,vector<string> >::iterator it=mrt.begin();it!=mrt.end();++it){
126
        map<string,int> isprt;
127
        for(size_t i=0;i<it->second.size();++i){
128
            string dis=it->first+" "+it->second[i];
129
            if(isprt.count(dis)==0){
130
                cout<<dis<<endl;
131
                isprt[dis]=1;
132
            }
133
        }
134
    }
135
    return 0;
136
}

（学习参考：201712-3 Crontab ccf）

201712-4 行车路线

1
//CCF 201712-4 行车路线
2
#include <bits/stdc++.h>
3
#define INF 0x3f3f3f3f
4
using namespace std;
5
long long bigR[505][505], smallR[505][505]; //大路长度，小路长度
6
long long tiredB[505], tiredS[505]; //大路的疲劳度，小路的疲劳度
7
bool visited[505]; //经过路口：1为已经过
8
int n, m; //路口数，道路数
9
void floyd() { //预处理小路的连通性
10
    for(int k=1; k<=n; k++)
11
        for(int i=1; i<=n; i++)
12
            for(int j=1; j<=n; j++)
13
                if(smallR[i][j]>smallR[i][k]+smallR[k][j] && smallR[i][k]!=INF && smallR[k][j]!=INF)
14
                    smallR[i][j] = smallR[i][k] + smallR[k][j];
15
}
16
int main() {
17
    memset(smallR, INF, sizeof(smallR));
18
    memset(bigR, INF, sizeof(bigR));
19
    cin >> n >> m;
20
    for(int i=1; i<=m; i++) {
21
        int t, a, b, c; //道路类型，起点路口，终点路口，道路长度
22
        cin>> t >> a >> b >> c;
23
        if(t==1 && smallR[a][b]>c) //t==1 小道
24
            smallR[a][b] = smallR[b][a] = c;
25
        else if(t==0 && bigR[a][b]>c) //t==0 大道
26
            bigR[a][b] = bigR[b][a] = c;
27
    }
28
    floyd();
29
    memset(tiredB, INF, sizeof(tiredB));
30
    memset(tiredS, INF, sizeof(tiredS));
31
    queue<int> q; //经过路口队列
32
    tiredB[1] = tiredS[1] = 0; //初始化大路小路的疲劳度
33
    q.push(1);
34
    visited[1] = 1;
35
    while(!q.empty()) {
36
        int now = q.front();
37
        q.pop();
38
        visited[now] = 0;
39
        for(int i=1; i<=n; i++) { //依次遍历n个路口
40
            long long v = bigR[now][i];
41
            if(tiredB[i] > tiredB[now]+v) { //大路加大路
42
                tiredB[i] = tiredB[now] + v;
43
                if(visited[i])  continue;
44
                visited[i] = 1;
45
                q.push(i);
46
            }
47
            if(tiredB[i] > tiredS[now]+v) { //大路加小路
48
                tiredB[i] = tiredS[now]+v;
49
                if(visited[i])  continue;
50
                visited[i] = 1;
51
                q.push(i);
52
            }
53
            if(smallR[now][i] < 1e10) {
54
                v = smallR[now][i] * smallR[now][i];
55
                if(tiredS[i] > tiredB[now]+v) { //小路加大路
56
                    tiredS[i] = tiredB[now]+v;
57
                    if(visited[i])  continue;
58
                    visited[i] = 1;
59
                    q.push(i);
60
                }
61
            }
62
        }
63
    }
64
    cout << min(tiredB[n], tiredS[n]) << endl;
65
    return 0;
66
}

学习参考：

201712-5 商路

9月

201709-1 打酱油

1
//CCF 201709-1 打酱油
2
#include <bits/stdc++.h>
3
using namespace std;
4
int buy(int n){
5
    if(n<50)
6
        return n<30 ? n/10 : 4+(n-30)/10;
7
    return max(4+buy(n-30), 7+buy(n-50));
8
}
9
int main(){
10
    int N; //小明的钱数
11
    cin >> N;
12
    cout << buy(N) <<endl;
13
    return 0;
14
}

201709-2 公共钥匙盒

1
//CCF 201709-2 公共钥匙盒
2
#include <bits/stdc++.h>
3
using namespace std;
4
struct teacher{
5
    int num, s, e; //老师要使用的钥匙编号、开始上课的时间、上课的时长
6
    teacher(int x=0, int y=0, int z=0):num(x), s(y), e(z){}
7
};
8
vector<teacher> p, q;
9
int keyN, teaN, key[1024]; //钥匙数、老师数、挂钩上的钥匙组
10
bool cmpStart(const teacher &a, const teacher &b){
11
    return a.s < b.s; //比较开始使用时刻
12
}
13
bool cmpStop(const teacher &a, const teacher &b){
14
    return a.e==b.e ? a.num<b.num : a.e<b.e; //比较使用的钥匙或使用时长
15
}
16
int searchKeyPos(int keyId){ //搜索钥匙位置
17
    for(int i=1; i<=keyN; i++)
18
        if(keyId == key[i]) return i;
19
    cout << "can't find " << keyId << endl;
20
    return -1;
21
}
22
int main(){
23
    cin >> keyN >> teaN; 
24
    for(int i=1; i<=keyN; i++) //初始化钥匙序号
25
        key[i] = i;
26
    for(int i=0; i<teaN; i++){ //初始化老师使用钥匙情况
27
        teacher x;
28
        cin >> x.num >> x.s >> x.e;
29
        x.e += x.s;
30
        p.push_back(x);
31
        q.push_back(x);
32
    }
33
    sort(p.begin(), p.end(), cmpStart); //根据开始时间从小到大排 
34
    sort(q.begin(), q.end(), cmpStop); //根据结束时间从小到大排 
35
    int i=0, j=0;
36
    while(i<teaN && j<teaN){
37
        if(p[i].s < q[j].e){
38
            int pos = searchKeyPos(p[i++].num);
39
            key[pos] = -1;
40
        }
41
        else if(p[i].s >= q[j].e){
42
            int pos = searchKeyPos(-1);
43
            key[pos] = q[j++].num;
44
        }
45
    }
46
    while(j < teaN){
47
        int pos = searchKeyPos(-1);
48
        key[pos] = q[j++].num;
49
    }
50
    for(int i=1; i<=keyN; i++)
51
        cout << key[i] << " ";
52
    return 0;
53
}

201709-3 JSON查询

1
// CFF 201709-3 JSON查询
2
#include <bits/stdc++.h>
3
using namespace std;
4
bool IsRoot(string &json_str, size_t pos){ //判断是否为根元素
5
    int p_cnt = 0;
6
    for(size_t i=0; i<pos; i++){
7
        if(json_str[i] == '{') p_cnt++;
8
        if(json_str[i] == '}') p_cnt--;
9
    }
10
    return p_cnt==0;
11
}
12
vector<string> Split(string str){ //将字符串按'.'分割为字符串向量
13
    size_t pos = str.find(".");
14
    vector<string> ret;
15
    while(pos != string::npos){
16
        ret.push_back(str.substr(0, pos));
17
        str = str.substr(pos+1);
18
        pos = str.find(".");
19
    }
20
    ret.push_back(str);
21
    return ret;
22
}
23
string SubJsonStr(string json_str, int l_pos){ //返回子JSON串
24
    int p_cnt = 1;
25
    size_t r_pos = l_pos;
26
    while(p_cnt){
27
        if(json_str[r_pos]=='{')    p_cnt++;
28
        else if(json_str[r_pos]=='}')   p_cnt--;
29
        r_pos++;
30
    }
31
    return json_str.substr(l_pos, r_pos-l_pos-1) + ',';
32
}
33
void Search(vector<string> &ret, string json_str){ //JSON查询
34
    size_t i = 0;
35
    while(i < ret.size()-1){ //依次遍历待查询JSON串向量的每一项
36
        size_t pos = json_str.find(ret[i]+":{");
37
        if(pos==string::npos || !IsRoot(json_str, pos)){
38
            cout << "NOTEXIST\n";
39
            return;
40
        }
41
        json_str = SubJsonStr(json_str, pos+ret[i].size()+2);
42
        i++;
43
    }
44
    size_t pos = json_str.find(ret.back()+":");
45
    if(pos==string::npos || !IsRoot(json_str, pos))
46
        cout << "NOTEXIST\n";
47
    else{
48
        i = pos + ret.back().size() + 1;
49
        if(json_str[i] == '{')  cout << "OBJECT\n"; //是对象的情况
50
        else{
51
            size_t dp = json_str.find(",", i);
52
            if(dp == string::npos){
53
                cout << "NOTEXIST\n";
54
                return;
55
            }
56
            string x;
57
            while(i < dp)
58
                x += json_str[i++];
59
            cout << "STRING " << x << endl; //是字符串的情况
60
        }
61
    }
62
}
63
int main(){
64
    string json_str; //JSON字符串
65
    int n, m;
66
    cin >> n >> m;
67
    cin.get(); cin.get();  // '{' 与 '\n'
68
    for(int i=0; i<n; i++){
69
        char ch;
70
        while((ch=cin.get()) != '\n'){
71
            if(ch==' ' || ch=='"') continue;
72
            if(ch == '\\'){
73
                json_str += cin.get(); //至包含一个 '\'
74
                continue;
75
            }
76
            json_str += ch;
77
        }
78
    }
79
    json_str[json_str.length()-1] = ',';
80
    while(m--){
81
        string str;  //待查询JSON字符串
82
        cin >> str;
83
        vector<string> ret = Split(str);  //将待查询JSON分割为字符串向量
84
        Search(ret, json_str);  //JSON查询
85
    }
86
    return 0;
87
}

201709-4 通信网络

201709-5 除法

简单尝试的超时代码：

1
// CFF 201709-5 除法
2
#include <bits/stdc++.h>
3
using namespace std;
4
int l, r, v, sum = 0; //起点、终点、除数、和
5
void doDivid(int n, int *a){
6
    cin >> l >> r >> v;
7
    for(int i=l; i<=r; i++)
8
        if(a[i]%v == 0)   
9
            a[i] /= v;
10
}
11
int getSum(int n, int a[]){
12
    cin >> l >> r;
13
    for(int i=l; i<=r; i++)
14
        sum += a[i];
15
    return sum;
16
}
17
int main(){
18
    int n, m; //数的个数和操作的次数
19
    cin >> n >> m;
20
    int a[n+1]; //n个整数：下标为1～n
21
    for(int i=1; i<=n; i++)
22
        cin >> a[i];
23
    for(int i=0; i<m; i++){
24
        int opt; //操作标识
25
        cin >> opt;
26
        if(opt == 1) //倍数做除法
27
            doDivid(n, a);
28
        else if(opt == 2) //求和运算
29
            cout << getSum(n, a) << endl;
30
    }
31
    return 0;
32
}

下面是上网学习到的树形数组解决方案：源代码地址 

1
// CFF 201709-5 除法
2
#include <cstdio>
3
long long tree[101024]; //树形数组
4
int n, m, a[101024]; //数的个数、操作的次数、一组数
5
void update(int i, int val){ //更新树形数组
6
    while(i <= n){
7
        tree[i] += val;
8
        i += -i & i; //i+(-i&i)是i的父节点，-i&i得出i末尾0的个数
9
    }
10
}
11
long long getsum(int i){ //求和
12
    long long sum = 0;
13
    while(i > 0){
14
        sum += tree[i];
15
        i -= -i & i; //i-(-i&i)是前一个棵树的根节点
16
    }
17
    return sum;
18
}
19
int main(){
20
    scanf("%d %d", &n, &m);
21
    for(int i=1; i<=n; ++i){
22
        scanf("%d", &a[i]);
23
        update(i, a[i]);
24
    }
25
    for(int i=1; i<=m; ++i){
26
        int opt, l, r, w; //操作标识、起点、终点、除数
27
        scanf("%d %d %d", &opt, &l, &r);
28
        if(opt == 2) printf("%lld\n", getsum(r)-getsum(l-1));
29
        else{
30
            scanf("%d", &w);
31
            if(w == 1) continue;
32
            while(l <= r){
33
                if(a[l]>=w && a[l]%w==0){
34
                    update(l, -(a[l]-a[l]/w));
35
                    a[l] /= w;
36
                }
37
                ++l;
38
            }
39
        }
40
    }
41
    return 0;
42
}

学习参考：

3月

201703-1 分蛋糕

1
//CCF 201703-1 分蛋糕
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, k;
6
    int s = 0; //每个人依次分到蛋糕的总重量
7
    int i = 0; //已分配的蛋糕数量
8
    int w; //依次输入的每块蛋糕的重量
9
    int f = 0; //分到蛋糕的朋友数
10
    cin >> n >> k;
11
    while(i<n){
12
        cin >> w;
13
        ++i;
14
        s = w;
15
        while(i<n && s<k){ //当还有蛋糕并且此人分到蛋糕重量少于k
16
            cin >> w;
17
            s += w;
18
            ++i;
19
        }
20
        ++f;
21
    }
22
    cout << f;
23
    return 0;
24
}

201703-2 学生排队

1
// CCF 201703-2 学生排队
2
#include <bits/stdc++.h>
3
using namespace std;
4
int n, m;
5
int mpos[1024], ran[1024]; //移动位置数组， 队伍排序数组
6
void move(int pos, int len, int step){ //位置，长度，步长
7
    int temp = ran[pos];
8
    while(len){
9
        ran[pos] = ran[pos+step];
10
        mpos[ran[pos]] = pos;
11
        pos += step;
12
        --len;
13
    }
14
    mpos[temp] = pos;
15
    ran[pos] = temp;
16
}
17
int main(){
18
    cin >> n >> m;
19
    for(int i=1; i<=n; i++)
20
        ran[i] = mpos[i] = i; //1-n做标记
21
    for(int i=0; i<m; i++){
22
        int id, val; //序号，移动数值
23
        cin >> id >> val;
24
        int pos = mpos[id]; //开始移动的位置
25
        val<0 ? move(pos, -val, -1) : move(pos, val, 1);
26
    }
27
    for(int i=1; i<=n; i++)
28
        cout << ran[i] << " ";
29
    return 0;
30
}

201703-3 Markdown

1
//CCF 201703-3 Markdown
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    string line, text; //Md文本行与html文本
6
    bool is_over = false; //判断是否结束
7
    getline(cin, line); //读取一行数据
8
    while(true){
9
        if(line.size()>0)   text += line + "\n";
10
        else if(line.size()==0 && text.size()>0){
11
            size_t pos = text.find("_"); //强调文本
12
            while(pos != string::npos){ //用 <em> 替换 _
13
                text.replace(pos, 1, "<em>");
14
                size_t next_pos = text.find("_", pos);
15
                text.replace(next_pos, 1, "</em>");
16
                pos = text.find("_", next_pos);
17
            }
18
            pos = text.find("[");
19
            while(pos != string::npos){ //用 <a> 替换 []()
20
                size_t next_pos = text.find("]", pos);
21
                size_t left_pos = text.find("(", next_pos);
22
                size_t right_pos = text.find(")", left_pos);
23
                string text_for_link = text.substr(pos+1, next_pos-pos-1); //链接文本
24
                string link = text.substr(left_pos+1, right_pos-left_pos-1); //链接
25
                text.replace(text.begin()+pos, text.begin()+right_pos+1, "<a href=\""+link+"\">"+text_for_link+"</a>");
26
                pos = text.find("[", right_pos);
27
            }
28
            if(text[0] == '#'){ //用 <h1>标题</h1> 替换 # 标题
29
                int i = 0;
30
                while(text[i]=='#') ++i;
31
                text = text.substr(i+1);
32
                text = "<h" + string(1, '0'+i) + ">" + text;
33
                text.insert(text.size()-1, "</h"+string(1, '0'+i)+">");
34
            }else if(text[0] == '*'){ //用 <ul><li>组合 替换 * 列表
35
                text.insert(0, "<ul>\n");
36
                text.insert(text.size(), "</ul>\n");
37
                size_t pos = text.find("*");
38
                while(pos != string::npos){ //用 <li> 替换 * 列表项
39
                    size_t next_pos = text.find("\n", pos);
40
                    text.insert(next_pos, "</li>");
41
                    text.replace(pos, 2, "<li>");
42
                    pos = text.find("*", next_pos);
43
                }
44
            }else{ //正常段落格式 <p>段落文本</p>
45
                text = "<p>" + text;
46
                text.insert(text.size()-1, "</p>");
47
            }
48
            cout << text;
49
            text = "";
50
        }
51
        line = "";
52
        if(is_over) break; //结束
53
        if(!getline(cin, line)){
54
            is_over = true;
55
            line = "";
56
        }
57
    }
58
    return 0;
59
}

201703-4 地铁修建

1
//CCF 201703-4 地铁修建
2
#include <bits/stdc++.h>
3
using namespace std;
4
struct edge {
5
    int u, v; //隧道的开始枢纽，终点枢纽
6
    int w; //建造所需时间
7
    edge(int a, int b, int c) : u(a), v(b), w(c){}
8
    bool operator <(const edge &p) const {
9
        return w < p.w; //自定义比较方式：比较建造所需时间
10
    }
11
}; //隧道的结构体
12
vector<edge> tunnel; //隧道向量
13
int n, m; //交通枢纽数，候选隧道数
14
int company[100001]; //n个公司负责的枢纽
15
int find(int x) {
16
    return x==company[x] ? x : company[x]=find(company[x]);
17
}
18
int kruskal() {
19
    for(int i=1; i<=n; i++) company[i] = i;
20
    for(int i=0; i<m; i++) {
21
        int x = find(tunnel[i].u), y = find(tunnel[i].v);
22
        if(x != y)  company[x] = y;
23
        if(find(1) == find(n))  return tunnel[i].w;
24
    }
25
    return -1;
26
}
27
int main() {
28
    cin >> n >> m; 
29
    for(int i=0; i<m; i++) {
30
        int a, b, c; //枢纽a，枢纽b，a与b之间隧道建造的时间
31
        cin >> a >> b >> c;
32
        tunnel.push_back(edge(a, b, c));
33
    }
34
    sort(tunnel.begin(), tunnel.end()); //按照修建时间生序排列
35
    cout << kruskal();
36
    return 0;
37
}

学习参考：

201703-5 引水入城

2016年

12月

201612-1 中间数

1
//CCF 201612-1 中间数
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n;
6
    cin >> n;
7
    vector<int> v;
8
    for(int i=0; i<n; ++i){
9
        int x;
10
        cin >> x;
11
        v.push_back(x);
12
    }
13
    sort(v.begin(), v.end());
14
    int j = v.size()/2, i = (v.size()%2==0) ? j-1 : j;
15
    int e = v[j];
16
    while(i>=0 && j<n && v[i]==v[j] && v[i]==e)
17
        --i, ++j;
18
    if(i>=0 && (v[i]==e || v[j]==e))
19
        cout << -1;
20
    else cout << e;
21
    return 0;
22
}

201612-2 工资计算

1
//CCF 201612-2 工资计算
2
#include <bits/stdc++.h>
3
using namespace std;
4
double rate[] = {0, 0.03, 0.1, 0.2, 0.25, 0.3, 0.35, 0.45};
5
int v[]={3500,1500,3000,4500,26000,20000,25000};
6
int u[]={3500,1500,3000,4500,26000,20000,25000};
7
void cpt(){ //计算各个工资临界值的税费
8
    for(int i=1; i<7; ++i){
9
        u[i] += u[i-1]; //u的循环结果依次为各个临界工资值
10
        v[i] = v[i-1] + v[i]*(1-rate[i]);  //v的循环结果依次为各个临界工资值对应的税费
11
    }
12
}
13
int main(){
14
    int t, i = 0;
15
    cin >> t;
16
    if(t <= 3500){ //税后所得少于3500，则S少于3500，即不交税
17
        cout << t <<endl;
18
        return 0;
19
    }
20
    cpt(); //计算临界工资对应的税费
21
    while(v[i]<=t && i<7) ++i;  
22
    --i;
23
    int s = u[i] + (t-v[i])/(1-rate[i+1]); //计算税前工资
24
    cout << s << endl;
25
    return 0;
26
}

201612-3 权限查询

1
//CCF 201612-3 权限查询
2
#include <bits/stdc++.h>
3
const int NOVALUE = -1; //不分等级
4
const int TRUE = -2;
5
const int FALSE = -3;
6
using namespace std;
7
struct _privilege { //权限
8
    string category;
9
    int level;
10
};
11
vector<_privilege> privilege;
12
struct _role { //角色
13
    string role;
14
    int s;
15
    vector<_privilege> privilege; //每个角色有多个权限
16
};
17
vector<_role> role;
18
struct _user { //用户
19
    string user;
20
    int t;
21
    vector<string> role; //每个用户有多个角色
22
};
23
vector<_user> user;
24
string getcategory(string& s){ //得到权限类别
25
    int pos = s.find(":");
26
    if(pos == (int)string::npos)    return s;
27
    else    return s.substr(0, pos);
28
}
29
int getlevel(string &s){ //得到权限等级
30
    int pos = s.find(":");
31
    if(pos == (int)string::npos)    return NOVALUE;
32
    else    return atoi(s.substr(pos+1, s.length()-1).c_str());
33
    //atoi: 将string转换为int
34
}
35
int privilegematch(_privilege& p1, _privilege& p2){ //权限匹配
36
    if(p1.category != p2.category)  return FALSE;
37
    else if(p2.level == NOVALUE) { //不分等级查询
38
        if(p1.level == NOVALUE) return TRUE;
39
        else    return p1.level;
40
    } else { //分等级查询
41
        if(p1.level == NOVALUE) return TRUE;
42
        else {
43
            if(p1.level >= p2.level)    return TRUE;
44
            else    return FALSE;
45
        }
46
    }
47
}
48
int rolematch(string& rl, _privilege& prvl){ //角色匹配
49
    int ans = FALSE;
50
    for(int i=0; i<(int)role.size(); i++) {
51
        if(role[i].role == rl) {
52
            for(int j=0; j<role[i].s; j++) {
53
                int rt = privilegematch(role[i].privilege[j], prvl);
54
                if(rt > ans)    ans = rt;
55
            }
56
        }
57
    }
58
    return ans;
59
}
60
int query(string& usr, _privilege& prvl){ //查询用户权限
61
    for(int i=0; i<(int)user.size(); i++) {
62
        if(user[i].user == usr) {
63
            int ans = FALSE;
64
            for(int j=0; j<user[i].t; j++) {
65
                int rt = rolematch(user[i].role[j], prvl);
66
                if(rt > ans)    ans = rt;
67
            }
68
            return ans;
69
        }
70
    }
71
    return FALSE;
72
}
73
int main(){
74
    int p, r, u, q;
75
    cin >> p; //权限类别数量
76
    string c; //每个权限类别
77
    _privilege prvl;
78
    for(int i=1; i<=p; i++) {
79
        cin >> c;
80
        prvl.category = getcategory(c);
81
        prvl.level = getlevel(c);
82
        privilege.push_back(prvl);
83
    }
84
    cin >> r; //角色数量
85
    for(int i=1; i<=r; i++) {
86
        _role rl;
87
        cin >> rl.role >> rl.s;
88
        for(int j=1; j<=rl.s; j++) {
89
            cin >> c;
90
            prvl.category = getcategory(c);
91
            prvl.level = getlevel(c);
92
            rl.privilege.push_back(prvl);
93
        }
94
        role.push_back(rl);
95
    }
96
    cin >> u; //用户数量
97
    for(int i=1; i<=u; i++) { //输入每个用户
98
        _user us;
99
        cin >> us.user >> us.t;
100
        for(int j=1; j<=us.t; j++) {
101
            cin >> c;
102
            us.role.push_back(c);
103
        }
104
        user.push_back(us);
105
    }
106
    cin >> q; //查询数量
107
    string suser; //每个授权查询
108
    for(int i=1; i<=q; i++) {
109
        cin >> suser >> c; //查询用户、权限
110
        prvl.category = getcategory(c);
111
        prvl.level = getlevel(c);
112
        int ans = query(suser, prvl);
113
        if(ans == TRUE) cout << "true" << endl;
114
        else if(ans == FALSE)   cout << "false" << endl;
115
        else    cout << ans << endl;
116
    }
117
    return 0;
118
}

学习参考：201612-3 权限查询

201612-4 压缩编码

201612-5 卡牌游戏

9月

201609-1 最大波动

1
//CCF 201609-1 最大波动
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, max = 0;
6
    cin >> n;
7
    int a[n];
8
    cin >> a[0];
9
    for(int i=1; i<n; i++){
10
        cin >> a[i];
11
        int tmp = abs(a[i]-a[i-1]);
12
        max = max > tmp ? max : tmp;
13
    }
14
    cout << max << endl;
15
    return 0;
16
}

201609-2 火车购票

1
// CFF 201609-2 火车购票
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n;
6
    cin >> n;
7
    vector<int> v(20, 5); //一节车厢有20排、每一排5个座位
8
    for(int i=0; i<n; i++){
9
        int x;
10
        cin >> x; //输入要购入的票数
11
        for(int r=0; r<20&&x>0; r++) //逐行查找
12
            if(v[r] >= x){ //该行空余座位大于需求x
13
                int seat = r*5+5-v[r]+1; //给空闲座位编号
14
                v[r] -= x; //x个已购，更新空余座位
15
                while(x--){
16
                    cout << seat++;
17
                    if(x>0) cout << " ";
18
                    else cout << endl;
19
                }
20
            }
21
        if(x>0) //没有连续座位
22
            for(int r=0; r<20&&x>0; r++)
23
                while(v[r]>0 && x>0){
24
                    int seat = r*5+5-v[r]+1;
25
                    cout << seat++;
26
                    --v[r];
27
                    --x;
28
                    if(x>0) cout << " ";
29
                    else cout << endl;
30
                }
31
    }
32
    return 0;
33
}

201609-3 炉石传说

1
// CCF 201609-3 炉石传说
2
#include <bits/stdc++.h>
3
using namespace std;
4
struct role{
5
    int attack, health; //每个角色的攻击力和健康值
6
    role(int ak, int ht):attack(ak), health(ht){}
7
};
8
vector<role> va, vb; //两个角色vector
9
int n, turn = 0; //操作个数、转换回合标志
10
void display(vector<role> &v){ //输出生命值、随从个数等信息
11
    cout << v[0].health << endl;
12
    cout << v.size()-1;
13
    for(size_t i=1; i<v.size(); i++)    
14
        cout << " " << v[i].health;
15
    cout << endl;
16
}
17
int main(){
18
    va.push_back(role(0,30));
19
    vb.push_back(role(0,30));
20
    cin >> n;
21
    for(int i=0; i<n; i++){
22
        string action; //每个操作
23
        cin >> action;
24
        if(action == "summon"){ //召唤随从
25
            int pos, ak, ht; //位置、攻击力、健康值
26
            cin >> pos >> ak >> ht;
27
            if(turn==0) va.insert(va.begin()+pos,role(ak,ht));
28
            else vb.insert(vb.begin()+pos,role(ak,ht));
29
        }else if(action=="end") //结束该回合
30
            turn = (turn+1)%2;
31
        else if(action=="attack"){ //攻击
32
            int i, j; //发起攻击的随从号、被攻击的对方角色号
33
            cin >> i >> j;
34
            if(turn==0){
35
                va[i].health -= vb[j].attack;
36
                vb[j].health -= va[i].attack;
37
                if(va[i].health<=0&&i)
38
                    va.erase(va.begin()+i);
39
                if(vb[j].health<=0&&j)
40
                    vb.erase(vb.begin()+j);
41
            }else{
42
                vb[i].health -= va[j].attack;
43
                va[j].health -= vb[i].attack;
44
                if(va[j].health<=0&&j)
45
                    va.erase(va.begin()+j);
46
                if(vb[i].health<=0&&i)
47
                    vb.erase(vb.begin()+i);
48
            }
49
        }
50
        if(va[0].health<=0 || vb[0].health<=0)
51
            break;
52
    }
53
    if(va[0].health<=0&&vb[0].health>0) //后手玩家胜
54
        cout << -1 << endl;
55
    else if(va[0].health>0&&vb[0].health<=0) //先手玩家胜
56
        cout << 1 << endl;
57
    else cout << 0 << endl; //游戏尚未结束
58
    display(va);
59
    display(vb);
60
    return 0;
61
}

201609-4 交通规划

1
//CCF 201609-4 交通规划
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int INF = 0x7fffffff;
5
int n, m; //城市数，铁路数
6
struct edge {
7
    int v;
8
    int cost;
9
    edge(int x, int c) : v(x), cost(c){}
10
};
11
struct cmp {
12
    bool operator()(edge &a, edge &b) {
13
        return a.cost > b.cost;
14
    }
15
};
16
vector<edge> vg[10000];
17
int main() {
18
    cin >> n >> m;
19
    for(int i=0; i<m; i++) {
20
        int a, b, c; //城市a，城市b，a与b之间双向铁路的长度
21
        cin >> a >> b >> c;
22
        --a, --b;
23
        vg[a].push_back(edge(b, c));
24
        vg[b].push_back(edge(a, c));
25
    }
26
    //dijkstra
27
    priority_queue<edge,vector<edge>,cmp> pq;
28
    vector<int> dist(n, INF);
29
    vector<int> cost(n, INF);
30
    vector<bool> visit(n, 0);
31
    pq.push(edge(0, 0));
32
    dist[0] = cost[0] = 0;
33
    while(!pq.empty()) {
34
        edge t = pq.top(); //最短路径（花费）边
35
        pq.pop();
36
        visit[t.v] = 1; //访问该节点
37
        for(size_t i=0; i<vg[t.v].size(); i++) {
38
            edge e = vg[t.v][i]; //该节点的所有邻接边
39
            if(visit[e.v])  continue; //另外一端节点访问过了，跳过
40
            if(dist[e.v] > dist[t.v]+e.cost) { //更新最短路径
41
                dist[e.v] = dist[t.v] + e.cost;
42
                cost[e.v] = e.cost;
43
                pq.push(edge(e.v, dist[e.v])); //新的更新边
44
            }
45
            else if(dist[e.v] == dist[t.v]+e.cost)
46
                cost[e.v] = min(cost[e.v], e.cost);
47
        }
48
    }
49
    int sum = 0;
50
    for(int i=0; i<n; i++)
51
        sum += cost[i];
52
    cout << sum << endl;
53
    return 0;
54
}

学习参考：

201609-5 祭坛

4月

201604-1 折点计数

1
// CFF 201604-1 折点计数
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, num = 0;
6
    cin >> n;
7
    int a[n];
8
    cin >> a[0] >> a[1];
9
    for(int i=2; i<n; i++){
10
        cin >> a[i];
11
        if((a[i-2]>a[i-1] && a[i-1]<a[i]) || (a[i-2]<a[i-1] && a[i-1]>a[i]))
12
            num++;
13
    }
14
    cout << num << endl;
15
    return 0;
16
}

201604-2 俄罗斯方块

1
// CCF 201604-2 俄罗斯方块
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int ROW = 15; //方格图行数
5
const int COL = 10; //方格图列数
6
const int N = 4;    //新方块阶数
7
int board[ROW+1][COL]; //初始方格图，最下面一行全为1
8
int block[N][N]; //新方块
9
struct { int row, col; } coords[N];  //新方块的模式块数组
10
int main(){
11
    int row, col;
12
    // 输入数据
13
    for(int i=0; i<ROW; i++)
14
        for(int j=0; j<COL; j++)
15
            cin >> board[i][j];
16
    for(int i=0; i<N; i++)
17
        for(int j=0; j<N; j++)
18
            cin >> block[i][j];
19
    cin >> col; 
20
    // 底边全放1
21
    for(int j=0; j<COL; j++)
22
        board[ROW][j] = 1;
23
    // 提取新方块的模式块坐标
24
    int k = 0;
25
    for(int i=N-1; i>=0; i--)
26
        for(int j=0; j<N; j++)
27
            if(block[i][j] == 1) {
28
                coords[k].row = i;
29
                coords[k].col = j;
30
                k++;
31
            }
32
    // 模拟新方块落下过程
33
    row = 1, col--;
34
    bool checkflag;
35
    while(true){
36
        checkflag = false;
37
        for(int i=0; i<N; i++)
38
            if(board[row + coords[i].row][col + coords[i].col] == 1) {
39
                checkflag = true;
40
                break;
41
            }
42
        if(checkflag)   break;
43
        row++;
44
    }
45
    row--;
46
    // 合并新方块到方格图
47
    for(int i=0; i<N; i++)
48
        board[row + coords[i].row][col + coords[i].col] = 1;
49
    // 输出结果
50
    for(int i=0; i<ROW; i++) {
51
        for(int j=0; j<COL; j++) {
52
            if(j != 0)  cout << " ";
53
            cout << board[i][j];
54
        }
55
        cout << endl;
56
    }
57
    return 0;
58
}

201604-3 路径解析

1
// CCF 201604-3 路径解析
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n; //路径个数
6
    string curDir; //当前目录
7
    cin >> n >> curDir;
8
    getchar();
9
    for(int i=0; i<n; i++){
10
        string line; //每一个待处理路径
11
        getline(cin, line);
12
        size_t pos;
13
        //添加当前目录
14
        if(line[0] != '/')  line = curDir + '/' + line;
15
        if(line.size() == 0)    line = curDir;
16
        //除去多个'///'
17
        while((pos = line.find("//")) != -1){ 
18
            int count = 2; // '/'的个数
19
            while(line[pos + count] == '/') count++;
20
            line.erase(pos, count-1);
21
        }
22
        //除去'../'
23
        while((pos = line.find("/../")) != -1){ 
24
            if(pos == 0)    line.erase(pos+1, 3);
25
            else{
26
                size_t nxp = line.rfind("/", pos-1);
27
                line.erase(nxp, pos-nxp+3);
28
            }
29
        }
30
        while((pos = line.find("/./")) != -1) //除去'./'
31
            line.erase(pos+1, 2);
32
        if(line.size()>1 && line[line.size()-1]=='/') //除去末尾'/'
33
            line.erase(line.size()-1);
34
        cout << line << endl;
35
    }
36
    return 0;
37
}

201604-4 游戏

201604-5 网络连接

2015年

12月

201512-1 数位之和

1
// CFF 201512-1 数位之和
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, sum = 0;
6
    cin >> n;
7
    while(n>0){
8
        int t = n%10;
9
        sum += t;
10
        n /= 10;
11
    }
12
    cout << sum << endl;
13
    return 0;
14
}
15
16
// CFF 201512-1 数位之和——改进版
17
#include<bits/stdc++.h>
18
using namespace std;
19
int main(){
20
    char x;
21
    int sum=0;
22
    while((x=getchar()) != '\n')
23
        sum += x-'0';
24
    cout << sum;
25
    return 0;
26
}

201512-2 消除类游戏

1
//CCF 201512-2 消除类游戏
2
#include <bits/stdc++.h>
3
using namespace std;
4
int n, m, a[30][30];
5
int main(){
6
    //输入数据
7
    cin >> n >> m;
8
    for(int i=0; i<n; i++)
9
        for(int j=0; j<m; j++)
10
            cin >> a[i][j];
11
    //行可消除的标记为负
12
    for(int i=0; i<n; i++)
13
        for(int j=0; j<m-2; j++)
14
            if(abs(a[i][j])==abs(a[i][j+1]) && abs(a[i][j+1])==abs(a[i][j+2])){
15
                if(a[i][j] > 0) a[i][j] *= -1;
16
                if(a[i][j+1] > 0) a[i][j+1] *= -1;
17
                if(a[i][j+2] > 0) a[i][j+2] *= -1;
18
            }
19
    //列可消除的标记为负
20
    for(int j=0; j<m; j++)
21
        for(int i=0; i<n-2; i++)
22
            if(abs(a[i][j])==abs(a[i+1][j]) && abs(a[i+1][j])==abs(a[i+2][j])){
23
                if(a[i][j] > 0) a[i][j] *= -1;
24
                if(a[i+1][j] > 0) a[i+1][j] *= -1;
25
                if(a[i+2][j] > 0) a[i+2][j] *= -1;
26
            }
27
    //完成消除
28
    for(int i=0; i<n; i++){
29
        for(int j=0; j<m; j++){
30
            if(a[i][j] < 0) a[i][j] = 0;
31
            if(j != 0)  cout << " ";
32
            cout << a[i][j];
33
        }
34
        cout << endl;
35
    }
36
    return 0;
37
}

201512-3 画图

1
//CCF 201512-3 画图
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int DIRECTSIZE = 4;
5
struct direct {
6
    int dx, dy;
7
} direct[DIRECTSIZE] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
8
const int N = 100;
9
char grid[N+1][N+1]; //画布
10
void fill(int x, int y, char c, int m, int n){ //递归填充：被填充的点的四周也要填充
11
    int nx, ny;
12
    grid[y][x] = c;
13
    for(int i=0; i<DIRECTSIZE; i++) {
14
        ny = y + direct[i].dy;
15
        nx = x + direct[i].dx;
16
        if(0<=nx && nx<m && 0<=ny && ny<n && grid[ny][nx]!='|' 
17
            && grid[ny][nx]!='-' && grid[ny][nx]!='+' && grid[ny][nx]!=c)
18
            fill(nx, ny, c, m, n);
19
    }
20
}
21
int main(){
22
    int m, n, q; //画布的宽度、高度、画图操作个数
23
    int x1, y1, x2, y2; //坐标
24
    int start, end; //线段起点和终点
25
    memset(grid, '.', sizeof(grid)); // 变量初始化：全部设置为“.”
26
    cin >> m >> n >> q;
27
    for(int i=1; i<=q; i++) { //依次完成q个画图操作
28
        int option; //每行的画图形式
29
        cin >> option;
30
        if(option == 0) { //画线段
31
            cin >> x1 >> y1 >> x2 >> y2;
32
            if(x1 == x2) {
33
                start = min(y1, y2);
34
                end = max(y1, y2);
35
                for(int j=start; j<=end; j++)
36
                    if(grid[j][x1] == '-' || grid[j][x1] == '+')
37
                        grid[j][x1] = '+';
38
                    else    grid[j][x1] = '|';
39
            } else if(y1 == y2) {
40
                start = min(x1, x2);
41
                end = max(x1, x2);
42
                for(int j=start; j<=end; j++)
43
                    if(grid[y1][j] == '|' || grid[y1][j] == '+')
44
                        grid[y1][j] = '+';
45
                    else    grid[y1][j] = '-';
46
            }
47
        } else if(option == 1) { //填充字符
48
            char c; //填充字符
49
            cin >> x1 >> y1 >> c;
50
            fill(x1, y1, c, m, n); //递归填充
51
        }
52
    }
53
    for(int i=n-1; i>=0; i--) {
54
        for(int j=0; j<m; j++)
55
            cout << grid[i][j];
56
        cout << endl;
57
    }
58
    return 0;
59
}

学习参考：201512-3 画图

201512-4 送货

201512-5 矩阵

9月

201509-1 数列分段

1
// CFF 201509-1 数列分段
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, s = 1;
6
    cin >> n;
7
    int a[n];
8
    cin >> a[0];
9
    for(int i=1; i<n; i++){
10
        cin >> a[i];
11
        if(a[i]!=a[i-1])
12
            s++;
13
    }
14
    cout << s << endl;
15
    return 0;
16
}

201509-2 日期计算

1
// CCF 201509-2 日期计算
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int y, d, k = 0;
6
    cin >> y >> d;
7
    int limit[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
8
    if(y%400==0 || (y%4==0&&y%100)) //是闰年
9
        limit[1] = 29;
10
    for(int i=1; i<12; i++) // 每月的临界天数
11
        limit[i] += limit[i-1];
12
    while(d > limit[k])
13
        k++;
14
    int month = k + 1, day = d - limit[k-1];
15
    cout << month << endl << day << endl;
16
    return 0;
17
}

201509-3 模板生成系统

1
//CCF 201509-3 模板生成系统
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, m;
6
    cin >> n >> m;
7
    cin.get();
8
    string str_in, str_out; //输入和输出的字符串
9
    map<string, string> mmp; //需要处理的map键值对
10
    while(n--){
11
        string line;
12
        getline(cin, line);
13
        str_in += line + '\n';
14
    }
15
    while(m--){
16
        string key, val; //map的键与值
17
        cin >> key;
18
        cin.get();
19
        getline(cin, val);
20
        val = val.substr(1, val.size()-2);
21
        mmp[key] = val;
22
    }
23
    size_t pos, next_pos;
24
    while((pos=str_in.find("{{ ")) != string::npos){ //完成值的填充
25
        next_pos = str_in.find(" }}") + 3;
26
        string key(str_in.begin()+pos+3, str_in.begin()+next_pos-3);
27
        str_out += str_in.substr(0, pos);
28
        str_in = str_in.substr(next_pos);
29
        string var = mmp.count(key) ? mmp[key] : "";
30
        str_out += var;
31
    }
32
    str_out += str_in;
33
    cout << str_out;
34
    return 0;
35
}

201509-4 高速公路

201509-5 最佳文章

3月

201503-1 图像旋转

1
// CFF 201503-1 图像旋转
2
#include <bits/stdc++.h>
3
using namespace std;
4
int a[1024][1024];
5
int main(){
6
    int n, m;
7
    cin >> n >> m;
8
    for(int i=0; i<n; i++)
9
        for(int j=0; j<m; j++)
10
            cin >> a[i][j];
11
    for(int j=m-1; j>=0; j--){
12
        for(int i=0; i<n; i++)
13
            cout << a[i][j] << " ";
14
        cout << endl;
15
    }
16
    return 0;
17
}

201503-2 数字排序

1
// CCF 201503-2 数字排序
2
#include <bits/stdc++.h>
3
using namespace std;
4
int n, a[1024]; //整数个数与整数序列
5
struct node{
6
    int id, cnt; //每个整数的序号和出现次数值
7
    node(int a, int b):id(a), cnt(b){}
8
};
9
vector<node> v; //node结构体类型的vector
10
bool cmp(const node &a, const node &b){ //次数相同时候升序为真
11
    return a.cnt==b.cnt ? a.id<b.id : a.cnt>b.cnt;
12
}
13
int main(){
14
    cin >> n;
15
    for(int i=0; i<n; i++){
16
        int t;
17
        cin >> t;
18
        a[t]++;
19
    }
20
    for(int i=0; i<=1000; i++)
21
        if(a[i])    v.push_back(node(i, a[i]));
22
    sort(v.begin(), v.end(), cmp); //自定义比较规则cmp排序
23
    for(size_t i=0; i<v.size(); i++) //size_t: unsigned int类型的别名
24
        cout << v[i].id << " " << v[i].cnt << endl;
25
    return 0;
26
}

201503-3 节日

1
//CCF 201503-3 节日
2
#include <bits/stdc++.h>
3
using namespace std;
4
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //不是闰年
5
bool IsLeapYear(int y){ //判断是否是闰年
6
    return (y%400==0)||(y%4==0&&y%100);
7
}
8
int HowManyDays(int s, int y, int m){ //计算s年1月1日离y年m月1日有多少天
9
    int days = 0;
10
    while(s < y)    days += IsLeapYear(s++) ? 366 : 365;
11
    if(IsLeapYear(y))   month[2] = 29;
12
    for(int i=1; i<m; i++)  days += month[i];
13
    return days;
14
}
15
int WhichDayInWeek(int w, int b, int c){ //第b个星期c是几号
16
    int day = 1;
17
    while(w != c){
18
        day++;
19
        w++;
20
        if(w == 8) w = 1;
21
    }
22
    return day + 7*(b-1);
23
}
24
int main(){
25
    int a, b, c, y1, y2; //a月第b个星期c、起始年份、终止年份
26
    cin >> a >> b >> c >> y1 >> y2;
27
    for(int year=y1; year<=y2; year++){
28
        int w = (HowManyDays(1850, year, a)+2)%7; //y1-y2每年a月1日是星期几
29
        if(w == 0)  w = 7;
30
        int day = WhichDayInWeek(w, b, c); //求出是a月的几号
31
        if(day > month[a])  cout << "none" << endl;
32
        else printf("%d/%02d/%02d\n", year, a, day);
33
        month[2] = 28;
34
    }
35
    return 0;
36
}

201503-4 网络延时

1
//CCF 201503-4 网络延时
2
#include <bits/stdc++.h>
3
using namespace std;
4
vector<int> v[20018];
5
int n, m;
6
void dfs(int u, int depth, int &maxdepth, int &maxdepvertex, bool visit[]) {
7
    visit[u] = 1;
8
    if(depth > maxdepth) {
9
        maxdepth = depth;
10
        maxdepvertex = u;
11
    }
12
    for(size_t i=0; i<v[u].size(); i++) {
13
        int w = v[u][i]; //u的邻接点
14
        if(!visit[w]) 
15
            dfs(w, depth+1, maxdepth, maxdepvertex, visit);
16
    }
17
}
18
int main() {
19
    cin >> n >> m; //交换机数，终端电脑数
20
    for(int i=2; i<=n; i++) {
21
        int x; //第2～n台交换机连接的上一层交换机的编号
22
        cin >> x;
23
        v[x].push_back(i);
24
        v[i].push_back(x);
25
    }
26
    for(int i=1; i<=m; i++) {
27
        int x; //第1～m台终端连接的交换机的编号
28
        cin >> x;
29
        v[x].push_back(10000+i);
30
        v[10000+i].push_back(x);
31
    }
32
    bool v1[20018] = {0}, v2[20018] = {0}; //visit数组
33
    int maxdepth = -1, maxdepvertex = -1;
34
    dfs(1, 0, maxdepth, maxdepvertex, v1);
35
    dfs(maxdepvertex, 0, maxdepth, maxdepvertex, v2);
36
    cout << maxdepth;
37
    return 0;
38
}

学习参考：201503-4 网络延时 ccf

201503-5 最小花费

2014年

12月

201412-1 门禁系统

1
// CFF 201412-1 门禁系统
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n;
6
    cin >> n;
7
    int cnt[1024] = {0}; //每条记录依次出现的实时次数
8
    int a[1024] = {0}; //每条记录第几次出现
9
    for(int i=0; i<n; i++){
10
        int x;
11
        cin >> x;
12
        cnt[x]++;
13
        a[i] = cnt[x];
14
    }
15
    for(int i=0; i<n; i++)
16
        cout << a[i] << " ";
17
    return 0;
18
}

201412-2 Z字形扫描

1
//CCF 201412-2 Z字形扫描
2
#include <bits/stdc++.h>
3
using namespace std;
4
int n, a[500][500];
5
int main(){
6
    cin >> n;
7
    for(int i=0; i<n; i++)
8
        for(int j=0; j<n; j++)
9
            cin >> a[i][j];
10
    for(int i=0; i<2*n-1; i++){ //一共有 2*n-1 条斜线 
11
        int s = i<n ? 0 : (i-n+1); 
12
        int e = i<n ? i : (n-1);
13
        if(i%2 == 0) //第i条斜线编号是偶数: 从左下打印到右上
14
             for(int j=s; j<=e; j++)
15
                  cout << a[i-j][j] << " ";
16
        else //第i条斜线编号是奇数: 从右上打印到左下 
17
            for(int j=s; j<=e; j++)
18
                  cout << a[j][i-j] << " ";
19
    }
20
    cout << endl;
21
    return 0;
22
}

201412-3 集合竞价

1
//CCF 201412-3 集合竞价
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int N = 5000; //交易行数最大值
5
struct trading { //交易
6
    int orderno; //交易编号
7
    char t; //买（buy）、卖（sell）标志，取值为b、s
8
    float price; //价格
9
    long long quantity; //数量
10
    bool operator < (const trading& n) const { // < 操作符重载
11
        if(t == 's')    return price > n.price;
12
        else    return price < n.price; // t == 'b'
13
    }
14
};
15
bool canceltrading[N+1]; //标记是否撤销了第i行交易记录
16
int main(){
17
    //初始化与输入部分
18
    trading t;
19
    string strading; //每一行交易操作
20
    int tradingno = 0, cancelno; //交易号码、撤销的交易号
21
    priority_queue<trading> sell, buy; //卖、买两个优先队列：数字大的优先级高
22
    memset(canceltrading, false, sizeof(canceltrading)); //变量初始化
23
    while(cin >> strading) {
24
        if(strading[0] == 'c') { //撤销交易
25
            tradingno++;
26
            cin >> cancelno;
27
            canceltrading[cancelno] = true; //设置撤销标志
28
        } else if(strading[0] == 'b' || strading[0] == 's') {
29
            t.orderno = ++tradingno;
30
            cin >> t.price >> t.quantity;
31
            if(strading[0] == 'b') { //将交易放入买入的优先队列
32
                t.t = strading[0];
33
                buy.push(t);
34
            } else { //将交易放入卖出的优先队列
35
                t.t = strading[0];
36
                sell.push(t);
37
            }
38
        } else  break;
39
    }
40
    //集合竞价处理部分
41
    t.price = 0; //开盘价
42
    t.quantity = 0; //此开盘价下的成交量
43
    trading b, s;
44
    while(true) {
45
        while(!buy.empty()) { //清除被取消的buy订单
46
            b = buy.top(); //b为买队列的队头
47
            if(canceltrading[b.orderno])   buy.pop();
48
            else    break;
49
        }
50
        while(!sell.empty()) { //清除被取消的sell订单
51
            s = sell.top(); //s为卖队列的队头
52
            if(canceltrading[s.orderno])   sell.pop();
53
            else    break;
54
        }
55
        if(buy.empty() || sell.empty()) break; //买卖队列只要有一个为空就结束
56
        if(b.price >= s.price) { //买卖交易开始处理
57
            t.quantity += min(b.quantity, s.quantity);
58
            t.price = b.price;
59
            if(b.quantity == s.quantity) {
60
                buy.pop();
61
                sell.pop();
62
            } else if(b.quantity > s.quantity) {
63
                b.quantity -= s.quantity;
64
                buy.pop();
65
                buy.push(b);
66
                sell.pop();
67
            } else {
68
                buy.pop();
69
                s.quantity -= b.quantity;
70
                sell.pop();
71
                sell.push(s);
72
            }
73
        } else  break;
74
    }
75
    // 输出结果部分
76
    printf("%.2f", t.price);
77
    cout << " " << t.quantity << endl;
78
    return 0;
79
}

学习参考：

201412-4 最优灌溉

1
//CCF 201412-4 最优灌溉
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int INF = 1061109567;
5
int mmp[1010][1010]; //各个麦田之间的水渠费用map
6
int lowdist[1010]; //最小花费数组
7
int visit[1010]; //建水渠的麦田数组 1:建 0:不建
8
void prim(int n){ //Prim算法(最小生成树算法)
9
    for(int i=1; i<=n; i++)
10
        lowdist[i] = mmp[1][i];
11
    visit[1] = 1;
12
    int k, sum = 0; //sum为总费用
13
    for(int i=1; i<n; i++){
14
        int min_val = INF; //动态变化的最小费用
15
        for(int j=1; j<=n; j++)
16
            if(!visit[j] && lowdist[j] < min_val){
17
                min_val = lowdist[j];
18
                k = j;
19
            }
20
        visit[k] = 1;
21
        sum += min_val;
22
        for(int j=1; j<=n; j++)
23
            if(!visit[j] && mmp[k][j] < lowdist[j])
24
                lowdist[j] = mmp[k][j];
25
    }
26
    cout << sum;
27
}
28
int main(){
29
    int n, m; //麦田数、可建的水渠数
30
    cin >> n >> m;
31
    memset(mmp, INF, sizeof(mmp)); //将mmp的内容全设为INF
32
    memset(visit, 0, sizeof(visit)); //初始化所有麦田不建水渠
33
    for(int i=0; i<m; i++){
34
        int start, end, value; //水渠起点、终点以及费用
35
        cin >> start >> end >> value;
36
        if(mmp[start][end] > value)
37
            mmp[start][end] = mmp[end][start] = value;
38
    }
39
    prim(n);
40
    return 0;
41
}

学习参考：最小生成树Prim算法理解

201412-5 货物调度

9月

201409-1 相邻数对

1
// 201409-1 相邻数对
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, num = 0;
6
    cin >> n;
7
    int a[n];
8
    for(int i=0; i<n; i++)
9
        cin >> a[i];
10
    sort(a, a+n);
11
    for(int i=1; i<n; i++){
12
        if(a[i]-a[i-1] == 1)
13
            num++;
14
    }
15
    cout << num <<endl;
16
    return 0;
17
}

201409-2 画图

1
// CCF 201409-2 画图
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, xy[100][100] = {0}; //矩形个数、坐标系大小
6
    cin >> n;
7
    int x1, y1, x2, y2, sum = 0; //每个矩形的坐标、颜色方块数
8
    for(int i=0; i<n; i++){ //处理每一个矩形
9
        cin >> x1 >> y1 >> x2 >> y2;
10
        for(int j=x1; j<x2; j++)
11
            for(int k=y1; k<y2; k++)
12
                if(!xy[j][k]){ //避免重复
13
                    sum++;
14
                    xy[j][k] = 1;
15
                }
16
    }
17
    cout << sum << endl;
18
    return 0;
19
}

201409-3 字符串匹配

1
//CCF 201409-3 字符串匹配
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    string str; //待匹配字符串、输出文本
6
    int is_dif, n; //大小写敏感标识符、文本行数
7
    cin >> str >> is_dif >> n;
8
    while(n--){
9
        string new_str;  //每一行识别文本
10
        cin >> new_str;
11
        if(is_dif == 1){ //大小写敏感
12
            size_t pos = new_str.find(str);
13
            if(pos != string::npos)
14
                cout << new_str << endl;
15
        }else{ //大小写不敏感: 全转化为小写再匹配
16
            string tmp, txt; //临时的str、new_str
17
            for(size_t i=0; i<str.size(); i++)
18
                tmp += tolower(str[i]);
19
            for(size_t i=0; i<new_str.size(); i++)
20
                txt += tolower(new_str[i]);
21
            size_t pos = txt.find(tmp);
22
            if(pos != string::npos)
23
                cout << new_str << endl;
24
        }
25
    }
26
    return 0;
27
}

201409-4 最优配餐

1
//CCF 201409-4 最优配餐
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int N = 1000;
5
const int DIRECTSIZE = 4;
6
struct direct { //前进方向
7
    int drow, dcol;
8
} direct[DIRECTSIZE] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
9
int buyer[N+1][N+1]; //客户坐标下的订餐量
10
int visited[N+1][N+1]; //经过的点坐标 1:不可再经过 0:可经过
11
int buyercount = 0; //客户数量
12
long long ans = 0; //最终送餐费用
13
struct node {
14
    int row, col, step;
15
    node(){}
16
    node(int r, int c, int s){row=r, col=c, step=s;}
17
};
18
queue<node> q; //分店节点队列
19
void bfs(int n){ //广度优先搜索
20
    node front, v;
21
    while(!q.empty()){
22
        front = q.front();
23
        q.pop();
24
        for(int i=0; i<DIRECTSIZE; i++){
25
            //移动一格
26
            v.row = front.row + direct[i].drow;
27
            v.col = front.col + direct[i].dcol;
28
            v.step = front.step + 1;
29
            //行列越界则跳过
30
            if(v.row<1 || v.row>n || v.col<1 || v.col>n) continue;
31
            // 已经访问过的点不再访问
32
            if(visited[v.row][v.col]) continue;
33
            // 如果是订餐点，则计算成本并且累加
34
            if(buyer[v.row][v.col] > 0) {
35
                visited[v.row][v.col] = 1;
36
                ans += buyer[v.row][v.col] * v.step;
37
                if(--buyercount == 0)   return;
38
            }
39
            // 向前搜索：标记v点为已经访问过，v点加入队列中
40
            visited[v.row][v.col] = 1;
41
            q.push(v);
42
        }
43
    }
44
}
45
int main(){
46
    int n, m, k, d; //方格图大小、分店数、客户数、禁止通行点的数量
47
    int x, y, c; //分店/客户/禁止点坐标与订餐量
48
    memset(buyer, 0, sizeof(buyer));
49
    memset(visited, 0, sizeof(visited));
50
    cin >> n >> m >> k >> d;
51
    for(int i=1; i<=m; i++){ //依次输入分店坐标
52
        cin >> x >> y;
53
        q.push(node(x, y, 0));
54
        visited[x][y] = 1;
55
    }
56
    for(int i=1; i<=k; i++){ //依次输入客户坐标
57
        cin >> x >> y >> c;
58
        if(buyer[x][y]==0)
59
            buyercount++;
60
        buyer[x][y] += c;
61
    }
62
    for(int i=1; i<=d; i++){ //依次输入禁止通行的点
63
        cin >> x >> y;
64
        visited[x][y] = 1;
65
    }
66
    bfs(n);
67
    cout << ans << endl;
68
    return 0;
69
}

学习参考：

201409-5 拼图

3月

201403-1 相反数

1
// 201403-1 相反数
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, num = 0;
6
    cin >> n;
7
    int a[1024] = {0};
8
    for(int i=0; i<n; i++){
9
        int x;
10
        cin >> x;
11
        a[abs(x)]++;
12
    }
13
    for(int i=0; i<1000; i++){
14
        if(a[i]==2)
15
            num++;
16
    }
17
    cout << num <<endl;
18
    return 0;
19
}

201403-2 窗口

1
//CCF 201403-2 窗口
2
#include <bits/stdc++.h>
3
using namespace std;
4
struct window{
5
    int x1, y1, x2, y2, num; //窗口位置坐标、窗口序号
6
    window(int a=0,int b=0,int c=0,int d=0,int x=0):x1(a),y1(b),x2(c),y2(d),num(x){}
7
};
8
vector<window> v;
9
bool check(int x, int y, window &w){ //检查(x, y)是否在窗口w上
10
    return (x>=w.x1 && y>=w.y1 && x<=w.x2 && y<=w.y2) ? true : false;
11
}
12
int todo(int x, int y){
13
    size_t i = 0;
14
    while(i < v.size()){
15
        if(check(x, y, v[i])){
16
            window temp = v[i];
17
            v.erase(v.begin()+i); //删除第i项
18
            v.insert(v.begin(), temp); //重新插入
19
            cout << temp.num << endl;
20
            return 0;
21
        }
22
        i++;
23
    }
24
    cout << "IGNORED\n";
25
}
26
int main(){
27
    int n, m; //n个窗口、m次点击操作
28
    cin >> n >> m;
29
    v.resize(n);
30
    for(int i=n-1; i>=0; i--){ //依次建立各个窗口结构体
31
        int x1, y1, x2, y2;
32
        cin >> x1 >> y1 >> x2 >> y2;
33
        v[i] = window(x1, y1, x2, y2, n-i);
34
    }
35
    while(m--){ //依次执行操作
36
        int x, y;
37
        cin >> x >> y;
38
        todo(x, y);
39
    }
40
    return 0;
41
}

201403-3 命令行选项

1
//CCF 201403-3 命令行选项
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int N = 256;
5
char delimiter[] = " "; //字符串分割符
6
void spilt(vector<string>& v, char *s, char *t){
7
    char *sp;
8
    sp = strtok(s, t); //字符串切割函数，参数为字符串和分割符
9
    while(sp) {
10
        v.push_back(sp);
11
        sp = strtok(NULL, t); //第一次用一个字符串做第一个参数，以后用NULL做第一个参数
12
    }
13
}
14
void mygetline(char *pc){
15
    char c;
16
    while((c=getchar()) != '\n' && c !=EOF)
17
        *pc++ = c;
18
    *pc = '\0';
19
}
20
int main(){
21
    string format; //命令格式
22
    int n; //命令行数
23
    char s[N+1]; //每行命令
24
    cin >> format >> n;
25
    getchar();
26
    for(int i=1; i<=n; i++) { // 输入n行命令行进行处理
27
        vector<string> sv; //分割后的命令行片段vector
28
        map<string, string> m;
29
        mygetline(s); // 输入命令行
30
        spilt(sv, s, delimiter); // 切分命令行：命令和各个参数分开
31
        for(int j=1; j<(int)sv.size(); j++) { // 处理各个参数，放入map变量ｍ中
32
            if(sv[j].size() == 2 && sv[j][0] == '-') { // 判断是否是选项，选项则处理
33
                int pos = format.find(sv[j][1]);
34
                if(pos == -1) // 选项在格式中未找到则出错结束
35
                    break; 
36
                if(m.find(sv[j]) == m.end()) // 选项未出现过则添加
37
                    m[sv[j]] = "";
38
                if(format[pos+1] == ':' && j+1 < (int)sv.size()) { // 更新参数：后出现优先
39
                    m[sv[j]] = sv[j+1];
40
                    j++;
41
                }
42
            } else
43
                break;
44
        }
45
        // 输出结果
46
        cout << "Case " << i << ":";
47
        for(map<string,string>::iterator iter=m.begin(); iter!=m.end(); iter++) {
48
            cout << " " << iter->first;
49
            if(iter->second != "")
50
                cout << " " << iter->second;
51
        }
52
        cout << endl;
53
    }
54
    return 0;
55
}

201403-4 无线网络

1
//CCF CCF201403-4 无线网络
2
#include <bits/stdc++.h>
3
using namespace std;
4
const int MAXN = 100 + 100; //路由器最大数量
5
struct {  long long x, y;  } coord[MAXN+1]; //n+m个路由器的坐标结构数组
6
struct status {
7
    long long x, y;
8
    int step, kcount; //步数，可连接路由器数
9
};
10
bool visited[MAXN+1]; //已访问过的路由器设置为true
11
int router(int n, int m, int k, int begin, int end, long long r){
12
    int max;
13
    memset(visited, false, sizeof(visited));
14
    status start, front, v; //开始路由器，队头路由器，访问路由器
15
    start.x = coord[begin].x; //设置根结点start
16
    start.y = coord[begin].y;
17
    start.step = 0;
18
    start.kcount = 0;
19
    queue<status> q; //路由器访问队列
20
    q.push(start);
21
    visited[begin] = true;
22
    while(!q.empty()) {
23
        front = q.front(); //依次出队列访问
24
        q.pop();
25
        if(front.x==coord[end].x && front.y==coord[end].y) //到达终点 结束
26
            return front.step - 1;
27
        if(front.kcount == k)   max = n; //搜索可以连接的路由器
28
        else    max = n + m;
29
        for(int i=0; i<max; i++) {
30
            if(visited[i])  continue;
31
            if((front.x-coord[i].x)*(front.x-coord[i].x)+(front.y-coord[i].y)*(front.y-coord[i].y) > r*r)
32
                continue; //判定下一个路由器坐标是否在半径r之内，不在则跳过，在则继续搜索
33
            else {
34
                visited[i] = true;
35
                //计算步数，并且将第i个路由器加入队列
36
                v.x = coord[i].x;
37
                v.y = coord[i].y;
38
                v.step = front.step + 1;
39
                if(i >= n)
40
                    v.kcount = front.kcount + 1;
41
                else
42
                    v.kcount = front.kcount;
43
                q.push(v);
44
            }
45
        }
46
    }
47
    return 0;
48
}
49
int main() {
50
    int n, m, k; //已放置路由器数，可再放置的位置数，新增路由器最大数
51
    long long r; //确保网络间连接的最大距离
52
    cin >> n >> m >> k >> r;
53
    for(int i=0; i<n+m; i++) //依次输入原路由器和新增路由器的位置
54
        cin >> coord[i].x >> coord[i].y;
55
    cout << router(n, m, k, 0, 1, r) << endl;
56
    return 0;
57
}

201403-5 任务调度

2013年

12月

201312-1 出现次数最多的数

1
//CCF 201312-1 出现次数最多的数
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, maxval = -1;
6
    cin >> n;
7
    int a[10001] = {0};
8
    for(int i=0; i<n; i++){
9
        int t;
10
        cin >> t;
11
        a[t]++;
12
    }
13
    for(int i=1; i<=10000; i++)
14
        maxval = max(maxval, a[i]);
15
    for(int i=1; i<=10000; i++)
16
        if(maxval == a[i]){
17
            cout << i << endl;
18
            break;
19
        }
20
    return 0;
21
}

201312-2 ISBN号码

1
// CCF 201312-2 ISBN号码
2
#include <bits/stdc++.h>
3
using namespace std;
4
char valX(int s){
5
    return s%11==10 ? 'X' : '0'+s%11; //数字转字符: +'0'
6
}
7
int main(){
8
    int sum = 0, i = 1, j = 0;
9
    char str[16], ch;
10
    while((ch=cin.get()) != '\n'){
11
        str[j++] = ch;
12
        if(isdigit(ch)){
13
            if(i<=9)    sum += i*(ch-'0'); //字符转数字: -'0'
14
            i++;
15
        }
16
    }
17
    str[j] = '\0'; //空字符表示字符串末尾
18
    char x = valX(sum);
19
    if(str[j-1] == x)
20
        cout << "Right\n";
21
    else{
22
        str[j-1] = x;
23
        printf("%s\n", str);
24
    }
25
    return 0;
26
}

201312-3 最大的矩形

1
// CCF 201312-3 最大的矩形
2
#include <bits/stdc++.h>
3
using namespace std;
4
int main(){
5
    int n, ans = -1, height[1024]; //矩阵个数、最大矩形面积、矩形高度数组
6
    cin >> n;
7
    for(int i=1; i<=n; i++)
8
        cin >> height[i];
9
    for(int i=1; i<=n; i++){
10
        int min_height = height[i];
11
        for(int j=i+1; j<=n; j++){
12
            min_height = min(min_height, height[j]);
13
            ans = max(min_height*(j-i+1), ans);
14
        }
15
    }
16
    cout << ans << endl;
17
    return 0;
18
}

201312-4 有趣的数

1
// CCF 201312-4 有趣的数
2
/* 方法一：组合数学的思路：（假设0、1、2、3分别有a、b、c、d个）
3
   （1）0在1前面且不在首位：a+b-1种
4
   （2）2和3其中一个在首位，假设是2在首位。将剩余c-1个2和d个3插入已经放好的a+b+1个数中，
5
       即：把c+d-1个相同球放入a+b+1个相同的盒子（可空）中，即C(a+b+1+c+d-1-1,c+d-1)种
6
   （3）2和3一共有c+d-1种
7
    故总共有： C(a+b+1+c+d-1-1,c+d-1) * （a+b-1） * （c+d-1）种
8
*/
9
#include <bits/stdc++.h>
10
#define MAX 1010
11
using namespace std;
12
long long MOD=1000000007, n, s[MAX][MAX], ans=0;
13
int main(){
14
    for(int i=1; i<MAX; i++)
15
        s[i][i]=1, s[i][1]=i, s[i][0]=1;
16
    for(int i=2; i<MAX; i++)
17
        for(int j=1; j<i; j++)
18
            s[i][j] = (s[i-1][j-1]+s[i-1][j]) % MOD;
19
    cin >> n;
20
    for(int i=2; i<=n-2; i++){
21
        ans = (ans+s[n-1][i-1]*(i-1)*(n-i-1)) % MOD;
22
    }
23
    cout << ans << endl;
24
    return 0;
25
}
26
/* 方法二：动态规划
27
题目给出了0，1，2，3四个数，现考察一系列中间状态，即选取四个数的子集，在满足题设条件下，共有如下6种状态
28
状态0：2 
29
状态1：0 2 
30
状态2：2 3 
31
状态3：0 1 2 
32
状态4：0 2 3 
33
状态5：0 1 2 3 
34
最终我们需要求得的结果是状态5，用sta[i][j]表示一系列中间过程，其中i表示数的位数，j表示状态
35
显然，i=0时，所有的不同结果都为0（边界条件）
36
对于状态0来说，所选取的集合只有2，所以对于任意数位n，其不同个数始终为1
37
对于状态1来说，数位为i时的结果可以通过第i-1位状态获得，包括
38
              (1)通过状态0获得，只能在第i位时添加0，即sta[i-1][0]
39
              (2)通过本身状态1获得，在第i位添加0或者2，即sta[i-1][1]*2
40
              所以，sta[i][1]=sta[i-1][0]+sta[i-1][1]*2
41
对于状态2来说，数位为i时的结果可以通过第i-1位状态获得，包括
42
              (1)通过状态0获得，只能在第i位时添加3，即sta[i-1][0]
43
              (2)通过本身状态2获得，只能在第i位添加3，即sta[i-1][2]
44
              所以，sta[i][2]=sta[i-1][0]+sta[i-1][2]
45
其余状态同理，也即是，对于任意状态，总可以通过前序状态或者本身状态获得
46
所有转移方程如下
47
sta[i][0]=1
48
sta[i][1]=sta[i-1][0]+sta[i-1][1]*2
49
sta[i][2]=sta[i-1][0]+sta[i-1][2]
50
sta[i][3]=sta[i-1][1]+sta[i-1][3]*2
51
sta[i][4]=sta[i-1][1]+sta[i-1][2]+sta[i-1][4]*2
52
sta[i][5]=sta[i-1][3]+sta[i-1][4]+sta[i-1][5]*2
53
对状态的补充：
54
一个数情况，必须是2（首位必须是2）
55
           (0)2
56
两个数情况，必须有2，其余只能是0，3（0必须在1前面）
57
           (1)0 2
58
           (2)2 3
59
三个数情况，必须有2，其余可能是0，1或者0，3
60
           (3)0 1 2
61
           (4)0 2 3
62
四个数情况，(5)0 1 2 3
63
6种状态整理完毕
64
*/
65
#include <bits/stdc++.h>
66
using namespace std;
67
long long mod=1000000007, sta[1024][6], n;
68
int main(){
69
    scanf("%lld", &n);
70
    for(long long i=1; i<=n; i++){
71
        sta[i][0] = 1;
72
        sta[i][1] = (sta[i-1][0]+sta[i-1][1]*2) % mod;
73
        sta[i][2] = (sta[i-1][0]+sta[i-1][2]) % mod;
74
        sta[i][3] = (sta[i-1][1]+sta[i-1][3]*2) % mod;
75
        sta[i][4] = (sta[i-1][1]+sta[i-1][2]+sta[i-1][4]*2) % mod;
76
        sta[i][5] = (sta[i-1][3]+sta[i-1][4]+sta[i-1][5]*2) % mod;
77
    }
78
    printf("%lld\n", sta[n][5]);
79
    return 0;
80
}

学习参考：

201312-5 I’m stuck!