头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2012 ICPC 杭州站

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
#include<iostream>
using namespace std;
int dat[256];
#pragma warning(disable:4996)
int main()
{
dat['A'] = 16;
dat['B'] = 7;
dat['C'] = 8;
dat['D'] = 1;
dat['E'] = 1;
dat['F'] = 2;
dat['G'] = 3;
int T;
int A, B;
cin >> T;
for (int tim = 1; tim <= T; tim++)
{
cin >> A;
int flagA = 0;
int flagA1 = 0;
int flagB = 0;
int flagB1 = 0;
int sum = 0;
char tmp;
for (int i = 0; i < A; i++)
{
cin >> tmp;
if (tmp == 'B')flagA = 1;
else if (tmp == 'C')flagA1 = 1;
sum += dat[tmp];
}
if ((!flagA||!flagA1)&&sum>1)sum--;
cin >> B;
int sumB = 0;
for (int i = 0; i < B; i++)
{
cin >> tmp;
sumB += dat[tmp];
if (tmp == 'B')flagB = 1;
else if (tmp == 'C')flagB1 = 1;
}
if ((!flagB1||!flagB)&&sumB>1)sumB--;
if (sum > sumB)puts("red");
else if (sum == sumB)puts("tie");
else puts("black");
}
return 0;
}

K:

$MST。$


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
#include<bits/stdc++.h>
using namespace std;
int f[60];
double ans=0;
int Find(int a)
{
return f[a]==a?a:f[a]=Find(f[a]);
}
int join(int a,int b)
{
f[Find(a)]=Find(b);
}

struct edge
{
int u,v;
double w;
} e[3000];

bool cmp(edge a,edge b)
{
return a.w<b.w;
}

void join(edge &e)
{
if(Find(e.u)!=Find(e.v))
{
f[Find(e.u)]=Find(e.v);
ans+=e.w;
}
}

struct Point
{
int x,y;
} point[60];
int n,a,b;

int main()
{
while(~scanf("%d",&n))
{
if(n==0) break;
for(int i=0; i<60; i++)
f[i]=i;
scanf("%d %d",&a,&b);
for(int i=1; i<=n; i++)
{
scanf("%d %d",&point[i].x,&point[i].y);
}

int cnt=0;

for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
{
e[++cnt].u=i;
e[cnt].v=j;
e[cnt].w=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
}
sort(e+1,e+cnt+1,cmp);
ans=0;
f[a]=b;
ans+=sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));
for(int i=1; i<=cnt; i++)
join(e[i]);
printf("%.2lf\n",ans);
}
}

H:

$对每个点跑一边堆优化的Dij。$


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
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int f[1005];
int Find(int a)
{
return f[a]==a?a:f[a]=Find(f[a]);
}

void join(int a,int b)
{
f[Find(a)]=Find(b);
}

struct dijkstra
{
static const int maxn=1005;
static const int maxm=20010;

struct edge
{
int v,w,nex;
} g[maxm];

int head[maxn],d[maxn];
bool done[maxn];
int n,cnt;

void ini(int newn)
{
n=newn;
cnt=0;
memset(head,-1,sizeof(head));
}

void add_edge(int u,int v,int w)
{
g[cnt].v=v;
g[cnt].w=w;
g[cnt].nex=head[u];
head[u]=cnt++;
}

struct HeapNode
{
int d,u;
bool operator < (const HeapNode& rhs)const
{
return d>rhs.d;
}
};

int short_path(int s)
{
int ret=s;
priority_queue<HeapNode>q;
//memset(d,0,sizeof(d));
fill(d,d+n+1,1e9);
d[s]=0;
memset(done,0,sizeof(done));
q.push(HeapNode{d[s],s});
while(!q.empty())
{
HeapNode x=q.top();
q.pop();
int u=x.u;
if(done[u])
continue;
done[u]=true;
for(int i=head[u]; ~i; i=g[i].nex)
{
if(d[g[i].v]>d[u]+g[i].w)
{
d[g[i].v]=d[u]+g[i].w;
if(d[g[i].v]>d[ret])
ret=g[i].v;
q.push(HeapNode{d[g[i].v],g[i].v});
}
}
}
return ret;
}
} g;




