csp-201712

20171201（最小差值）

代码1

排序，找出每相邻两个数差值的最小值。

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

int n;
vector<int> num;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    num.resize(n);
    for(int i=0;i<n;i++) cin>>num[i];
    sort(num.begin(),num.end());
    int ans = INT_MAX;
    for(int i=0;i<n-1;i++){
        ans = min(ans,num[i+1]-num[i]);
    }
    cout<<ans;
}

20171202（游戏）

代码1

使用vector<bool> isOut 来表示各个小朋友是否出局, isOut[0]=true表示0+1=1号小朋友出局。int cnt=1 记录当前应该报第什么数，int outNum=0记录出局了多少个人。bool canOut(int x) 判断数字x是否可以出局。

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

int n,k;
int cnt=1, outNum=0;
vector<bool> isOut;

bool canOut(int x){
    if(x%k==0){
        return true;
    }else if(x-(x/10)*10==k){
        return true;
    }else{
        return false;
    }
}

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n>>k;
    //init
    isOut.resize(n);
    for(int i=0;i<n;i++) isOut[i]=false;

    int i=0;
    while(outNum != n-1){
        if(isOut[i]){
            i = (i+1)%n;
            continue;
        }
        if(canOut(cnt)){
            isOut[i]=true;
            outNum++;
        }
        cnt++;
        i = (i+1)%n;
    }
    //output
    for(int i=0;i<n;i++){
        if(isOut[i]==false){
            cout<<i+1;
            break;
        }
    }
}

20171203（Crontab）

代码1

设计一个数据结构来表示每个任务的可满足的运行时间段和系统时间

1
2
3
4
5
6
7
8
9
10
11
12
13
struct RunnableTime{
    bool minutes[60];
    bool hours[24];
    bool days[32]; //[1,31]
    bool months[13]; //[1,12]
    bool weekdays[7]; //表示星期几
}
struct Time{
    int year, month, day, hour, minute;
    bool operator<(const Time& t2)const{
        
    }
}

写一个函数void incTime(Time& t) 来递增系统时间。bool satisfy(const RunnableTime& rt, const Time& t) 来看rt是否在满足t时间，这个函数可能要用到星期转换的函数int getWeekDay(const Time& t) 。

对于输入，要处理, 和- 的情况。可以写一个函数pair<RunnableTime,string> dealInput(string input) 来得到时间段和任务名的对应关系，最后存储到vector<pair<RunnableTime,string>> rtToDuty 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

struct RunnableTime{
    bool minutes[60];
    bool hours[24];
    bool days[32]; //[1,31]
    bool months[13]; //[1,12]
    bool weekdays[7]; //表示星期几
    RunnableTime(){
        memset(minutes,0,sizeof(minutes));
        memset(hours,0,sizeof(hours));
        memset(days,0,sizeof(days));
        memset(months,0,sizeof(months));
        memset(weekdays,0,sizeof(weekdays));
    }
};
struct Time{
    int year, month, day, hour, minute;
    bool operator<(const Time& t2)const{
        if(year!=t2.year){
            return year<t2.year;
        }else if(month != t2.month){
            return month<t2.month;
        }else if(day != t2.day){
            return day<t2.day;
        }else if(hour != t2.hour){
            return hour<t2.hour;
        }else{
            return minute<t2.minute;
        }
    }
};

