Codeforces Round #572 (Div. 2)

B. Number Circle

题意:给你 $s_1,s_2,dots,s_ns1,s2,…,sn 。你要将它们排列成一个环形，使得该环每个位置上的数都严格小于它两个“邻居”的和。如果有这种方案，在第一行输出YES，在第二行输出任意一种方案；否则输出NO即可。$

如果把你输出的数列记作 $x_ixi 的“邻居”是 x_{i-1}xi−1 和 x_{i+1}xi+1；特殊地，x_1x1 的“邻居”是 x_2x2 和 x_nxn ,x_nxn 的邻居是 x_1x1 和 x_{n-1}xn−1 。很显然，你可以从环的任意一个位置开始输出，这只会造成环的旋转，不会影响结果。$

贪心：

将其排序观察 a2 发现贪心只能取 a1 a3作为其邻居所以一路这样下去直到最后三个

如果是升序的话要满足 a[n]<a[1]+a[n-1]

但是可以最后三个可以变成 a[n-2] a[n] a[n-1] 此时只要满足 a[n]<a[n-2]+a[n-1] 即可（且这对比上面那对显然更容易满足）

C 签到

D1. Add on a Tree

给定一棵树一开始边权全部为0

每次可以选择两个叶子结点和一个v 将其路径上的所有边加v 问能通过该操作（无限次）构造出任意种边权

显然当存在一个结点的vis==2 时不行其他都可以（反证 vis==2说明连有两边要使这两边的数值不同是不可能的）

E. Count Pairs

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
#define lson l,m,pos<<1
#define rson m+1,r,pos<<1|1
//////////////////////////////////
#define inf 0x3f3f3f3f3f3f3f3f
const int N=1e5+5;

map<int,int>mp;
set<int>s;
ll n,m,k,p;
ll x;
int main()
{
    cin>>n>>p>>k;
    rep(i,1,n)
    {
        scanf("%lld",&x);
        mp[((x%p*x%p*x%p*x%p)%p-(k%p*x%p)+p)%p]++;
        s.insert(((x%p*x%p*x%p*x%p)%p-(k%p*x%p)+p)%p);
    }
    ll ans=0;
    for(auto v:s)
    ans+=mp[v]*(mp[v]-1)/2;
    cout<<ans<<endl;

    return 0;
}

View Code