A. Array Coloring

题意

给定 {an}\{a_n\}，请问你能否把这个序列染成两个颜色，使得每个颜色的和的奇偶性相同。

解法

只要和为偶数就一定可以。和为奇数就一定不可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read();
    vector<int> v;
    int sum = 0;
    for(int i=1;i<=n;i++){
        int x=read();
        v.push_back(x);
        sum+=x;
    }

    if(sum%2==1)NO
    else YES;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Maximum Rounding

题意

给你一个数，可以随意四舍五入到任意位任意次，请问这个数最大能是多少？

解法

每一位能进位就进位，记录当前进到了哪一位，后面的全部置为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
char s[N];
void solve(int kase){
    scanf("%s",s+1);
    s[0]=0;
    int n=strlen(s+1);
    for(int i=1;i<=n;i++){
        s[i]-='0';
    }

    int lastpos=INT_MAX;
    for(int i=n;i>=0;i--){
        if(s[i]>=5){
            s[i-1]++;
            lastpos=i;
        }
    }

    if(s[0]!=0)printf("%d",s[0]);
    for(int i=1;i<=n;i++){
        if(i>=lastpos)putchar('0');
        else printf("%d",s[i]);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Assembly via Minimums

题意

有 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n，现在用所有 ai,aja_i,a_j 的最小值构造出一个长度为 n(n−1)2\dfrac{n(n-1)}{2} 的 bb 数组。

给出 bb 数组，求出 aa 数组。

解法

不难发现 bb 数组中有 n−1n-1 个最小数，n−2n-2 个第二小数，……，11 个第二大数，00 个最大数。
排序然后依次处理即可。最大数直接输出一个 10910^9 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read();
    map<int,int> cnt;
    for(int i=1;i<=n*(n-1)/2;i++){
        cnt[read()]++;
    }    

    int now = n-1;
    for(auto [k,v]:cnt){
        while(v>=now && now>0){
            v-=now;
            now--;
            printf("%d ",k);
        }
    }
    printf("%d",(int)1e9);
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Strong Vertices

题意

给定 aa 、bb 数组，当且仅当 au−av≥bu−bva_u-a_v\ge b_u-b_v 时 u,vu,v 有连边。

求出所有能到达所有点的点。

解法

条件简单改写成 au−bu≥av−bva_u-b_u\ge a_v-b_v。

并且我们还能发现一个性质：若 (a,b),(b,c)(a,b),(b,c) 有边，则 (a,c)(a,c) 也一定有边。因此我们要找的节点就是 a−ba-b 最大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


void solve(int kase){
    int n=read();
    vector<int> a(n),b(n),d(n);
    for(int i=0;i<n;i++){
        a[i]=read();
    }
    for(int i=0;i<n;i++){
        b[i]=read();d[i]=a[i]-b[i];
    }

    auto x = *max_element(all(d));
    vector<int> ans;
    for(int i=0;i<n;i++){
        if(d[i]==x){
            ans.push_back(i+1);
        }
    }
    printf("%lu\n",ans.size());
    for(int k:ans){
        printf("%d ",k);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E. Power of Points

题意

给定 x1,x2,…,xnx_1,x_2,\ldots,x_n。
现在有一个整数 ss，有 nn 个区间 [xi,s][x_i,s]（可能是 [s,xi][s,x_i]），求出当 s=x1,x2,…,xns=x_1,x_2,\ldots,x_n 时，所有的区间长度。

解法

维护左边的端点数和右边的端点数，动态计算即可。记得开 long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


void solve(int kase){
    int n=read();
    vector<pii> v;
    for(int i=0;i<n;i++){
        v.push_back({read(),i});
    }
    sort(all(v));

    vector<ll> ans(n);
    ll now = 0;
    for(int i=0;i<n;i++){
        now += v[i].first-v[0].first+1;
    }
    ans[v[0].second]=now;

    ll cntLeft=1, cntRight=n-1;
    for(int i=1;i<n;i++){
        ll diff = v[i].first-v[i-1].first;
        
        now += cntLeft*diff;        
        now -= cntRight*diff;

        cntLeft++,cntRight--;
        ans[v[i].second]=now;
    }

    for(int i=0;i<n;i++){
        printf("%lld ",ans[i]);
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

F. Sum and Product

题意

给定 {an}\{a_n\}，有 qq 个询问，每次询问给出 x,yx,y，求出 ai+aj=xa_i+a_j=x 且 aiaj=ya_ia_j=y 的 (i,j)(i,j) 个数（i<ji<j）。

解法

直接解这个方程。

Δ=x2−4y\Delta=x^2-4y，
ai=x+Δ2,aj=x−Δ2a_i=\dfrac{x+\sqrt \Delta}{2},a_j=\dfrac{x-\sqrt \Delta}{2}。

注意判断是否有整数解，并且特判两个解相等的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


void solve(int kase){
    int n=read();
    map<int,int> cnt;
    for(int i=0;i<n;i++){
        int x=read();
        cnt[x]++;
    }

    int q=read();
    while(q--){
        ll x=read<ll>(),y=read<ll>();

        ll p = x*x-y*4;
        if(p<0){
            printf("0 ");
            continue;
        }

        ll sp = sqrt(p);
        if(sp * sp != p){
            printf("0 ");
            continue;
        }

        if((x+sp)%2!=0){
            printf("0 ");
            continue;
        }

        int a1 = (x+sp)/2;
        int a2 = a1-sp;
        if(a1==a2){
            ll cnt1 = cnt[a1];
            printf("%lld ",cnt1*(cnt1-1)/2);
        }
        else{
            ll cnt1 = cnt[a1],cnt2=cnt[a2];
            printf("%lld ",cnt1*cnt2);
        }
    }
    puts("");
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

G. Counting Graphs

题意

给定一颗树。请求出满足下面条件的图的个数：

  1. 没有重边和自环。
  2. 以这棵树为最小生成树
  3. 只有一颗最小生成树
  4. 边权不超过给定的 SS。

解法

考虑在最小生成树上加边。
考虑两个点之间连边的边权应该是怎么样的。事实上，两个点之间连边的边权应该大于它们的路径上的边权最大值（不然就可以换一条边，不是最小生成树了）。

设 P(u,v)P(u,v) 为 u→vu\rightarrow v 路径上边权的最大值，我们要求出的就是如下表达式 ∏1≤u<v≤n(S−P(u,v)+1)\displaystyle \prod_{1\le u < v\le n}(S-P(u,v)+1)。

O(n2)O(n^2) 求法是很显然的，但是如何快速求呢？

要想要不重不漏的统计所有点对，我们考虑什么时候考虑这一对对答案的贡献。事实上，我们可以在它们路径上边权最大的那条边被加入的时候统计这一对的贡献。

因此，将所有边的边权从小到大进行排序，依次加入边，然后答案就应该加入 (S−w+1)(S-w+1) 的边连接的两个联通分量大小的乘积减一次方（因为有一对本来就有边了），这样可以在 O(nlog⁡n)O(n\log n) 复杂度完成本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
const ll MOD = 998244353;

int fa[N],sz[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int i,int j){
    i=find(i),j=find(j);
    if(i==j)return;
    fa[i]=j;
    sz[j]+=sz[i];sz[i]=0;
}



ll fastpow(ll a, ll b) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

void solve(int kase){
    ll n=read(),s=read();
    for(int i=1;i<=n;i++){
        fa[i]=i,sz[i]=1;
    }

    vector<tuple<int,int,int>> edges;
    for(int i=0;i<n-1;i++){
        int u=read(),v=read(),w=read();
        edges.push_back({w,u,v});
    }

    sort(all(edges));
    ll ans = 1;
    for(auto [w,u,v]:edges){
        int uu = find(u), vv=find(v);
        ll k = (ll)sz[uu]*sz[vv]-1;
        ans = ans*fastpow(s-w+1,k)%MOD;
        unite(u,v);
    }
    printf("%lld\n",ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}