Codeforces Round #837 (Div. 2)

A. Hossam and Combinatorics

知识点：简单题
复杂度：\(O(nlogn)\)

很明显能看出，该题与数据的位置无关，只与大小有关
所以我们可直接排序，判断最大与最小元素个数即可
注意特判所有元素均相等情况

#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;

ll n, m, k;
int a[N];

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    if (a[1] == a[n]) cout << n * (n - 1) << endl;
    else
    {
        ll x(0), y(0);
        rep(i, 1, n) if (a[i] == a[1]) x++;
        rep(i, 1, n) if (a[i] == a[n]) y++;
        cout << x * y * 2 << endl;
    }
}

B. Hossam and Friends

知识点：计数，思维题
复杂度：\(O(nlogn)\)

很明显能观察出当一段区间内有一对互不相认的人时，该区间不合法
所以我们可以枚举区间左端点，找到每一对中不相认的较大编号的人的最小值，即可得到合法个数
显然当一对不相认的人的较小编号在我们枚举的区间左端点左边时，该较大编号对我们没影响，可以删去
分别用vector和multiset实现即可

#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;

int n, m, k;
vc<int> h[N];
void solve()
{
    cin >> n >> m;
    rep(i, 1, n) h[i].clear();
    multiset<int> s;
    s.insert(n + 1);
    rep(i, 1, m)
    {
        int x, y; cin >> x >> y;
        if (x > y) swap(x, y);
        h[x].pb(y);
        s.insert(y);
    }
    ll ans(0);
    rep(i, 1, n)
    {
        ans += *s.begin() - i;
        for (auto x : h[i]) s.erase(s.find(x));
    }
    cout << ans << endl;
}

C. Hossam and Trainees

知识点：质因数分解，线性筛
复杂度：\(O(n^2logn)\)

fst了，1e3*1e3==1e9，我可真是大聪明

显然我们可以用一个set存储所有数的质因数，如果有两个数有相同的质因数时，输出YES
如果直接暴力筛质因数，复杂度为\(O(1e5*\sqrt{1e9}*log(1e5*10))\)，复杂度爆炸
（1e9大小的数最多有10个不同的质因子）
但是如果我们先筛出\(\sqrt{1e9}\)内的质数，
那么负责度就降为\(O(1e5*\frac{\sqrt{1e9}}{ln\sqrt{1e9}}*log(1e6)+\sqrt{1e9})\)，大约为\(O(1e6*log(1e6))\)

#define rep(i,l,r) for(int i=l,_##i=r;i<=_##i;i++)
#define per(i,r,l) for(int i=r,_##i=l;i>=_##i;i--)
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define pll pair<ll,ll>
#define pii pair<int,int>
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T> >;
const int N = 1e5 + 5;

int n, m, k;
int a[N];

const int M = 4e4 + 5;

bool prime[M];
int p[M], pn = 0;
 
void get_prime(int n)
{
    fill(prime + 2, prime + n + 1, true);
    for (int i = 2; i <= n; i++)
    {
        if (prime[i]) p[++pn] = i;
        for (int j = 1; p[j] * i <= n; j++)
        {
            prime[i * p[j]] = false;
            if (i % p[j] == 0) break;
        }
    }
}

void solve()
{
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    set<int> s;
    rep(i, 1, n)
    {
        for (int j = 1; j <= pn && p[j] <= a[i] / p[j]; j++)
        {
            if (a[i] % p[j] == 0)
            {
                if (s.count(p[j]))
                {
                    YES;
                    return;
                }
                s.insert(p[j]);
                while (a[i] % p[j] == 0) a[i] /= p[j];
            }
        }
        if (a[i] > 1)
        {
            if (s.count(a[i]))
            {
                YES;
                return;
            }
            s.insert(a[i]);
        }
    }
    NO;
}

void init()
{
    cin >> T_T;
    get_prime(40000);
}

D. Hossam and (sub-)palindromic tree

知识点：不知道
复杂度：\(O(不知道)\)

没做出来，有时间就补