数学（六） (2-1)

A.Tricky Template

难度：0，思维

实际上想通一个东西就明白了，无论任何情况a，b总能与模板匹配，我们找到一个字母不让c匹配就可以

1.a=b=c 取c的大写字母

2.a!=b!=c 取c的大写字母

3.a=b!=c 取a小写字母都可以

4.a=c!=b 取除c，b以外的大写字母，相当于无效答案，此时这个字母都匹配

void solve()

{

int n;

string a,b,c;

cin＞＞n＞＞a＞＞b＞＞c;

for(int i=0;i＜n;i++)

if(a[i]!=c[i]&&b[i]!=c[i])

{

cout＜＜"YES"＜＜endl;

return;

}

cout＜＜"NO"＜＜endl;

}

B. Forming Triangles

因为是2α[i] 作为三角形的边长，所以情况很简单，只有两种情况能构成三角形.

简易证明：

1.三边不等,我们不妨设a＜b＜c，显然小边之和小于第三边;

2.两边相等，a＞b=c,同样无法组成三角形，此时只能有a＜b=c的情况可以组成三角形

3.三边相等时显然成立。

因此对于a=b=c，a＜b=c这两种情况，用组合数算即可

参考jiangly，C³ₖ 用来枚举第一种情况，k为枚举到当前数时，其出现次数。 C²ₖ * tot 用来枚举第二种情况，tot为在此之前（也就是比当前数字小的数字的出现次数总和）。

void solve() {

int n;std::cin＞＞n;

std::vector＜int＞cnt(n + 1);

for (int i = 0; i＜n; i++) {

int a;

std::cin＞＞a;

cnt[a]++;

}

i64 ans = 0;int tot = 0;

for (int i = 0; i ＜= n; i++) {

//已经排序过，因为枚举的是从0到n的数字

ans += 1LL * cnt[i] * (cnt[i] - 1) * (cnt[i] - 2) / 6;

ans += 1LL * cnt[i] * (cnt[i] - 1) / 2 * tot;

tot += cnt[i];

}

std::cout＜＜ans＜＜"\n";

}

C. Closest Cities

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。