偷偷摆烂导致小号掉了16分，但是队友涨了16分，一定是米哈游的问题！
A. Array Coloring
题意：给出一个长为\(n\)的数组，问能否把所有元素分别染成两种颜色中的一种，并且使得同种颜色的元素和它们最后的奇偶性相同。
Solution
算出奇数个数看是不是奇数个即可
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int cnt0=0,cnt1=0;
for(int i=1;i<=n;i++)
{
if(a[i]&1)cnt1++;
else cnt0++;
}
if(cnt1&1)cout<<"NO\n";
else cout<<"YES\n";
}
B. Maximum Rounding
题意：给出一个\(x\)，可以进行任意次四舍五入操作，每次四舍五入的位置任选，问\(x\)进行若干次操作后最大是多少
Solution
从低位往高位一步步看即可
void solve()
{
string s;cin>>s;
int flag=0;
int pos=-1;
for(int i=s.length()-1;i>=0;i--)
{
if(s[i]-'0'>=5)
{
pos=i;
if(i>0)s[i-1]++;
else flag=1;
}
}
if(pos>=0)
for(int i=pos;i<s.length();i++)s[i]='0';
if(flag)cout<<"1";
cout<<s<<"\n";
}
C. Assembly via Minimums
题意：有一个长为\(n\)的数组\(a\)，通过\(a\)可以得到长为\(\frac{n(n-1)}{2}\)数组\(b\)，\(b\)数组的元素为\(a\)数组中任选两个不同的数，取其中的最小值得到，现在给出打乱的数组\(b\)，求数组\(a\)
Solution
将\(b\)排序，从\(1\)开始每\(n,n-1,...,1\)个相同就是最小值，最后一个直接随便找个最大的即可
void solve()
{
int n;cin>>n;
for(int i=1;i<=n*(n-1)/2;i++)cin>>b[i];
sort(b+1,b+1+n*(n-1)/2);
int cnt=1;
int pos=1;
while(pos<=n*(n-1)/2)
{
a[cnt++]=b[pos];
pos+=(n-cnt+1);
}
a[cnt]=b[n*(n-1)/2];
for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
D. Strong Vertices
题意：给出两个数组\(a,b\)，现在建立一张图，如果有\(a[u]-a[v]>b[u]-b[v]\)，则有从\(u\)到\(v\)的一条有向边，问哪些点可以到其它所有点
Solution
交换发现\(a[u]-b[u]>a[v]-b[v]\)
所以建立一个新数组为\(a\)与\(b\)的差值数组，从大往小遍历看即可
struct node
{
int x,y;
bool operator <(const node&t)const &{
if(x!=t.x)return x<t.x;
else return y<t.y;
}
}e[N];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++)
{
//cout<<a[i]<<" "<<b[i]<<"\n";
e[i].x=a[i]-b[i];
//cout<<e[i].x<<"\n";
e[i].y=i;
//sort(e+1,e+1+n);
}
sort(e+1,e+1+n);
//for(int i=1;i<=n;i++)cout<<e[i].x<<" \n"[i==n];
int pos=0;
for(int i=1;i<=n;i++)
{
if(e[i].x==e[n].x)
{
pos=i;break;
}
}
cout<<n-pos+1<<"\n";
for(int i=pos;i<=n;i++)
{
cout<<e[i].y<<" \n"[i==n];
}
}
E. Power of Points
题意：给出一个若干个数\(x_1,...x_n\)，对于整数\(s\)，构造\(n\)个区间\([s,x_1],[s,x_2],...,[s,x_n]\)，定义\(f_p\)为点\(p\)被包含的区间个数
现在求对于\(s\in\{x_1,...,x_n\}\)，\(\sum_{p=1}^{10^9}f_p\)
Solution
其实就是求所有区间的长度，用前缀和处理一下就很容易得到答案了
struct node
{
int x,y;
bool operator <(const node&t)const &{
if(x!=t.x)return x<t.x;
else return y<t.y;
}
}e[N];
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
b[i]=a[i];
e[i].x=a[i];
e[i].y=i;
}
sort(b+1,b+1+n);
sort(e+1,e+1+n);
for(int i=2;i<=n;i++)b[i]+=b[i-1];
for(int i=1;i<=n;i++)
{
ans[e[i].y]=n+(e[i].x*i-b[i])+(b[n]-b[i])-(e[i].x*(n-i));
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
}
F. Sum and Product
题意：给出一个数组\(a\)，进行\(q\)次询问，每次询问找到满足以下要求的数对个数：
1.\(1\leq i<j\leq n\)
2.\(a_i+a_j=x,a_i \times a_j=y\)
其中\(x\)与\(y\)由询问给出
Solution
既然已知\(x,y\)，可以直接算出\(a_i,a_j\)，对\(a\)数组排序，然后二分找到满足答案的个数即可，注意判重
int getx(int x)
{
int l=lower_bound(a+1,a+1+n,x)-a;
if(l>n||a[l]!=x)return 0;
int r=upper_bound(a+1,a+1+n,x)-a;
r--;
if(r>n||a[r]!=x)return 0;
return r-l+1;
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int q;cin>>q;
while(q--)
{
int x,y;cin>>x>>y;
int z=x*x-4*y;
if(z<0)
{
cout<<"0 ";
continue;
}
int l=sqrt(z);
if(l*l!=z)
{
cout<<"0 ";
continue;
}
int a1=x+l,a2=x-l;
int res=0;
if((x+l)%2==0)
{
a1/=2,a2/=2;
int b1=x-a1;
int b2=x-a2;
if(a1>b1)swap(a1,b1);
if(a2>b2)swap(a2,b2);
if(a1==a2)
{
if(a1==b1)
{
int len=getx(a1);
res+=len*(len-1)/2;
}else res+=getx(a1)*getx(b1);
}else
{
if(a1==b1)
{
int len=getx(a1);
res+=len*(len-1)/2;
res+=getx(a2)*getx(b2);
}else if(a2==b2)
{
int len=getx(a2);
res+=len*(len-1)/2;
res+=getx(a1)*getx(b1);
}
}
}
cout<<res<<" ";
}
cout<<"\n";
}
G. Counting Graphs
题意：给出一棵树，问有多少张图，满足以下条件：
1.没有自环和重边
2.边权都不超过\(s\)
3.这个图有且仅有一棵最小生成树，并且这棵树是给出的树
Solution
考虑到最小生成树的条件，我们不难发现，假如我们要加入一条\(<u,v>\)的边，那么它的权值必须大于树上\(u\)到\(v\)经过的权值最大的边，所以我们可以通过kruskal重构树，遍历所有非叶子节点，它对答案的贡献为\((max(0,w[x]-s)+1)^{sz[lson]\times sz[rson]-1}\)
struct node
{
int u, v, w;
bool operator<(const node &t) const &
{
return w < t.w;
}
};
int n, s;
vector<node> g;
vector<int> e[N << 1];
int t[N << 1];
int find(int x)
{
return t[x] == x ? t[x] : t[x] = find(t[x]);
}
int idx = n;
int w[N<<1];
void kruskal() // kruskal重构树
{
for (auto it : g)
{
int u = it.u, v = it.v, ww = it.w;
int x = find(u), y = find(v);
// cout<<x<<" "<<y<<"\n";
if (x != y)
{
idx++;
t[idx] = idx;
t[x] = t[y] = idx;
w[idx] = ww;
//cout<<ww<<"\n";
e[x].push_back(idx);
e[y].push_back(idx);
e[idx].push_back(x);
e[idx].push_back(y);
}
}
}
int sz[N << 1];
int ans = 1;
int ksm(int x, int y, int mod1 = mod)
{
int res = 1;
x %= mod1;
while (y > 0)
{
if (y & 1)
{
res = res * x % mod1;
}
y >>= 1;
x = (x * x) % mod1;
}
return res;
}
void dfs(int x)
{
if (x <= n)
{
sz[x] = 1;
return;
}
int lson = e[x][0], rson = e[x][1];
dfs(lson), dfs(rson);
sz[x] = sz[lson] + sz[rson];
ans = (ans * ksm(max(0LL, s - w[x]) + 1, (sz[lson] * sz[rson] - 1))) % mod;
}
void solve()
{
ans = 1;
cin >> n >> s;
g.clear();
for (int i = 1; i <= n; i++)
t[i] = i;
for(int i=1;i<=2*n;i++)e[i].clear();
for (int i = 1; i < n; i++)
{
int u, v, w;
cin >> u >> v >> w;
g.push_back({u, v, w});
}
sort(g.begin(), g.end());
idx = n;
kruskal();
dfs(idx);
cout << ans << "\n";
}