A题
简单模拟。
/*************************************************************************
> File Name: A.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 08时08分12秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <string>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int n;
string s;
double a, f; int main(void) {
while (cin >> n) {
cin >> s;
cin >> a >> f; double sum = 0.0;
int m = (int)s.length();
bool flag = true;
for (int i = ; i < m; i++) {
if (s[i] == 'L') sum -= a;
else sum += a;
if (sum >= f || sum <= -f) {flag = false; break;}
}
printf("%s\n", flag ? "YES" : "NO");
} return ;
}
B题
判断最大值和剩下的值的和的关系
/*************************************************************************
> File Name: B.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 14时26分17秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int n, m; int main(void) {
ios::sync_with_stdio(false);
while (cin >> m >> n) {
long long sum = , t = -, a;
for (int i = ; i < m; i++) cin >> a, t = max(t, a), sum += a;
sum -= t;
if (t > sum + ) cout << "NO\n";
else cout << "YES\n";
}
return ;
}
C题
模拟。
/*************************************************************************
> File Name: C.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 14时32分40秒
> Propose:
************************************************************************/
#include <map>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int vis[]; int main(void) {
ios::sync_with_stdio(false);
int n;
while (cin >> n) {
map<string, int> var;
vector<string> s(n + );
for (int i = ; i <= n; i++) cin >> s[i];
memset(vis, , sizeof(vis)); for (int i = ; i <= n; i++) {
if (var.find(s[i]) == var.end()) var[s[i]] = ;
else var[s[i]]++;
if (!vis[var[s[i]]]) vis[var[s[i]]] = i;
}
for (int i = ; i <= n && vis[i]; i++) cout << i << ' ' << s[vis[i]] << endl;
} return ;
}
D题
从后往前计算，判断当前点在左上或者右上或者左下或者右下，然后分别乘以不同的系数，并且更新点的位置。
/*************************************************************************
> File Name: D.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 14时56分31秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int t, a, b, c, d, x, y;
typedef long long LL; int main(void) {
ios::sync_with_stdio(false);
cin >> t;
while (t--) {
int n;
cin >> n;
cin >> a >> b >> c >> d;
cin >> x >> y; int times = ;
while ((<<times) < max(x, y)) times++;
LL ans = ;
while (times--) {
if (x <= (<<times)) {
if (y <= (<<times)) ans *= a;
else ans *= b, y -= <<times;
} else {
x -= <<times;
if (y <= (<<times)) ans *= c;
else ans *= d, y -= <<times;
}
}
cout << ans << endl;
} return ;
}
E题
比赛时候没有过。可以先枚举角度（从０到2*pi，每次加1e-7，加多了就会ＷＡ），求得系数。
/*************************************************************************
> File Name: E.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 15时34分16秒
> Propose:
************************************************************************/ #include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int main(void) {
/*double ans;
ans=0.0;
double pi = acos(-1.0);
for (double i = 0.0; i < 2 * pi; i += 0.0000001)
{
ans += sqrt(5.0 - 4.0 * cos(i));
}
ans /= 2 * pi * 10000000;
cout << ans << endl; */
int r;
while (cin >> r) cout << (int)(r * 2.12709) <<endl;
return ;
}
F题
因为y-x < 1e4，以此作为着手点。先去掉Ａi中大于y-x+1的系数，然后去重。
之后就转化为完全背包。
/*************************************************************************
> File Name: F.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月01日 星期一 19时14分48秒
> Propose:
************************************************************************/
#include <set>
#include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ int n, x, y, dp[]; int main(void) {
ios::sync_with_stdio(false);
while (cin >> n) {
cin >> x >> y;
int cnt = ;
vector<int> a;
for (int i = ; i <= n; i++) {
int tmp;
cin >> tmp;
if (tmp <= y - x + ) a.push_back(tmp - );
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
cnt = a.size();
memset(dp, 0x3f, sizeof(dp));
int V = y - x;
dp[] = ;
for (int i = ; i < cnt; i++) {
for (int j = a[i]; j <= V; j++) {
if (dp[j - a[i]] != 0x3f3f3f3f) dp[j] = min(dp[j], dp[j - a[i]] + a[i]);
}
}
if (dp[V] == 0x3f3f3f3f) puts("IMPOSSIBLE");
else puts("POSSIBLE"); } return ;
}
H题
给ｎ个不大于１e9的数，要求找出２个数使得这两个数进行没有进位的加法的结果最大。
思路：用Trie树维护每一个数，初始时树为空，没输入一个数，先在树中找某个数与之进行无进位加法可以得到的最大值，
更新最大值，然后将该数加进树中。
下面就是如何找到与某个数进行加法可以得到的最大值，从高位枚举到低位，肯定优先满足最高位最大，这样才能使得结果最大，
对于每一位，降序枚举进行加法可以得到的和，就是９到０，看能否满足，如果满足就跳出并判断下一位，并更新结果。
Accepted Code:
/*************************************************************************
> File Name: H.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年09月02日 星期二 20时27分32秒
> Propose:
************************************************************************/
#include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
/*Let's fight!!!*/ #define rep(i, n) for (int i = (0); i < (n); i++)
#define per(i, n) for (int i = (n); i > 0; i--)
#define FOR(i, n) for (int i = (1); i <= (n); i++)
#define ROF(i, n) for (int i = (n); i >= (1); i--)
const int MAX_N = ;
int ch[MAX_N][], p[];
struct Trie {
int sz;
Trie() {
memset(ch[], -, sizeof(ch[]));
sz = ;
}
void insert(int num) {
int u = ;
for (int i = ; i >= ; i--) {
int id = num / p[i];
if (id >= ) id %= ;
if (ch[u][id] == -) {
memset(ch[sz], -, sizeof(ch[sz]));
ch[u][id] = sz++;
}
u = ch[u][id];
}
}
int find_max(int num) {
int u = , ans = ;
for (int i = ; i >= ; i--) {
int id = num / p[i];
if (id >= ) id %= ;
for (int j = ; j >= ; j--) {
int tmp = j - id;
tmp = (tmp + ) % ;
if (ch[u][tmp] != -) {
ans += p[i] * j;
u = ch[u][tmp];
break;
}
}
}
return ans;
}
}; int main(void) {
ios_base::sync_with_stdio(false);
p[] = ;
FOR (i, ) p[i] = p[i - ] * ;
int n;
while (cin >> n) {
Trie A;
int ans = -, num;
rep (i, n) {
cin >> num;
if (i != ) ans = max(ans, A.find_max(num));
A.insert(num);
}
cout << ans << endl;
} return ;
}