Preface
补题，上周末没比赛很难受啊，而且这周要考CET-4，这周的模考听力只错了2pts，感觉自信慢慢flag
嘛值得一提的是学校还是沦陷了，让我们自愿返乡了
但是我知道以我的自制力现在回去明年来缓考肯定是寄的，所以在得知学校大概率有阳的情况下继续留守
嘛感觉不管回不回去对我没太大影响的说
这场一晚上只做了ABCD，主要是D我写完自己感觉有问题在改，结果交上去直接过了？
A. SSeeeeiinngg DDoouubbllee
SB题
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
int t,n,c[26]; char s[105];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;++i) ++c[s[i]-'a'];
for (i=0;i<26;++i) for (j=1;j<=c[i];++j) putchar(i+'a');
for (i=25;~i;--i) for (j=1;j<=c[i];++j) putchar(i+'a');
for (putchar('\n'),i=0;i<26;++i) c[i]=0;
}
return 0;
}
B. XOR = Average
好像我的构造方法很奇怪，让我构思了挺久
首先我们发现当\(n\)为奇数时直接令所有数等于\(1\)即可，接下来浅显地考虑下\(n=2\)的情况，发现用1 3即可
然后我们发现这样当\(n\)质因数分解后仅有一个\(2\)的话，我们只要用\(\frac{n}{2}\)组1 3即可
这就启发了我们，我们只要找出所有\(2^k\)的分法，然后让\(\frac{n}{2^k}\)为奇数构造即可
手玩一下不难发现\(n=4\)的时候可以用3 3 3 7来构造，同理\(n=8\)有7 7 7 7 7 7 7 15
以此类推，\(2^k\)的话就是由\(2^k-1\)个\(2^k-1\)和一个\(2^{k+1}-1\)构成
#include<cstdio>
#include<cstring>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; scanf("%d",&n); int p=1,tmp=n;
while (!(tmp&1)) tmp>>=1,p<<=1;
for (i=1;i<=n/p;++i) for (printf("%d ",(p<<1)-1),j=1;j<p;++j)
printf("%d ",p-1); putchar('\n');
}
return 0;
}
C. Almost All Multiples
刚开始没看到字典序最小的限制，以为是随便输一种（那不是SB题嘛）
然后随便写了个发现一直WA，后来去仔细看了眼题目才发现是字典序最小
首先我们发现用\(n\)放在\(a_x\)上，其它\(2\sim n-1\)都等于自己是一定可行的，那么我们考虑优化字典序
不难发现\(2\sim x-1\)的数不能变，因为它们已经足够小
那么考虑在\(x+1\sim n-1\)中找一个数可以替换\(x\)，不难发现这个数\(y\)要满足\(x|y\and y|n\)
同时如果用\(y\)替换了\(a_x\)那后面依然可以如法炮制，看在后面能否找一个数替换\(a_y\)即可
重复这个过程即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x,ans[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; scanf("%d%d",&n,&x); ans[1]=x; ans[n]=1;
if (n%x) { puts("-1"); continue; }
if (n==x)
{
for (printf("%d ",n),i=2;i<n;++i) printf("%d ",i);
printf("1\n"); continue;
}
for (i=2;i<x;++i) ans[i]=i; int cur=x; for (i=x+1;i<n;++i)
if (i%cur==0&&n%i==0) ans[cur]=i,cur=i; else ans[i]=i;
for (ans[cur]=n,i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}
D. Range = √Sum
莫名奇妙的乱搞做法，但就是能过的说
首先一个naive的想法就是确定\(x\)，令\(\sqrt {\sum_{i=1}^n a_i}=x\)，然后考虑确定\(y\)作为最小数，\(y+x\)作为最大数
不难发现这样我们只要在剩下的\([y+1,y+x-1]\)中找出\(n-2\)个不相同的数，使得这\(n-2\)个数的和等于\(x^2-y-(y+x)\)即可
从\([y+1,y+x-1]\)取数是存在范围的，如果拿最小的\(n-2\)个就是\((n-2)\times (y+1)+\frac{(n-3)(n-2)}{2}\)，拿最大的\(n-2\)个就是\((n-2)\times (y+x-1)-\frac{(n-3)(n-2)}{2}\)
不难发现在这中间的任意一个数都能被表示出来，那么我们现在就考虑怎样在确定\(x\)的情况下求出\(y\)，即要求不等式成立：
\[(n-2)\times (y+1)+\frac{(n-3)(n-2)}{2}\le x^2-y-(y+x)\le (n-2)\times (y+x-1)-\frac{(n-3)(n-2)}{2} \]即
\[\frac{x^2+(1-n)\times x+\frac{1}{2}n^2-\frac{3}{2}n+1}{n}\le y\le \frac{x^2-x-\frac{1}{2}n^2-\frac{3}{2}n+1}{n} \]那么我们只要枚举\(x\)，然后看是否存在一个整数\(y\)满足上式即可
当\(x,y\)都确定后构造答案就非常简单了，先设\(n-2\)个数都取最小的
然后从后往前考虑每个数，差多少就往后移即可，如果不够的话就移到当前没用过的最大的数，这个具体看代码很好理解
综上，虽然我们不知道枚举\(x\)的上界是多少，但是根据直觉这个东西应该不大（毕竟区间的变化是平方级别的），因此可以通过
#include<cstdio>
#include<iostream>
#include<cmath>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,ans[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; if (scanf("%d",&n),n==2) { puts("1 3"); continue; }
for (i=n-1;;++i)
{
int L=ceil((1.0*i*i+1.0*i*(1-n)+0.5*n*n-1.5*n+1)/n);
int R=floor((1.0*i*i-i-0.5*n*n-1.5*n+1)/n); if (L>R) continue;
long long sum=1LL*(n-2)*(L+1)+1LL*(n-3)*(n-2)/2LL;
long long tar=1LL*i*i-i-2LL*L; int lim=L+i-1;
for (j=2;j<=n-1;++j) ans[j]=L+j-1;
for (j=n-1;j>=2&&sum<tar;--j)
if (lim-ans[j]>=tar-sum) ans[j]+=tar-sum,sum=tar;
else sum+=lim-ans[j],ans[j]=lim,--lim;
ans[1]=L; ans[n]=L+i; break;
}
for (i=1;i<=n;++i) printf("%d%c",ans[i]," \n"[i==n]);
}
return 0;
}