牛客练习赛36

Rabbit的字符串

就是最小表示法啊

#include<iostream>
#include<cstdio>
#include<cstring>
#define M 2010000
using namespace std;

int k,m,n,b,l,r;
char c[M],d[M];

int Min(char *s, int n){
    int i=0,j=1,k;
    while(i<n&&j<n){
        k=0;
        while(s[(i+k)%n]==s[(j+k)%n]&&k<n) k++;
        if(k==n) return i;
        if(s[i+k]>s[j+k])i+=k+1;
        else j+=k+1;
        if(i==j)j++;
    }
    return min(i,j);
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++) cin>>c[i];
	if(Min(c,n)!=0) printf("YES");
	else printf("NO");
}

Rabbit的工作(1)

(f[i][j])表示前(i)天工作(j)天最小体力消耗

每次从后往前枚举最后一段工作时间

没了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,m,k,f[401][401],a[401],d[410],ans;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) d[i]=d[i-1]+i;
	memset(f,0x3f,sizeof(f)); f[0][0]=0;
	for(int i=1;i<=n;i++) scanf("%1ld",&a[i]),f[i][0]=0;
	for(int i=1;a[i];i++) f[i][i]=d[i];
	for(int i=1;i<=n;i++)
    {
        if(a[i]) for(int l=1;l<=i;l++) 
		{
			for(int j=i;j>=2 && a[j]&& i-j+1<=l;j--) 
			if(f[j-2][l-i+j-1]+d[i-j+1]<=k)	f[i][l]=min(f[i][l],f[j-2][l-i+j-1]+d[i-j+1]);
			if(f[i][l]<=k) ans=max(ans,l);
		}
	    for(int j=1;j<=i;j++) f[i][j]=min(f[i][j],f[i-1][j]);
    }
    printf("%d",ans);
}

Rabbit的工作(2)

ZUTTER用优秀的(O(n^3))加边界优化把它卡过去了！！！！

这个故事告生动诉我们一个真理人有多大胆，地有多大产

正解

为了去掉所有任务的限制先给每个工作分一天，把(V[2]-V[n])整体建(V[1])

然后这不就是一个完全背包了嘛！！！

(O(n^2))解决

ZUTTER的心理动向

感觉只有(O(n^3))做法啊

怕不是斜率优化单调性优化线段树优化

可是我不会啊！！！

2≤ N,K≤ 2000,K≤ W≤ min(4000,2*K)

矮这个(w)范围比(n,k)只大一倍有点奇怪啊

把(n)提到最外层再枚举(w)再枚举(k)感觉会快很多啊

经过一波冷静分析似乎复杂度挺有前途的!!??

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int i,m,n,j,k,a[2001],w,f[4001][2001];

int main()
{
	scanf("%d%d%d",&n,&k,&w);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	memset(f,-0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=n;i++) 
		for(int j=0;j<=w-i;j++)
			for(int l=max(0,k-(w-j)/i);l<k;l++)
				f[j+i][l+1]=max(f[j+i][l+1],f[j][l]+a[i]);	
	printf("%d",f[w][k]);
}

~~然后就用暴力过了一道只有6个人过的题~~

Rabbit的数列

分块啊

可是我不会啊

咕咕咕

Rabbit的机器人

甚至没看题

咕咕咕

Rabbit的蛋糕

计算几何

可是我也不会啊（我怎么这么菜啊QAQ

咕咕咕