2022牛客多校第4场

contest传送门

战况

standing

这次发挥比较平常，看题解才发现这次有一道字符串题目，但是那道题只有一个队写了出来。

补题

K-NIO’s Sword

题意

玩家要打怪，初始有一把攻击力为 $0$ 的剑，需要按顺序从 $1$ 到 $n$ 打怪。

只有剑的攻击力和怪的编号同余的时候才能打败怪物。

玩家可以升级剑，每次升级剑相当于在当前攻击力的后面加上一个数字。

问最少需要升级多少次。

思路

记录当前攻击力为 $A$ ，准备打编号为 $i$ 的怪，为了打败他，要进行 $k$ 次升级。

则有式子 $(i-1)*10^k+x \equiv i(mod n) (0 \leq x < 10^k)$ 。

直接暴力枚举 $k$ 的值，直到得到的 $w<10^k$ 。 $k$ 即为后面需要加的位数。

当 $n=1$ 时要特判答案为 $0$ 。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

LL n;

inline void solve(){
	scanf("%lld",&n);
    LL ans=0;
    if(n==1){
        printf("0\n");
        return;
    }
    for(LL i=1;i<=n;++i){
        LL now=1,jj=10;
        for(;;){
            LL kk=(i-((i-1)*jj)%n+n)%n;
            if(kk>=0&&kk<jj){
                ans+=now;
                break;
            }
            ++now;
            jj*=10;
        }
    }
	
	printf("%lld\n",ans);
}

signed main(){
//	int t;scanf("%d",&t);
//	while(t--)
		solve();
	
	return 0;
}

总结

要根据题目推式子。

H-Wall Builder II

题意

给出 $n$ 个 $1 \times 1$ 的矩形， $n-1$ 个 $1 \times 2$ 的矩形， $n-2$ 个 $1 \times 3$ 的矩形 $\dots$ ， $1$ 个 $1 \times n$ 的矩形，把这些矩形拼成一个大矩形，使得这个大矩形周长最小，这些矩形不能旋转。

思路

我们可以直到这个大矩形的总面积 $S$ 是固定的，我们可以枚举所有可能的长和宽，寻找能不能拼出这个大矩形。使用贪心的思想进行枚举，枚举顺序是周长从小到大即可。

代码

#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=205;

int n,num[MAXX],S,sum;
array<int,4> ans[MAXX*MAXX];

inline void solve(){
	scanf("%d",&n);
    sum=n*(n+1)/2;
    memset(num,0,sizeof(num));
    S=0;
    for(int i=1;i<=n;++i){
        num[i]=n+1-i;
        S+=i*num[i];
    }
	
    int anslen=0;
    for(int h=sqrt((double)S);h>=1;--h){
        int l=S/h;
        if(h*l!=S) continue;
        for(int i=1;i<=n;++i){
            num[i]=n+1-i;
            S+=i*num[i];
        }
        int p=0;
        bool cannot=false;
        for(int hi=1;hi<=h;++hi){
            int len=0;
            while(len<l){
                bool changed=false;
                for(int i=min(l-len,n);i>=1;--i){
                    if(num[i]){
                        ans[++p]={len,hi-1,len+i,hi};
                        len+=i;changed=true;
                        --num[i];
                        break;
                    }
                }
                if(!changed){
                    cannot=true;
                    break;
                }
            }
            if(cannot) break;
        }
        if(cannot) continue;
        anslen=(l+h)*2;
        break;
    }

    printf("%d\n",anslen);
    for(int i=1;i<=sum;++i){
        printf("%d %d %d %d\n",ans[i][0],ans[i][1],ans[i][2],ans[i][3]);
    }
}

signed main(){
	int t;scanf("%d",&t);
	while(t--)
		solve();
	
	return 0;
}