A - Airport Coffee
留坑。
B - Best Relay Team
枚举首棒
#include <bits/stdc++.h> using namespace std; #define N 510
#define INF 0x3f3f3f3f struct node
{
string name;
double v1, v2;
inline void scan()
{
cin >> name >> v1 >> v2;
}
inline bool operator < (const node &r) const
{
return v2 < r.v2;
}
}arr[N]; int n;
double Min;
string ans[], tmpname[]; int main()
{
cin.tie();
cout.tie();
ios::sync_with_stdio(false);
cin >> n;
for (int i = ; i <= n; ++i) arr[i].scan();
sort(arr + , arr + + n);
Min = INF * 1.0;
for (int i = ; i <= n; ++i)
{
double tmp = ;
tmp += arr[i].v1;
tmpname[] = arr[i].name;
for (int j = , cnt = ; j <= n && cnt < ; ++j)
{
if (i == j) continue;
tmp += arr[j].v2;
tmpname[cnt++] = arr[j].name;
}
if (tmp < Min)
{
Min = tmp;
for (int j = ; j < ; ++j) ans[j] = tmpname[j];
}
}
cout << setiosflags(ios::fixed) << setprecision() << Min << endl;
for (int i = ; i < ; ++i) cout << ans[i] << endl;
return ;
}
C - Compass Card Sales
按题意模拟即可
#include <bits/stdc++.h>
using namespace std; #define N 100010 int n;
set <int> se; struct node
{
int pos, v, pre, nx;
inline node() {}
inline node(int _pos, int _v)
{
pos = _pos;
v = _v;
pre = -, nx = -;
}
inline bool operator < (const node &r) const
{
return v < r.v;
}
}R[N], G[N], B[N]; struct DT
{
int r, g, b, id;
int id_r, id_g, id_b;
int v_r, v_g, v_b, v;
inline void scan()
{
scanf("%d%d%d%d", &r, &g, &b, &id);
v = ;
}
inline void Get()
{
int pre, nx;
v_r = ; pre = R[id_r].pre, nx = R[id_r].nx;
if (R[id_r].v != R[pre].v && R[id_r].v != R[nx].v)
{
v_r += (R[id_r].v - R[pre].v + ) % ;
v_r += (R[nx].v - R[id_r].v+ ) % ;
} v_b = ; pre = B[id_b].pre, nx = B[id_b].nx;
if (B[id_b].v != B[pre].v && B[id_b].v != B[nx].v)
{
v_b += (B[id_b].v - B[pre].v + ) % ;
v_b += (B[nx].v - B[id_b].v + ) % ;
} v_g = ; pre = G[id_g].pre, nx = G[id_g].nx;
if (G[id_g].v != G[pre].v && G[id_g].v != G[nx].v)
{
v_g += (G[id_g].v - G[pre].v + ) % ;
v_g += (G[nx].v - G[id_g].v + ) % ;
}
v = v_r + v_g + v_b;
}
inline void Remove()
{
int pre, nx;
pre = R[id_r].pre, nx = R[id_r].nx;
R[pre].nx = nx; R[nx].pre = pre;
se.insert(R[pre].pos); se.insert(R[nx].pos); pre = G[id_g].pre, nx = G[id_g].nx;
G[pre].nx = nx; G[nx].pre = pre;
se.insert(G[pre].pos); se.insert(G[nx].pos); pre = B[id_b].pre, nx = B[id_b].nx;
B[pre].nx = nx; B[nx].pre = pre;
se.insert(B[pre].pos); se.insert(B[nx].pos);
}
}arr[N]; struct Node
{
int id, v, pos;
inline Node() {}
inline Node(int pos, int id, int v) : pos(pos), id(id), v(v) {}
inline bool operator < (const Node &r) const
{
return v > r.v || v == r.v && id < r.id;
}
}; bool used[N];
int sum[N];
priority_queue <Node> q; inline void Run()
{
while (scanf("%d", &n) != EOF)
{
while (!q.empty()) q.pop();
memset(used, false, sizeof used);
memset(sum, , sizeof sum);
for (int i = ; i <= n; ++i)
{
arr[i].scan();
R[i] = node(i, arr[i].r);
G[i] = node(i, arr[i].g);
B[i] = node(i, arr[i].b);
}
if (n == )
{
printf("%d\n", arr[].id);
continue;
}
sort(R + , R + + n);
sort(G + , G + + n);
sort(B + , B + + n);
for (int i = ; i <= n; ++i)
{
arr[R[i].pos].id_r = i;
arr[G[i].pos].id_g = i;
arr[B[i].pos].id_b = i;
if (i == )
{
R[i].pre = n; G[i].pre = n; B[i].pre = n;
R[i].nx = i + ; G[i].nx = i + ; B[i].nx = i + ;
}
else if (i == n)
{
R[i].pre = i - ; G[i].pre = i - ; B[i].pre = i - ;
R[i].nx = ; G[i].nx = ; B[i].nx = ;
}
else
{
R[i].pre = i - ; G[i].pre = i - ; B[i].pre = i - ;
R[i].nx = i + ; G[i].nx = i + ; B[i].nx = i + ;
}
}
for (int i = ; i <= n; ++i)
{
arr[i].Get(); sum[i] = arr[i].v;
q.emplace(i, arr[i].id, sum[i]);
}
int cnt = ;
while (cnt < n)
{
Node tmp = q.top(); q.pop();
if (used[tmp.pos] || sum[tmp.pos] != tmp.v) continue;
++cnt; printf("%d\n", tmp.id); used[tmp.pos] = true;
se.clear(); arr[tmp.pos].Remove();
for (auto it : se)
{
arr[it].Get();
sum[it] = arr[it].v;
q.emplace(it, arr[it].id, sum[it]);
}
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run(); return ;
}
D - Distinctive Character
题意：给出n个玩家，有k个特征，用01串表示每个玩家有哪些特征，构造一个01串，和每个玩家对比有一个分数，有一个相同特征得一分，使得最大的分数最小
思路：可以将题意理解为有一个不同得一分，使得最小的分数最大。那么这时候可以用BFS跑一遍（类最短路？），然后找最大即可。
#include<bits/stdc++.h> using namespace std; const int maxn = << ; int n, k;
char str[];
int vis[maxn];
int dis[maxn]; inline void work(int x)
{
for(int i = k - ; i >= ; i--)
{
int u = << i;
if(u & x) cout << "";
else cout << "";
}
cout << endl;
} int main()
{
while(~scanf("%d %d", &n, &k))
{
memset(vis, , sizeof vis);
memset(dis, -, sizeof dis);
queue<int>q;
int tot = << k;
for(int i = ; i <= n; ++i)
{
scanf("%s", str);
int tmp = ;
for(int i = ; i < k; ++i)
{
tmp = tmp * + str[i] - '';
}
vis[tmp] = ;
}
for(int i = ; i < tot; ++i)
{
if(vis[i] == )
{
q.push(i);
dis[i] = ;
}
}
while(!q.empty())
{
int st = q.front();
q.pop();
for(int i = ; i < k; ++i)
{
int now = st ^ ( << i);
if(dis[now] == -)
{
// work(now);
dis[now] = dis[st] + ;
q.push(now);
}
}
}
int Max = -;
int ans = -;
for(int i = ; i < tot; ++i)
{
if(dis[i] > Max)
{
Max = dis[i];
ans = i;
}
}
for(int i = k - ; i >= ; --i)
{
int u = << i;
if(u & ans)
{
printf("");
}
else
{
printf("");
}
}
printf("\n");
}
return ;
}
E - Emptying the Baltic
细胞(油田)。变种
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define N 510 int n, m;
ll G[N][N];
ll val[N][N];
bool vis[N][N];
int dir[][] = {,,,,-,,,-,,,,-,-,-,-,}; struct node{
int x, y;
ll v;
inline node(){}
inline node(int x, int y, ll v) :x(x), y(y), v(v){}
inline bool operator < (const node & b)const
{
return v > b.v;
}
}; inline bool judge(int x, int y)
{
if(x > n || x < || y < || y > m || vis[x][y] || G[x][y] >= ) return false;
else return true;
} int x, y; inline void BFS()
{
memset(val, , sizeof val);
memset(vis, false, sizeof vis);
priority_queue<node>q;
q.push(node(x, y, G[x][y]));
vis[x][y] = true;
val[x][y] = G[x][y];
while(!q.empty())
{
node st = q.top();
q.pop();
for(int i = ; i < ; ++i)
{
int dx = st.x + dir[i][];
int dy = st.y + dir[i][];
if(judge(dx, dy))
{
ll tmp = max(G[dx][dy], st.v);
val[dx][dy] = tmp;
G[dx][dy] = tmp;
q.push(node(dx, dy, tmp));
vis[dx][dy] = true;
}
}
}
} int main()
{
while(~scanf("%d %d", &n, &m))
{
for(int i = ; i <= n; ++i)
{
for(int j = ; j <= m; ++j)
{
scanf("%lld", &G[i][j]);
if(G[i][j] >= )
{
G[i][j] = ;
}
}
}
scanf("%d %d", &x, &y);
BFS();
ll ans = ;
for(int i = ; i <= n; ++i)
{
for(int j = ; j <= m; ++j)
{
if(val[i][j] < )
{
ans += -val[i][j];
}
}
}
printf("%lld\n", ans);
}
return ;
}
F - Fractal Tree
留坑。
G - Galactic Collegiate Programming Contest
题意：给出ICPC过题记录，给出id为1的队伍的排名
思路：先hash, 离散化，数据结构维护一下
#include <bits/stdc++.h> using namespace std; #define N 100010
#define ll long long const ll D = (ll)1e9; int n, m, q;
ll arr[N], brr[N], sum[N], cnt; struct DT
{
int id;
ll v;
inline void scan()
{
scanf("%d%lld", &id, &v);
v = sum[id] + D - v;
sum[id] = v;
arr[++cnt] = v;
}
}Data[N]; inline void Init_Hash()
{
for (int i = ; i <= cnt; ++i) brr[i] = arr[i];
sort(brr + , brr + + cnt);
m = unique(brr + , brr + + cnt) - brr - ;
} inline int Get(ll x)
{
return lower_bound(brr + , brr + + m, x) - brr;
} struct node
{
int l, r;
int sum;
inline node() {}
inline node(int l, int r, int sum) : l(l), r(r), sum(sum) {}
}tree[N << ]; inline void pushup(int id)
{
tree[id].sum = tree[id << ].sum + tree[id << | ].sum;
} inline void build(int id, int l, int r)
{
tree[id] = node(l, r, );
if (l == r) return;
int mid = (l + r) >> ;
build(id << , l, mid);
build(id << | , mid + , r);
} inline void update(int id, int pos, int val)
{
if (tree[id].l == tree[id].r)
{
tree[id].sum += val;
return;
}
int mid = (tree[id].l + tree[id].r) >> ;
if (pos <= mid) update(id << , pos, val);
else update(id << | , pos, val);
pushup(id);
} int anssum; inline void query(int id, int l, int r)
{
if (l > r) return;
if (tree[id].l >= l && tree[id].r <= r)
{
anssum += tree[id].sum;
return;
}
int mid = (tree[id].l + tree[id].r) >> ;
if (l <= mid) query(id << , l, r);
if (r > mid) query(id << | , l, r);
} int main()
{
while (scanf("%d%d", &n, &q) != EOF)
{
int id; ll v;
memset(sum, , sizeof sum); cnt = ;
for (int i = ; i <= q; ++i) Data[i].scan();
Init_Hash();
memset(sum, , sizeof sum); build(, , q);
for (int i = ; i <= q; ++i)
{
int id = Data[i].id; int pos = Get(Data[i].v);
if (sum[id]) update(, sum[id], -);
update(, pos, ); sum[id] = pos;
anssum = ; query(, sum[] + , q);
printf("%d\n", anssum + );
}
}
return ;
}
H - Hubtown
留坑。
I - Import Spaghetti
题意：给出依赖关系，求最小的循环长度
思路：存图，枚举起点跑最短路
#include <bits/stdc++.h> using namespace std; #define N 100010
#define INF 0x3f3f3f3f unordered_map <string, int> mp;
int cnt, n;
string str[N], s;
vector <string> ans;
int Max, tot; inline int Get(string s)
{
if (mp.find(s) == mp.end()) mp[s] = ++cnt, str[cnt] = s;
return mp[s];
} struct Edge
{
int to, nx;
inline Edge() {}
inline Edge(int to, int nx) : to(to), nx(nx) {}
}edge[N << ]; int head[N], pos; inline void Init()
{
memset(head, -, sizeof head);
pos = ; cnt =; mp.clear(); ans.clear(); Max = INF;
} inline void addedge(int u, int v)
{
edge[++pos] = Edge(v, head[u]); head[u] = pos;
} int dist[N];
bool used[N];
int pre[N]; struct node
{
int to, w;
inline node() {}
inline node(int to, int w) : to(to), w(w) {}
inline bool operator < (const node &r) const
{
return w > r.w;
}
}; inline void Dijkstra(int root)
{
for (int i = ; i <= n; ++i) dist[i] = INF, used[i] = false, pre[i] = -;
priority_queue <node> q; q.emplace(root, );
while (!q.empty())
{
int u = q.top().to, w = q.top().w; q.pop();
used[u] = true;
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
if (w + < dist[v])
{
pre[v] = u;
dist[v] = w + ;
q.emplace(v, dist[v]);
}
}
}
} int main()
{
cin.tie(); cout.tie();
ios::sync_with_stdio(false);
while (cin >> n)
{
Init();
// cout << "bug\n";
for (int i = ; i <= n; ++i)
{
cin >> s; Get(s);
// cout << s << endl;
}
// cout << "bug\n";
for (int i = ; i <= n; ++i)
{
cin >> s >> tot;
int u = Get(s);
getline(cin, s);
while (tot--)
{
getline(cin, s);
// cout << s << endl;
stringstream ss;
ss << s;
while (ss >> s)
{
if (s == "import") continue;
if (s.end()[-] == ',') s.erase(s.end() - );
addedge(u, Get(s));
}
}
}
for (int i = ; i <= n; ++i)
{
Dijkstra(i);
if (dist[i] < Max)
{
Max = dist[i];
int it = pre[i];
ans.clear();
while (it != i)
{
ans.emplace_back(str[it]);
it = pre[it];
}
ans.emplace_back(str[i]);
}
}
if (Max == INF)
{
cout << "SHIP IT" << endl;
continue;
}
reverse(ans.begin(), ans.end());
for (int i = , len = ans.size(); i < len; ++i) cout << ans[i] << " \n"[i == len -];
}
return ;
}
J - Judging Moose
签到
#include <bits/stdc++.h> using namespace std; int a, b; int main()
{
while (scanf("%d%d", &a, &b) != EOF)
{
if (a == && b == )
puts("Not a moose");
else if (a == b)
{
printf("Even %d\n", a + b);
}
else
printf("Odd %d\n", max(a, b) * );
}
return ;
}
K - Kayaking Trip
题意：给出三种人，每种人有力量值，然后有(人数总和)/2 条皮划艇，一条皮划艇的速度为 $v = c_i(s_1 + s_2)$, 求如何分配人员，使得速度最小的皮划艇速度最大
思路：二分答案，贪心check
#include <bits/stdc++.h> using namespace std; #define N 100010
#define INF 0x3f3f3f3f int n[], s[], m, tmp[];
int arr[N]; struct node{
int x, y, v;
inline node() {}
inline node(int x, int y, int v) : x(x), y(y), v(v) {}
inline bool operator < (const node &b) const
{
return v < b.v;
}
}brr[]; int cnt; inline bool check(int mid)
{
for (int i = ; i < ; ++i) tmp[i] = n[i];
for (int i = ; i <= m; ++i)
{
bool flag = false;
for (int j = ; j <= cnt; ++j)
{
int x = brr[j].x, y = brr[j].y;
if (arr[i] * brr[j].v >= mid)
{
if (x == y)
{
if (tmp[x] >= )
{
tmp[x] -= ;
flag = true;
break;
}
}
else
{
if (tmp[x] >= && tmp[y] >= )
{
--tmp[x], --tmp[y];
flag = true;
break;
}
}
}
}
if (flag == false) return false;
}
return true;
} int main()
{
while (scanf("%d%d%d", &n[], &n[], &n[]) != EOF)
{
m = n[] + n[] + n[];
m >>= ;
for (int i = ; i < ; ++i) scanf("%d", s + i);
for (int i = ; i <= m; ++i) scanf("%d", arr + i);
cnt = ;
for (int i = ; i < ; ++i)
for (int j = i; j < ; ++j)
brr[++cnt] = node(i, j, s[i] + s[j]);
sort(brr + , brr + + cnt);
int l = , r = INF, ans;
while (r - l >= )
{
int mid = (l + r) >> ;
if (check(mid))
{
ans = mid;
l = mid + ;
}
else
{
r = mid - ;
}
}
printf("%d\n", ans);
}
return ;
}