csp-201709

20170901（打酱油）

代码1

这题运用贪心的方法，N元钱能买多少个5瓶就买多少个，剩下能买多少个3瓶就买多少个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int N;
int ans = 0;

int main(){
    cin>>N;
    int a = N/50;
    int b = N - a*50;
    ans += a*7;
    int c = b/30;
    int d = b - c*30;
    ans += c*4;
    ans += d/10;
    cout<<ans<<endl;
}

20170902（公共钥匙盒）

代码1

设计一个数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
struct Trans{
    int time,id,type;
    bool operator<(const Trans& t2){
        if(time != t2.time){
			return time<t2.time;
        }else if(type != t2.type){
            return type>t2.type;
        }else{
            return id<t2.id;
        }
    }
}

表示在什么时间做什么事，第一个表示取/还的时间，第二个表示钥匙编号，第三个表示0是取，1是还。根据输入将所有的trans保存在vector<Trans> transes 中，然后排序。vector<int> keys 保存每个位置的钥匙编号，-1表示为空位置。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct Trans{
    int time,id,type;
    Trans(int a,int b,int c){
        time = a;
        id = b;
        type = c;
    }
    bool operator<(const Trans& t2)const{
        if(time != t2.time){
            return time<t2.time;
        }else if(type != t2.type){
            return type>t2.type;
        }else{
            return id<t2.id;
        }
    }
};
int N,K;
vector<int> keys;
vector<Trans> transes;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>N>>K;
    keys.resize(N);
    for(int i=0;i<N;i++) keys[i] = i+1;
    for(int i=0;i<K;i++){
        int id,time,dur;
        cin>>id>>time>>dur;
        transes.push_back(Trans{time,id,0});
        transes.push_back(Trans{time+dur,id,1});
    }
    sort(transes.begin(),transes.end());

    for(int i=0;i<transes.size();i++){
        Trans& t = transes[i];
        if(t.type == 0){
            for(int j=0;j<N;j++){
                if(keys[j]==t.id){
                    keys[j] = -1;
                }
            }
        }else{
            for(int j=0;j<N;j++){
                if(keys[j]==-1){
                    keys[j] = t.id;
                    break;
                }
            }
        }
    }

    //output
    for(int i=0;i<N;i++){
        if(i==0) cout<<keys[i];
        else cout<<" "<<keys[i];
    }
}

20170903（JSON查询）

代码1

将所有的输入的行都保存在一个没有换行符的字符串中string input。将查询分解为vector<string> query ，第0个表示0级查询的字符串，第1个表示1级查询的字符串。构建一个函数pair<int,string> Query(int beg, vector<string>& query, int k) 表示从beg位置的左括号开始查找当前层的query[k]字符，若找到了，则要么返回字符串类型，要么返回对象，要么继续向下递归查找，若没有找到，则返回没有找到。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
string input;

//从x开始找到下一个引号的位置，若没有则返回-1
int findNextYinhao(int x){
    int i;
    for(i=x;i<input.size()&&input[i]!='"';){
        if(input[i]=='\\'){
            i = i+2;
        }else{
            i++;
        }
    }
    return (i<input.size()?i:-1);
}
//x可以是右引号后面的位置。看对应的值是对象还是字符串，若是对象，则first=false
pair<bool,int> findValue(int x){
    int i;
    for(i=x;input[i]!='{'&&input[i]!='"';i++){}
    if(input[i]=='{') return {false,i};
    else return {true,i};
}
//将s中的转义字符去掉
void dealString(string& s){
    string s2;
    int i=0,j;
    while(i<s.size()){
        j = s.find('\\',i);
        if(j != string::npos){
            s2 += s.substr(i,j-i);
            s2 += s.substr(j+1,1);
            i = j+2;
        }else{
            s2 += s.substr(i);
            i = s.size();
        }
    }
    s = s2; //error
}
//first=0表示找到了字符串，first=1表示对象，first=2表示不存在
pair<int,string> Query(int beg, vector<string>& query, int k){
    int i1=findNextYinhao(beg),i2;
    while(i1!=-1){ //每次循环开始，i1总是指向键的第一个引号
        i2=findNextYinhao(i1+1);
        string s1 = input.substr(i1+1,i2-i1-1);
        dealString(s1); //error
        pair<bool,int> valueType = findValue(i2+1); //表明后面的值是字符串还是对象
        if(s1==query[k]){
            if(k==query.size()-1){
                if(valueType.first==false){ //object
                    return {1,""};
                }else{ //string
                    int j1 = valueType.second;
                    int j2 = findNextYinhao(j1+1);
                    string value = input.substr(j1+1,j2-j1-1);
                    dealString(value);
                    return {0,value};
                }
            }else{
                if(valueType.first==false){ //递归
                    return Query(valueType.second,query,k+1);
                }else{
                    return {2,""};
                }
            }
        }else{
            if(valueType.first == false){ //后面是对象
                i1 = valueType.second+1;
                int layer=1;
                while(layer>0){
                    if(input[i1]=='{'){
                        layer++;
                    }else if(input[i1]=='}'){
                        layer--;
                    }
                    i1++;
                }
                i1 = findNextYinhao(i1);
            }else{ //后面时字符串
                i1 = findNextYinhao(valueType.second+1);
                i1 = findNextYinhao(i1+1);
            }
        }
    }
    return {2,""};
}

