\(A. Array Coloring\)
显然需要奇数个偶数即可满足题目。
void solve(){
int n=read(),res=0;
for(int i=1;i<=n;i++){
int x=read();
if(x%2)res++;
}
puts(res%2==0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(B. Maximum Rounding\)
模拟四舍五入，如果更高位的数字能五入，那么低位跟着变成 \(0\) 。
void solve(){
string s;
cin>>s;
reverse(s.begin(),s.end());
vector<char>ans;
int fl=0;
for(int i=0;i<s.size();i++){
if(s[i]>='5'){
s[i]='0';
if(i+1>=s.size()){
s=s+'1';
}else {
s[i+1]++;
}
fl=i;
}
}
for(int i=0;i<fl;i++){
s[i]='0';
}
reverse(s.begin(),s.end());
cout<<s<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(C. Assembly via Minimums\)
首先第 \(n\) 小的数字出现 \(\frac{(n-1)*n}{2}\) 次。那么排序之后按照这个顺序记录答案就好了。
vector<int>vec[N];
int a[N];
void solve(){
int n=read(),cnt=1,xunhuan=n;
for(int i=1;i<=n;i++){
vec[i].clear();
}
for(int i=1;i<=n*(n-1)/2;i++){
a[i]=read();
}
sort(a+1,a+1+n*(n-1)/2);
for(int i=1;i<=n*(n-1)/2;i++){
cnt++;
int x=a[i];
vec[n-xunhuan+1].push_back(x);
vec[cnt].push_back(x);
if(cnt==n){
xunhuan--;
cnt=n-xunhuan+1;
}
}
for(int i=1;i<=n;i++){
int maxx=-inf;
for(auto x:vec[i]){
maxx=max(maxx,x);
}
cout<<maxx<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(D. Strong Vertices\)
转化式子就发现跟图没一点关系，记录 \(a_i-b_i\) 的最大值出现过几次即可。
struct node{
int d;
int id;
friend bool operator<(const node&a,const node&b){
if(a.d==b.d)return a.id>b.id;
return a.d<b.d;
}
}vec[N];
int a[N],b[N],d[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
for(int i=1;i<=n;i++){
vec[i].d=a[i]-b[i];
vec[i].id=i;
}
sort(vec+1,vec+1+n);
int maxx=vec[n].d;
vector<int>ans;
for(int i=n;i>=1;i--){
if(maxx==vec[i].d){
ans.push_back(vec[i].id);
}
}
cout<<ans.size()<<'\n';
for(auto x:ans){
cout<<x<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(E. Power of Points\)
太久远了，没什么印象了(所以下次写题解还是要尽早)。
好像就是递推一个式子，把复杂度降下来。
struct node{
int val;
int id;
friend bool operator<(const node&a,const node&b){
if(a.val==b.val)a.id<b.id;
return a.val<b.val;
}
}a[N];
void solve(){
int n=read();
vector<int>ans(n+1);
for(int i=1;i<=n;i++){
a[i].val=read();
a[i].id=i;
}
sort(a+1,a+1+n);
ans[a[1].id]=0;
for(int i=1;i<=n;i++){
ans[a[1].id]+=a[i].val-a[1].val+1;
}
for(int i=2;i<=n;i++){
if(a[i].val==a[i-1].val){
ans[a[i].id]=ans[a[i-1].id];
continue;
}
int p=(i-1)*(a[i].val-a[i-1].val),q=(n-i+1)*(a[i].val-a[i-1].val);
ans[a[i].id]=ans[a[i-1].id]+p-q;
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(F. Sum and Product\)
太久远了，不记得考场上我怎么写的了，好像就是把式子转化了一下解一个显然的方程就可以了。
void solve(){
int n=read();
// cout<<"-------------------------\n";
map<int,int>mp;
for(int i=1;i<=n;i++){
mp[read()]++;
}
int q=read(),ans=0;
for(int i=1;i<=q;i++){
map<int,int>vis;
ans=0;
int x=read(),y=read();
if((x*x-4*y)*1.0/2<0){
cout<<0<<' ';
continue;
}
if((x*x-4*y)*1.0/2==0){
// cout<<"here:";
int j=round((x+sqrt(x*x-4*y))*1.0/2);
// cout<<" j:"<<j<<" ";
if(j*(x-j)==y&&vis[j]==0&&vis[x-j]==0){
ans+=mp[j]*(mp[x-j]-1)/2;
vis[j]=1;vis[x-j]=1;
}
if((j+1)*(x-(j+1))==y&&vis[j+1]==0&&vis[x-(j+1)]==0){
ans+=mp[j+1]*(mp[x-(j+1)]-1)/2;
vis[j+1]=1;vis[x-(j+1)]=1;
}
if((j-1)*(x-(j-1))==y&&vis[j-1]==0&&vis[x-(j-1)]==0){
ans+=mp[j-1]*(mp[x-(j-1)]-1)/2;
vis[j-1]=1;vis[x-(j-1)]=1;
}
cout<<ans<<' ';
continue;
}
int j=round((x+sqrt(x*x-4*y))*1.0/2);
// cout<<"j:"<<j<<' ';
if(j*(x-j)==y&&vis[j]==0&&vis[x-j]==0){
ans+=mp[j]*mp[x-j];
vis[j]=1;vis[x-j]=1;
}
if((j+1)*(x-(j+1))==y&&vis[j+1]==0&&vis[x-(j+1)]==0){
ans+=mp[j+1]*mp[x-(j+1)];
vis[j+1]=1;vis[x-(j+1)]=1;
}
if((j-1)*(x-(j-1))==y&&vis[j-1]==0&&vis[x-(j-1)]==0){
ans+=mp[j-1]*mp[x-(j-1)];
vis[j-1]=1;vis[x-(j-1)]=1;
}
j=round((x-sqrt(x*x-4*y))*1.0/2);
// cout<<"j:"<<j<<' ';
if(j*(x-j)==y&&vis[j]==0&&vis[x-j]==0){
ans+=mp[j]*mp[x-j];
vis[j]=1;vis[x-j]=1;
}
if((j+1)*(x-(j+1))==y&&vis[j+1]==0&&vis[x-(j+1)]==0){
ans+=mp[j+1]*mp[x-(j+1)];
vis[j+1]=1;vis[x-(j+1)]=1;
}
if((j-1)*(x-(j-1))==y&&vis[j-1]==0&&vis[x-(j-1)]==0){
ans+=mp[j-1]*mp[x-(j-1)];
vis[j-1]=1;vis[x-(j-1)]=1;
}
// cout<<"ans:"<<ans<<' ';
cout<<ans<<" ";
// cout<<'\n';
}
cout<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
\(G. Counting Graphs\)
使用 \(Kruskal\) 模拟最小树的生成过程，然后每次合并的时候，可以增加连接两个联通块的边，边权为当前值到最大值。
struct node{
int x,y;
int w;
friend bool operator<(const node&a,const node&b){
return a.w<b.w;
}
}ed[N];
int p[N], siz[N];//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int find(int x){ // 返回x的祖宗节点
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int qmi(int m, int k, int p){
int res = 1 % p, t = m;
while (k){
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
void solve(){
int n=read(),s=read();
for (int i = 1; i <= n; i ++ ) { // 初始化，假定节点编号是1~n
p[i] = i;
siz[i] = 1;
}
for(int i=1;i<n;i++){
ed[i].x=read();
ed[i].y=read();
ed[i].w=read();
}
sort(ed+1,ed+n);
int ans=1;
for(int i=1;i<n;i++){
int x=ed[i].x;
int y=ed[i].y;
int w=ed[i].w;
if(w>s)break;
ans=(ans*=qmi(s-w+1,(siz[find(x)]*siz[find(y)]-1),mod))%mod;
siz[find(y)] += siz[find(x)];
p[find(x)] = find(y);
}
cout<<ans<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}