第16届大连理工大学程序设计竞赛（验题人题解）

J.签到

签到，人口普查题，输出3.14

G.长椅

签到，如果总和能被n整除，即可以调平，否则不能

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a[N];
ll sum;
int main(){
    scanf("%d",&n);
    assert(1<=n && n<=100000);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        sum+=a[i];
        assert(1<=a[i] && a[i]<=1000000000);
    }
    puts(sum%n?"No":"Yes");
    return 0;
}

C.圆阵

签到，如果n%2==0(n>2)，根据鸽巢原理，必有两个偶数会相邻，否则相邻放即可

然而这个n=2也输出NO，验题的时候也wa了一发

出题人：圆环上的相邻指a[i]和a[(i+1)%x](x是圆环上元素个数)，这不是常识吗

并表示可以当corner case考察，~~直到今天被公开处刑~~

#include
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	if(n%2==0){
		puts("NO");
		return 0;
	} 
	puts("YES");
	for(int i=2;i<=n;++i){
		printf("%d%c",i," n"[i==n]);
	} 
	return 0;
}

A.歌会

签到，被出烂的「导弹拦截」和dirworth定理，

根据dilworth定理，最大反链中元素的数目必等于最小链划分中链的数目，

所以，能分成两个单调不降的序列，等价于不存在长度为3的严格递减子序列

可以二分，也可以直接放（能放第一个尾就放第一个，否则放第二个尾）

#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
int t,n,a[N],mx[N],mn[N];
bool solve(){
    for(int i=2;ia[i] && a[i]>mn[i+1])return 0;
    }
    puts("YES");
    int fi=-1,se=-1,ans;
    for(int i=1;i<=n;++i){
        if(a[i]>=fi)fi=a[i],ans=1;
        else se=a[i],ans=2;
        printf("%d%c",ans," n"[i==n]);
    }
    return 1;
}
int main(){
    scanf("%d",&t);
    assert(1<=t && t<=10);
    while(t--){
        scanf("%d",&n);
        assert(1<=n && n<=100000);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            assert(1<=a[i] && a[i]<=1000000000);
        }
        for(int i=1;i<=n;++i){
            mx[i]=max(mx[i-1],a[i]);
        }
        mn[n+1]=a[n];
        for(int i=n;i>=1;--i){
            mn[i]=min(mn[i+1],a[i]);
        }
        if(!solve())puts("NO");
    }
    return 0;
}

E.海胆

签到，a和b的相同的因子个数，即gcd(a,b)的因子个数，

对于一个数x，如果a能整除x，则x/a也能整除x，二者不等的时候，贡献两个因子，

只有a=x/a的时候，因子个数才能为奇数，此时x为完全平方数，

所以，判断gcd(a,b)是不是完全平方数即可，为了避免精度问题，这里还检查了x-1和x+1

#include
using namespace std;
typedef long long ll;
ll mx=1e18;
ll a,b,ans;
ll gcd(ll x,ll y){
    return y?gcd(y,x%y):x;
}
int main(){
    scanf("%lld%lld",&a,&b);
    assert(1<=a && a<=mx);
    assert(1<=b && b<=mx);
    ans=gcd(a,b);
    ll x=sqrt(ans);
    bool ok=0;
    for(ll i=x-1;i<=x+1;++i){
        ok|=(i*i==ans);
    }
    puts(ok?"Odd":"Even");
    return 0;
}

I.画画

构造题，出题人强行加的中档构造题，好像起到了一些区分作用（？）

答案不唯一，这里给出一种构造方法，中间放形如0102矩形，一侧全放0另一侧全放2

