发表于 | 更新于 | 评论数：

超级好的题，需要自己动一下脑子才不超时.
我们首先算出包含自己本身的并且有重复的num1[]来然后第二波kmp的时候进行进一步的失配指针偏移 

1
2
if(j<i/2)
j=nex[j];

这样能够保证我们的j是不重复的j然后把之前的num1数组按照格式乘起来即可 

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll nex[1000005],mod=ll(1e9)+7,num[1000005];
char s[1000005];
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		memset(nex,0,sizeof(nex));
		memset(num,0,sizeof(num));
		scanf("%s",s+1);
		ll len=strlen(s+1);
		ll j=0,ans=1;
		num[0]=0;
		num[1]=1;
		for(int i=2;i<=len;i++)
		{
			while(j&&s[i]!=s[j+1])
			j=nex[j];
			if(s[i]==s[j+1])
			j++;
			nex[i]=j;
			num[i]=num[j]+1;
		}
		j=0;
		for(int i=2;i<=len;i++)
		{
			while(j&&s[i]!=s[j+1])
			j=nex[j];
			if(s[i]==s[j+1])
			j++;
			while(j>i/2)
			j=nex[j];
			ans=ans%mod*(num[j]+1)%mod;
			ans%=mod;
		}
		printf("%lld\n",ans%mod);
	}
}

发表于 | 评论数：




模板洛谷P4777

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
#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
long long a[100005],b[100005];
void gcd(ll a,ll b,ll& x,ll& y,ll& d)
{
	if(!b)
	x=1,y=0,d=a;
	else
	gcd(b,a%b,y,x,d),y-=a/b*x;
}
int main()
{
	long long t;
	cin>>t;
	for(int i=1;i<=t;i++)
	cin>>a[i]>>b[i];
	for(int i=1;i<t;i++)
	{
		ll A=a[i],B=a[i+1],C=(b[i+1]-b[i]),x,y,d=__gcd(A,B);
		if(C%d)
		return cout<<"-1",0;
		A/=d,B/=d,C/=d;
		gcd(a[i],a[i+1],x,y,d);
		x=(x*C%B+B)%B;
		a[i+1]=a[i]/d*a[i+1];
		b[i+1]=(a[i]*x%a[i+1]+b[i])%a[i+1];
	}
	cout<<b[t];
}

发表于 | 评论数： 
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
int st[200005],p,l[200005],r[200005],ll[200005],rr[200005],pos,ans,js[200005];
struct tree
{
    long long l,r,sum,f;
}t[400005];
struct node
{
    int s,id;
}a[100005];
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].sum=t[p].f=0;
    if(t[p].l==t[p].r)
    return;
    int mid=(t[p].l+t[p].r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
void lazy(int p)
{
    if(t[p].f)
    {
        t[p<<1].f+=t[p].f;
        t[p<<1|1].f+=t[p].f;
        t[p<<1].sum+=(t[p<<1].r-t[p<<1].l+1)*t[p].f;
        t[p<<1|1].sum+=(t[p<<1|1].r-t[p<<1|1].l+1)*t[p].f;
        t[p].f=0;
    }
}
void change(int p,int x,int y,int z)
{
    if(x<=t[p].l&&y>=t[p].r)
    {
        t[p].sum+=(t[p].r-t[p].l+1)*z;
        t[p].f+=z;
        return;
    }
    lazy(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(x<=mid)
    change(p<<1,x,y,z);
    if(y>mid)
    change(p<<1|1,x,y,z);
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
long long gs(int p,int x,int y)
{
    if(x<=t[p].l&&y>=t[p].r)
    return t[p].sum;
    lazy(p);
    int mid=(t[p].l+t[p].r)>>1;
    long long ans=0;
    if(x<=mid)
    ans+=gs(p<<1,x,y);
    if(y>mid)
    ans+=gs(p<<1|1,x,y);
    return ans;
}
bool cmp(node a,node b)
{
    return a.s<b.s;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i].s),a[i].id=i;
    for(int i=1;i<=n;i++)
    {
        while(p&&a[st[p]].s>=a[i].s)
        p--;
        l[i]=p?st[p]:0;
        st[++p]=i;
    }
    p=0;
    for(int i=n;i;i--)
    {
        while(p&&a[st[p]].s>=a[i].s)
        p--;
        r[i]=p?st[p]:n+1;
        st[++p]=i;
    }
    p=0;
    build(1,1,100001);
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].s-(gs(1,l[a[i].id]+1,r[a[i].id]-1)/(r[a[i].id]-(l[a[i].id]+1)))>=1)
        {
            ans+=a[i].s-(gs(1,l[a[i].id]+1,r[a[i].id]-1)/(r[a[i].id]-(l[a[i].id]+1)));
            ll[++pos]=l[a[i].id]+1;
            rr[pos]=r[a[i].id]-1;
            js[pos]=a[i].s-(gs(1,l[a[i].id]+1,r[a[i].id]-1)/(r[a[i].id]-(l[a[i].id]+1)));
            change(1,l[a[i].id]+1,r[a[i].id]-1,a[i].s-(gs(1,l[a[i].id]+1,r[a[i].id]-1)/(r[a[i].id]-(l[a[i].id]+1))));
        }   
    }
    printf("%d\n",ans);
    for(int i=1;i<=pos;i++)
    for(int j=1;j<=js[i];j++)
    printf("%d %d\n",ll[i],rr[i]);
}

