2.9 寒假练习赛Round 1

貌似好久没有写了，今天来补一下寒假的比赛。

T1 NKOJ 4489 同色三角形

何老板给出坐标平面上的n个点(编号1到n)。其中不存在3个点共线的情况。
任意两点都用被何老板用蓝色线条或者橙色线条连接了起来。
如果一个三角形的三条边颜色是相同，颜色就很朴素，何老板称为朴素三角形。何老板请你帮忙计算，平面上总共有多少个朴素三角形。

思路：直接暴力找就行了（wtcl）。

#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

int a[1005][1005];

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        a[x][y] = a[y][x] = 1;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            for (int k = j + 1; k <= n; k++)
            {
                if ((a[i][j] == a[i][k]) && (a[i][k] == a[j][k])) ans++;
            }
        }
    }
    printf("%lld", ans);
}

T2 NKOJ 4490 素数的个数

建议自行看题。

思路：预处理出每个质数能被A数组整除的次数，因Ai <= 10000000故只需处理10000000以内的质数，然后维护前缀和即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn = 10000000;

ll vis[maxn << 2], p[maxn << 2], num[maxn << 2], sum[maxn << 2];

inline void prime()
{
    for (ll i = 2; i <= maxn; i++)
    {
        if (!vis[i]) p[++p[0]] = i;
        for (ll j = 1; j <= p[0] && i * p[j] <= maxn; j++)
        {
            vis[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}


main()
{
    prime();
    ll n, x;
    scanf("%lld", &n);
    while (n--)
    {
        scanf("%lld", &x);
        for (ll i = 2; i * i <= x; i++)
        {
            if (!vis[i] && x % i == 0)
            {
                num[i]++;
            }
            while (x % i == 0) x /= i;
        }
        if (x) num[x]++;
    }
    for (ll i = 1; i <= 10000000; i++)
    {
        sum[i] = sum[i - 1] + num[i];
    }
    ll m;
    scanf("%lld", &m);
    while (m--)
    {
        ll l, r;
        scanf("%lld%lld", &l, &r);
        if (l >= 10000000) 
        {
            puts("0");
            continue;
        }
        if (r >= 10000000) r = 10000000;
        printf("%lld\n", sum[r] - sum[l - 1]);
    }
}

T3 NKOJ 4497 科学馆开灯

科学馆走廊上有一排共n盏灯，从左往右编号1到n，同时墙上有n个开关，每个开关对应一盏灯。今晚何老板来机房查看信竞队员的训练情况。此前队员们已经打开了其中一些灯。何老板觉得走廊灯光昏暗，不利于大家行走，于是他想把所有灯都打开，让走廊变得明亮起来。
何老板开灯的操作很独特，每次开灯操作他只会选一盏满足下列两个条件的灯：
1.该灯处于关闭状态
2.该灯相邻的灯中至少有一盏已经处于开启状态了

何老板想知道，使得所有灯都点亮，总共有多少种不同的方案。请你帮他计算，结果可能很大，mod 1000000007 再输出。

思路：考虑两个性质：对于两盏亮灯中的一段区间而言，每次都是左右都可选，于是对于每一种方案都有2^len-1种点亮顺序（注意最后一盏灯没有左右），再考虑点亮任两个区间的方案数。因为可以将点亮顺序任意交织，等同于将ab两个区间点亮时挑lena个点将其点亮，就是插板法。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll fac[1005] = {1}, ifac[1005], a[1005];

void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

inline ll KSM(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1) (ans *= a) %= mod;
        b >>= 1, (a *= a) %= mod;
    }
    return ans;
}

inline ll inv(ll a)
{
    ll x, y;
    exgcd(a, mod, x, y);
    return (x % mod + mod) % mod;
}

inline ll C(ll n, ll m)
{
    return fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    ll qwq = n - m, ans = 0, len = 0;
    for (ll i = 1; i <= m; i++)
    {
        scanf("%lld", &a[i]);
    }
    for (ll i = 1; i <= 1000; i++)
    {
        fac[i] = fac[i - 1] * i % mod;    
        ifac[i] = inv(fac[i]);
    }
    ifac[0] = inv(fac[0]);
    sort(a + 1, a + m + 1);
    ans += C(qwq, a[1] - 1), qwq -= a[1] - 1;
    for (ll i = 2; i <= m; i++)
    {
        len = a[i] - a[i - 1] - 1;
        ans = (ans * C(qwq, len) % mod + mod) % mod, qwq -= len;
        if (len) ans = (ans * KSM(2, len - 1) % mod + mod) % mod;
    }
    printf("%lld", ans);
}

2.9 寒假练习赛Round 1

推荐阅读