Reku
0%

Codeforces Round #403 (Div. 2, based on Technocup 2017 Finals)

Posted on Edited on In Views: Valine:

A. Andryusha and Socks 略 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010];
int p[100010];
int fans;
int ans;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=2*n;i++)
	{
		if(p[a[i]]==1) p[a[i]]=0,ans--;
		else p[a[i]]=1,ans++;
		fans=max(ans,fans);
	}
	cout<<fans<<endl;
	return 0;
}

B. The Meeting Place Cannot Be Changed 虽然是个无脑三分，但是出现在div 2B还是挺神奇的

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
#include<bits/stdc++.h>
using namespace std;
int n;
int x[60010];
int v[60010];
const double eps=1e-12;
double ff(double t)
{
	double ans=0.0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,fabs(t-x[i])*1.0/v[i]);
	}
	return ans;
}
double three_devide(double low,double up)  
{  
    double m1,m2;
	int tot=0;  
    while(tot<=100)  
    {
    	tot++;
        m1=low+(up-low)/3.0;  
        m2=up-(up-low)/3.0;  
        if(ff(m1)>=ff(m2)+eps)  
            low=m1;  
        else  
            up=m2;  
    }  
    return (m1+m2)/2;  
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&x[i]);
	for(int i=1;i<=n;i++) scanf("%d",&v[i]);
	printf("%.10lf\n",ff(three_devide(1.0,1e9)));
	return 0;
}

C. Andryusha and Colored Balloons 题意有点忘了...大致是找个度最大的点，然后无脑广搜吧？

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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n;
vector<int> e[200010];
int du[200010];
int v[200010];
int y[200010];
int ans=0;
vector<int> w;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].pb(b);
		e[b].pb(a);
		du[a]++;
		du[b]++;
	}
	int x=1;
	for(int i=1;i<=n;i++)
	{
		if(du[i]>du[x]) x=i;
	}
	queue<int> q;
	q.push(x); v[x]=1;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		int tt=1;
		y[v[t]]=1;
		w.pb(v[t]);
		for(auto &i:e[t])
		{
			if(v[i]!=0) y[v[i]]=1;
		}
		for(auto &i:e[t])
		{
			if(v[i]==0)
			{
				while(y[tt]==1) tt++;
				v[i]=tt;
				y[v[i]]=1;
				q.push(i);
			}
			w.pb(v[i]);
		}
		for(auto &i:w) y[i]=0;
		w.clear();
	}
	printf("%d\n",du[x]+1);
	for(int i=1;i<=n;i++) printf("%d ",v[i]);
	return 0;
}

D. Innokenty and a Football League 稍作处理一下，就是一个二分图匹配。 当然听说2-SAT也能做。 通过这个题目，终于搞清了二分图模板的用法

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
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int MAXN = 50005;
const int MAXM = 200005;

int n, m;
int match1[MAXN], match2[MAXN];
int Q[MAXN], D1[MAXN], D2[MAXN];
vector <int> E[MAXN];

inline bool bfs() {
    int s = 0, t = 0, u, v;
    memset(D1, -1, sizeof(D1));
    memset(D2, -1, sizeof(D2));
    for (int i = 0; i < n; i++)
        if (match1[i] == -1)
            Q[t++] = i, D1[i] = 0;
    while (s != t)
        if ((u = Q[s++]) != n)
            for (int i = 0; i < (int)E[u].size(); i++)
                if (D2[v = E[u][i]] == -1) {
                    D2[v] = D1[u] + 1;
                    if (D1[match2[v]] == -1)
                        D1[Q[t++] = match2[v]] = D2[v] + 1;
                }
    return D1[n] != -1;
}

bool dfs(int u) {
    for (int i = 0, v; i < (int)E[u].size(); i++)
        if (D2[v = E[u][i]] == D1[u] + 1 && (D2[v] = -1) && (match2[v] == n || dfs(match2[v]))) {
            match1[u] = v;
            match2[v] = u;
            D1[u] = -1;
            return true;
        }
    D1[u] = -1;
    return false;
}

