csp-201509

2020-08-31

20150903（模板生成系统）

代码1

用unordered_map<string, string> varToStr 来建立变量到字符串的映射。对于每一行，找到，若找不到则把它看做正常字符串，若找到了，再看中间的字符串是不是，例如name，若是，则替换，否则将它看做正常的字符串。

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

vector<string> input;
int m,n;
unordered_map<string,string> varToStr;

int main(){
    //freopen("D://input.txt","r",stdin);
    cin>>m>>n;
    cin.get();
    for(int i=0;i<m;i++){
        string line;
        getline(cin,line);
        input.push_back(line);
    }
    for(int i=0;i<n;i++){
        string line,var,str;
        getline(cin,line);
        int k = line.find(' ');
        var = line.substr(0,k);
        int k1 = line.find('"',k);
        int k2 = line.find('"',k1+1);
        str = line.substr(k1+1,k2-k1-1);
        varToStr[var] = str;
    }

    for(int i=0;i<m;i++){
        string& line = input[i];
        string line2;
        int k1=0, k2;
        while(k1<line.size()){
            k2 = line.find("{{",k1);
            if(k2==string::npos){
                line2 += line.substr(k1);
                k1 = line.size();
            }else{
                line2 += line.substr(k1,k2-k1);
                k1 = k2;
                k2 = line.find("}}",k1+2);
                string s1 = line.substr(k1+3,k2-k1-4);
                if(varToStr.find(s1)!=varToStr.end()){
                    line2 += varToStr[s1];
                }
                k1 = k2+2;
            }
        }
        cout<<line2<<endl;
    }
}

20150904（高速公路）

代码1

对每个点运行BFS算法，得到这个点可达的所有点，然后就可以知道哪两个点是互通的了。但是肯定超时，得60或70分没问题。

代码2

用tarjan算法求强联通分量。