Reku
0%

Codeforces Div 2 D 天梯 51——55

Posted on Edited on In Views: Valine:

http://codeforces.com/problemset/problem/167/B 动态规划 \(q[i][j][k]\) 代表已经走完第i个tour，赢了j场，现在书包里还有k个空余的概率 不过状态转移有点烦 还要先按照a[i]的降序把tour排列起来

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
#include<bits/stdc++.h>
using namespace std;
int n,l,k;
double p[210]={};
int a[210]={};
double q[210][210][210]={};
double ans=0;
void qsort(int l,int r)
{
	int i,j,mid;
	i=l;
	j=r;
	mid=a[(i+j)/2];
	while(i<j)
	{        
	        while(a[i]>mid)  i++;
			while(a[j]<mid)  j--;
			if(i<=j)
			{
				swap(a[i],a[j]);
				swap(p[i],p[j]);
				i++;
				j--;       
			}    
	}
    if(l<j)  qsort(l,j);
	if(l<r)  qsort(i,r); 
}
int main()
{
	cin>>n>>l>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
		p[i]/=100.0;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	qsort(1,n);
	q[0][0][min(n,k)]=1.0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				if(q[i][j][k]==0) continue;
				//cout<<i<<" "<<j<<" "<<k<<" "<<q[i][j][k]<<endl;
				if(a[i+1]==-1)
				{
					if(k>0)	q[i+1][j+1][k-1]+=q[i][j][k]*p[i+1];
					q[i+1][j][k]+=q[i][j][k]*(1.0-p[i+1]);
				}
				else
				{
					q[i+1][j+1][min(n,k+a[i+1])]+=q[i][j][k]*p[i+1];
					q[i+1][j][k]+=q[i][j][k]*(1.0-p[i+1]);
				}
			}
		}
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(i>=l)
			{
				ans+=q[n][i][j];
			}
		}
	}
	printf("%.10lf",ans);
	return 0;
}

