注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

Codeforces Round #265 (Div. 1)  

2014-09-08 16:19:10|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
464A. No to Palindromes!
定义一个字符串为“好的”,当且仅当它不含有长度大于1的回文子串。(字符集为前p个小写英文字母)
现在给出一个长度为n的“好的”字符串,求比它字典序大的下一个长度为n的“好的”字符串,或输出不存在。
1≤n≤1000,1≤p≤26。
Solution
首先如果思路是"while(next()) if(good()) output();"显然会被"1000 3 abcabcabcabc...."卡掉。(我cha了2个人)
一个字符串为“好的”,当且仅当它不含有长度为2或3的回文子串,即对于任意的i,满足s[i]≠s[i-1]且s[i]≠s[i-2]。
从后向前枚举新串与原串第一个不同的位置,再枚举这个位置的新的字符,用上面的策略贪心确定后面的字符或确定无解。
char s[1086], t[1086];
int main(){
	int n, p; read(n); read(p);
	int m; scanf("%s", s); m = strlen(s);
	g(i, 0, m) s[i] -= 'a';
	h(i, m - 1, 0) g(c, s[i] + 1, p){
		memcpy(t, s, sizeof(s));
		t[i] = c;
		if(i >= 1 && t[i] == t[i - 1]) continue;
		if(i >= 2 && t[i] == t[i - 2]) continue;
		bool bad = false;
		g(j, i + 1, m){
			t[j] = 128;
			g(d, 0, p) if(!((j >= 1 && d == t[j - 1]) || (j >= 2 && d == t[j - 2]))){
				t[j] = d; break;
			}
			if(t[j] == 128){
				bad = true; break;
			}
		}
		if(bad) continue;
		g(i, 0, m) printf("%c", 'a' + t[i]);
		printf("\n"); return 0;
	}
	printf("NO\n");
	return 0;
}
464B. Restore Cube
有一个正方体(边长大于0)放在空间直角坐标系当中(顶点的坐标都是整数),它可以用8×3的矩阵表示,其中第i行第j列的格子表示第i个顶点的第j维坐标。现在每一行的3个数都有可能被打乱(不会跨行打乱),要求还原出一个合法的解或输出无解。
Solution
6^8枚举每个点处的置换,然后判断是否是正方体。
判断正方体可以算出8个点两两间共28个距离,排序后一定是前12个距离相等,中间12个相等且都是前12个的sqrt2倍,最后4个相等且都是前12个的sqrt3倍。
加剪枝就能过了。
(或,把6^8枚举改成6^7枚举,因为只要存在合法方案,对于任意的点,总能找到方案使得这个点在这个方案里的置换是恒等置换)
int sx[8], sy[8], sz[8];
LL x[8], y[8], z[8];
LL dist[28];
#define sqr(x) (x) * (x)
struct fin{};
inline void dfs(int n){
	if(n == 8){
		int tot = 0;
		g(i, 0, 8) g(j, i + 1, 8) dist[tot++] = sqr(x[i] - x[j]) + sqr(y[i] - y[j]) + sqr(z[i] - z[j]);
		std::sort(dist, dist + tot);
		if(dist[0] == 0) return;
		g(i, 1, 12) if(dist[i] != dist[0]) return;
		LL tmp = dist[0] * 2LL;
		g(i, 12, 24) if(dist[i] != tmp) return;
		tmp += dist[0];
		g(i, 24, 28) if(dist[i] != tmp) return;
		printf("YES\n");
		g(i, 0, 8) printf("%I64d %I64d %I64d\n", x[i], y[i], z[i]);
		throw(fin());
	}else{
		int tot = 0;
		g(i, 0, n) g(j, i + 1, n) dist[tot++] = sqr(x[i] - x[j]) + sqr(y[i] - y[j]) + sqr(z[i] - z[j]);
		std::sort(dist, dist + tot);
		LL tmp = dist[0] * 2LL, tmp2 = dist[0] * 3LL;
		g(i, 1, tot) if(dist[i] != dist[0] && dist[i] != tmp && dist[i] != tmp2) return;
		x[n] = sx[n]; y[n] = sy[n]; z[n] = sz[n];
		dfs(n + 1);
		x[n] = sx[n]; y[n] = sz[n]; z[n] = sy[n];
		dfs(n + 1);
		x[n] = sy[n]; y[n] = sx[n]; z[n] = sz[n];
		dfs(n + 1);
		x[n] = sy[n]; y[n] = sz[n]; z[n] = sx[n];
		dfs(n + 1);
		x[n] = sz[n]; y[n] = sx[n]; z[n] = sy[n];
		dfs(n + 1);
		x[n] = sz[n]; y[n] = sy[n]; z[n] = sx[n];
		dfs(n + 1);
	}
}
int main(){
	g(i, 0, 8) scanf("%d%d%d", &sx[i], &sy[i], &sz[i]);
	try{
		dfs(0);
		printf("NO\n");
	}catch(fin){
	}
	// printf("%d\n", clock());
	return 0;
}
464C. Substitutes in Number
给出一个数字串s和n次操作,每次操作形如d->t,其中d是一个数字,t是一个数字串(可以为空),意义是把s中的每个d都替换成t。问n次操作以后,把s看成十进制数后对1e9+7取模的值。
Solution
对于一个数字串,我们实际上只关心它对1e9+7取模的值。
如果只维护这个,我们将无法连接两个数字串,所以还要维护它的长度。(更好地是维护10的长度次幂,因为如果维护长度就要对1e9+6而非1e9+7取模)
考虑倒着处理每次操作,我们开10个数字串变量x[0]到x[9],x[i]表示当前的i实际上表示的是什么数字串。对于每次操作,我们只需要进行赋值:x[d]=sigma_{i是t中的字符}x[i],其中sigma的加法表示数字串的连接。这样就显然是对的。
最后答案就是sigma_{i是s中的字符}x[i]。
struct data{
	LL val, len;
	inline data(LL v = 0LL, LL l = 1LL) :val(v % 1000000007LL), len(l % 1000000007LL){}
} d[10];
inline data operator *(const data x, const data y){
	return data(x.val * y.len + y.val, x.len * y.len);
}
char buf[10000086], *cb = buf;
char b2[100086], s[100086];

