首页 > 代码库 > ACM-ICPC Dhaka Regional 2012 题解

ACM-ICPC Dhaka Regional 2012 题解

2024-07-30 16:19:08   229人阅读

B:

Uva: 12582 - Wedding of Sultan

给定一个字符串（仅由大写字母构成）一个字母表示一个地点，经过这个点或离开这个点都输出这个地点的字母）
问：
每个地点经过的次数（维护一个栈就可以了，注意进入起点和离开起点都不算入起点的次数）

#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 105;
int b[N];
char a[N];
stack<char> s;
void work() {
	memset(b, 0, sizeof b);
	while(s.size()) s.pop();
	int n = strlen(a);
	s.push(a[0]);
	for(int i = 1; i < n; i ++) {
		b[s.top() - 'A'] ++;
		if(s.top() == a[i]) {
			s.pop();
		} else {
			s.push(a[i]);
		}
	}
	b[a[0]-'A'] --;
	
	for(int i = 0; i < 26; i ++) {
		if(b[i] > 0) {
			printf("%c = %d\n", i+'A', b[i]);
		}
	}
}
int main() {
    int T, cas = 0;
	scanf("%d", &T);
    while(T-- > 0) {
		scanf("%s", a);
        printf("Case %d\n", ++cas);
        work();
    }
    return 0;
}

C:

Uva: 12583 - Memory Overflow

有n天，常数k，n长的字符串
每天有一个字母来拜访主角，主角只能记住最后k天的字母，问主角能辨认出几个字母
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
template <class T>
inline bool rd(T &ret) {
	char c; int sgn;
	if (c = getchar(), c == EOF) return 0;
	while (c != '-' && (c<'0' || c>'9')) c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
	ret *= sgn;
	return 1;
}
template <class T>
inline void pt(T x) {
	if (x <0) {
		putchar('-');
		x = -x;
	}
	if (x>9) pt(x / 10);
	putchar(x % 10 + '0');
}
using namespace std;
const int N = 1000;
typedef long long ll;
int n, k;
int cnt[N];
char s[N];
int work(){
    if(k == 0) return 0;
    queue<char> q;
    memset(cnt, 0, sizeof cnt);
    int ans = 0;
    for(int i = 0; s[i]; i++){
        if(cnt[s[i]])
            ans++;

        if((int)q.size() == k)
        {
            cnt[q.front()]--;
            q.pop();
        }
        q.push(s[i]);
        cnt[s[i]]++;
    }
    return ans;
}
int main(){
    int T, Cas = 1; rd(T);
    while (T--){
        rd(n); rd(k); scanf("%s", s);
        int ans = work();
        printf("Case %d: %d\n", Cas++, ans);
	}
	return 0;
}
E:

Uva: 12585 - Poker End Games

有2个人X,Y，每个人手里有纸牌对应a 和 b张
每局游戏有0.5概率 X 获得Y手中 min(a,b)张
0.5概率 Y获得X手中 min(a,b)张
若有人手里没有牌则另一个人胜利。
问获胜需要的场数的期望 和 X获胜的概率
思路：
爆搜一下
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
double E, P;
void dfs(int n, int m, int t) {
	if(t > 50) return ;
	
	if(n == 0 || m == 0) {
		double p = 1;
		for(int i = 0; i < t; i ++) {
			p *= 0.5;
		}
		E += t*p;
		if(n != 0) P += p;
	} else {
		dfs(n-min(n, m), m+min(n, m), t+1);
		dfs(n+min(n, m), m-min(n, m), t+1);
	}
}
int main() {
    int T, cas = 0;
	scanf("%d", &T);
    while(T-- > 0) {
    	int n, m;
		scanf("%d%d", &n, &m);
		E = 0.0, P = 0.0;
		dfs(n, m, 0);
        printf("Case %d: %.6f %.6f\n", ++cas, E, P);
    }
    return 0;
}

F:

UVA: 12586 - Overlapping Characters


大模拟，写写写

#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
const int N = 50;
const int r = 17;
const int c = 43;
struct node {
	char s[r][c];
};

map<char, node> dic;
int n, q, len;
int vis[r][c];
char ok[N], s[N];

void pu() {
	for (int i = 0; i < len; ++i)
		ok[i] = 'N';
	memset(vis, -1, sizeof vis);
			
	for (int i = 0; i < len; ++i)
		for (int j = 0; j < r; ++j)
			for (int k = 0; k < c; ++k)
				if (dic[s[i]].s[j][k] == '*') {
					if (vis[j][k] == -1)
						vis[j][k] = i;
					else
						vis[j][k] = -2;
				}

	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			if (vis[i][j] >= 0)
				ok[vis[i][j]] = 'Y';
}
void work() {
	node in;
	dic.clear();
	scanf("%s", s);
	len = strlen(s);
	for (int i = 0; i < len; ++i) {
		for (int j = 0; j < 17; ++j)
			scanf("%s", in.s[j]);
		dic[s[i]] = in;
	}
	for (int i = 1; i <= q; ++i) {
		scanf("%s", s);
		len = strlen(s);
		printf("Query %d: ", i);
		pu();
		for (int j = 0; j < len; ++j)
			putchar(ok[j]);
		putchar('\n');
	}
}
int main() {
	while (~scanf("%d%d", &n, &q))
		work();
	return 0;
}

G:

Uva: 12587 - Reduce the Maintenance Cost

==写死爹了
题解：点击打开链接

I:

Uva: 12589 - Learning Vector

题意：给定n个向量，选k个向量，
使得向量围成的面积最大。
思路：
设我们在 向量a, b 之中选一个。
则得到一个方程表示2个向量各自增加的面积
化简后就能排个序。

#include<cstdio>
#include<cstring>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
const int Inf = 1e9;
const int H = 2500+2;
const int N = 50+2;
struct node {
	int w, h;
};

int T = 0, d[N][N][H];
node a[N];
bool cc(const node& i, const node& j) {
	return i.h*j.w>= j.h*i.w;
}
void work() {
	int n, K, mxh = 0, s = 0;
	scanf("%d%d", &n, &K);
	for (int i=0; i<n; ++i) {
		scanf("%d%d", &a[i].w, &a[i].h);
		s += a[i].h;
	}
	sort(a, a + n, cc);
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= K; ++j)
			for (int k = 0; k <= s; ++k)
				d[i][j][k] = -Inf;
	d[0][0][0] = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j <= i && j <= K; ++j)
		for (int k = 0; k <= mxh; ++k)
			if (d[i][j][k] >= 0) {
				d[i+1][j][k] = max(d[i+1][j][k], d[i][j][k]);
				if (j+1 <= K) {
					d[i+1][j+1][k+a[i].h] = max(d[i+1][j+1][k+a[i].h], d[i][j][k] + a[i].w*k*2 + a[i].h*a[i].w);
					mxh = max(mxh, k+a[i].h);
				}
			}
	int ans = 0;
	for (int i = 0; i <= mxh; ++i)
		ans = max(ans, d[n][K][i]);
	printf("Case %d: %d\n", ++T, ans);
}
int main() {
	int cas;
	scanf("%d", &cas);
	while (cas-->0)
		work();
	return 0;
}


ACM-ICPC Dhaka Regional 2012 题解


联系
我们