发表于 | 评论数：

过于经典的深搜题目，而且难度还不算低…..
思路上需要知道多少的长度可以构成合法的长度需要从[最大的长度,所有的长度之和]之间并且这个长度能够使所有长度之和的一个约数
所以我们这么枚举即可从小到大。然后到了关键的地方怎么dfs呢，这里要放一个三元组一个表示当前的位置，一个表示当前拼成的合法的个数一个表示当前的一个合法长度的长
这里需要排序降序排序这样枚举好枚举也是一个降低复杂度的方法…
需要判断一下如果合法的长度满足我们的要求的话就返回即可。这里用的条件判断的dfs，实际上也可以自己设置变量这里就是减少了代码量.
如果我们当前的长度满足了单个的要求那么从第一个开始继续搜索同时合法长度加一
搜索的时候也要记录bk免得一个木棒用了好几次
剪枝一个是如果当前第一个就不满足情况直接返回即可一个就是如果后面跟第一个失败的一样的长度直接过
总的来说剪枝第一是排序这样找的时候好找，第二是如果当前就不满足条件直接跳出，第三如果相同就直接遍历

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 <bits/stdc++.h>
using namespace std;
int bk[10005],a[100005],now,l,n,sum;
bool cmp(int a,int b)
{
	return a>b;
}
int dfs(int p,int cnt,int len)//p当前的位置,cnt当前拼出来了几根木条了,len表示当前拼接的木条的长度
{
	if(cnt==now)
	return 1;
	if(len==l)
	return dfs(1,cnt+1,0);
	for(int i=p;i<=n;i++)
	if(!bk[i]&&len+a[i]<=l)
	{
		bk[i]=1;
		if(dfs(i+1,cnt,len+a[i]))
		return 1;
		bk[i]=0;
		if(len==0)
		return 0;
		while(i<n&&a[i+1]==a[i])
		i++;
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		sort(a+1,a+1+n,cmp);
		for(int i=a[1];i<=sum;i++)
		if(sum%i==0)
		{
			now=sum/i;
			l=i;
			memset(bk,0,sizeof(bk));
			if(dfs(1,0,0))
			{
				printf("%d\n",i);
				break;
			}
		}
	}
}

发表于 | 评论数：

很好的DP题，本质上是数字三角形的变形从5第一层到4 5 6第二层这样可以把可到达的位置分层然后套用数字三角形即可 

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
#include <bits/stdc++.h>
using namespace std;
long long bk[100005][20],f[100005][20];
long long n,m,ans,x,y;
int main()
{
	while(~scanf("%lld",&n))
	{
		if(n==0)
		break;
		m=0,ans=0;
		memset(bk,0,sizeof(bk));
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld",&x,&y);
			bk[y][x]++;
			m=max(m,y);
		}
		for(int j=0;j<=10;j++)
		f[m][j]=bk[m][j];
		for(int i=m;i;i--)
		for(int j=0;j<=10;j++)
		f[i-1][j]=max(f[i][j-1],max(f[i][j],f[i][j+1]))+bk[i-1][j];
		printf("%lld\n",f[0][5]);	 
	}
}
0%