int main(){
	g(i, 0, 10) d[i] = data(i, 10);
	int n; scanf("%s%d", s, &n);
	while((*cb = getchar()) != EOF) ++cb;
	--cb;
	while(n--){
		while(*cb != '>') --cb;
		int l = *(cb - 2) - '0';
		data tmp;
		for(char *c = cb + 1; *c >= '0'; ++c) tmp = tmp * d[*c - '0'];
		d[l] = tmp;
		--cb;
	}
	data ans; int sl = strlen(s);
	g(i, 0, sl) ans = ans * d[s[i] - '0'];
	printf("%I64d\n", ans.val);
	return 0;
}
464D. World of Darkraft - 2
你有k种装备,每种装备你都有一个,且为Lv1。你有n次机会打怪,每次怪物都会随机掉落k种中的一种,其Lv在[1,当前你这种装备的Lv+1]中随机决定。这时你会持有2个这种装备,所以你会选择其中Lv较低的卖掉,售价是它的Lv。问n次打怪后你期望获得的钱数。
n≤10^5,k≤100。
Solution
首先每种装备都是一样的,所以算出一种装备的答案乘上k就好了。
先考虑一个平方级别的做法:
dp[T][L]表示有T次机会打怪,当前装备等级为L,期望获得的钱数。
那么dp[T][L]= ((k-1)/k)*dp[T-1][L] + (1/k)*【(L/(L+1))*(dp[T-1][L]+(L+1)/2) + (1/(L+1))*(dp[T-1][L+1]+L)】
大概解释就是,有(k-1)/k的概率根本打不到这个怪,剩下的概率当中的L/(L+1)会保持原等级,获得的钱期望是(L+1)/2,最后1/(L+1)是升级,获得了L的钱。
最后答案就是dp[n][1]*k。

