acmTrick.md

算法竞赛的小技巧

STL篇

• count函数：

count(a.begin(), a.end(), 1) 获取a中1出现的次数

• accumulate函数

accumulate(a.begin(), a.end(), 0)	从0开始累加a中的元素

accumulate还可以自定义数据类型：

vector<pair<ll, ll>> a;
ll sum = accumulate(a.begin(), a.end(), 0LL, [](ll a, pair<ll, ll> x){return a + x.first;});

注意long long时的初始值要加上LL

• 组反向排序(从大到小)

sort(a.rbegin(), a.rend())

• string类型find

int a = s.find('1');	//找到第一个出现'1'的位置

找不到返回string::npos。示例用法：

char c;
if(string("codeforces").find(c) != string::npos){
	puts("YES");
}
//	string可以用string("")初始化

• string类型substr

s.substr(a);	//截取s从位置a到末尾的子字符串
s.substr(s.find('1'))	//可以配合find使用

常用代码pieces

• 树的存储

vector<vector<int>> g(n);
for(int i = 1; i < n; i++){
    int x;
    cin >> x;
    x--;
    g[x].push(i);
    g[i].push(x);
}

• 交互题

bool ask(你询问的内容){
	cout << 一些你应该输出的;
	cout.flush();
	return 判断条件 ? true : false;
}

• min_element & max_element

  //	求下标
  int idx = min_element(a.begin(), a.begin() + n) - a.begin();
  //	求最值
  int x = *min_element(a.begin(), a.end());