这次的题来自2017ECNA Regional Contest，难度还行吧毕竟连我都可以A两三道。
链接在此https://vjudge.net/contest/292809#overview
A,B都是计算几何的题，A有个坑点是要考虑中空。由于我们太菜了，这两道直接跳过嘻嘻嘻。
D签到题。直接上代码
#include<bits/stdc++.h>
using namespace std;
int step[110];
int main()
{
int n, k, t, last = 0, sum = 0;
string s;
cin >> n >> k;
while(k--){
cin >> s;
if(s[0] == 'u'){
cin >> t;
last -= t;
}
else{
step[last++] = atoi(s.c_str());
}
}
for(int i = 0; i < last; i++) sum += step[i];
while(sum < 0) sum += n;
printf("%d", sum % n);
return 0;
}
G题是我AC的第二道。就普通的dp吧感觉没什么难的，但我忘了初始化初始化初始化！！！代码如下：
#include<bits/stdc++.h>
using namespace std;
int course[110], dp[110][30];
int main(){
int n, m;
while(scanf("%d%d", &n, &m) != EOF){
vector <int > eat;
int ans = -1;
memset(dp, 0, sizeof(dp));//初始化！！！
eat.push_back(0);
while(m){
eat.push_back(m);
m = m * 2 / 3;
}
//for(int i = 0; i < eat.size(); i++) cout << "eat[" << i << "] = " << eat[i] << endl;
for(int i = 1; i <= n; i++){
cin >> course[i];
for(int j = 0; j < eat.size(); j++){
if(j > 0)dp[i][j] = dp[i - 1][j - 1] + min(course[i], eat[j]);
if(i > 2) dp[i][j] = max(dp[i][j], dp[i - 2][j] + min(course[i], eat[j]));
if(i > 2) dp[i][0] = max(dp[i][0], dp[i - 2][j]);//！！！
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
}
return 0;
}
E是我肝的第三道。盯着mkr大佬的完美代码瞅了2h+，终于找到bug了真TM令人绝望。bug原因的存在 A has-a A 的情况。
贴上大佬神仙代码
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MAXNODE 500
int n, m;
string names[MAXN * 2 + 5];
int cnt_names;
struct Entry {
string lhs, rhs;
string rel;
} rel[MAXN + 5];
bool has[MAXNODE + 5][MAXNODE + 5];
bool is[MAXNODE + 5][MAXNODE + 5];
bool vis[MAXNODE + 5];
string qlhs, qrhs, qrel;
void dfs_is(int u, int start) {
vis[u] = true;
is[start][u] = true;
for (int i = 1; i <= cnt_names; ++i)
if (i != u && !vis[i] && is[u][i])
dfs_is(i, start);
}
void dfs_has(int u, int start, bool isFirst) {
if (isFirst) {
for (int i = 1; i <= cnt_names; ++i)
if (!vis[i] && has[u][i])
dfs_has(i, start, false);
//vis[u] = true; 就是这句话，查了我2h+
}
else {
vis[u] = true;
has[start][u] = true;
for (int i = 1; i <= cnt_names; ++i)
if (!vis[i] && (is[u][i] || has[u][i]))
dfs_has(i, start, false);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
cin >> rel[i].lhs >> rel[i].rel >> rel[i].rhs;
names[i * 2 - 1] = rel[i].lhs;
names[i * 2] = rel[i].rhs;
}
sort(names + 1, names + 1 + 2 * n);
cnt_names = unique(names + 1, names + 1 + 2 * n) - (names + 1);
for (int i = 1; i <= n; ++i) {
int lhs, rhs;
lhs = lower_bound(names + 1, names + 1 + cnt_names, rel[i].lhs) - (names + 1) + 1;
rhs = lower_bound(names + 1, names + 1 + cnt_names, rel[i].rhs) - (names + 1) + 1;
if (rel[i].rel == "is-a")
is[lhs][rhs] = true;
else
has[lhs][rhs] = true;
}//这种预处理tql
for (int i = 1; i <= cnt_names; ++i) {
memset(vis, 0, sizeof vis);
dfs_is(i, i);
}
for (int i = 1; i <= cnt_names; ++i) {
memset(vis, 0, sizeof vis);
for (int j = 1; j <= cnt_names; ++j){
if (is[i][j]) dfs_has(j, i, true);
}
}
for (int i = 1; i <= m; ++i) {
cin >> qlhs >> qrel >> qrhs;
int lhs, rhs;
lhs = lower_bound(names + 1, names + 1 + cnt_names, qlhs) - (names + 1) + 1;
rhs = lower_bound(names + 1, names + 1 + cnt_names, qrhs) - (names + 1) + 1;
if (qrel == "is-a")
cout << "Query " << i << ": " << (is[lhs][rhs] ? string("true") : string("false")) << endl;
else
cout << "Query " << i << ": " << (has[lhs][rhs] ? string("true") : string("false")) << endl;
}
}
/*
反例input
2
2
A is-a B
B has-a B
A has-a B
*/
J应该就是个大模拟，可惜我们时间不够了。还是比赛经验不足啊。有空贴上CFHJ代码。
4.6 3:30
来贴上J代码了
#include<bits/stdc++.h>
using namespace std;
int use[20], rec[20], u[20], v[20], t[20], sum;
int main(){
for(int i = 0; i < 10; i++) cin >> use[i] >> rec[i];
for(int i = 0; i < 10; i++) cin >> u[i] >> v[i] >> t[i];
for(int j = 0; j < 30; j++){
int i = j % 10;
if(sum >= t[i]){
int temp = sum - t[i];
int k = temp / (u[i] + v[i]) * (u[i] + v[i]);
t[i] += k + u[i];
sum = max(sum, t[i]);
t[i] += v[i];
}
sum += use[i];
t[i] = max(t[i], sum);
sum += rec[i];
}
cout << sum - rec[9] << endl;
return 0;
}
以上代码是参考题解的......见https://blog.csdn.net/axuhongbo/article/details/81742271
我自己写的模拟相对而言确实不够简洁,但我找了3h的bug硬是找不着嘻嘻嘻
还是贴上, 希望有大神看到后能救救孩子
#include<bits/stdc++.h>
#define ll long long
using namespace std;
typedef struct{
ll l, r, delta, T, t;
}D;
D d[20];
ll us[20], rec[20];
int main()
{
for(int i = 0; i < 10; i++)
cin >> us[i] >> rec[i];
for(int i = 0; i < 10; i++){
ll a, b, c;
cin >> a >> b >> c;
d[i].T = a + b;
d[i].l = c % d[i].T;
d[i].r = (c + a) % d[i].T;
d[i].delta = a;
d[i].t = c;
}
ll cur = 0;
for(int times = 0; times < 3; times++){
for(int i = 0; i < 10; i++){
ll v = cur % d[i].T;
if(cur < d[i].t){
cur += us[i];
if(cur > d[i].t) d[i].l = cur % d[i].T;
}
else if(d[i].l < d[i].r){
cur += us[i];
if(v < d[i].l){
v += us[i];
if(v > d[i].l) d[i].l = v % d[i].T;
}
else if(v >= d[i].r){
v += us[i];
if(v > d[i].l + d[i].T) d[i].l = v % d[i].T;
}
else{
cur += d[i].r - v;
v += d[i].r - v + us[i];
if(v > d[i].l + d[i].T) d[i].l = v % d[i].T;
}
}
else{
cur += us[i];
if(v < d[i].l && v >= d[i].r){
v += us[i];
if(v > d[i].l) d[i].l = v % d[i].T;
}
else{
if(v >= d[i].l){
d[i].r += d[i].T;
cur += d[i].r - v;
v += d[i].r - v + us[i];
if(v > d[i].l + d[i].T) d[i].l = v % d[i].T;
}
else{
cur += d[i].r - v;
v += d[i].r - v + us[i];
if(v > d[i].l) d[i].l = v % d[i].T;
}
}
}
cur += rec[i];
d[i].r = (d[i].l + d[i].delta) % d[i].T;
//printf("d[%d].l = %d, d[%d].r = %d, cur = %d\n", i, d[i].l, i, d[i].r, cur);
}
}
cout << cur - rec[9]<< endl;
return 0;
}