考虑装备的等级最高大概能是多少,假设k=1(最坏情况),可以证明Lv的期望是Theta(logn)。这就说明,Lv几乎不可能达到较大的级别。直接无视较大的L(比如L≥700)视其dp值为0即可。
内存好像吃的有点多,滚动数组搞一搞……
int n, k;
real _ldp[708], _dp[708], *ldp = _ldp, *dp = _dp;

int main(){
	scanf("%d%d", &n, &k);
	memset(dp, 0, sizeof(_dp));
	memset(ldp, 0, sizeof(_dp));
	f(T, 1, n){
		f(L, 1, 700) dp[L] = ((L * (ldp[L] + (L + 1) / 2.0) + ldp[L + 1] + L) / (L + 1) + ldp[L] * (k - 1)) / k;
		std::swap(dp, ldp);
	}
	printf("%.20lf\n", (double) (ldp[1] * k));
	return 0;
}
464E. The Classic Problem
无向图最短路,每条边的描述u v w表示u与v之间有一条长度为2^w的边,求s到t的最短路mod 1e9+7的值,并输出一个方案。
点数,边数,w≤10^5。
Solution
边权没这么大的话直接裸Dijkstra……
现在需要维护一堆高精度数,需要支持”+2^w“和”比大小“两种操作,考虑对其二进制表示维护可持久化线段树。
(以下内容中”左“表示数的低位,”右“表示高位,与书写习惯相反)
”+2^w“:如果第w位是0,直接把它改成1;否则,找到w右侧的第一个0,把它改成1,把中间的一堆1改成0。
于是需要在线段树的每个点存这个区间里0的个数。
”比大小“:如果右孩子相等,大小就由左孩子决定;否则由右孩子决定。递归到根以后只剩下0和1直接比。
于是需要每个点存个哈希值。
区间刷0如果用打标记实现是一件很烦人的事情,所以预处理出一个全是0的树,直接用其中的节点替换(准确说是直接返回)即可。
我的代码又长又慢又费空间……(我有特殊的写Dijkstra技巧233)
std::map<PII, int> _hash;
inline int hash(int l, int r){
	int &ans = _hash[PII(l, r)];
	if(ans == 0) ans = _hash.size();
	return ans;
}

struct node{
	node *ls, *rs;
	int data, sum;
} pool[30000000], *cp = pool, *lazy[2][18];
inline node *newnode(node *ls, node *rs){
	cp->ls = ls; cp->rs = rs;
	cp->data = hash(ls->data, rs->data); cp->sum = ls->sum + rs->sum;
	return cp++;
}
inline node *newnode(int data){
	cp->ls = cp->rs = NULL; cp->data = data - 2; cp->sum = 1 - data; return cp++;
}
inline node *chg(node *root, int ll, int rr, int x, int siz = 17, int l = 0, int r = 131071){
	if(ll > rr) return root;
	if(l == ll && r == rr) return lazy[x][siz];
	else{
		int m = (l + r) >> 1;
		if(rr <= m) return newnode(chg(root->ls, ll, rr, x, siz - 1, l, m), root->rs);
		else if(ll > m) return newnode(root->ls, chg(root->rs, ll, rr, x, siz - 1, m + 1, r));
		else return newnode(chg(root->ls, ll, m, x, siz - 1, l, m), chg(root->rs, m + 1, rr, x, siz - 1, m + 1, r));
	}
}
inline int gsum(node *root, int ll, int rr, int l = 0, int r = 131071){
	if(ll > rr) return 0;
	if(l == ll && r == rr) return root->sum;
	else{
		int m = (l + r) >> 1;
		if(rr <= m) return gsum(root->ls, ll, rr, l, m);
		else if(ll > m) return gsum(root->rs, ll, rr, m + 1, r);
		else return gsum(root->ls, ll, m, l, m) + gsum(root->rs, m + 1, rr, m + 1, r);
	}
}
inline int kth(node *root, int k, int l = 0, int r = 131071){
	if(l == r) return l;
	else{
		int m = (l + r) >> 1, ls = root->ls->sum;
		if(k <= ls) return kth(root->ls, k, l, m);
		else return kth(root->rs, k - ls, m + 1, r);
	}
}
inline node *add(node *root, int x){
	int y = kth(root, gsum(root, 0, x - 1) + 1);
	return chg(chg(root, x, y - 1, 0), y, y, 1);
}
//-1 less	0 equal		1 greater
inline int cmp(node *x, node *y){
	if(x->ls){
		if(x->rs->data == y->rs->data) return cmp(x->ls, y->ls);
		else return cmp(x->rs, y->rs);
	}else{
		if(x->data < y->data) return -1;
		else if(x->data > y->data) return 1;
		else return 0;
	}
}
const LL MODLL = 1000000007LL;
inline LL gint(node *root, LL &sz){
	if(root->ls){
		LL lsz, rsz;
		LL lint = gint(root->ls, lsz), rint = gint(root->rs, rsz);
		sz = lsz * rsz % MODLL;
		return (lint + rint * lsz) % MODLL;
	}else{
		sz = 2; return root->data + 2;
	}
}

