1
7
2016
0

Diary of OI

Jan.7th
注:黑粗体为超链接
这种东西显然是要记忆化搜索的么
$Ans_{l,r}$表示搜出来的在第l个左括号到第r个左括号构成的序列中第l个左括号与与它相对应的右括号之间的距离
然后这样最多是$n^2$种,再加上每次搜索枚举l的右括号到左括号之间包括多少个其他的左括号  这样最多n次
所以就是$n^3$
 C++ Code By WTRC
1
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
1
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
1
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==0return;
    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);
}
——————————————————————————————
Category: Diary | Tags: codeforces | Read Count: 435

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com