Reku
0%

Codeforces Div 2 D 天梯 16——20

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/429/B \(d1_{ij}\) 代表从点 \((1,1)\) 到 \((i,j)\)的最大锻炼程度 \(d2_{ij}\) 代表从点 \((n,1)\) 到 \((i,j)\)的最大锻炼程度 \(d3_{ij}\) 代表从点 \((n,m)\) 到 \((i,j)\)的最大锻炼程度 \(d4_{ij}\) 代表从点 \((1,m)\) 到 \((i,j)\)的最大锻炼程度 但是算最后结果的时候要避开中间的冲突，所以写起来十分烦人（其实不冲突的情况只有两种） 因为开始思路不够清晰，所以写了好长时间TAT

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
int t[1010][1010]={};
int d1[1010][1010]={};
int d2[1010][1010]={};
int d3[1010][1010]={};
int d4[1010][1010]={};
int ans;
int p;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&t[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			d1[i][j]=t[i][j]+max(d1[i-1][j],d1[i][j-1]);
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=1;j<=m;j++)
		{
			d2[i][j]=t[i][j]+max(d2[i+1][j],d2[i][j-1]);
		}
	}
	for(int i=n;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
		{
			d3[i][j]=t[i][j]+max(d3[i+1][j],d3[i][j+1]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=1;j--)
		{
			d4[i][j]=t[i][j]+max(d4[i-1][j],d4[i][j+1]);
		}
	}
	for(int i=2;i<n;i++)
	{
		for(int j=2;j<m;j++)
		{
			p=d1[i][j-1]+d2[i+1][j]+d3[i][j+1]+d4[i-1][j];
			ans=max(p,ans);
			p=d1[i-1][j]+d2[i][j-1]+d3[i+1][j]+d4[i][j+1];
			ans=max(p,ans);
		}
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/451/D 这题写出来之后似乎也不是很难的样子... 但是之前被思维定势限制住了，觉得必须先把字符串压缩一下，题目会简单一些...但事实证明不压缩更简单... 因为字符串只是由ab构成，那么，如果子串的头字母和尾字母相同，那么这个子串就一定是good的... 所以我们只需要统计一下出现过的ab的位置是奇数还是偶数就可以了...计算方法也比较显然... 我真是蠢得可以...

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
#include<bits/stdc++.h>
using namespace std;
string s;
long long ce[2],co[2];
long long e,o;
int main()
{
	cin>>s;
	o=s.size();
	for(int i=0;i<s.size();i++)
	{
		int p=s[i]-'a';
		if(i%2==0)
		{
			o+=co[p];
			e+=ce[p];
			co[p]++;
		}
		else
		{
			o+=ce[p];
			e+=co[p];
			ce[p]++;
		}
	}
	cout<<e<<" "<<o<<endl;
	return 0;
}

http://codeforces.com/problemset/problem/271/D 这也能被卡...妈的... 题目解法倒是非常傻逼，就是字符串尺取法一下，然后再来个字符串哈希就行了，但是实力被卡... 我觉得算法肯定没什么问题 

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
#include<bits/stdc++.h>
using namespace std;
string s;
string v;
int k;
int p;
int l,r;
int t;
map<string,bool> ha;
char c[1510]={};
char u[1510]={};
int ans;
int main()
{
	scanf("%s%s",&c,&u);
	s=c;
	v=u;
	scanf("%d",&k);
	l=0;
	r=-1;
	p=0;
	for(int i=0;i<s.size();i++)
	{
		r++;
		if(v[s[i]-'a']=='0') p++;
		while(p>k)
		{
			if(v[s[l]-'a']=='0') p--;
			l++;
		}
		for(int j=l;j<=r;j++)
		{
			t=j-l+1;
			if(ha[s.substr(l,t)]==0)
			{
				ha[s.substr(l,t)]=1;
				ans++;
			}
			t=r-j+1;
			if(ha[s.substr(j,t)]==0)
			{
				ha[s.substr(j,t)]=1;
				ans++;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

然后我复制了一个不明觉厉的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
ll a[3000000],k,c;
char s[1520],v[30];
int main()
{
	cin>>s>>v>>k;
	for(int i=0;s[i];i++)
		for(ll j=i,kk=k,h=0;s[j]&&(v[s[j]-'a']>'0'||kk--);j++)
			a[c++]=h=(h*131)^s[j];
	sort(a,a+c);
	cout<<unique(a,a+c)-a;
}

其实就是字符串哈希然后排序去重... 不知道为什么会被卡掉... http://codeforces.com/contest/407/problem/B 开始的时候没看到 1<=Pi<=i 然后思考了好长时间...感觉这题十分不可做... 后来发现这个条件之后，这题就可以用动态规划解决了 di代表第奇数次进入点i到从1号门出来，总共花费多少步 然后状态转移就比较明显啦 

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
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long n;
long long p[1010]={};
long long d[1010]={};
long long ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
	}
	d[1]=1;
	for(int i=2;i<=n;i++)
	{
		if(i==p[i]) d[i]=1;
		else
		{
			d[i]=1;
			for(int j=p[i];j<=i-1;j++)
			{
				d[i]+=d[j]+1;
				d[i]%=mod;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans+=d[i]+1;
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/484/B 我好像就是凭着感觉乱搞... 算法似乎也很难用语言表述... 还是直接看代码吧... 

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
#include<bits/stdc++.h>
using namespace std;
int a[2000010]={};
int q[2000010]={};
int n;
int u;
int x;
bool cmp(int x,int y)
{
	return x<y;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>u;
		q[i]=u;
		a[u]=u;
	}
	sort(q+1,q+n+1,cmp);
	for(int i=1;i<=2000000;i++)
	{
		a[i]=max(a[i],a[i-1]);
	}
	for(int i=1;i<=n;i++)
	{
		if(q[i]!=q[i-1])
		for(int j=q[i];j<=2000000;j+=q[i])
		{
			if(a[j-1]>=q[i]) x=max(x,a[j-1]%q[i]);
		}
	}
	cout<<x;
	return 0;
}