Skip to content

2016年06月份CCF总结反思

总体感悟

  • 第一题：太蠢，不谈
  • 第二题：走了很大弯路，应该思考一下，第二题不难的
  • 第三题：吐血了，STL一定要会用
  • 第四题：很好的题目，如何把最小生成树和最短路径结合起来。

第四题题解

这个题目很好，特地写一下，即最小生成树和最短路径如何结合。

首先，要以Dijkstra为主，但是不同的是，要记录每个点的lastedge，比如有条边(1,2,10)被选中，那么点2的lastedge就是该边。

每次更新的时候，如果发现最短路径是相同的，那么看看lastedge是否比这条新边大，如果大那么lastedge就更新这条边。这就保证了最小生成树的产生。

细节收获

vector的总结反思

insert(v.begin()+pos,element)
erase(v.begin()+pos,element)

两个vector作比较

就不要去想什么奇技淫巧了。

int a_index = 0;
for (auto& x : b)
{
    if(a_index == a_count) return;
    ...
}

map的总结反思

查找key值是否存在

if(map.count(key) > 0)

遍历输出

for (auto x = demo.begin(); x != demo.end(); ++x)
{
    cout << x->first << " " << x->second << endl;
}

String的总结反思

其他样式转为string

采用to_string()即可。

去除末尾字符

  1. 首先要知道C++是利用记录字符串长度来知道如何结束，C是利用结尾为'\0'来看的。
  2. 因此不推荐str[str.size()-1] = '\0'这种写法，因为这样C++维护的字符串长度不变，会造成以后错误
  3. 推荐使用str.erase(str.end()-1);

字符串切割操作

就是利用getline(istream,string,char)，就是不断的把istream放进string中，如果遇到char的那个字符，就停止。

template<typename Out>
void split(const std::string &s, char delim, Out result) {
    std::stringstream ss(s);
    std::string item;
    while (std::getline(ss, item, delim)) {
        *(result++) = item;
    }
}

std::vector<std::string> split(const std::string &s, char delim) {
    std::vector<std::string> elems;
    split(s, delim, std::back_inserter(elems));
    return elems;
}

字符串忽略大小写比较

struct iequal
{
    bool operator()(int c1, int c2) const
    {
        return std::toupper(c1) == std::toupper(c2);
    }
};

bool iequals(const std::string& str1, const std::string& str2)
{
    return std::equal(str1.begin(), str1.end(), str2.begin(), iequal());
}

字符串清空空格字符

bool isspace(int item)
{
    if (item == ' ') 
        return true; 
    return false;
}
str.erase(remove_if(str.begin(), str.end(), isspace), str.end());

详细解释一下
bool isOdd(int item)
{
    return (item - '0') % 2;
}
int main()
{
    string test = "123456";
    remove_if(test.begin(),test.end(),isOdd);
    cout << test << endl;
    // 输出结果为246456
    // 可以看到它把所有不应该remove的元素都放在了前面
    // 而他的返回值也顺理成章地是那些合法元素的最后位置+1，这个例子中就是3，其指向的是4，所以利用erase就可以把456都删除掉了
}

字符串去掉前导0

利用find_first_not_of即可

str.erase(0, min(str.find_first_not_of('0'), str.size()-1))

控制流

文件读入

freopen("in.txt","r",stdin)

读取一行然后进行内部操作

for (...)
{
    string line;
    getline(cin,line);
    stringstream ss(line);
    ss >> x >> y;
}

getline的问题

第一次getline前如果有scanf等读取输入的操作，需要在scanf之后使用cin.get()或cin.ignore()`