Codeforces Round #301 (Div. 2) 题解

【Combination Lock(A)】

求出两个字符串每一位数字最小之差相加即可。

【AC CODE】15ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10;
char a[MAXN], b[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	scanf("%d%*c", &n);
	scanf("%s%s",a,b);
	int ans = 0;
	rep(i,0,n)
	{
		a[i] -= '0';
		b[i] -= '0';
		int tmp;
		if(a[i] >= b[i]) tmp = min(a[i]-b[i],10-a[i]+b[i]);
		else tmp = min(b[i]-a[i], 10-b[i]+a[i]);
		ans += tmp;
	}
	printf("%d\n", ans);
	return 0;
}

 【School Marks(B)】

贪心+暴力；当前中位数左边一个值大于等于y时肯定插入1值，这样中位数变成了左边那个数，插入1保证的sum尽量小，因为要小于x；否则插入一个y，让中位数变成y；最后看sum是否超过x即可。由于N只有999，所以插入可以直接暴力。我下面代码的x和y互换了。

【AC CODE】30ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 1000+10;
int a[MAXN],len, m,n,k,p,x,y, sum;

void insert(int v)
{
	if(!len) a[len++] = v;
	else
	{
		int k = upper_bound(a,a+len,v)-a;
		per(i,len-1,k)
			a[i+1] = a[i];
		a[k] = v;
		len++;
	}
	sum += v;
}
vector<int> ans;
bool sloved()
{
	int cnt = n-k;
	ans.clear();
	if(x > y) return false;
	if(1 == n)
	{
		if(0 == len)
		{
			ans.push_back(x);
			return p >= x;
		}
		return sum <= x && a[m] >= x;
	}
	while(cnt)
	{
		if(len < m) insert(1),ans.push_back(1);
		else
		{
			if(a[len/2-1] >= x) insert(1),ans.push_back(1);
			else insert(x),ans.push_back(x);
		}
		if(sum > y) return false;
		cnt--;
	}
	return sum <= y && a[m] >= x;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	while(~scanf("%d %d %d %d %d", &n, &k, &p, &y, &x))
	{
		m = n/2;
		len = sum = 0;
		rep(i,0,k)
		{
			int v;
			scanf("%d%*c", &v);
			insert(v);
		}
		ans.clear();
		if(!sloved()) puts("-1");
		else
		{
			rep(i,0,ans.size()) printf("%d ",ans[i]);
			putchar('\n');
		}
	}
	return 0;
}

 【Ice Cave(C)】

直接BFS，注意初始位置不需要压碎即可。

