B
告诉你所有元素和，以及拿走一个最大值的剩余元素和，构造原序列。首先肯定有一个元素是最大值，剩下的就是构造一个最大值不超过某个值的，和为定值的序列。
最简单的构造方式就是元素和均分，这样可以让最大元素尽量小，肯定不会超过最大值的限制
void solve(){
cin>>n>>m>>k;
int mx=m-k;
n--;
cout<<mx<<' ';
int a=k/n;
int b=k%n;
rep(i,1,n){
if(i<=b){
cout<<a+1<<' ';
}
else{
cout<<a<<' ';
}
}
cout<<'\n';
}
C
每次从一个排列里拿走一个元素，输出剩余的元素。共n个这样的输出。从这n个残缺的排列里还原原始排列。
如何确定一个元素在序列中的位置？一种方法是：一个元素后面有多少元素是固定的，统计每个数字后面出现过多少个不同元素，就能确定他在原始排列中是第几个
这可以对于每个元素都开一个set实现。遍历这n个残缺的排列，把每个元素后面的元素都加入这个元素的set。由于n=100，这样复杂度是n^3，是可行的
最后根据后面的元素个数降序排列，就是原始排列的顺序
void solve(){
cin>>n;
set<int>s[n+1];
rep(i,1,n){
vi a(n);
rep(j,1,n-1){
cin>>a[j];
}
rep(j,1,n-1){
rep(k,j+1,n-1){
s[a[j]].insert(a[k]);
}
}
}
vector<vector<int>>b;
rep(i,1,n){
b.pb({s[i].size(),i});
}
sort(b.begin(),b.end());
reverse(b.begin(),b.end());
rep(i,1,n){
cout<<b[i-1][1]<<' ';
}
cout<<'\n';
}
D
一段连续的数字被称为一段，例如x+1,x+2……x+n，问共有多少段。
这其实和每一站都会上下人，问公交车上人数最大人数有点像，对于出现相同元素，都要分成多层，每一层一个元素只能出现一次。不同之处在于本题每一层，如果中间断开了，会被视为多个。
思路可以借鉴公交车那题，开个map记录每种元素的个数，从小到大遍历所有元素，每遍历到一次，就出现次数减一。遍历时如果断了，也就是不连续，就记录出现了新的一段。如果扫完一轮了，还有元素，就重复这个过程
void solve(){
cin>>n;
map<int,int>mp;
rep(i,1,n){
int t;
cin>>t;
mp[t]++;
}
int ans=0;
while(mp.size()){
int pre=-1;
vi del;
for(auto &[k,v]:mp){
if(k!=pre+1){
ans++;
//cout<<k<<' '<<ans<<'\n';
}
pre=k;
v--;
if(v==0)del.pb(k);
}
for(int x:del)mp.erase(x);
}
cout<<ans<<'\n';
}
E
位运算构造。很妙，但仔细想其实也很典。
首先本题的条件是x^y=(x+y)/2，我们又知道x+y=x^y+2(x&y)，可以理解为加法对于01，加完是1，对于11，加完会在更高一位是1，所以要乘2。带入可以得到x^y=2(x&y)。题目给出x^y了，那么x&y我们也可以求出。
那么问题转化成：已知x^y，x&y，构造x,y？这显然可以按位构造，我们可以根据x^y x&y每一位的情况，来判断xy每一位的情况
具体来说，x&y在一位为1，xy在这一位都必须为1，如果x&y为0，去看x^y,如果为1，说明xy在这一位一个1一个0，1可以随便给xy其中一个。如果x^y这一位为0，xy这一位都为0
何时无解呢？x&y=(x^y)/2肯定是整数，所以x^y必须是偶数。并且x^y x&y显然不能在同一位上都为1。出现以上任意一种情况都无解
void solve(){
int x;
cin>>x;
int y=x/2;
if(x%2==1||(y&x)!=0){
cout<<-1<<'\n';
return;
}
int a=0,b=0;
rep(i,0,30){
if(y>>i&1){
a|=1<<i;
b|=1<<i;
}
else{
if(x>>i&1){
a|=1<<i;
}
}
}
cout<<a<<' '<<b<<'\n';
}
F
给一棵树上所有点按一个顺序依次染色，每次染色后求当前两个染色点间最小距离。
首先这个问题可以转化为，维护一个dis数组，存每个点到最近的染色点的距离，然后我们每染色一个点的时候，直接查这个点的dis，和之前的最小值取个min就行了
现在的问题就是染色一个点之后怎么更新dis数组。暴力的思想是，从这个新染色的点开始bfs，对搜到的点更新dis。这样太慢了，需要剪枝。一个显然的剪枝是，如果这次bfs到达x点的距离，比这个点到其他染色点的距离更远，就不用更新了，并且这个分支再往下搜索，到这次染色点的距离只会更大，肯定也不会更新了，剪枝这个分支。
另一个不那么显然的剪枝是，我们维护全局最短距离ans，如果当前搜索到的点x,dis[x]>=ans，由于ans是不增的，dis[x]肯定对ans没影响，直接停止搜索。
如果只用第一个剪枝,会tle22。
int c[N],dis[N],ans;
vi g[N];
void bfs(int s){
dis[s]=0;
queue<int>q;
q.push(s);
while(q.size()){
int u=q.front();
q.pop();if(dis[u]>=ans)break;
for(int v:g[u]){
if(dis[v]<=dis[u]+1)continue;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
void solve(){
int c0;
cin>>n>>c[0];
rep(i,1,n-1)cin>>c[i];
rep(i,1,n){
g[i].clear();
dis[i]=n+1;
}
rep(i,1,n-1){
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
ans=n+1;
bfs(c[0]);
rep(i,1,n-1){
ans=min(ans,dis[c[i]]);
bfs(c[i]);
cout<<ans<<' ';
}
cout<<'\n';
}