CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » acm_life_from_zero » 2018-2019_acm-icpc_asia_xuzhou_regional_contest
2020-2021:teams:acm_life_from_zero:2018-2019_acm-icpc_asia_xuzhou_regional_contest

目录

比赛信息

比赛链接 2/13 rank 76th

比赛回顾

李元恺

30min前 看B（超长题面）看G

40min时 开始写G

1:30前 通过G

1:40前 看H、I、M，想出H，想I和M

2:30时 想出M（这里想复杂了，M无脑暴力即可）

2:52时 开始写H

3:30时 写完H

4:40前 调试H（这里被spj演了，spj不过滤行末空格）

反思

李元恺

这场比赛成绩较差，主要两个问题，一个是yxA没有调过，另一个是我写代码失误比较多，h浪费太多时间，最后没有时间写M。我的两个失误：开始写G时写着写着忘了恰选K个的条件，浪费了大概20min；H题没看见公告，瞎检查了很久，另外题目只限制了n，没有限制k，我对大小k的数组memest导致超时，wa了一次，如果有4题排名还能看qwq

题解

G

题意：一棵树，m条关键路径（可重可交），求有多少种选法选出k条关键路径使他们至少有一个公共点

题解：一个简单的想法是计每个点作为公共点的贡献来计算答案，不重不漏的一个简单办法是只在离根最近的公共点处记录贡献。这等价于k条路径种至少有一条路径的两端点lca为该点。于是分别计算每个点被多少条关键路径覆盖和每个点是多少条路径的lca再组合一下即可 

#include <bits/stdc++.h>
 
using namespace std;
int n,m,k;
struct Edge {
	int to,next;
}bus[606060];
int g[306060][21],fa[303030],st[303030],t[303030];
int z,dep[303030],lcacnt[303030];
long long jc[303030],njc[303030];
long long pow2[303030];
long long ans;
const int mod = 1000000007;
inline void AddE(int from,int to) {
	bus[++z].to = to;
	bus[z].next = st[from];
	st[from] = z;
}
 
 
inline long long Pow(long long di,int ci) {
	long long ret = 1;
	while (ci) {
		if (ci&1)
			ret = ret*di%mod;
		di = di*di%mod;
		ci >>= 1;
	}
	return ret;
}
 
inline long long ni(int x) {
	return Pow(x,mod-2);
}
 
inline long long C(int n,int m) {
	if (m > n) {
		return 0;
	}
	return jc[n]*njc[m]%mod*njc[n-m]%mod;
}
 
inline void dfs(int now) {
	for (int i = st[now];i;i = bus[i].next) {
		if (bus[i].to == fa[now])
			continue;
		g[bus[i].to][0] = fa[bus[i].to] = now;
		dep[bus[i].to] = dep[now]+1;
		dfs(bus[i].to);
	}
}
 
inline int lca(int A,int B) {
	if (dep[A] < dep[B])
		swap(A,B);
	int x = dep[A]-dep[B];
	for (int i = 0;i <= 20; i++) {
		if ((1<<i)&x)
			A = g[A][i];
	}
	if (A == B)
		return A;
	for (int i = 20;i >= 0; i--)
		if (g[A][i] != g[B][i]) {
			A = g[A][i];
			B = g[B][i];
		}
	return fa[A];
}
 
int calcans(int now) {
	for (int i = st[now];i;i = bus[i].next) {
		if (bus[i].to == fa[now]) {
			continue;
		}
		t[now] += calcans(bus[i].to);
	}
	ans += C(t[now],k) - C(t[now] - lcacnt[now],k);
	//cout << now << " " << t[now] << " " << lcacnt[now] << " " << ans << endl;
	return t[now];
}
 
