A

注意到

只要X符合 (X-1)%K==0 就可以由1向右跳得到

void Phantom_73()
{
    ll ans=0,n,k; cin>>n>>k;
    for(int i=0;i<n;++i) 
    {
        ll x; cin>>x;
        if((x-1)%K==0)
            ans++;
    }
    cout<<ans;
 
}

B

注意到

A模上任意X即 A%X他的取值范围为 [0,A/2]; 然后即可循环贪心放置

第一个放0 第二个放1...... 第N个放N-1

void Phantom_73()
{
 	ll n; cin>>n;
    for(int i=0;i<n;++i)
    {
        ll x; cin>>x;
        if((x/2)<i)
        {
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
	return;
}

C

注意到

咱们把数组排序得到 数组b。

如果 b[i] * b[n-1] < x ,说明b[i]这个元素无论和哪个元素组队都无法被替换。

即a[i]必须在b[i]这个位置不然他无论如何都无法排序到b[i]这个位置。

vec<ll>a;
vec<ll>b;
ll n,tttt=1; 
void Phantom_73()
{
    ll x; cin>>x;
    for(int i=0;i<n-1;++i)
    {
        ll cj=b[i]*b[n-1];
        if(cj<x&&b[i]!=a[i])
        {
            cout<<"No\n";
            return;
        }
        else if(cj>=x) break;
    }
    cout<<"Yes\n";
    return;
}
int main() 
{
    AC;
    cin>>n>>tttt;
    a.resize(n);
    b.resize(n);
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b.begin(),b.end());
    while(tttt--) Phantom_73();
    return 0;
}

D

注意到

我们可以 枚举根，用树形DP

我们用f[u]表示u不指向父亲时子树的最大值g[u]表示u指向父亲时的最大值。

用dfs 遍历每个节点，算出把边改成 u 指向子节点的收益,排序后取收益最大的若干个.

枚举数量算出最优解，最后输出根节点不指向父亲的结果即可。

#define LINF 0x3f3f3f3f3f3f3f3f
vec<vec<ll>>t;
vec<ll>f,g;
void dfs(int u,int fa)
{
    vec<ll>c;
    ll zl=0;
    for(int v:t[u])if(v!=fa)
    {
        dfs(v,u);
        zl+=g[v];
        c.push_back(f[v]-g[v]);
    }
    sort(c.rbegin(),c.rend());
    ll k=c.size();
    vec<ll>qz(k+1);
    for(ll i=0;i<k;i++) qz[i+1]=qz[i]+c[i];
    f[u]=-1e18;
    g[u]=-1e18;
    for(ll i=0;i<=k;i++)
    {
        f[u]=mx(f[u],i*i+zl+qz[i]);
        g[u]=mx(g[u],(i+1)*(i+1)+zl+qz[i]);
    }
}
void Phantom_73()
{
    int n;cin>>n;
    t.resize(n);
    f.resize(n);
    g.resize(n);
    for(int i=0;i<n-1;++i)
    {
        ll u,v;cin>>u>>v;
        u--;v--;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    dfs(0,-1);
    cout<<f[0]<<'\n';
}