数学（六）

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

预处理出来从1到i的前缀以及后缀和（1＜=i＜=n），查询的时候查表即可得到。

void solve() {

int n;cin＞＞n;

vector＜int＞ a(n);

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

cin＞＞a[i];

}

vector＜int＞ l(n), r(n);//l[i]表示从0到i所需要花费的最小值

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

if (i == n - 1 || a[i + 1] - a[i]＞a[i] - a[i - 1]) {

l[i] = l[i - 1] + 1;

} else {

l[i] = l[i - 1] + a[i] - a[i - 1];

}

}

r[n - 1] = 0;

for (int i = n - 2; i ＞= 0; i--) {

if (i == 0 || a[i] - a[i - 1]＞a[i + 1] - a[i]) {

r[i] = r[i + 1] + 1;

} else {

r[i] = r[i + 1] + a[i + 1] - a[i];

}

}

int q;cin＞＞q;

while (q--) {

int x, y;

cin＞＞x＞＞y;

x--, y--;

int ans;

if (x＜y) {

ans = r[x] - r[y];

} else {

ans = l[x] - l[y];

}

cout＜＜ans＜＜"\n";

}

}

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。