Jan.7th
注：黑粗体为超链接
这种东西显然是要记忆化搜索的么
$Ans_{l,r}$表示搜出来的在第l个左括号到第r个左括号构成的序列中第l个左括号与与它相对应的右括号之间的距离
然后这样最多是$n^2$种，再加上每次搜索枚举l的右括号到左括号之间包括多少个其他的左括号 这样最多n次
所以就是$n^3$
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } struct seg{ int l,r; }a[605]; int n; int Ans[605][605]; bool DFS(int l,int r){ if (l>r) return 1; if (Ans[l][r]) return Ans[l][r]>0; if (l==r){ if (a[l].l<=1){Ans[l][r]=1;return 1;} else{Ans[l][r]=-1;return 0;} } int len=(r-l)*2+1; if (len>=a[l].l&&len<=a[l].r) if (DFS(l+1,r)){Ans[l][r]=len;return 1;} int high=min(r-l-1,(a[l].r-1)/2); Rep(i,a[l].l/2,high){ if (DFS(l,l+i)&DFS(l+i+1,r)){Ans[l][r]=i*2+1;return 1;} } Ans[l][r]=-1;return 0; } void Write(int l,int r){ if (l>r) return; if (l==r){printf("()");return;} printf("(");Write(l+1,l+Ans[l][r]/2); printf(")");Write(l+Ans[l][r]/2+1,r); } int main(){ n=IN(); Rep(i,1,n) a[i].l=IN(),a[i].l=(a[i].l&1)?a[i].l:a[i].l+1,a[i].r=IN(); if (!DFS(1,n)) return puts("IMPOSSIBLE"),0; Write(1,n); } |
暴力把所有串都搞出来然后排序去重就行
把输进来的二进制数当做字符串 输出最多的有几个相同就行了
从最后一种球开始，一个球必须放最后面，剩下ak-1个球可以放在Restk-1个格子里
$Rest_i=\sum_{j=1}^{i}a_j$
然后对于倒数第二种、倒数第三种，继续这样做
一直做到第二种就可以了
$Ans=\prod_{i=2}^{k}C_{Rest_i-1}^{a_i-1}$
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long #define MOD 1000000007 using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int QPow(int Base,int Pow){ int ret=1; for (;Pow;Pow>>=1,Base=1ll*Base*Base%MOD) if (Pow&1) ret=1ll*ret*Base%MOD; return ret; } int k,Ans=1,All,a[1005]; int Fact[1005],Inv[1005]; void Init(){ Fact[0]=1; Rep(i,1,All) Fact[i]=1ll*Fact[i-1]*i%MOD; Inv[All]=QPow(Fact[All],MOD-2); Per(i,All-1,0) Inv[i]=1ll*Inv[i+1]*(i+1)%MOD; } int C(int m,int n){ int ret=1ll*Fact[m]*Inv[m-n]%MOD*Inv[n]%MOD; return ret; } int main(){ k=IN();All=0; Rep(i,1,k) a[i]=IN(),All+=a[i]; Init(); Per(i,k,2) Ans=1ll*Ans*C(All-1,a[i]-1)%MOD,All-=a[i]; printf("%d\n",Ans); |
我们找规律以后发现长度为n的符合题意的排列有$F_n$种
$F_n$就是斐波那契数列的第n项
然后不就是SB题了嘛
C++ Code By WTRC
|
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
#include<cstdio>
#include<cstring> #include<algorithm> #include<cctype> #include<ctime> #include<cstdlib> #include<string> #include<queue> #define Rep(x,a,b) for (int x=a;x<=b;x++) #define Per(x,a,b) for (int x=a;x>=b;x--) #define ll long long using namespace std; inline int IN(){ int x=0,ch=getchar(),f=1; while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar(); if (ch=='-'){f=-1;ch=getchar();} while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } int now,n; ll k,f[55]; void Solve(int len,ll pos){ if (len==0) return; if (pos>=f[len-1]){ printf("%d %d ",now+1,now);now+=2; Solve(len-2,pos-f[len-1]); } else printf("%d ",now),now++,Solve(len-1,pos); } int main(){ scanf("%d%I64d",&n,&k);now=1; f[0]=f[1]=1; Rep(i,2,n) f[i]=f[i-1]+f[i-2]; Solve(n,k-1); } |
——————————————————————————————
评论 (0)
