首页 > 其他分享 >NEERC2013题解

NEERC2013题解

时间：2024-09-23 23:13:50浏览次数：11  
标签：int 题解 s1 ans lst NEERC2013 s2 dp

B. Bonus Cards

简单dp一下，记 \(f_{ij}\) 为前i次有j次分给第一类的概率。最后再算上我在第一类被选上的概率即可。

const int N = 3005;
#define int long long
int n, a, b; double f[N][N], g[N][N];

signed main(void) {
#ifdef ONLINE_JUDGE
 	freopen("bonus.in","r",stdin);
 	freopen("bonus.out","w",stdout);
#endif
	read(n), read(a), read(b); f[0][0] = 1.0; a++;
	if (n > a + b) {
		printf("1\n1\n");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		f[i][0] = f[i - 1][0] * (double) (b - i + 1) / (double) (2 * a + b - i + 1);
		for (int j = 1; j <= i; j++) {
			int A = 2 * (a - (j - 1)), B = b - (i - j);
			if (j <= a && i - j <= b) f[i][j] = f[i - 1][j - 1] * (double) A / (double) (A + B);
			A = 2 * (a - j), B = b - (i - j) + 1;
			if (i - 1 >= j && j <= a && i - j <= b) f[i][j] += f[i - 1][j] * (double) B / (double) (A + B);
		}
	}
	
//	printf("%Lf\n%Lf\n%Lf\n", f[2][0], f[2][1], f[2][2]);
	
	b++; a--; g[0][0] = 1.0;
	for (int i = 1; i <= n; i++) {
		g[i][0] = g[i - 1][0] * (double) (b - i + 1) / (double) (2 * a + b - i + 1);
		for (int j = 1; j <= i; j++) {
			int A = 2 * (a - (j - 1)), B = b - (i - j);
			if (j <= a && i - j <= b) g[i][j] = g[i - 1][j - 1] * (double) A / (double) (A + B);
			A = 2 * (a - j), B = b - (i - j) + 1;
			if (i - 1 >= j && j <= a && i - j <= b) g[i][j] += g[i - 1][j] * (double) B / (double) (A + B);
		}
	}
	
	a++;
	double reta = 0, retb = 0, tmp = 0;
	for (int i = 0; i <= n; i++) {
		tmp += f[n][i];
		if (i && i <= a) reta += f[n][i] * (double) i / (double) a;
		if (n - i && n - i <= b) retb += g[n][i] * (double) (n - i) / (double) b;
	}
	
//	printf("%Lf\n", tmp);
	printf("%.16lf\n%.16lf\n", reta, retb);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

D. Dictionary

我们考虑每个串接在另一个串上时可以省去的边数，那么这可以转化成无确定根的最小树形图问题。

const int N = 50 + 5, M = 3000 + 5;

struct Edge {
	int u, v, w;
} E[M];
std::vector <int> T, e_rep[M];
bool e_chs[M];
int n, m, W[N][N];
std::string s[N];

int CheckSubstr(std::string t, std::string str) {
	if(t.empty()) return 0;
	int t_len = t.size(), str_len = str.size();
	for(int i = 0; i + t_len <= str_len; ++i)
		if(str.substr(i, t_len) == t) return i;
	return -1;
}

int idx[N], n_idx[N], in_id[N], pre[N], vis[N];
int Choose(int i) {
	T.push_back(i);
	return E[i].w;
}
int DMST(int r) {
	int res = 0, cur_n = n + 1;
	for(int i = 1; i <= cur_n; ++i) idx[i] = i;
	while(true) {
		int v_cnt = 0;
		for(int i = 1; i <= cur_n; ++i)
			pre[i] = vis[i] = n_idx[i] = 0;
		for(int i = 1; i <= m; ++i) {
			int u = idx[E[i].u], v = idx[E[i].v], w = E[i].w;
			if(v != idx[r] && u != v && (!pre[v] || w < E[in_id[v]].w))
				in_id[v] = i, pre[v] = u;
		}
		for(int i = 1; i <= cur_n; ++i) {
			int u = i;
			for(; u && !vis[u]; u = pre[u]) vis[u] = i;
			if(u != idx[r] && vis[u] == i) {
				n_idx[u] = ++v_cnt;
				res += Choose(in_id[u]);
				for(int v = pre[u]; v != u; v = pre[v]) {
					n_idx[v] = v_cnt;
					res += Choose(in_id[v]);
				}
			}
		}
		for(int i = 1; i <= m; ++i) {
			int u = idx[E[i].u], v = idx[E[i].v];
			if(n_idx[u] != n_idx[v] && n_idx[v]) {
				E[i].w -= E[in_id[v]].w;
				e_rep[in_id[v]].push_back(i);
			}
		}
		for(int i = 1; i <= cur_n; ++i)
			if(!n_idx[i]) n_idx[i] = ++v_cnt;
		for(int i = 1; i <= n + 1; ++i) idx[i] = n_idx[idx[i]];
		if(v_cnt == cur_n) {
			for(int i = 1; i <= cur_n; ++i)
				if(i != idx[r]) res += Choose(in_id[i]);
			break;
		}
		cur_n = v_cnt;
	}
	std::reverse(T.begin(), T.end());
	for(int i : T) {
		e_chs[i] = true;
		for(int j : e_rep[i])
			if(e_chs[j]) {
				e_chs[i] = false;
				break;
			}
	}
	return res;
}

int tr_cnt;
std::vector <int> nxt[N], pos_id[N];
void Dfs(int u, int p) {
	if(p) {
		int su_siz = s[u].size(), k = su_siz - W[p][u],
			x = CheckSubstr(s[u].substr(0, k), s[p]);
		for(int i = 0; i <= k; ++i)
			pos_id[u].push_back(pos_id[p][x + i]);
		for(int i = k + 1, j = pos_id[p][x + k]; i <= su_siz; ++i) {
			printf("%d %c\n", j, s[u][i - 1]);
			pos_id[u].push_back(j = ++tr_cnt);
		}
	} else {
		pos_id[u].push_back(++tr_cnt);
		printf("0\n");
	}
	for(int v : nxt[u]) {
		Dfs(v, u);
	}
}
void Construct() {
	for(int i : T) {
		if(!e_chs[i]) continue;
		int u = E[i].u, v = E[i].v;
		nxt[u].push_back(v);
	}
	Dfs(n + 1, 0);
}

signed main(void) {
#ifdef ONLINE_JUDGE
    freopen("dictionary.in","r",stdin);
    freopen("dictionary.out","w",stdout);
#endif
    std::cin >> n;
    for(int i = 1; i <= n; ++i)
        std::cin >> s[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) {
            int k = 0, sj_siz = s[j].size();
            for(; k + 1 <= sj_siz && ~CheckSubstr(s[j].substr(0, k + 1), s[i]); ++k);
            k = sj_siz - k;
            W[i][j] = k;
            E[++m] = (Edge) { i, j, k };
        }
    for(int i = 1; i <= n; ++i) {
        int si_siz = s[i].size();
        E[++m] = (Edge) { n + 1, i, si_siz };
        W[n + 1][i] = si_siz;
    }
    printf("%d\n", DMST(n + 1) + 1);
    Construct();
	return 0;
}

F. Fraud Busters

签到模拟题

signed main(void) {
#ifdef ONLINE_JUDGE
	freopen("fraud.in","r",stdin);
	freopen("fraud.out","w",stdout);
#endif
	readstr(t + 1);
	int n; read(n);
	for (int i = 1; i <= n; i++) {
		readstr(s[i] + 1); bool f = true;
		for (int j = 1; j <= 9; j++)
			if (t[j] != '*' && t[j] != s[i][j]) f = false;
		if (f) ans.push_back(i);
	}
	
	writeln(ans.size());
	for (auto u : ans) puts(s[u] + 1);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

H. Hack Protection

对每个左端点，考虑每个右端点对应的与是什么，这只有 \(O(\log(a_i))\) 段。

在每一段内询问某种数出现了多少次即可。

const int N = 100005;
int v[N],lv; vector<int>G[N];
int n, a[N], st[N][17], Log[N];
inline int And(int l, int r) { static int t; t = Log[r-l+1]; return st[l][t] & st[r - (1 << t) + 1][t]; }
inline int query(int l, int r, int x){
	int p = lower_bound(v+1,v+lv+1,x)-v; if (v[p] ^ x) return 0;
	return upper_bound(G[p].begin(),G[p].end(),r) - lower_bound(G[p].begin(),G[p].end(),l);
}
 
int L[34],R[34],V[34],cntl;
 
inline void make(void) {
	static int l[34], r[34], v[34], len; len = cntl;
	memcpy(l, L, cntl + 1 << 2), memcpy(r, R, cntl + 1 << 2), memcpy(v, V, cntl + 1 << 2);
	int nl = l[1], nr = r[1], nv = v[1]; cntl = 0;
	for (int i = 2; i <= len; i++) {
		if (v[i] == nv) { nl = l[i]; continue; }
		++cntl; L[cntl] = nl, R[cntl] = nr, V[cntl] = nv;
		nl = l[i], nr = r[i], nv = v[i];
	}
	if (nl != -1) { ++cntl; L[cntl] = nl, R[cntl] = nr, V[cntl] = nv; }
}
 
signed main(void) {
#ifdef ONLINE_JUDGE
    freopen("hack.in","r",stdin);
    freopen("hack.out","w",stdout);
#endif
	ll ans = 0; read(n);
	for (int i = 1; i <= n; i++) {
		read(a[i]), st[i][0] = a[i], a[i] ^= a[i - 1], v[++lv] = a[i];
		Log[i] = Log[i - 1];
		if (1 << Log[i] + 1 < i) ++Log[i];
	}
	
	for (int j = 1; j <= Log[n]; ++j)
	for (int i = 1; i + (1 << j) - 1 <= n; i++) st[i][j] = st[i][j - 1] & st[i + (1 << j - 1)][j - 1];
	sort(v + 1, v + n + 1), lv = unique(v + 1, v + n + 1) - (v + 1);
	for (int i = 1; i <= n; i++) G[lower_bound(v + 1, v + lv + 1, a[i]) - v].push_back(i);
	for (int i = n; i >= 1; i--) {
		++cntl; L[cntl] = R[cntl] = i,V[cntl] = st[i][0];
		for (int j = 1; j < cntl; j++) V[j] &= st[i][0];
		make();
		for (int j = 1; j <= cntl; j++) ans += query(L[j],R[j],a[i-1]^V[j]); 
	}
	
	writeln(ans);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

J. Join the Conversation

读入略麻烦的LIS。

const int N = 5e4 + 5;
string s[N]; int n, dp[N], ans, las[N];
unordered_map <string, int> lst;
vector <int> ret;

signed main(void) {
//#ifdef ONLINE_JUDGE
//	freopen("join.in","r",stdin);
//	freopen("join.out","w",stdout);
//#endif
//	ios :: sync_with_stdio(false);
//	cin.tie(0); cout.tie(0);
	cin >> n; int ed; getline(cin, s[0]);
	for (int i = 1; i <= n; i++) {
		dp[i] = 1; int k = 1;
		getline(cin, s[i]);
//		cout << s[i] << '\n';
		string s1, s2; s1 = s2 = ""; bool f = 0;
		for (int j = 0; j < s[i].size(); j++)
			if (s[i][j] == ':') break; else s1 += s[i][j], ++k;
		if (lst.find(s1) == lst.end()) lst[s1] = i;
		for (int j = k; j < s[i].size(); j++) {
			if (s[i][j] == ' ') {
				if (s2 != "" && s2[0] == '@' && lst.find(s2) != lst.end() && s1 != s2)
				if (dp[lst[s2]] + 1 > dp[lst[s1]]) {
					lst[s1] = i; las[i] = lst[s2];
					dp[lst[s1]] = dp[lst[s2]] + 1;
				}
				s2 = "";
			} else s2 += s[i][j];
		}
		if (s2 != "" && s2[0] == '@' && lst.find(s2) != lst.end() && s1 != s2)
			if (dp[lst[s2]] + 1 > dp[lst[s1]]) {
				lst[s1] = i; las[i] = lst[s2];
				dp[lst[s1]] = dp[lst[s2]] + 1;
			}
		s2 = "";
//		cout << s1 << "::" << s2 << '\n';
		if (dp[i] > ans) ans = dp[i], ed = i;
//		cout << dp[i] << '\n';
	}
	
	while (ed) {
		ret.push_back(ed);
		ed = las[ed];
	}
	reverse(ret.begin(), ret.end());
	cout << ret.size() << '\n';
	for (auto u : ret) cout << u << ' ';
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

K

因为lbw用线段树写炸了，所以我才用。

const int N = 1e6 + 5;
int n, p, c, h, b[N], l[N], h1[N], h2[N], sum;
vector <int> ans;
 
struct SegmentTree {
	int t[N << 2 | 1];
	SegmentTree(void) { Ms(t, 0); }
	inline void pushup(int pos) { t[pos] = max(t[pos << 1], t[pos << 1 | 1]); }
	inline void build(int pos, int l, int r) {
		if (l == r) { if (l == h) t[pos] = 0; else t[pos] = h1[l] + h2[l]; return; }
		int mid = l + r >> 1; build(pos << 1, l, mid); build(pos << 1 | 1, mid + 1, r);
		pushup(pos);
	}
	
	inline void update(int pos, int l, int r, int x, int v) {
		if (l == r) { t[pos] += v; return; }
		int mid = l + r >> 1;
		if (x <= mid) update(pos << 1, l, mid, x, v);
		else update(pos << 1 | 1, mid + 1, r, x, v);
		pushup(pos);
	}
	
	inline int query(void) { return t[1]; }
} T;
 
signed main(void) {
    freopen("kabaleo.in","r",stdin);
    freopen("kabaleo.out","w",stdout);
	read(n), read(p), read(c), read(h);
	for (int i = 1; i <= n; i++) read(b[i]), h1[b[i]]++;
	for (int i = 1; i <= p; i++) {
		read(l[i]), h2[l[i]]++;
		if (l[i] != h) ++sum;
	}
	
	T.build(1, 1, c);
	for (int i = 1; i <= n; i++) {
		T.update(1, 1, c, b[i], -1); h1[b[i]]--; h1[h]++;
		int N = h1[h], M = 0;
		if (n == 1 && l[p] == h) { ans.push_back(i); goto F; }
		M = T.query();
		if (N - sum > M) ans.push_back(i);
		F : ;
		T.update(1, 1, c, b[i], 1); h1[b[i]]++; h1[h]--;
	}
	
	writeln(ans.size());
	for (auto u : ans) writeln(u, ' ');
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

标签：int,题解,s1,ans,lst,NEERC2013,s2,dp
From： https://www.cnblogs.com/EternalEpic/p/18428155

相关文章

  • 题解：CF888G Xor-MST
    题解：CF888GXor-MST题目大意：给定\(n\)个点的点权,任意两点间边权是点权的异或和。求这张完全图的MST的权值。思路：Boruvka+Trie树+按位贪心。关键就在于如何求出Boruvka中的best数组。考虑对点权建trie树，对于节点\(i\)本轮的连边，就是找“和它最相似”的那......
  • SP1825 FTOUR2 - Free tour II 题解
    题目传送门前置知识点分治|树状数组解法维护点对信息，考虑点分治。本题比luoguP4149[IOI2011]Race多了个前缀查询\(\max\)。套个支持单点修改、区间查询\(\max\)的数据结构即可。直接线段树维护区间\(\max\)貌似会TLE，换成树状数组维护前缀\(\max\)即可。注......
  • LGP3183 题解
    原题链接：P3183[HAOI2016]食物链。难度：Easy。根据定义，食物链是一个DAG，所以可以进行拓扑排序。食物链也就转化成了：图中从一个入度为\(0\)的点到一个出度为\(0\)的点的路径。那么只需要拓扑排序求出所有起点到每个点的路径条数，然后累加出度为\(0\)的点的值即可。需要注......
  • LGP1901 题解
    原题链接：P1901发射站难度：Easy。注意到"最近的且比它高"，容易想到用单调栈维护每个能量发射站左右第一个比它高的，最后统计答案即可。具体的令f[i][0/1]表示能量发射站\(i\)右边/左边第一个\(h_x>h_i\)的位置\(x\)。用单调栈从左向右扫一遍，得到f[i][0]。用单调栈从右......
  • [题解] ICPC网络预选赛 2024 第二场 E Escape （含题目翻译）
    [题解]ICPC网络预选赛2024第二场EEscape（含题目翻译）tag:图论、BFS、最短路题干为原文DeepL翻译题目描述Sneaker在一个巨大的迷宫中醒来，现在他想逃离这个迷宫。通过迷宫中每个房间的地图，Sneaker了解了迷宫的结构。迷宫由......
  • 【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计
    【题解】SolutionSet-NOIP2024集训Day36dp优化+状态设计https://www.becoder.com.cn/contest/5550最后一题较难。「NOIP2023」天天爱打卡考虑dp。\(f_{i,j}\)：前\(i\)天，到第\(i\)天为止连续打卡\(j\)天。有转移：\[f_{i,0}=\max(f_{i,j})\\f_{i,j}=\max(f_{i......
  • Codeforces Round 972（Div.2）题解
    CodeforcesRound972（Div.2）题解A.SimplePalindrome贪心贪心，尽可能元素数量平均，并且相同字母放在一起。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#de......
  • Codeforces Round 973 (Div.2) A-E题解
    CodeforcesRound973(Div.2)A-E题解比赛传送门A.Zhan'sBlender数学显然答案为\(\lceil\frac{n}{min(x,y)}\rceil\)。#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.en......
  • 题解：AT_abc372_e [ABC372E] K-th Largest Connected Components
    题意给出\(q\)个操作。将\(u\)和\(v\)连边。问\(u\)所在的连通块中编号第\(k\)大的点。思路连通块很容易想到并查集，求第\(k\)大可以用平衡树（虽然赛时没看到\(k\le10\)），合并时将信息从将小的连通块合并到大的连通块，这样可以减少时间复杂度。什么？你不会写平衡......
  • 题解：AT_arc184_a [ARC184A] Appraiser
    题意\(1000\)个硬币中有\(10\)个假币，你每次可以询问两个位置的硬币类型是否相同，你需要用不超过\(950\)次询问找出所有假币的位置。思路将前\(990\)个硬币每\(11\)个分一组，共\(90\)组，余\(10\)个单独分一组。询问每组第\(1\)个硬币和这组后面硬币的关系。因为只......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99