inline int hopcroft_karp() {
    memset(match1, -1, sizeof(match1));
    for (int i = 0; i < n; i++)
        match2[i] = n;
    int ret = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0, u; j < E[i].size(); j++)
            if (match2[u = E[i][j]] == n) {
                match1[i] = u;
                match2[u] = i;
                ret++;
                break;
            }
    while (bfs())
        for (int i = 0; i < n; i++)
            if (match1[i] == -1 && dfs(i))
                ret++;
    return ret;
}
string s1,s2,t;
unordered_map<string,int> ha;
unordered_map<int,string> ha2;
int sz;
int a1[1010];
int a2[1010];
struct pp{
	int a,num;
} qq[1010];
bool cmp(pp &x,pp &y)
{
	return x.a<y.a;
}
int main()
{
	scanf("%d",&n);
	sz=n-1;
	for(int i=0;i<n;i++)
	{
		cin>>s1>>s2;
		t=""; t+=s1[0]; t+=s1[1]; t+=s1[2];
		if(ha.find(t)==ha.end()) ha[t]=++sz,ha2[sz]=t;
		a1[i]=ha[t];
		t=""; t+=s1[0]; t+=s1[1]; t+=s2[0];
		if(ha.find(t)==ha.end()) ha[t]=++sz,ha2[sz]=t;
		a2[i]=ha[t];
		qq[i].a=a1[i];
		qq[i].num=i;
	}
	sort(qq,qq+n,cmp);
	for(int i=0;i<n;i++)
	{
		bool bj=0;
		if(i!=0&&qq[i].a==qq[i-1].a) bj=1;
		if(i!=n-1&&qq[i].a==qq[i+1].a) bj=1;
		int tt=qq[i].num;
		E[tt].pb(a2[tt]);
		E[a2[tt]].pb(tt);
		m+=2;
		if(bj==0) E[tt].pb(a1[tt]),E[a1[tt]].pb(tt),m+=2;
	}
	int pp=n;
	n=sz+1;
	int u=hopcroft_karp();
	u/=2;
	if(u==pp) puts("YES");
	else {puts("NO");return 0;}
	for(int i=0;i<pp;i++) cout<<ha2[match1[i]]<<endl;
	return 0;
}

E. Underground Lab 搞一个生成树，然后生成一下欧拉路径，然后直接把欧拉路径分块即可。 感觉非常的强。

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;
#define pb push_back
int n,m;
int k;
vector<int> e[200010];
int fa[200010];
int c[200010];
int ff(int x)
{
	if(x==fa[x]) return x;
	fa[x]=ff(fa[x]);
	return fa[x];
}
vector<int> ans;
void dfs(int x,int f)
{
	ans.pb(x);
	for(auto &i:e[x])
	{
		if(i!=f)
		{
			dfs(i,x);
			ans.pb(x);
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(ff(x)==ff(y)) continue;
		e[x].pb(y);
		e[y].pb(x);
		fa[ff(x)]=ff(y);
	}
	dfs(1,-1);
	for(int i=1;i<=k;i++) c[i]=ans.size()/k;
	for(int i=1;i<=ans.size()%k;i++)
	{
		c[i]++;
	}
	int u=0;
	for(int i=1;i<=k;i++)
	{
		printf("%d ",c[i]);
		for(int j=u;j<=u+c[i]-1;j++)
		{
			printf("%d ",ans[j]);
		}
		printf("\n");
		u=u+c[i];
	}
	return 0;
}

F. Axel and Marston in Bitland 用\(dp[i][j][k][z]\)来代表从\(k\)到\(z\)有一条长度为\(2^i\)的以\(j\)开头的边(\(j\)为\(0\)或者\(1\))。 因为这个路径长度，一定为\(2^i\)，并且如果起始边确定，那整个路径就确定了。 然后做dp就可以了。 最后一维可以用bitset优化掉。

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;
int n,m;
bitset<510> dp[62][2][510];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int v,u,t;
		scanf("%d%d%d",&v,&u,&t);
		dp[0][t][v][u]=1;
	}
	for(int i=1;i<=60;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				for(int w=0;w<=1;w++)
				{
					if(dp[i-1][w][j][k]==1)
					{
						dp[i][w][j]|=dp[i-1][!w][k];
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dp[60][0][1][i]==1)
		{
			printf("-1\n");
			return 0;
		}
	}
	long long ans=0;
	int t=0;
	bitset<510> w;
	w.reset();
	w[1]=1;
	for(int i=59;i>=0;i--)
	{
		bitset<510> mid;
		mid.reset();
		for(int j=1;j<=n;j++) if(w[j]==1) mid|=dp[i][t][j];
		if(mid.count())
		{
			w=mid;
			ans+=(1LL<<i);
			t=!t;
		}
	}
	if(ans>1e18)
	{
		printf("-1\n");
		return 0;
	}
	printf("%lld\n",ans);
	return 0;
}