首页 > 代码库 > ACM-ICPC Dhaka Regional 2012 题解
ACM-ICPC Dhaka Regional 2012 题解
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 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。