【AC CODE】31ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 500+10,f[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct NODE{
	int x,y;
};
int n,m, si, sj, ei, ej, a[MAXN][MAXN];

bool sloved()
{
	queue<NODE> q;
	q.push({si,sj});
	//a[si][sj]++;
	while(!q.empty())
	{
		NODE now = q.front();q.pop();
		rep(i,0,4)
		{
			int ni = now.x+f[i][0], nj = now.y+f[i][1];
			if(0 <= ni && n > ni && 0 <= nj && m > nj)
			{
				if(a[ni][nj] < 1)
				{
					a[ni][nj]++;
					q.push({ni,nj});
				}
				else if(a[ni][nj] == 1)
				{
					if(ni == ei && nj == ej) return true;
					continue;
				}
			}
		}
	}
	return false;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	while(~scanf("%d %d%*c",&n, &m))
	{
		rep(i,0,n)
		{
			rep(j,0,m)
			{
				int c = getchar();
				if(c == '.') a[i][j] = 0;
				else a[i][j] = 1;
			}
			getchar();
		}
		scanf("%d %d %d %d", &si, &sj, &ei, &ej);
		si--,sj--,ei--,ej--;
		if(sloved()) puts("YES");
		else puts("NO");
	}
	return 0;
}

【Bad Luck Island(D)】

概率DP，没做过概率DP，直接不会了，学习了一下，这题还是比较水的概率DP。

dp[i][j][k]表示有i个石头，j个剪刀，k个布的概率。初始为1,；转移方程：

总的可能情况数：sum = i*j+i*k+j*k

石头和剪刀相遇：dp[i][j-1][k] += dp[i][j][k]*i*j/sum;

石头和布相遇：dp[i-1][j][k] += dp[i][j][k]*i*k/sum;

剪刀和布相遇：dp[i][j][k-1] += dp[i][j][k]*j*k/sum;

【AC CODE】46ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100+10;
double dp[MAXN][MAXN][MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int r,s,p;
	while(~scanf("%d %d %d%*c", &r, &s, &p))
	{
		clc(dp,0);
		dp[r][s][p] = 1;
		per(i,r,0)
		{
			per(j,s,0)
			{
				per(k,p,0)
				{
					if(!i && !k || !i && !j || !j && !k) continue;
					double sum = i*j+i*k+j*k;
					if(i)
						dp[i-1][j][k] += dp[i][j][k]*i*k/sum;
					if(j)
						dp[i][j-1][k] += dp[i][j][k]*i*j/sum;
					if(k)
						dp[i][j][k-1] += dp[i][j][k]*j*k/sum;
				}
			}
		}
		double ans1 = 0, ans2 = 0, ans3 = 0;
		repe(i,1,r) ans1 += dp[i][0][0];
		repe(i,1,s) ans2 += dp[0][i][0];
		repe(i,1,p) ans3 += dp[0][0][i];
		printf("%.9f %.9f %.9f\n", ans1, ans2, ans3);
	}
	return 0;
}

 【Infinite Inversions(E)】

就是求逆序对，只是值比较大，需要离散化，然后有些没出现的连续点由于他们的位置没有改变直接把他们缩成一个点即可，然后就是正常的求逆序对，该用什么用什么，我用的线段树，常数稍微大了点。

【AC CODE】327ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000*2*2+10;
struct IN{
	int a,b;
}in[MAXN];
unordered_map<int,int> num;
int cnt,p[MAXN], s[MAXN], tb[MAXN],tol;
LL sum[MAXN<<1];

inline void insert(int v)
{
	if(num.find(v) == num.end())
	{
		num[v] = cnt;
		p[cnt++] = v;
	}
}
inline int get_id(int v){
	return lower_bound(tb,tb+tol,v)-tb;
}
inline int id(int x, int y){return x+y|x!=y;}
inline void push_up(int x, int y, int m){
	sum[id(x,y)] = sum[id(x,m)]+sum[id(m+1,y)];
}
void add(int x, int y, int p, int v)
{
	if(x == y)
	{
		sum[id(x,y)] += v;
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) add(x,m,p,v);
	else add(m+1,y,p,v);
	push_up(x,y,m);
}
LL query(int x, int y, int ql, int qr)
{
	if(ql <= x && y <= qr) return sum[id(x,y)];
	int m = (x+y)>>1;
	LL ans = 0;
	if(ql <= m) ans += query(x,m,ql,qr);
	if(qr > m) ans += query(m+1,y,ql,qr);
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int n;
	while(~scanf("%d%*c", &n))
	{
		cnt = 0;
		num.clear();
		insert(1);
		rep(i,0,n)
		{
			int a,b;
			scanf("%d %d%*c", &a, &b);
			in[i] = {a,b};
			insert(a), insert(b);
		}
		sort(p,p+cnt);
		p[cnt] = p[cnt-1]+1;
		memcpy(s,p,sizeof(int)*(cnt+1));
		rep(i,0,n)
		{
			int a = lower_bound(p,p+cnt,in[i].a)-p, b = lower_bound(p,p+cnt,in[i].b)-p;
			swap(s[a],s[b]);
		}
		tol = 0;
		rep(i,0,cnt)
		{
			tb[tol++] = p[i];
			if(p[i+1]-p[i] > 1)
				tb[tol++] = p[i]+1;
		}
		LL ans = 0;
		clc(sum,0);
		rep(i,0,cnt)
		{
			int v = get_id(s[i]);
			ans += query(0,tol-1,v,tol-1);
			add(0,tol-1,v,1);
			if(p[i+1]-p[i] > 1)
			{
				v = get_id(p[i]+1);
				ans += query(0,tol-1,v,tol-1)*(p[i+1]-p[i]-1);
				add(0,tol-1,v,p[i+1]-p[i]-1);
			}
		}
		printf("%I64d\n", ans);
	}
	return 0;
}

 

dawxy

作者： dawxy

https://github.com/dawxy

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码