题解 | #Task Computing#

更多题解在个人博客：https://blog.nowcoder.net/n/0680219d90264ae6b22505f19e2c75c0 同步更新。

H.Wall Builder II

难度：easy

首先不难想出应该是接近正方形时边长最小（这个可以用均值不等式证明）。

然后就是构造答案了，贪心应该是可以的，但考场没想到，写的二进制拆分多重背包带输出方案，所幸的是也过了。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pa;
const int MAXN=105;
pa pre[MAXN*MAXN];
int cnt[MAXN];
bool dp[MAXN*MAXN];
int main()
{
    int T;
    cin>>T;
    int n;
    while(T--)
    {
        scanf("%d",&n);
        int sum=0;
        for(int i=1;i<=n;++i) sum+=i*(n-i+1),cnt[i]=n-i+1;
        int tmp=sqrt(sum);
        for(int i=tmp;i>=1;--i)
        {
            if(sum%i==0)
            {
                tmp=i;
                break;
            }
        }
        cout<<(tmp+sum/tmp)*2<<endl;
        if(tmp<sum/tmp) tmp=sum/tmp;
        for(int i=1;i<=sum/tmp;++i)
        {
            memset(dp,0,sizeof(dp));
            memset(pre,0,sizeof(pre));
            dp[0]=1;
            for(int j=n;j>=1;--j)
            {
                int x=cnt[j];
                for(int s=1;x;s<<=1)
                {
                    if(s>x) s=x,x=0;
                    else x-=s;
                    for(int k=tmp;k>=j*s;--k)
                        if(!dp[k] && dp[k-j*s]) dp[k]=1,pre[k]={j,s};
                }
            }
            int now=tmp,l=0;
            while(now)
            {
                for(int j=1;j<=pre[now].second;++j)
                    printf("%d %d %d %d\n",l,i-1,l+pre[now].first,i),l+=pre[now].first;
                cnt[pre[now].first]-=pre[now].second;
                now-=pre[now].first*pre[now].second;
            }
        }
    }
    return 0;
}

K.NIO's Sword

难度：easy

一道简单题居然在考场最后一小时才想出来……

其实正解并不难，要判断 $x$ 是否能变成 $x + 1$ 只需枚举步数（不需要关心具体方案）。

设当前枚举步数为 $a$ ，则 $x$ 能变成的范围为： $[x \times 10^a,(x+1) \times 10^a-1]$

为简化，令 $L=x \times 10^a$ ， $R=(x+1) \times 10^a-1$ 。

$1$ .当 $R - L + 1 > = n$ 显然能构造出余数为 $[0, n - 1]$ 的所有数，成立。

$2$ .当 $(L\%n)<=(R\%n)$ ，需满足 $(x+1)\%n$ 在 $[L, R]$ 。

$3$ .当 $(L\%n)>(R\%n)$ ，发现可构造出的余数为 $[L, n - 1]$ 和 $[0, R]$ ，那么需满足 $(x+1)\%n$ 在该区间。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN=1e6+5;
int ten[MAXN];
signed main()
{
    ten[0]=1;
    for(int i=1;i<=6;++i) ten[i]=ten[i-1]*10;
    int n;
    cin>>n;
    if(n==1)
    {
        printf("0");
        return 0;
    }
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=7;++j)
        {
            int l=(i-1)*ten[j],r=i*ten[j]-1;
            if(r-l+1>=n)
            {
                ans+=j;
                break;
            }
            l%=n,r%=n;
            if(r>l)
            {
                if(l<=i%n && i%n<=r)
                {
                    ans+=j;
                    break;
                }
            }
            else
            {
                if(l<=i%n || i%n<=r)
                {
                    ans+=j;
                    break;
                }
            }
        }
    }
    printf("%lld",ans);
    return 0;
}

N.Particle Arts

难度：check-in

之所以说是签到题，是因为题目已经提示的很详细了，在粒子相互碰撞时，每个位上的 $1$ 的总数是不变的。

于是大胆猜想最后粒子一定是能放 $1$ 放 $1$ ，不能就放 $0$ 。

本蒟蒻的写法比较菜，要靠int128才不会爆。

#include<bits/stdc++.h>
using namespace std;

#define int __int128_t
const int MAXN=1e5+5;
long long a[MAXN];
int cnt[15];
int gcd(int x,int y)
{
    int tmp=x%y;
    while(tmp) x=y,y=tmp,tmp=x%y;
    return y;
}
signed main()
{
    long long n;
    cin>>n;
    int x=0,y=n;
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),x+=a[i];
    int d=gcd(x,y);
    x/=d,y/=d;
    for(int i=1;i<=n;++i)
        for(int j=0;j<15;++j)
            if(a[i]&(1<<j))
                ++cnt[j];
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;++i)
        for(int j=0;j<15;++j)
            if(cnt[j])
                a[i]+=(1<<j),--cnt[j];
    for(int i=1;i<=n;++i) a[i]*=y;
    int ansx=0,ansy=y*y*n;
    for(int i=1;i<=n;++i)
        ansx+=(x-a[i])*(x-a[i]);
    d=gcd(ansx,ansy);
    ansx/=d,ansy/=d;
    printf("%lld/%lld",(long long)ansx,(long long)ansy);
    return 0;
}