void splitQuery(string line, vector<string>& query){
    int i1 = 0, i2;
    while(i1<line.size()){
        i2 = line.find('.',i1);
        query.push_back(line.substr(i1,i2-i1));
        i1 = (i2==string::npos?line.size():i2+1);
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    cin.get();
    for(int i=0;i<n;i++){
        string line;
        getline(cin,line);
        input += line;
    }

    while(m--){
        string line;
        cin>>line;
        vector<string> query;
        splitQuery(line,query);
        pair<int,string> ans = Query(0,query,0);
        if(ans.first == 0){
            cout<<"STRING "<<ans.second<<endl;
        }else if(ans.first == 1){
            cout<<"OBJECT"<<endl;
        }else{
            cout<<"NOTEXIST"<<endl;
        }
    }
}

43行，51行，犯了点粗心错误。

20070904（通信网络）

代码1

对每个点a运行BFS算法，就知道a和谁可以互相知道。vector<set<int>> know 表示哪个点知道哪个点，know[1]里面的点就是1知道的点。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<bool>> graph;
vector<set<int>> know;

void bfs(int x){
    know[x].insert(x);
    queue<int> q;
    vector<bool> vis(n+1);
    for(int i=0;i<n+1;i++) vis[i] = false;
    q.push(x);
    vis[x] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int j=1;j<=n;j++){
            if(j!=u && graph[u][j] && !vis[j]){
                know[x].insert(j);
                know[j].insert(x);
                q.push(j);
                vis[j] = true;
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    know.resize(n+1);
    graph.resize(n+1);
    for(int i=0;i<n+1;i++){
        graph[i].resize(n+1);
        for(int j=0;j<n+1;j++){
            graph[i][j] = false;
        }
    }
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a][b] = true;
    }

    for(int i=1;i<=n;i++){
        bfs(i);
    }

    //output
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(know[i].size()==n){
            ans++;
        }
    }
    cout<<ans;
}

60分。运行超时。

代码2

其实我只要将vector<set<int>> know 换成int know[][] 就好了。从k1开始遍历，所有能遍历到的k2，都有know[k1][k2]=1和know[k2][k1]=1。还有，要把邻接矩阵改为邻接表，这很重要，因为可以减少遍历每个点的邻接点的时间，以前是要遍历n次，但是现在只用遍历邻接点数量次。

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
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int>> graph;
int know[1005][1005];

void bfs(int x){
    know[x][x] = 1;
    know[x][0]++;
    queue<int> q;
    vector<bool> vis(n+1,false);
    //for(int i=0;i<n+1;i++) vis[i] = false;
    q.push(x);
    vis[x] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int j=0;j<graph[u].size();j++){
            int v = graph[u][j];
            if(v!=u && !vis[v]){
                if(know[x][v]==0){
                    know[x][v] = 1;
                    know[x][0]++;
                }
                if(know[v][x]==0){
                    know[v][x] = 1;
                    know[v][0]++;
                }
                q.push(v);
                vis[v] = true;
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>m;
    graph.resize(n+1);
    memset(know,0,sizeof(know));

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
    }

    for(int i=1;i<=n;i++){
        bfs(i);
    }

    //output
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(know[i][0]==n){
            ans++;
        }
    }
    cout<<ans;
}
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家