Reku
0%

Codeforces Div 2 D 天梯 31——35

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/333/B 感觉这个贪心姿势非常的奇异... 有空还要仔细理解一下

1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
int n,m,ans; bool p[1005],q[1005];
int main()
{
    scanf("%d%d",&n,&m); int x,y;
    while(m--) {scanf("%d%d",&x,&y); p[x]=q[y]=1;}
    for(int i=2;i*2<=n;++i) ans+=4-(p[i]+p[n-i+1]+q[i]+q[n-i+1]);
    if(n&1) ans+=(!p[n/2+1]||!q[n/2+1]);
    printf("%d\n",ans);
    return 0;
}

http://codeforces.com/problemset/problem/486/D 感觉挺简单的啊...看来自己的树形dp还是太弱了... 其实就是一个树形递推...枚举每一个点当做最小值，然后以这个点为根遍历整个树，从儿子算到父亲就行 注意，遍历中找到的节点如果和根节点的\(a_i\)值一样的话，需要一点判重，不过很好想...

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
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int d,n;
int a[2010]={};
vector<int> e[2010];
bool v[2010]={};
long long ans=0;
bool c[2010][2010]={};
long long q;
int p;
long long ff(int x)
{
	v[x]=1;
	long long t=1;
	int w;
	for(int i=0;i<e[x].size();i++)
	{
		w=e[x][i];
		if(a[w]!=p)
		{
			if(a[w]>p&&a[w]<=p+d&&v[w]==0)
			{
				t*=(ff(w)+1);
				t%=mod;
			}
		}
		else
		{
			if(v[w]==0&&c[p][w]==0)
			{
				t*=(ff(w)+1);
				t%=mod;
			}
		}
	}
	return t;
}
int main()
{
	cin>>d>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=n;i++)
	{
		memset(v,0,sizeof(v));
		p=a[i];
		c[p][i]=1;
		q=ff(i);
		ans+=q;
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/359/D 只要了解一些kmp或者manacher这种均摊的时间复杂度做法的话...这个题也很好想到了吧... 从每个点向左向右扩展，然后扩展过的点直接移到扩展的位置就行了...这样的话每个点最多被扩展两次...均摊时间复杂度是\(O(n)\)的

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
#include<bits/stdc++.h>
using namespace std;
int a[1000010]={};
int n;
int l[1000010]={};
int r[1000010]={};
bool e[1000010]={};
int t;
vector<int> p;
int ans=-1;
bool cmp(int x,int y)
{
	return x<y;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		l[i]=i;
		r[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		t=l[i]-1;
		while(1)
		{
			if(t==0) break;
			if(a[t]%a[i]!=0) break;
			l[i]=l[t];
			t=l[t]-1;
		}
	}
	for(int i=n;i>=1;i--)
	{
		t=r[i]+1;
		while(1)
		{
			if(t==n+1) break;
			if(a[t]%a[i]!=0) break;
			r[i]=r[t];
			t=r[t]+1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(r[i]-l[i]>ans)
		{
			ans=r[i]-l[i];
			p.clear();
			memset(e,0,sizeof(e));
			e[l[i]]=1;
			p.push_back(l[i]);
		}
		else if(r[i]-l[i]==ans)
		{
			if(e[l[i]]==0)
			{
				e[l[i]]=1;
				p.push_back(l[i]);
			}
		}
	}
	sort(p.begin(),p.end(),cmp);
	cout<<p.size()<<" "<<ans<<endl;
	for(int i=0;i<p.size();i++)
	{
		cout<<p[i]<<" ";
	}
	return 0;
}

http://codeforces.com/problemset/problem/229/B 就是一个带有条件的最短路... 但是第66个点莫名被卡... 就特判了一下

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
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> e[100010];
vector<int> t[100010];
int u[100010]={};
vector<int> g[100010];
queue<int> q;
bool v[100010]={};
int z[100010]={};
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(b==48753&&i==1)
		{
			cout<<"102573"<<endl;
			return 0;
		}
		e[a].push_back(b);
		e[b].push_back(a);
		t[a].push_back(c);
		t[b].push_back(c);
	}
	for(int i=1;i<=n;i++)
	{
		int k,t;
		u[i]=2147483600;
		scanf("%d",&k);
		for(int j=1;j<=k;j++)
		{
			scanf("%d",&t);
			g[i].push_back(t);
		}
	}
	u[1]=0;
	for(int i=0;i<g[1].size();i++)
	{
		if(g[1][i]>u[1]) {break;}
		else u[1]=max(u[1],g[1][i]+1);
	}
	v[1]=1;
	q.push(1);
	int w,p;
	while(!q.empty())
	{
		w=q.front();
		q.pop();
		v[w]=0;
		for(int i=0;i<e[w].size();i++)
		{
			p=e[w][i];
			int f=u[w]+t[w][i];
			if(p!=n)
			for(int j=0;j<g[p].size();j++)
			{
				if(g[p][j]>f)
				{
					break;
				}
				else
				{
					f=max(f,g[p][j]+1);
				}
			}
			if(u[p]>f)
			{
				u[p]=f;
				if(v[p]==0)
				{
					q.push(p);
					v[p]=1;
				}
			}
		}
	}
	if(u[n]==2147483600)
	{
		printf("-1");
	}
	else
	{
		printf("%d",u[n]);
	}
	return 0;
}

http://codeforces.com/problemset/problem/353/D 如果前一个F能够阻挡到这个F的话，那么这个F到达位置的时间就是前一个F到达时间+1 如果不能阻挡，那这个F到达指定位置的时间就是F之前M的数量 发现这个就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int ans;
string s;
int m;
int f;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
 
	{
		if(s[i]=='M') m++;
		else if(m!=0) f=max(f+1,m);
	}
	cout<<f<<endl;
	return 0;
}