inline void work() {
	ans = 0;
	z = 0;
	scanf("%d%d%d",&n,&m,&k);
	for (int i = 1;i <= n; i++) {
		dep[i] = lcacnt[i] = t[i] = fa[i] = st[i] = 0;
		for (int j = 0;j <= 20; j++)
			g[i][j] = 0;
	}
	int aa,bb;
	for (int i = 1;i < n; i++) {
		scanf("%d%d",&aa,&bb);
		AddE(aa,bb);
		AddE(bb,aa);
	}
	fa[0] = 0;
	g[0][0] = 0;
	fa[1] = g[1][0] = 0;
	dfs(1);
	for (int i = 1;i <= 20; i++)
		for (int j = 1;j <= n; j++)
			g[j][i] = g[g[j][i-1]][i-1];
	for (int i = 1;i <= m; i++) {
		scanf("%d%d",&aa,&bb);
		int gg = lca(aa,bb);
		lcacnt[gg]++;
		t[gg]--;
		t[fa[gg]]--;
		t[aa]++;
		t[bb]++;
	}
	calcans(1);
	ans %= mod;
	ans += mod;
	ans %= mod;
	printf("%I64d\n",ans);
}
int main() {
	pow2[0] = 1;
	njc[0] = jc[0] = 1;
	for (int i = 1;i <= 300000; i++) {
		pow2[i] = (pow2[i-1] << 1);
		jc[i] = i*jc[i-1]%mod;
		njc[i] = ni(jc[i]);
		if (pow2[i] >= mod) {
			pow2[i] -= mod;
		}
	}
	int T;
	scanf("%d",&T);
	while(T--) {
		work();
	}
	return 0;
}

H

题意：数轴上有n个线段（可重可交），可以用k种颜色对线段上色，求最大化被k种颜色都盖住的数轴长度和一个可行解

题解：STL题，容易贪心任意有交线段尽量染不同色即可，优先队列维护没有染的颜色，set维护一下颜色不确定的线段（当且仅当已经染了所有颜色后才会出现颜色不确定的线段） 

#include <bits/stdc++.h>

using namespace std;

int T;
priority_queue<int> colset;
set<int> blank;
int col[202020];
struct Pa {
	int l,r;
}p[202020];
struct KP {
	int pos,tag,type;
}kp[404040];

bool cmp(KP A,KP B) {
	return A.pos < B.pos;
}
inline void work() {
	int n,k,cnt = 0;
	scanf("%d%d",&n,&k);
	for (int i = 1;i <= n; i++) {
		col[i] = 0;
		scanf("%d%d",&p[i].l,&p[i].r);
		kp[++cnt].pos = p[i].l;
		kp[cnt].tag = i;
		kp[cnt].type = 1;
		kp[++cnt].pos = p[i].r;
		kp[cnt].tag = i;
		kp[cnt].type = 0;
	} 
	if (k > n) {
		printf("0\n");
		for (int i = 1;i < n;i++) {
			printf("1 ");
		}
		printf("1\n");
		return ;
	}
	while (colset.top() > k) {
		colset.pop();
	}
	while (colset.top() < k) {
		colset.push(colset.top()+1);
	}
	int ans = 0;
	sort(kp+1,kp+n+n+1,cmp);
	int last = 0;
	for (int i = 1;i <= n+n; i++) {
		int j = i+1;
		if (colset.empty()) {
			ans += kp[i].pos - last;
		}
		while (kp[j].pos == kp[i].pos && j <= n+n) {
			j++;
		}
		for (int x = i;x < j; x++) {
			if (!kp[x].type) {
				if (col[kp[x].tag]) {
					colset.push(col[kp[x].tag]);
				}
				else {
					blank.erase(kp[x].tag);
					col[kp[x].tag] = 1;
				}
			}
			else
				blank.insert(kp[x].tag);
		}
		while (!colset.empty() && !blank.empty()) {
			int tmp = colset.top();
			colset.pop();
			int tag = (*blank.lower_bound(0));
			col[tag] = tmp;
			blank.erase(tag);
		}
		last = kp[i].pos;
		i = j-1;
	}
	printf("%d\n",ans);
	for (int i = 1;i < n; i++) {
		printf("%d ",col[i]);
	}
	printf("%d\n",col[n]);
}
int main() {
	colset.push(1);
	scanf("%d",&T);
	while(T--) {
		work();
	}
	return 0;
}

