在叶子童鞋的推荐下打了这场比赛...
感觉被虐爆了...
怎么这么多构造题...
我还没写过呢...
交互题是毛线...看了好久没看懂...就放弃了...(我语文好差QAQ...)
最后只会T1...T2没时间了，就随便水了一发...居然拿了30分(rp--)...
下面有一些是自己/小伙伴YY的想法...有一些是题解...先放官方题解...
就不放题面了...复制过来效果很神奇...
分析：
这个你脑补一下，划分成的长度一定是1~n的某个全排列，然后算一算，发现能够组合出来的长度只有$frac{n(n+1)}{2}$种，如果两两不同，那么就需要每一种长度都只被计算一次，然后就会发现，如果n>=3是做不到这一点的...详细证明请见题解...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
int n,cas;
signed main(void){
scanf("%d",&cas);
while(cas--){
scanf("%d",&n);
if(n>3)
puts("-1");
else
puts("1");
}
return 0;
}//Cap ou pas cap. Cap.
#283. 直径拆除鸡
分析：
题解有点长...懒得看了...
这是一个神奇的想法...
我们枚举树高，然后除了最后一层的点，其他全都是三叉的，每一层的根节点前两个儿子都是一条链，第三个儿子递归...大概就是下面这张图...
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
int n,m;
inline int calc(int dep){
int ans=0,tmp=dep,N=n;
while(tmp)
ans+=N,N-=tmp*2+1,tmp--;
ans+=N;
if(ans>=m){
for(int i=dep,tot=0;i>=1;i--){
int root=tot+1;
tot+=2*i+1;
for(int j=root+1;j<=i+root;j++)
printf("%d %d
",j==root+1?root:j-1,j);
for(int j=root+i+1;j<=root+i+i;j++)
printf("%d %d
",j==root+i+1?root:j-1,j);
printf("%d %d
",root,root+i+i+1);
if(i==1&&tot+1<n){
for(int j=root+i+i+2;j<=n;j++)
printf("%d %d
",root,j);
}
}
}
return ans;
}
signed main(void){
scanf("%d%d",&n,&m);
if(n<=3){
for(int i=2;i<=n;i++)
printf("%d %d
",1,i);
return 0;
}
for(int i=1;i<=(n-1)/3;i++)
if(calc(i)>=m)
break;
return 0;
}//Cap ou pas cap. Cap.
By NeighThorn