int main()
{
int n,m;
while(~scanf("%d",&n))
{
mp.clear();
srand(time(NULL));
if(n==0) break;
g.ini(n+1);
string c,d;
for(int i=1; i<=n; i++)
{
cin>>c;
mp[c]=i;
f[i]=i;
}
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
cin>>c>>d;
join(mp[c],mp[d]);
g.add_edge(mp[c],mp[d],1);
g.add_edge(mp[d],mp[c],1);
}
int cnt=0;
for(int i=1; i<=n; i++)
{
if(f[i]==i)
cnt++;
}
if(cnt>1) puts("-1");
else
{
int ans=-1;
for(int i=1; i<=n; i++)
{
int s=i;
//int s=(rand()%n)+1;
int t=g.short_path(s);
ans=max(ans,g.d[t]);
//s=g.short_path(t);
//ans=max(ans,g.d[s]);
}
printf("%d\n",ans);
}
}
}

C:

队友写的。


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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=1e6+5;
int w[maxn];//ok
int cntsuf[maxn];//ok
int len[maxn];//ok
int pre[maxn];//ok
ll dp[maxn];
bool vis[maxn];//ok

int main(){
int n;
while(scanf("%d",&n)){
if(n==0)break;

for(int i=0;i<maxn;i++){
pre[i]=-1;
}

for(int i=0;i<maxn;i++){
len[i]=0;
}
for(int i=0;i<n;i++){
scanf("%d",w+i);
len[i-pre[w[i]]-1]++;
pre[w[i]]=i;
}


memset(vis,0,sizeof(vis));
cntsuf[n]=0;
for(int i=n-1;i>=0;i--){
if(!vis[w[i]]){
cntsuf[i]=cntsuf[i+1]+1;
vis[w[i]]-=true;
}
else cntsuf[i]=cntsuf[i+1];
}

int sum=0;
for(int i=n-1;i>=1;i--){
sum=sum+len[i];
}

dp[1]=n;
for(int i=2;i<n;i++){
dp[i]=dp[i-1]-cntsuf[n-i+1]+sum;
sum-=len[i-1];
}

int q;
scanf("%d",&q);
while(q--){
int tmp;
scanf("%d",&tmp);
printf("%lld\n",dp[tmp]);
}

}
}

J:

观察数据大小,直接枚举子集然后验证。


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
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
vector<int>v;
int m[55][55],d[15];
int n,k,ans;

struct Node
{
int x,y;
}node[11];

bool check(int a,int b,int i)
{
if(a<1||a>n||b<1||b>n) return false;
int dis=abs(node[v[i]].x-a)+abs(node[v[i]].y-b);
if(dis>d[v[i]]) return false;
return true;
}

bool check()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!m[i][j])
{
return false;
}
}
}
return true;
}


void color()
{
for(int i=0;i<v.size();i++)
{
for(int a=1;a<=n;a++)
{
for(int b=1;b<=n;b++)
{
if(check(a,b,i)) m[a][b]=1;
}
}
}
}

void solve()
{
for(int i=0; i<(1<<k); i++)
{
v.clear();
memset(m,0,sizeof(m));
for(int j=1;j<=k;j++)
m[node[j].x][node[j].y]=1;
for(int j=0; j<k; j++)
{
if(i&(1<<j)) v.push_back(j+1);
}
color();
if(check()) ans=min(ans,(int)v.size());
}
}

int main()
{
while(~scanf("%d",&n))
{
if(!n) break;
memset(m,0,sizeof(m));
memset(d,0,sizeof(d));
scanf("%d",&k);
for(int i=1; i<=k; i++)
{
int x,y;
scanf("%d %d",&x,&y);
m[x][y]=1;
node[i].x=x, node[i].y=y;
}
for(int i=1; i<=k; i++)
scanf("%d",&d[i]);
ans=inf;
solve();
if(ans==inf) puts("-1");
else printf("%d\n",ans);
}
}

未完待续。。。

avatar Decaku 很菜但也很想carry