补题

C

D

I

K

L - Rikka with Grid Graphs

题意：

一个大小不超过6*6的网格图（$n \times m$ 个点，不超过$2n \times m - n - m$条边），每条边都可以没有。定义定向操作是给网格图的每一条边定一个方向，问有多少种不同的定向方法使定向后图中不存在有向环

极限样例： 

  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+
  | | | | | |
  +-+-+-+-+-+

题解：

网上居然查不到题解。。。插头dp令人头秃，从早调到晚。

玄学题目，状态数为O(存的下)，时间为O(跑的过)，极限数据下cf上80%的提交会被卡掉

网格图、连通性两个关键词提示轮廓线dp，观察一下性质发现没法用括号表示法，暴力传递闭包记录状态，赌一手有效状态数不多（跑完后发现1W左右） 

#include <bits/stdc++.h>

using namespace std;
int T;
char h[20][200],l[20][200];

inline bool haveEdgeh(int i,int j) {
	return h[i][j*2] == '-';
}

inline bool haveEdgel(int i,int j) {
	return l[i][j*2-1] == '|';
}

int now,n,m;
map<long long,long long> f[2];
int uni[9][9],uni2[9][9];

inline void calc(int dir1,int dir2,int kp,long long val) {
	if (dir2) {
		if (dir2 == 1) {
			if (uni[kp+1][kp] || uni[kp+1][kp-1]) {
				return ;
			}
		}
		else {
			if (uni[kp][kp+1] || uni[kp-1][kp+1]) {
				return ;
			}
		}
	}
	for (int i = 0;i <= m; i++)
		for (int j = 0;j <= m; j++)
			uni2[i][j] = uni[i][j];
	for (int i = 0;i <= m; i++) {
		uni2[kp-1][i] = uni2[i][kp-1] = uni2[kp][i] = uni2[i][kp] = 0;
	}
	if (dir2 == 1) {
		int a[7],cnt = 0;
		for (int i = 0;i <= m; i++)
			if (i != kp && i != kp-1)
				if (uni[i][kp] || uni[i][kp-1]) {
					uni2[i][kp] = 1;
					a[cnt++] = i;
				}
		for (int i = 0;i <= m; i++)
			if (uni[kp+1][i] && i != kp && i != kp-1) {
				uni2[kp][i] = 1;
				for (int j = 0;j < cnt; j++)
					uni2[a[j]][kp+1] = 1,uni2[a[j]][i] = 1;
			}
	}
	else if (dir2 == -1) {
		int a[7],cnt = 0;
		for (int i = 0;i <= m; i++) {
			if (i != kp && i != kp-1)
			if (uni[kp][i] || uni[kp-1][i]) {
				uni2[kp][i] = 1;
				a[cnt++] = i;
			}
		}
		for (int i = 0;i <= m; i++)
			if (uni[i][kp+1] && i != kp && i != kp-1) {
				uni2[i][kp] = 1;
				for (int j = 0;j < cnt; j++)
					uni2[kp+1][a[j]] = 1,uni2[i][a[j]] = 1;
			}
	}
	if (dir1 == 1) {
		for (int i = 0;i <= m; i++)
			if (i != kp && i != kp-1)
			if (uni[i][kp] || uni[i][kp-1]) {
				uni2[i][kp-1] = 1;
			}
	}
	else if (dir1 == -1) {
		for (int i = 0;i <= m; i++) {
			if (i != kp && i != kp-1)
			if (uni[kp][i] || uni[kp-1][i]) {
				uni2[kp-1][i] = 1;
			}
		}
	}
	if (dir1 == 1 && dir2 == -1) {
		uni2[kp][kp-1] = 1;
		for (int i = 0;i <= m; i++) {
			if (i == kp || i == kp-1) {
				continue;
			}
			if (uni2[i][kp])
				uni2[i][kp-1] = 1;
		} 
	}
	if (dir2 == 1 && dir1 == -1) {
		uni2[kp-1][kp] = 1;
		for (int i = 0;i <= m; i++) {
			if (i == kp || i == kp-1) {
				continue;
			}
			if (uni2[kp][i])
				uni2[kp-1][i] = 1;
		} 
	}
	long long rstatus = 0;
	for (int i = m;i >= 0; i--) {
		for (int j = m;j >= 0; j--) {
			rstatus <<= 1;
			if (uni2[i][j]) {
				rstatus++;
			}
		}
	}
	f[now][rstatus] = f[now][rstatus] + val;
} 

