无聊的会议 (meeting. pas/. c/. cpp)

时间限制 1s 内存限制 128MB

题目描述

土豪学长作为一名光荣的学生会干部, 每天要参加很多无聊的会议. 他发现: 他开会的会议桌一定是正 n 边形, n 个干部坐在这个多边形顶点上. 因为太无聊了, 所以他想要数出所有的 “完全” 等腰三角形----这种等腰三角形的三个顶点一定全是给出 n 多边形的顶点, 且三个顶点上坐的干部性别相同.

土豪学长是土豪, 他用 1000000000% 10 的佣金雇用你, 让你帮他数. PS: 如果两个 “完全” 等腰三角形三个顶点相同, 计算时只算一个.

输入描述

第一行一个数字 T, 表示有 T 组数据.

接下来有 T 组数据, 每组数据共一行. 这一行给出一个长度为 n 的字符串, 表示正 n 边形 n 个顶点上干部的性别. 1 为男, 0 为女.

输出描述

对于第 i 组数据: 输出 “Case i: ans” (不带引号),ans 为 “完全” 等腰三角形的数量.

样例输入

5
0001
01
10001
1101010
111010

样例输出

Case 1: 1
Case 2: 0
Case 3: 1
Case 4: 3
Case 5: 2

数据范围

40% 的数据保证 \(n \leq 20\) 100% 的数据保证 \(n \leq 10^6\) 所有数据保证 \(T \leq 10\)

Explanation

大概将所有符合条件的三角形用类容斥原理解一下. 先算出所有的等腰三角形, 再算出所有的非完美等腰三角形 (即三个顶点不全为同色的三角形).

具体的解释在源代码内, 自行脑补细节.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 1000100;

lli n, arr[maxn];

// This evaluates all isosceles triangles (count, obviously), regardless of
// their vertex colours.
lli eval_total(void)
{
    // Every two points form an edge, an edge creates 3 triangles.
    // Three distinct edges can form 1 triangle, therefore
    // res = n * (n - 1) / 2 -> edges
    //       / 3 * 3;        -> all triangles
    lli res = n * ((n - 1) / 2);
    // Equilateral triangles can be created hence.
    if (n % 3 == 0)
        res -= n / 3 * 2;
    return res;
}

// This function evaluates the number of removed triangles.
// The removed triangles are those which satisfies:
//  1. Is an isosceles triangle
//  2. Vertexes are not of the same colour
// After this removal the rest remaining are those which satisfies the problem
// statements.
lli eval_removed(void)
{
    lli res = 0;
    if (n % 2 == 1) { // Odd
        lli cnt_0 = 0, cnt_1 = 0; // How many 0s and +1s, respectively
        for (int i = 1; i <= n; i++)
            (arr[i] == 0 ? cnt_0 : cnt_1)++;
        // At a chance any 0 and any 1 could form an edge, and this edge forms
        // exactly three isosceles triangles. These triangles are to be deduced
        // from the final result, as they do not satisfy property #2.
        // We do not count edge duplications now.
        res = cnt_0 * cnt_1 * 3;
        // If it is able to create equilateral triangles, find ways to deduct
        // the improper triangles.
        if (n % 3 == 0) {
            lli n_div_3 = n / 3,
                n_div_3_2 = n / 3 * 2;
            // In sheer syntax, this finds equilateral triangles that compose
            // duplications.
            for (int i = 1; i <= n; i++)
                res -= int(arr[i] != arr[(i - 1 + n_div_3) % n + 1]) +
                    int(arr[i] != arr[(i - 1 + n_div_3_2) % n + 1]);
        }
        // Restore duplex duplication correction.
        res /= 2;
    } else { // Even
        lli cnt_0_odd = 0, cnt_0_even = 0, // Refer to code above for details.
            cnt_1_odd = 0, cnt_1_even = 0;
        for (int i = 1; i <= n; i += 2)
            (arr[i] == 0 ? cnt_0_odd : cnt_1_odd)++;
        for (int i = 2; i <= n; i += 2)
            (arr[i] == 0 ? cnt_0_even : cnt_1_even)++;
        // Potential duplicates
        res = cnt_0_even * cnt_1_odd * 2 + cnt_1_even * cnt_0_odd * 2 +
            cnt_0_even * cnt_1_even * 4 + cnt_0_odd * cnt_1_odd * 4;
        // Because it is even
        lli n_div_2 = n / 2;
        for (int i = 1; i <= n; i++)
            res -= int(arr[i] != arr[(i - 1 + n_div_2) % n + 1]);
        // If it is able to create equilateral triangles, find ways to deduct
        // the improper triangles.
        if (n % 3 == 0) {
            lli n_div_3 = n / 3,
                n_div_3_2 = n / 3 * 2;
            // In sheer syntax, this finds equilateral triangles that compose
            // duplications.
            for (int i = 1; i <= n; i++)
                res -= int(arr[i] != arr[(i - 1 + n_div_3) % n + 1]) +
                    int(arr[i] != arr[(i - 1 + n_div_3_2) % n + 1]);
        }
        // Restore duplex duplication correction.
        res /= 2;
    }
    return res;
}

int T;
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        memset(str, 0, sizeof(str));
        scanf("%s", str + 1);
        n = strlen(str + 1);
        for (int i = 1; i <= n; i++)
            arr[i] = str[i] - '0';
        // What a nice idea...
        lli res = eval_total() - eval_removed();
        printf("Case %d: %lld\n", idx, res);
    }
    return 0;
}