http://codeforces.com/problemset/problem/348/B 非常烦的一道题... 主体思路还比较清晰，就是从树底到树顶进行贪心 需要记录几个值 sm 子树叶子节点的最小值 dm 子节点子树的值 to 该节点子树的值 h 该节点的高度 然后推的时候非常烦，要分类讨论 有一个坑点是，两个子树合并的时候，两个子树的sm是取gcd的...不能直接取最小值...后来我看数据调试才发现这个漏洞... 感觉我的思路中总是产生这种漏洞...要怎么解决呢orz

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<bits/stdc++.h>
using namespace std;
vector<int> e[100010]={};
struct vv
{
	long long a;
	long long sm;
	long long dm;
	long long to;
	long long h;
	int num;
} v[100010]={};
int n;
bool vis[100010]={};
int p[100010]={};
void ff(int x,int h)
{
	vis[x]=1;
	v[x].h=h;
	for(int i=0;i<e[x].size();i++)
	{
		if(vis[e[x][i]]==0)
		{
			v[x].sm=-1;
			v[x].dm=-1;
			ff(e[x][i],h+1);
		}
	}
	return;
}
bool cmp(vv a,vv b)
{
	return a.h>b.h;
}
long long ans=0;
long long gcd(long long a,long long b)
{
    long long t;
    while(b)
	{
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%I64d",&v[i].a);
		v[i].to=v[i].a;
		v[i].dm=v[i].a;
		v[i].sm=v[i].a;
		v[i].num=i;
	}
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	ff(1,0);
	sort(v+1,v+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		p[v[i].num]=i;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<e[v[i].num].size();j++)
		{
			int b=p[e[v[i].num][j]];
			if(v[b].h<v[i].h)
			{
				if(v[b].dm==-1)
				{
					v[b].dm=v[i].to;
					v[b].sm=v[i].sm;
					v[b].to+=v[i].to;
					continue;
				}
				while(1)
				{
					if(v[i].to==v[b].dm)
					{
						v[b].sm=gcd(v[b].sm,v[i].sm);
						v[b].to+=v[i].to;
						break;
					}
					if(v[i].to>v[b].dm)
					{
						long long bu=v[i].to/v[i].sm;
						long long su=v[i].to-v[b].dm;
						if(su%bu==0)
						{
							su/=bu;
						}
						else
						{
							su/=bu;
							su++;
						}
						ans+=su*bu;
						v[i].sm-=su;
						v[i].to-=su*bu;
					}
					if(v[i].to<v[b].dm)
					{
						long long bu=v[b].dm/v[b].sm;
						long long su=v[b].dm-v[i].to;
						if(su%bu==0)
						{
							su/=bu;
						}
						else
						{
							su/=bu;
							su++;
						}
						long long pp=v[b].to/v[b].dm;
						ans+=su*bu*pp;
						v[b].sm-=su;
						v[b].dm-=su*bu;
						v[b].to-=su*bu*pp;
					}
				}
			}
			
		}
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/301/B 观察一下数据范围就可以发现，一个节点肯定只能经过一次。 然后直接一个spfa就好了...

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
#include<bits/stdc++.h>
using namespace std;
int e[210][210]={};
int v[210][210]={};
int x[110]={};
int y[110]={};
int n;
int aa[110]={};
int d;
queue<pair<int,int>> q;
int main()
{
	cin>>n;
	cin>>d;
	for(int i=2;i<n;i++)
	{
		cin>>aa[i];
	}
	memset(e,-1,sizeof(e));
	for(int i=1;i<=n;i++)
	{
		cin>>x[i]>>y[i];
		x[i]+=100;
		y[i]+=100;
		if(i==1)
		{
			q.push(make_pair(x[i],y[i]));
			e[x[i]][y[i]]=0;
			v[x[i]][y[i]]=1;
		}
	}
	while(!q.empty())
	{
		pair<int,int> u;
		u=q.front();
		q.pop();
		int a,b;
		a=u.first;
		b=u.second;
		v[a][b]=0;
		for(int i=1;i<=n;i++)
		{
			if(x[i]!=a||y[i]!=b)
			{
				if(e[x[i]][y[i]]==-1||e[a][b]+(abs(x[i]-a)+abs(y[i]-b))*d-aa[i]<e[x[i]][y[i]])
				{
					e[x[i]][y[i]]=e[a][b]+(abs(x[i]-a)+abs(y[i]-b))*d-aa[i];
					if(v[x[i]][y[i]]==0)
					{
						v[x[i]][y[i]]=1;
						q.push(make_pair(x[i],y[i]));
					}
				}
			}
		}
	}
	cout<<e[x[n]][y[n]];
	return 0;
}

http://codeforces.com/problemset/problem/213/B 数位DP... \(dp[i][j]\) 表示长度为i的数字，用j到9的数字构成，有多少种状态 用组合数进行状态转移 不过边界条件好烦啊....

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
#include<bits/stdc++.h>
using namespace std;
long long c[110][110]={};
long long mod=1000000007ll;
long long d[110][11]={};
int n;
long long a[10]={};
void init()
{
  c[0][0]=c[1][0]=c[1][1]=1ll;
  for(int i=2;i<=100;i++)
  {
    c[i][i]=c[i][0]=1ll;
    for(int j=0;j<i;j++)
    {
      c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
    }
  }
}
int main()
{
	init();
	cin>>n;
	for(int i=0;i<10;i++) cin>>a[i];
	for(int i=0;i<=n;i++)
	{
		for(int j=9;j>=0;j--)
		{
			if(j==9)
			{
				if(i>=a[9]) d[i][j]=1;
			}
			else if(j==0)
			{
				for(int k=a[j];k<=i;k++)
				{
					d[i][j]+=d[i-k][j+1]*c[i-1][k];
					d[i][j]%=mod;
				}
			}
			else
			{
				for(int k=a[j];k<=i;k++)
				{
					d[i][j]+=d[i-k][j+1]*c[i][k];
					d[i][j]%=mod;
				}
			}
		}
	}
	long long ans=0ll;
	for(int i=1;i<=n;i++)
	{
		ans+=d[i][0];
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

http://codeforces.com/problemset/problem/106/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
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
#include<bits/stdc++.h>
using namespace std;  
#define N 1005  
vector<char>ans;  
struct node{  
    int x, y;  
    char c;  
    void put(){printf("(%d,%d) : %c\n", x, y, c);}  
}a[30];  
int step[4][2] = {-1,0, 1,0, 0,-1, 0,1};  
int work[100005][2];  
char s[N];  
int mp[N][N], n, m, k, top, h[N][N], l[N][N];  
bool okh(int H, int x, int y){return h[H][y]-h[H][x-1] == 0;}  
bool okl(int L, int x, int y){return l[L][y]-l[L][x-1] == 0;}  
bool ok(int x, int y, int i, int j){  
    if(x>i)swap(x,i); if(y>j)swap(y,j);  
    if(x==i)  
        return okh(x, y, j);  
    else  
        return okl(y, x, i);  
}  
bool inmap(int x, int y){return 1<=x&&x<=n&&1<=y&&y<=m;}  
bool judge(int x, int y){  
    for(int i = 0; i < k; i++) {  
        int ux = step[work[i][0]][0] * work[i][1] + x, uy = step[work[i][0]][1] *work[i][1] + y;  
        if(!inmap(ux,uy))return false;  
        if(!ok(x, y, ux, uy))return false;  
        x = ux; y = uy;  
    }  
    return true;  
}  
void solve(){  
    ans.clear();  
    for(int i = 0; i < top; i++)  
        if(judge(a[i].x, a[i].y))  
            ans.push_back(a[i].c);  
    if(ans.size()==0){  
        puts("no solution");  
        return ;  
    }  
    sort(ans.begin(), ans.end());  
    for(int i = 0; i < ans.size(); i++)printf("%c",ans[i]);  
    puts("");  
}  
void input(){  
    top = 0;  
    memset(mp, 0, sizeof mp);  
    memset(h, 0, sizeof h);  
    memset(l, 0, sizeof l);  
    for(int i = 1; i <= n; i++){  
        scanf("%s", s+1);  
        for(int j = 1; j <= m; j++)  
        {  
            if(s[j]=='#')  
            {  
                mp[i][j] = 1;  
                h[i][j] = 1;  
                l[j][i] = 1;  
            }  
            else if('A'<=s[j] && s[j]<='Z'){  
                    a[top].x = i; a[top].y = j; a[top].c = s[j];  
                    top++;  
            }  
        }  
    }  
    for(int i = 1; i <= n; i++)  
        for(int j = 1; j <= m; j++)  
            h[i][j] += h[i][j-1];  
    for(int i = 1; i <= m; i++)  
        for(int j = 1; j <= n; j++)  
            l[i][j] += l[i][j-1];  
    scanf("%d",&k);  
    for(int i = 0; i < k; i++){  
        scanf("%s %d", s, &work[i][1]);  
        if(s[0] == 'N') work[i][0] = 0;  
        else if(s[0]=='S') work[i][0] = 1;  
        else if(s[0]=='W') work[i][0] = 2;  
        else work[i][0] = 3;  
    }  
}  
int main(){  
    while(~scanf("%d %d",&n,&m)){  
        input();  
        solve();  
    }  
    return 0;  
}