题意：求每个点的度数
分析：可以在，每个字母的的两个端点里求出的的出度，那么除了起点外其他点还有一个入度，再+1
/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 13:22:03
* File Name :B.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int vis[33];
char s[N];
int p1[33], p2[33];
int ans[33]; int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
scanf ("%s", &s);
memset (ans, -1, sizeof (ans));
memset (vis, 0, sizeof (vis));
memset (p1, -1, sizeof (p1));
memset (p2, -1, sizeof (p2));
int len = strlen (s);
for (int i=0; i<len; ++i) {
if (ans[s[i]-'A'] == -1) ans[s[i]-'A'] = 0;
if (p1[s[i]-'A'] == -1) p1[s[i]-'A'] = i;
else p2[s[i]-'A'] = i;
}
for (int i=0; i<len; ++i) {
if (vis[s[i]-'A'] == 1) continue;
int j = p1[s[i]-'A'] + 1;
if (j == p2[s[i]-'A']) {
//ans[s[i]-'A'] = 1; vis[s[i]-'A'] = 1;
continue;
}
while (j < p2[s[i]-'A']) {
ans[s[i]-'A']++;
j = p2[s[j]-'A'] + 1;
}
vis[s[i]-'A'] = 1;
}
for (int i=0; i<26; ++i) ans[i]++;
ans[s[0]-'A']--; printf ("Case %d\n", ++cas);
for (int i=0; i<26; ++i) {
if (ans[i] <= 0) continue;
printf ("%c = %d\n", 'A' + i, ans[i]);
}
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}
水 C Memory Overflow
/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 12:55:22
* File Name :C.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 5e2 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
char s[N]; int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int n, k; scanf ("%d%d", &n, &k);
scanf ("%s", &s);
int ans = 0;
for (int i=0; i<n; ++i) {
bool flag = false;
for (int j=max (0, i-k); j<i; ++j) {
if (s[j] == s[i]) {
flag = true; break;
}
}
if (flag) ans++;
}
printf ("Case %d: %d\n", ++cas, ans);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}
暴力/高斯消元 E Poker End Games
只会暴力
/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 18:34:27
* File Name :E.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0); int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int a, b; scanf ("%d%d", &a, &b);
double p = 1.0, round = 0, win = 0;
int n = 1e6;
for (int i=1; i<=n; ++i) {
if (a == b) {
round += p * i;
win += p * 0.5;
break;
}
if (a > b) {
a -= b; b += b;
round += p * i * 0.5;
win += p * 0.5;
}
else if (a < b) {
b -= a; a += a;
round += p * i * 0.5;
}
p *= 0.5;
}
printf ("Case %d: %.6f %.6f\n", ++cas, round, win);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}
题意：判断能否根据某个点是'*'来区别出形状，必须是‘*'，其他的都是'.'才行。
/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 14:03:02
* File Name :F.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
char s[40][20][50];
char ss[40];
int id[40];
int ans[20]; int f(char ch) {
if (ch >= 'A' && ch <= 'Z') return ch - 'A';
else return 26 + (ch - '0');
} int main(void) {
int n, m, cas = 0; scanf ("%d%d", &n, &m);
scanf ("%s", &ss);
//printf ("%s\n", ss);
memset (id, -1, sizeof (id));
for (int i=0; i<n; ++i) {
id[f (ss[i])] = i;
for (int j=0; j<17; ++j) {
scanf ("%s", s[i][j]);
}
/*
for (int j=0; j<17; ++j) {
printf ("%s\n", s[i][j]);
}
*/
} for (int i=0; i<m; ++i) {
scanf ("%s", &ss);
int len = strlen (ss);
for (int j=0; j<len; ++j) {
ans[j] = 0;
if (id[f (ss[j])] == -1) continue;
for (int k=0; k<16 && !ans[j]; ++k) { //row
for (int l=0; l<43 && !ans[j]; ++l) { //col
bool flag = true;
if (s[id[f (ss[j])]][k][l] != '*') continue;
for (int ii=0; ii<len; ++ii) {
if (ii == j) continue;
if (id[f (ss[ii])] == -1) continue;
if (s[id[f (ss[ii])]][k][l] != '.') {
flag = false; break;
}
}
if (flag) ans[j] = 1;
}
}
}
printf ("Query %d: ", ++cas);
for (int i=0; i<len; ++i) {
printf ("%c", ans[i] ? 'Y' : 'N');
}
puts ("");
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}
DP I Learning Vector
题意：给了一些向量，问选出一些与x坐标轴组成的多变形面积最大
分析：开始以为贪心，因为很难想DP把之前的选的向量保存起来。看题解才知道，dp[i][j][h] 表示前i个选择了j个，最后高度为h组成的面积，那么状态转移时不需要知道之前的长度，用梯形面积公式累加多出来的面积就行了。另外，向量应该先极角排序。
/************************************************
* Author :Running_Time
* Created Time :2015/11/4 星期三 15:47:19
* File Name :I_2.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) { //三态函数，减少精度问题
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
struct Vec {
int x, y;
Vec () {}
Vec (int x, int y) : x (x), y (y) {}
}vs[55];
bool cmp(Vec A, Vec B) {
return dcmp (A.x * B.y - A.y * B.x) < 0;
} int dp[55][55][2550]; int main(void) {
int T, cas = 0; scanf ("%d", &T);
while (T--) {
int n, k; scanf ("%d%d", &n, &k);
int H = 0;
for (int x, y, i=1; i<=n; ++i) {
scanf ("%d%d", &vs[i].x, &vs[i].y);
H += vs[i].y;
}
sort (vs+1, vs+1+n, cmp);
memset (dp, -1, sizeof (dp));
dp[0][0][0] = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<=i && j<=k; ++j) {
for (int h=0; h<=H; ++h) {
if (dp[i][j][h] == -1) continue;
dp[i+1][j][h] = max (dp[i+1][j][h], dp[i][j][h]);
if (j < k) {
int hh = h + vs[i+1].y;
dp[i+1][j+1][hh] = max (dp[i+1][j+1][hh], dp[i][j][h] + (h + hh) * vs[i+1].x);
}
}
}
} int ans = 0;
for (int i=0; i<=H; ++i) if (ans < dp[n][k][i]) ans = dp[n][k][i];
printf ("Case %d: %d\n", ++cas, ans);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}