#include
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    assert(n%2==0 && 1<=n && n<=500);
    for(int i=0;i 
B.礼物 
思维题，如果有相同的值，答案显然是0 
否则按值域增序排序，只检查相邻的值即可 
反证法，设错过了最优解，假设a[i]和a[i+2]是最优解， 
则总可以发现a[i]和a[i+1]、a[i+1]和a[i+2]、a[i+2]和a[i+3]总有一对不劣于a[i]和a[i+2] 
类似的，数学归纳法知，该法不会错过最优解 
验题的时候没有发现这个性质，暴力找了离当前值值域最近的100个值， 
冲过去了，还以为是出题人数据出弱了 
#include
using namespace std;
typedef pair P;
const int N=1e5+10;
int t,n,m;
struct node{
    int v,id;
}e[N];
bool operator<(node a,node b){
    return a.v 
以下三个题难度近似，取决于对某个知识点的掌握程度 
D.谜题 
思维题，排序后，最小的值一定是a1+a2，次小的值一定是a1+a3， 
但是，第三小的可能是a1+a4，也可能是a2+a3， 
所以，枚举a2+a3的位置，最极限的情况是(a1+a2,a1+a3,a1+a4,...,a1+an,a2+a3) 
根据三个式子，解出a1、a2、a3的值，在set内把a1+a2,a1+a3,a2+a3各抹掉之后， 
最小的一定是a1+a4，解出a4，并找到a2+a4，a3+a4，一并抹掉 
此时最小的是a1+a5，解出a5，重复这个过程，直至所有数都被抹掉 
最后可以检查一下是不是满足增序的，以及各数不等且均正数 
注意set需要开mutiset，因为，ai+aj=ak+al是可能成立的(i!=j!=k!=l) 
看似O(n^3logn)，实则由于大量无解情况，根本跑不满 
#include
using namespace std;
const int N=305*305/2;
int n,m,a[N],del[N],c;
mapvis;
multisetq;
vector >ans;
vectorres;
void solve(){
    for(int j=3;j<=m;++j){
        q.insert(a[j]);
    }
    for(int i=3;i<=n;++i){
        int sum=a[1]+a[2]+a[i];
        if(sum%2)continue;
        sum/=2;
        if(vis[sum])continue;
        vis[sum]=1;
        for(int j=1;j<=c;++j){
            q.insert(del[j]);
        }
        c=0;
        q.erase(q.lower_bound(a[i]));
        del[++c]=a[i];
        res.clear();
        res.push_back(sum-a[i]);
        res.push_back(sum-a[2]);
        res.push_back(sum-a[1]);
        bool ok=1;
        for(int j=4;j<=n;++j){
            if(!q.size()){
                ok=0;
                break;
            }
            int now=*(q.begin())-res[0];
            for(auto &v:res){
                if(!q.count(v+now)){
                    ok=0;
                    break;
                }
                q.erase(q.lower_bound(v+now));
                del[++c]=v+now;
            }
            if(!ok)break;
            res.push_back(now);
        }
        if(!ok)continue;
        for(int j=1;jres[j-1]);
        }
        ok&=(res[0]>=1);
        ok&=(res[n-1]<=100000000);
        if(!ok)continue;
        if(ok)ans.push_back(res);
    }
}
int main(){
    scanf("%d",&n);
    assert(3<=n && n<=300);
    m=n*(n-1)/2;
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        assert(1<=a[i] && a[i]<=100000000);
    }
    sort(a+1,a+m+1);
    solve();
    int sz=ans.size();
    printf("%dn",sz);
    for(int i=0;i 
F.愿望 
树、分类讨论、构造 
思路： 
ai*aj是3的倍数意味着至少有一个是3的倍数，即ai%3==0可以和任意值匹配， 
ai+aj的限制可以令ai%3==1与ai%3==2的数对凑成3的倍数 
 
按距树根距离分层后，树上距离为3的点， 
只可能差一层(i层和i+1层)或差三层(i层和i+3层) 
而i层和i+2层是不会出现冲突的，启发我们按奇偶分层， 
 
实际上，把点分成二分图之后， 
（1）要么是ai%3==0的点占据了二分图点少的那一半，0与另一半两两之间均合法 
（2）要么是二分图一边由ai%3==0和ai%3==1的点构成，另一边由ai%3==0和ai%3==2的点构成 
0与另一半两两之间均合法，1和2之间由于ai+aj是3的倍数也合法 
 
具体实现： 
deg[0/1]放入距树根距离为奇/偶的点， 
now[0/1/2]分别放入值域ai%3==0/1/2的点号， 
du[0/1]是deg[0/1]的大小，len[0/1/2]是now[0/1/2]的大小， 
 
以下，分四种情况讨论 
讨论了du[0]/du[1]小于1/3的情况， 
讨论了du[0]/du[1]属于[1/2,2/3]的情况， 
显然有一个大于等于1/3，另一个就小于等于2/3， 
而有一个大于等于2/3时，另一个就小于等于1/3， 
所以，一定有解 
#include
using namespace std;
typedef long long ll;
typedef pair P;
#define fi first
#define se second 
#define pb push_back
#define sci(x) scanf("%d",&(x))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
const int N=2e5+10,M=1e6+10,INF=0x3f3f3f3f,mod=1e9+7;//998244353
vectore[N],deg[2];
queuenow[3];
int n,u,v,len[3],du[2],ans[N],par[N];
bool used[N];
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
void dfs(int u,int fa,int d){
	deg[d%2].pb(u);
	for(int v:e[u]){
		if(v==fa)continue;
		dfs(v,u,d+1);
	}
}
void out(){
	rep(i,1,n){
		printf("%d%c",ans[i]," n"[i==n]);
	}
}
void solve(){
	//odd:du[0] even:du[1] 
	if(len[1]<=du[0]&&du[0]<=len[1]+len[0]){
		for(int i:deg[0]){
			if(now[1].size())ans[i]=now[1].front(),now[1].pop();
			else if(now[0].size())ans[i]=now[0].front(),now[0].pop();
		}
		for(int i:deg[1]){
			if(now[2].size())ans[i]=now[2].front(),now[2].pop();
			else if(now[0].size())ans[i]=now[0].front(),now[0].pop();
		}
		out();
		return;
	}
	if(len[1]<=du[1]&&du[1]<=len[1]+len[0]){
		for(int i:deg[1]){
			if(now[1].size())ans[i]=now[1].front(),now[1].pop();
			else if(now[0].size())ans[i]=now[0].front(),now[0].pop();
		}
		for(int i:deg[0]){
			if(now[2].size())ans[i]=now[2].front(),now[2].pop();
			else if(now[0].size())ans[i]=now[0].front(),now[0].pop();
		}
		out();
		return;
	}
	if(len[0]>=du[0]){
		for(int i:deg[0]){
			ans[i]=now[0].front(),now[0].pop();
		} 
		for(int i:deg[1]){
			if(now[0].size())ans[i]=now[0].front(),now[0].pop();
			else if(now[1].size())ans[i]=now[1].front(),now[1].pop();
			else if(now[2].size())ans[i]=now[2].front(),now[2].pop();
		}
		out();
		return;
	}
	if(len[0]>=du[1]){
		for(int i:deg[1]){
			ans[i]=now[0].front(),now[0].pop();
		} 
		for(int i:deg[0]){
			if(now[0].size())ans[i]=now[0].front(),now[0].pop();
			else if(now[1].size())ans[i]=now[1].front(),now[1].pop();
			else if(now[2].size())ans[i]=now[2].front(),now[2].pop();
		}
		out();
		return;
	}
}
int main(){
	scanf("%d",&n);
    assert(1<=n && n<=200000);
    rep(i,1,n)par[i]=i;
	rep(i,1,n-1){
		scanf("%d%d",&u,&v);
        int fu=find(u),fv=find(v);
        assert(fu!=fv);
        par[fv]=fu;
		e[u].pb(v);
		e[v].pb(u);
	}
	rep(i,1,n){
		now[i%3].push(i);
	}
	dfs(1,-1,0);
	rep(i,0,1){
		du[i]=(int)deg[i].size();
	}
	rep(i,0,2){
		len[i]=(int)now[i].size();
	}
	solve();
	return 0;
} 
H.两人三足 
比较复杂，还是看官方题解吧 
首先题目保证一定有解，那就可以乱搞了，然后考虑按末位分治， 
x&y=x，表明x是y的子集，也就是右集合为0的位，左集合只能为0； 
右集合为1的位，左集合既可以为0，也可以为1， 
ll，lr，rl，rr，第一个字母表示左/右集合，第二个字母表示这一位为0/1 
rl表示右集合这一位为0，这一位为0的只能与左集合这一位为0的匹配， 
匹配完之后，rl不可能有剩下的，否则无解，只可能ll有剩下的， 
把ll剩下的，放入lr集合，一起和rr进行匹配， 
当前递归深度下，左/右集合有剩下没被匹配的值，就回溯到上一层继续进行匹配 
复杂度大概O(nlogV）（V是值域1e6） 
ll放入lr的个数非常少，T(n)=T(n/2)+O(n)才O(nlogn) 
#include
using namespace std;
typedef pair P;
int n,m;
vectorlef,rig;
vectorans;
void dfs(vector&l,vector&r,int lb){
    //for(auto &v:l)printf("%d ",v);puts("");
    //for(auto &v:r)printf("%d ",v);puts("");
    //printf("lb:%dn",lb);
    if(lb==20){
        if(l.size()>0){
            ans.push_back(P(l.back(),r.back()));
            l.pop_back();r.pop_back();
        }
        return;
    }
    vectorll,lr,rl,rr;
    for(int i=0;i>lb&1){
            lr.push_back(l[i]);
        }
        else{
            ll.push_back(l[i]);
        }
    }
    for(int i=0;i>lb&1){
            rr.push_back(r[i]);
        }
        else{
            rl.push_back(r[i]);
        }
    }
    if(rl.size()>0){
        dfs(ll,rl,lb+1);
    }
    for(auto &v:ll){
        lr.push_back(v);
    }
    if(rr.size()>0){
        dfs(lr,rr,lb+1);
    }
    l.clear();r.clear();
    for(auto &v:lr){
        l.push_back(v);
    }
    for(auto &v:rr){
        r.push_back(v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    assert(1<=n && n<=m);
    assert(n+m<=1000000);
    for(int i=0;i 
验题感受 
出题人一方面怕不够签到，一方面怕防不住ak； 
所以，中档题可能还是不太够， 
不过，要不，我们看在题都是一个人出的份上，原谅他 
花絮 
1. 麻将大模拟被删了 
2. 验题演员是怎么演的

第16届大连理工大学程序设计竞赛（验题人题解）

C/C++/C#相关栏目本月热门文章