CCF-CSP认证考试准备第十七天

写了一些第3题大模拟，难点为题意的理解和字符串的处理，以及一些模拟的难点，考虑到时间迫近，刷第3题效率不怎么高，继续刷之后的第1和2题，保持手感

### Day17:1.201803-1 2.201803-2 3.201803-3

#### 1.201803-1:跳一跳(小模拟)
简单，过

#### 2.201803-2:碰撞的小球(小模拟)
(1)满分代码:
```
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int n,L,t;
    cin>>n>>L>>t;
    vector<int> vballs(n,0);
    vector<int> vspeeds(n,1);
    for(int i=0;i<n;i++){
        cin>>vballs[i];
    }
    while(t--){
        //先移动前检查 
        for(int i=0;i<n;i++){
            //初始位置和最后位置优先考虑 
            if( (vballs[i]==L && vspeeds[i]==1) || (vballs[i]==0 && vspeeds[i]==-1)){
                vspeeds[i]=-vspeeds[i];
            }
            vballs[i]+=vspeeds[i];
        }
        //再检测是否碰撞(只改变一次) 
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(vballs[i]==vballs[j]){
                    vspeeds[i]=-vspeeds[i];
                    vspeeds[j]=-vspeeds[j];
                    break;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<vballs[i]<<" ";
    }
    return 0;
}
```
(2)注意：一开始检测碰撞j从0开始遍历，会导致一对i和j被更改两次，等于不变，j应该从i+1开始遍历；移动前检测初始位置不止要看位置，还要看速度，两个限制条件
(3)**原来想通过先排序来优化的，但是会丢失顺序导致输入有问题，但是可以构建结构体数组储存id，先按位置排序，检测碰撞只要检测i和i+1即可，大大优化，最后再按id返回原来顺序即可**，但这题数据量较小，没有较大区别

#### 3.201803-3:URL映射(大模拟)
鉴于离CCF-CSP认证还有4天，自己写第3题太耗时间，所以找到一个# [CCF-CSP 第三题字符串整理(模拟大法好)](https://www.cnblogs.com/demian/p/9609223.html "发布于 2018-09-08 14:56")博客，希望阅读别人的代码来增强自己的第3题能力
(1)本题难点：
1.规则的相邻两项之间用‘/’分开，所以我们先把所有项分开：(**重点学习**)分离字符串这里用**字符串流处理，先把所有的‘/’变为空格，然后一个一个把各项分开。**
2.**原代码是开多个数组，后面使用要回过头看，太麻烦，直接封装成结构体,思考想要储存什么数据（输入的，中途判断的条件），要用什么数据结构（数组，一维or二维？）**
3.题目中关于' \ '的判断，末尾有呢还是没有？
4.模拟的细节注意，判断条件的先后顺序决定能不能提前return false退出，以及能不能中间一个else if判断到那直接return true（写函数的好处体现出来了，return true和return false异常简单）
5.像这种去匹配n个规则的某一个的，函数传入参数为一个规则，遍历在main函数里面写，**这题的结果string result是作为引用参数传入函数来改变的，而不是作为函数的返回结果**，因为match函数最终是起到bool判断效果判断输出结果，但在判断中途就可以改变result，所以选择为引用参数传入函数
(2)优化满分代码:
```
#include<bits/stdc++.h>

#define LL unsigned long long

using namespace std;

const int MAXN = 101;

struct Rule {
    string name;               // 规则名称
    string pattern;            // 规则 URL 模式
    int paramCount;            // 规则中的参数个数
    int hasSlash;             // 规则是否以 '/' 结尾
    string parts[MAXN];        // 规则的各个部分
};

Rule rules[MAXN];               // 保存所有规则
string queryParts[MAXN];        // 保存查询 URL 的各个部分
int hasSlash;                   // 查询的 URL 是否以 '/' 结尾

// 判断输入的字符串是否为整数，并去除前导零
string isNum(string s) {  
    bool isOk = false;
    string num;
    int len = s.length();
    for(int i = 0; i < len; i++) {
        if (s[i] < '0' || s[i] > '9') return "-";//学习点1：这个函数返回值不是bool值(直接将判断和提取变成一个函数了)，所以不符合条件返回"-"
        if (isOk || s[i] != '0'){
            num += s[i];
            isOk = true;
        }
    }
    return num == "" ? "0" : num;
}

// 解析 URL 或规则，将其按 '/' 分割，并保存在 parts 数组中
void parseURL(string s, int &hasSlash, string parts[], int &count) {
    hasSlash = count = 0;
    int len = s.length();
    if (s[len - 1] == '/') hasSlash = 1;
    //学习点2，将' \ '变为空格后字符串输入流提取每一项字符串
    for (int p = 0; p < len; p++) {
        if (s[p] == '/') s[p] = ' ';
    }
    stringstream ssIn(s);
    string part;
    while (ssIn >> part) parts[count++] = part;
}

// 判断当前 URL 是否匹配第 j 条规则，并提取参数
bool match(int t, const Rule &rule, string &result) {  
    result = "";
    int p1 = 0, p2 = 0;
    if (hasSlash ^ rule.hasSlash) return false; 
    while (p1 < t && p2 < rule.paramCount) {
        if (queryParts[p1] == rule.parts[p2]);
        else if (rule.parts[p2] == "<int>") {
            string num = isNum(queryParts[p1]);
            if (num == "-") return false;
            result += " " + num;
        } 
        else if (rule.parts[p2] == "<str>") {
            result += " " + queryParts[p1];
        } 
        else if (rule.parts[p2] == "<path>") {
            result += " " + queryParts[p1++];
            while (p1 < t) result += "/" + queryParts[p1++];
            if (hasSlash) result += '/';
            return true;
        } 
        else return false;
        p1++; p2++;
    }
    if (p1 != t || p2 != rule.paramCount) return false; 
    return true;
}

int main() {                                          
    int n, m;
    cin >> n >> m;
    // 输入 n 条规则
    for (int i = 0; i < n; i++) {
        cin >> rules[i].pattern >> rules[i].name;
        parseURL(rules[i].pattern, rules[i].hasSlash, rules[i].parts, rules[i].paramCount);
    }
    // 输入 m 个查询 URL
    for (int i = 0; i < m; i++) {
        string result, query;
        int partCount = 0;
        hasSlash = 0;
        cin >> query;
        parseURL(query, hasSlash, queryParts, partCount);
        bool matched = false;
        //依次与n条规则相匹配
        for (int j = 0; j < n; j++) {
            if (match(partCount, rules[j], result)) {
                cout << rules[j].name << result << endl;
                matched = true;
                break;
            }
        }
        if (!matched) cout << 404 << endl;
    }
    return 0;
}

```
（3）**重点学习**：
**通过特定分隔符划分字符串片段**：
本题(将\变成空格): ^516dc0
```
for (int p = 0; p < len; p++) {
        if (s[p] == '/') s[p] = ' ';
    }
    stringstream ssIn(s);
    string part;
    while (ssIn >> part) parts[count++] = part;
```
**getline优化**:
```
stringstream ssIn(s); 
string part; count = 0; 
while (getline(ssIn, part, '/')) { // 直接以 '/' 分割 (注意getline的顺序)
    if (!part.empty()) { // 跳过空的部分 
    parts[count++] = part; 
    } 
}
```