inline void dp(int posi,int posj,long long status,long long val) {
//printf("%I64d ",status);
	for (int i = 0;i <= m; i++) {
		for (int j = 0;j <= m; j++) {
			if (status & 1) {
				uni[i][j] = 1;
			}
			else
				uni[i][j] = 0;
			status >>= 1;
		}
	}
	int len1,len2,set1[2],set2[2];
	if (haveEdgel(posi,posj)) {
		len1 = 2;
		set1[0] = -1;
		set1[1] = 1;
	}
	else {
		len1 = 1;
		set1[0] = 0;
	}
	if (haveEdgeh(posi,posj)) {
		len2 = 2;
		set2[0] = -1;
		set2[1] = 1;
	}
	else {
		len2 = 1;
		set2[0] = 0;
	}
	for (int i = 0;i < len1; i++)
		for (int j = 0;j < len2; j++) {
			calc(set1[i],set2[j],posj,val);
		}
}

inline long long reverse(long long status) {
	long long rstatus = 0;
	for (int i = 0;i <= m; i++) {
		for (int j = 0;j <= m; j++) {
			if (status & 1) {
				uni[i][j] = 1;
			}
			else
				uni[i][j] = 0;
			status >>= 1;
		}
	}
	for (int i = 1;i <= m; i++)
		for (int j = 1;j <= m; j++) {
			uni2[i][j] = uni[i-1][j-1];
		}
	for (int i = 0;i <= m; i++)
		uni2[i][0] = uni2[0][i] = 0;
	for (int i = m;i >= 0; i--) {
		for (int j = m;j >= 0; j--) {
			rstatus <<= 1;
			if (uni2[i][j]) {
				rstatus++;
			}
		}
	}
	return rstatus;
}

inline void work() {
	memset(h,0,sizeof(h));
	memset(l,0,sizeof(l));
	f[1].clear();
	f[0].clear();
	scanf("%d%d\n",&n,&m);
	for (int i = 1;i <= n; i++) {
		int cnt = 1;
		gets(h[i]+1);
		if (i < n) {	
			gets(l[i]+1);	
		}
	}
	now = 0;
	f[now][0] = 1;
	map<long long,long long>::iterator it;
	it = f[now].begin();
	for (int i = 1;i <= n; i++) {
		for (int j = 1;j <= m; j++) {
			now ^= 1;
			f[now].clear();
			for (it = f[now^1].begin();it != f[now^1].end(); ++it) {
				dp(i,j,it->first,it->second);
			}
		}
		now ^= 1;
		f[now].clear();
		for (it = f[now^1].begin();it != f[now^1].end(); ++it) {
			long long newstatus = reverse(it->first);
			f[now][newstatus] = /*f[now][newstatus] +*/ it->second;
		}
	}
	printf("%lld",f[now][0]);
}
int main() {
	scanf("%d",&T);
	while (T--) {
		work();
		if (T) {
			printf("\n");
		}
	}
	return 0;
}

M

2020-2021/teams/acm_life_from_zero/2018-2019_acm-icpc_asia_xuzhou_regional_contest.txt · 最后更改: 2020/05/27 21:49 由 lak

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3