struct bignum{
	node *root;
	inline bignum(node *r = lazy[0][17]) :root(r){}
	inline bignum operator +(int r){
		return bignum(add(root, r));
	}
	inline bool operator <(const bignum r) const{
		return cmp(root, r.root) == -1;
	}
	inline bool operator ==(const bignum r) const{
		return cmp(root, r.root) == 0;
	}
	inline bool operator >(const bignum r) const{
		return cmp(root, r.root) == 1;
	}
	inline int toInt() const{
		LL foo; return gint(root, foo);
	}
} ZERO, INF;

bignum tree[262144], dist[100086]; int pred[100086];
inline void chg(int x, bignum y){
	tree[x += 131072] = y;
	for(x >>= 1; x; x >>= 1) tree[x] = std::min(tree[x << 1], tree[x << 1 | 1]);
}
inline int gmin(){
	int x = 1;
	while(x < 131072) if(tree[x] == tree[x << 1]) x <<= 1; else x = (x << 1 | 1);
	chg(x -= 131072, INF);
	return x;
}

std::vector<PII> adj[100086];
std::vector<int> ans;

int main(){
	f(x, 0, 1){
		lazy[x][0] = newnode(x);
		f(i, 1, 17) lazy[x][i] = newnode(lazy[x][i - 1], lazy[x][i - 1]);
	}
	ZERO = lazy[0][17]; INF = lazy[1][17];
	g(i, 0, 262144) tree[i] = INF;
	
	int n, m; scanf("%d%d", &n, &m);
	while(m--){
		int s, t, w; scanf("%d%d%d", &s, &t, &w);
		adj[s].push_back(PII(t, w));
		adj[t].push_back(PII(s, w));
	}
	f(i, 1, n) dist[i] = INF;
	
	int S, T; scanf("%d%d", &S, &T);
	dist[S] = ZERO; pred[S] = 0; chg(S, ZERO);
	while(!(tree[1] == INF)){
		bignum cd = tree[1]; int c = gmin();
		foreach(e, adj[c]){
			int t = e->first; bignum td = cd + e->second;
			if(td < dist[t]){
				dist[t] = td; chg(t, td); pred[t] = c;
			}
		}
	}
	
	if(dist[T] == INF) printf("-1\n");
	else{
		printf("%d\n", dist[T].toInt());
		int c = T;
		while(c != S){
			ans.push_back(c); c = pred[c];
		}
		ans.push_back(S);
		printf("%d\n", ans.size());
		rforeach(i, ans) printf("%d ", *i);
		printf("\n");
	}
	return 0;
}
  评论这张
 
阅读(224)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018