题目大意
构造一个01网格图,1能走0不能走
使得从左上走到右下(只能走右或走下)的方案数恰好为x
n<=30,x<=1e9
题解
类似于进制转换,假设能把x写成\(x=\sum a_ip_i\),\(p_i\)表示第i位一个1代表的值,然后再独立构造求和
构造需要满足的条件:
①可以实现对单个\(p_i\)乘以\(a_i\)
②可以把\(a_ip_i\)求和
要求每一小部分都是独立的,不能有格子碰在一起
先这样构造1的块(数字是这样构造时的路径数),设每3行的右上角的数为p[i]:
1
10
74
549
4177
32568
259272
2100064
17257108
143537134
这样构造:
将画线的部分设为1,这样原始部分的方案不会改变,同时可以实现①\(a_i*p_i\)和②\(a_ip_i\)求和
(设p0=1,p1=10,上图就是\(3*p_0+2*p_1\)
按照这样连线 ,在最后一行连一竖来求和即可
如何求ai:从高到低求,如果x>=当前p[i]就减p[i],a[i]+1(也类似进制转换)
(也可以理解成让ai尽量小,所以一次减的数尽量大,每次减最大的能减的数
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
//#define file
using namespace std;
int n=30,x,i,j,k,l,id,X,Y;
int ans[31][31];
int f[11]={0,1,10,74,549,4177,32568,259272,2100064,17257108,143537134};
int v[11];
void init()
{
fo(i,1,n)
{
l=(i-1)/3+3;
fo(j,1,l)
ans[i][j]=1;
ans[i][n]=1;
}
}
int main()
{
#ifdef file
freopen("E.in","r",stdin);
#endif
init();
scanf("%d",&x);
fd(id,10,1)
{
while (x>=f[id])
{
x-=f[id];
++v[id];
}
if (v[id])
{
X=id*3-2;
Y=id+2;
fo(j,Y,n) ans[X][j]=1;
fo(j,n-v[id]+1,n) ans[X][j]=ans[X+1][j]=1;
}
}
printf("%d\n",n);
fo(i,1,n)
{
fo(j,1,n)
printf("%d ",ans[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}
- Programming Collegiate Provincial Counting Contestprogramming collegiate provincial counting programming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming provincial collegiate sponsored 2023 programming collegiate provincial 题解programming collegiate provincial programming collegiate jiangsu contest