int n;
Time beg,ed;
vector<pair<RunnableTime,string>> rtToDuty;
int daysOfMonth[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
map<string,int> monthToNum = {{"jan",1},{"feb",2},{"mar",3},{"apr",4},{"may",5},{"jun",6},{"jul",7},{"aug",8},{"sep",9},{"oct",10},{"nov",11},{"dec",12}};
map<string,int> weekdayToNum = {{"sun",0},{"mon",1},{"tue",2},{"wed",3},{"thu",4},{"fri",5},{"sat",6}};

bool isRunYear(int year){
    if(year%4==0&&year%100!=0 || year%400==0){
        return true;
    }else{
        return false;
    }
}

void incTime(Time& t){
    t.minute++;
    if(t.minute!=60){
        return;
    }
    t.minute=0;
    t.hour++;
    if(t.hour!=24){
        return;
    }
    t.hour=0;
    t.day++;
    if(t.month!=2&&t.day!=daysOfMonth[t.month]+1 || t.month==2&&(isRunYear(t.year)&&t.day!=30 || !isRunYear(t.year)&&t.day!=29)){
        return;
    }
    t.day = 1;
    t.month++;
    if(t.month != 13){
        return;
    }
    t.month=1;
    t.year++;
}
void tolower2(string& s){
    for(int i=0;i<s.size();i++){
        s[i] = tolower(s[i]);
    }
}
pair<RunnableTime,string> dealInput(string input){
    pair<RunnableTime,string> prs;
    prs.first = RunnableTime();
    string s;
    int i1=0,i2;
    int cnt = 0;
    while(i1!=input.size()){
        i2 = input.find(' ',i1);
        s = input.substr(i1,i2-i1);
        if(cnt==5){
            prs.second = s;
            break;
        }
        if(s=="*"){
            if(cnt==0){
                for(int i=0;i<60;i++) prs.first.minutes[i]=true;
            }else if(cnt==1){
                for(int i=0;i<24;i++) prs.first.hours[i]=true;
            }else if(cnt==2){
                for(int i=0;i<32;i++) prs.first.days[i]=true;
            }else if(cnt==3){
                for(int i=0;i<13;i++) prs.first.months[i]=true;
            }else{
                for(int i=0;i<7;i++) prs.first.weekdays[i]=true;
            }
        }else{
            int j1=0,j2=0;
            for(;j1<s.size();){
                if(j2<s.size() && s[j2]==',' || j2>=s.size()){
                    //prs.first.minute[stoi(s.substr(j1,j2-j1))] = true;
                    string s1 = s.substr(j1,j2-j1);
                    int num1;
                    if(isdigit(s1[0])){
                        num1 = stoi(s1);
                    }else{
                        tolower2(s1);
                        num1 = (cnt==3?monthToNum[s1]:weekdayToNum[s1]);
                    }
                    if(cnt==0){
                        prs.first.minutes[num1]=true;
                    }else if(cnt==1){
                        prs.first.hours[num1]=true;
                    }else if(cnt==2){
                        prs.first.days[num1]=true;
                    }else if(cnt==3){
                        prs.first.months[num1]=true;
                    }else{
                        prs.first.weekdays[num1]=true;
                    }
                    if(j2<s.size()){
                        j1 = j2+1;
                        j2++;
                    }else{
                        j1 = j2;
                    }
                }else if(j2<s.size() && s[j2]=='-'){
                    int j3 = j2;
                    for(j2=j2+1;j2!=s.size()&&s[j2]!=',';j2++){};
                    string s1=s.substr(j1,j3-j1),s2=s.substr(j3+1,j2-j3-1);
                    int num1,num2;
                    if(isdigit(s1[0])){
                        num1=stoi(s1);
                    }else{
                        tolower2(s1);
                        num1 = (cnt==3?monthToNum[s1]:weekdayToNum[s1]);
                    }
                    if(isdigit(s2[0])){
                        num2=stoi(s2);
                    }else{
                        tolower2(s2);
                        num2 = (cnt==3?monthToNum[s2]:weekdayToNum[s2]);
                    }
                    if(cnt==0){
                        for(int i=num1;i<=num2;i++) prs.first.minutes[i]=true;
                    }else if(cnt==1){
                        for(int i=num1;i<=num2;i++) prs.first.hours[i]=true;
                    }else if(cnt==2){
                        for(int i=num1;i<=num2;i++) prs.first.days[i]=true;
                    }else if(cnt==3){
                        for(int i=num1;i<=num2;i++) prs.first.months[i]=true;
                    }else{
                        for(int i=num1;i<=num2;i++) prs.first.weekdays[i]=true;
                    }
                    if(j2!=s.size()){
                        j1 = j2+1;
                        j2++;
                    }else{
                        j1 = j2;
                    }
                }else if(j2<s.size()){
                    j2++;
                }
            }
        }
        cnt++;
        i1 = i2+1;
    }
    return prs;
}
int getWeekDay(const Time& t){
    int weekday=4;
    for(int year=1970;year<t.year;year++){
        if(isRunYear(year)){
            weekday = (weekday+366)%7;
        }else{
            weekday = (weekday+365)%7;
        }
    }
    for(int month=1;month<t.month;month++){
        if(month!=2){
            weekday = (weekday+daysOfMonth[month])%7;
        }else{
            if(isRunYear(t.year)){
                weekday = (weekday+29)%7;
            }else{
                weekday = (weekday+28)%7;
            }
        }
    }
    weekday = (weekday+t.day-1)%7;
    return weekday;
}
bool satisfy(const RunnableTime& rt, const Time& t){
    if(!rt.months[t.month]){
        return false;
    }
    if(!rt.days[t.day]){
        return false;
    }
    if(!rt.hours[t.hour]){
        return false;
    }
    if(!rt.minutes[t.minute]){
        return false;
    }
    int weekday = getWeekDay(t);
    if(!rt.weekdays[weekday]){
        return false;
    }
    return true;
}
void printTime(const Time& t){
    cout<<setw(4)<<setfill('0')<<right<<t.year;
    cout<<setw(2)<<setfill('0')<<right<<t.month;
    cout<<setw(2)<<setfill('0')<<right<<t.day;
    cout<<setw(2)<<setfill('0')<<right<<t.hour;
    cout<<setw(2)<<setfill('0')<<right<<t.minute;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>n;
    rtToDuty.resize(n);
    for(int i=0;i<2;i++){
        string str;
        cin>>str;
        Time t;
        t.year = stoi(str.substr(0,4));
        t.month = stoi(str.substr(4,2));
        t.day = stoi(str.substr(6,2));
        t.hour = stoi(str.substr(8,2));
        t.minute = stoi(str.substr(10,2));
        if(i==0) beg = t;
        else ed = t;
    }
    cin.get();
    for(int i=0;i<n;i++){
        string input;
        getline(cin,input);
        rtToDuty[i] = dealInput(input);
    }

    for(Time t=beg;t<ed;incTime(t)){
        vector<string> duties;
        for(int j=0;j<n;j++){
            if(satisfy(rtToDuty[j].first,t)){
                duties.push_back(rtToDuty[j].second);
            }
        }
        for(int j=0;j<duties.size();j++){
            printTime(t);
            cout<<" "<<duties[j]<<endl;
        }
    }
}

95分。运行超时。2个小时做完。

代码2

我可以直接用Long long 存储系统时间，减少了转换为结构体的工作；代码1是对所有时间，计算符合该时间的crontab，时间复杂度是O(时间长度*n)，代码2根据每个crontab计算符合要求的时间，过程是遍历每个可能的年，每个可能的月，每个可能的日，每个可能的时，每个可能的分，看最后的时间是否在[beg, ed)内并满足星期的要求，若是，则在该时间对应的crontab set集合中插入该crontab，这个方案更好。

核心代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void computeCrontab(int c){//计算符合该crontab的时间，以及建立时间点到命令的映射ans
    for(int y=s/year; y<=t/year; y++){ //遍历所有年份
        for(int m : commandTime[3]){ //遍历crontab中符合要求的月份
            for(int d : commandTime[2]){ //遍历crontab中的所有天
                if(d > daysOfMonth(y,m))
                    continue;
                if(find(commandTime[4].begin(),commandTime[4].end(),
                        determineWeek(y,m,d)) != commandTime[4].end()){
                    //说明这一天的星期数是符合crontab要求的
                    for(int h : commandTime[1]){
                        for(int minute : commandTime[0]){
                            //格式化时间
                            long long temp = (long long)y*year + m*month + d*day + h*hour + minute;
                            if(temp>=s && temp<t){
                                ans[temp].push_back(c);
                            }
                        }
                    }
                }
            }

        }
    }
}

20171204（行车路线）

代码1

这题运用Dijkstra算法，但是有一点不同时，每次计算距离，不是直接累加，而是通过完整的路径来计算，所以核心是要记录路径。vector<int> pre 来保存每个点的最短路径的前驱结点，有了这个，就有了路径。

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

int n,m;
vector<vector<array<int,2>>> graph; //第一个数字表示道路类型(-1表示没有连接),第二个数字表示距离

long long getPathCost(vector<int>& path){
    long long ans = 0;
    int i = 0;
    while(i<path.size()-1){
        int a=path[i],b=path[i+1];
        if(graph[a][b][0]==0){
            ans += graph[a][b][1];
            i++;
        }else{
            int j=i+1;
            long long a = graph[path[i]][path[j]][1];
            while(j<path.size()-1 && graph[path[j]][path[j+1]][0]==1){
                a += graph[path[j]][path[j+1]][1];
                j++;
            }
            ans += a*a;
            i = j;
        }
    }
    return ans;
}

vector<int> pre;
vector<long long> dist;
vector<bool> vis;
void Dijkstra(){
    //init
    for(int i=0;i<=n;i++) pre[i]=0;
    for(int i=0;i<=n;i++) dist[i]=INF;
    for(int i=0;i<=n;i++) vis[i]=false;

    int u = 1;
    dist[1] = 0;
    for(int i=0;i<n;i++){
        u = -1;
        long long minDist = INF;
        for(int j=1;j<=n;j++){
            if(!vis[j] && dist[j]<minDist){
                u = j;
                minDist = dist[j];
            }
        }
        if(u == -1) break;
        vis[u] = true;
        for(int j=1;j<=n;j++){
            if(u!=j && graph[u][j][0]!=-1 && !vis[j]){
                vector<int> path;
                path.push_back(j);
                int a = u;
                while(a!=0){
                    path.push_back(a);
                    a = pre[a];
                }
                reverse(path.begin(),path.end());
                long long pathCost = getPathCost(path);
                if(pathCost < dist[j]){
                    dist[j] = pathCost;
                    pre[j] = u;
                }
            }
        }
    }
}
int main(){
    //freopen("D://input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    graph.resize(n+1);
    for(int i=0;i<=n;i++){
        graph[i].resize(n+1);
        for(int j=0;j<=n;j++){
            graph[i][j] = {-1,0};
        }
    }
    pre.resize(n+1);
    dist.resize(n+1);
    vis.resize(n+1);

    //input
    int type,a,b,c;
    for(int i=0;i<m;i++){
        cin>>type>>a>>b>>c;
        graph[a][b] = {type,c};
        graph[b][a] = {type,c};
    }

    Dijkstra();
    cout<<dist[n]<<endl;
}

90分。错误。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

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>谢谢大家