A - Birthday Cake
题意：给出一个蛋糕，一些糖果的坐标，一些切割线的ax+by=c直线方程。问这些切割线是否能把蛋糕恰好分成n块且每一块有且仅有一块糖果。
B - Bumped!
Kattis - bumped
题意：有n (0<n≤50000)个城市，m(0≤m≤150000)条公路，f(0≤f≤1000)个航班，起点s，终点t。公路双向可通过，航班单向，且有一次机票免费的机会。城市从0开始编号。
思路：跑f+1遍dijkstra，每次放进去一个免费航班，取距离d[t]最小值。复杂度
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
int n, m, f, s, t;
const int maxn = 5e4+5;
const int maxm = 1e6+5;
const int maxf = 1005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct edge {
int to, cost;
};
vector<edge> g[maxn];
typedef pair<int, int> P;
ll d[maxn];
void dij() {
priority_queue<P, vector<P>, greater<P> > que;
for(int i = 0; i < n; ++i) {
d[i] = INF;
}
d[s] = 0;
que.push(make_pair(0, s));
int v;
while(!que.empty()) {
P pp = que.top();
que.pop();
v = pp.second;
for(int i = 0; i < g[v].size(); ++i) {
edge e = g[v][I];
if(d[v] + e.cost < d[e.to]) {
d[e.to] = d[v] + e.cost;
que.push(make_pair(d[e.to], e.to));
}
}
}
}
int main() {
int fr_, to_, cst_;
scanf("%d%d%d%d%d", &n, &m, &f, &s, &t);
for(int i = 0; i < m; ++i) {
scanf("%d%d%d", &fr_, &to_, &cst_);
g[fr_].push_back((edge){to_, cst_});
g[to_].push_back((edge){fr_, cst_});
}
dij();
ll ans = d[t];
//cout << ans << endl;
for(int i = 0; i < f; ++i) {
scanf("%d%d", &fr_, &to_);
g[fr_].push_back((edge){to_, 0});
dij();
ans = min(ans, d[t]);
g[fr_].erase(g[fr_].end()-1);
}
printf("%lld\n", ans);
return 0;
}
C - Canonical Coin Systems
Kattis - canonical
题意：有不同面值的硬币，若组成一种面额的贪心解即最优解，输出canonical，否则输出non-canonical。
如集合{1,3,4}，为了组成面值6，贪心解是4+1+1（3枚硬币），但最优解应该是3+3（2枚硬币）。
思路：队友做的，按照贪心解跑一遍结果，然后再用背包跑一遍最优解，比对，若有不同则为non。
AC代码：
# include <iostream>
# include <cstring>
using namespace std;
const int MAX = 1e6;
const int INF = 0x3f3f3f3f;
int n;
int dp[2][MAX * 2 + 20];
int coin[105];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
while(cin >> n)
{
for(int i = 0; i < n; I++)
{
cin >> coin[i];
}
bool right = true;
memset(dp, INF, sizeof(dp));
dp[0][0] = dp[1][0] = 0;
int maxn = 2 * coin[n - 1] + 10;
for(int i = 1, j; i < maxn; I++)
{
for(j = 0; j < n; j++)
{
if(coin[j] > i)
break;
dp[0][i] = min(dp[0][i], dp[0][i - coin[j]] + 1);
}
dp[1][i] = dp[1][i - coin[j - 1]] + 1;
if(dp[1][i] != dp[0][I])
{
right = false;
break;
}
}
if(right)
{
cout << "canonical" << endl;
}
else
{
cout << "non-canonical" << endl;
}
}
}
D - Cat and Mice
E - Company Picnic
题意：一颗树表示一个公司的上下级关系，现在这个公司要举行一次娱乐活动，两个人各自一条腿绑在一起跑步，那么两个人的速度就是那个跑得慢的人的速度，一个人只能和他的父节点或者子节点组成一组。现在要尽可能多的组成小组，并且让平均速度尽量大。输出组数和最大平均速度。
E - Company Picnic
思路：比赛最后一道题，想用KM匹配做来着，后来感觉不对，又暴的没暴出来。赛后看好像是树形dp。待补。
F - GlitchBot
Kattis - glitchbot
题意：一个机器人，从(0,0)点出发，初始朝向为y轴正方向，首先告诉你目标位置(x,y)，给你n条指令，Right是右转，Left左转，Forward朝前走。现在要改变一条指令使得机器人走到目标位置。
思路：模拟即可
# include <iostream>
# include <string>
using namespace std;
const int MAX = 60;
const int f = -1;
const int l = 0;
const int u = 1;
const int r = 2;
const int d = 3;
const int cx[] = {-1, 0, 1, 0};
const int cy[] = {0, 1, 0, -1};
int ex, ey, n;
struct Step
{
int oper;
int state;
int x, y;
};
Step step[MAX];
bool walk(int x, int y, int number, int state)
{
for(int i = number; i < n; I++)
{
if(step[i].oper == f)
{
x += cx[state];
y += cy[state];
}
else if(step[i].oper == r)
{
state = (state + 1) % 4;//顺时针
}
else
{
state = (state + 4 - 1) % 4;//逆时针
}
}
return (x == ex && y == ey);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string str;
while(cin >> ex >> ey)
{
cin >> n;
int x = 0, y = 0, state = u;
for(int i = 0; i < n; I++)
{
cin >> str;
step[i].x = x, step[i].y = y, step[i].state = state;
if(str == "Forward")
{
step[i].oper = f;
x += cx[state];
y += cy[state];
}
else if(str == "Right")
{
step[i].oper = r;
state = (state + 1) % 4;//顺时针
}
else
{
step[i].oper = l;
state = (state + 4 - 1) % 4;//逆时针
}
}
for(int i = 0; i < n; I++)
{
if(step[i].oper != f && walk(step[i].x + cx[step[i].state], step[i].y + cy[step[i].state], i + 1, step[i].state))
{
cout << i + 1 << " Forward" << endl;
break;
}
if(step[i].oper != l && walk(step[i].x, step[i].y, i + 1, (step[i].state + 4 - 1) % 4))
{
cout << i + 1 << " Left" << endl;
break;
}
if(step[i].oper != r && walk(step[i].x, step[i].y, i + 1, (step[i].state + 1) % 4))
{
cout << i + 1 << " Right" << endl;
break;
}
}
}
}
G - Greeting Card
题意：给出n个点的坐标，求在他们的连线中，有多少条的长度等于2018。
思路：先离线跑一遍三角形斜边恰好等于2018的情况，发现只有两种：a = 0, b = 2018 和 a = 1118, b = 1680 剩下的就是存下每个点，算出来他周围相距2018的点，若该点存在，cnt++
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
//0 2018
//1118 1680
long long cx[] = {0, 0, 2018, -2018, 1118, 1680, -1118, -1680, 1680, 1118, -1118, -1680};
long long cy[] = {2018, -2018, 0, 0, 1680, 1118, 1680, 1118, -1118, -1680, -1680, -1118};
typedef pair<long, long> P;
const int maxn = 100000 + 5;
long long x[maxn], y[maxn];
int main()
{
int n;
scanf("%d", &n);
set<P> st;
P p;
for(int i = 0; i < n; ++i) {
scanf("%d %d", &x[i], &y[I]);
p.first = x[I];
p.second = y[I];
st.insert(p);
}
long long sum = 0;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < 12; ++j) {
p.first = x[i] + cx[j];
p.second = y[i] + cy[j];
if(st.count(p)) {
++sum;
}
}
}
printf("%lld\n", sum / 2);
return 0;
}
H - Imperfect GPS
I - Odd Gnome
Kattis - oddgnome
题意：签到题。给出一个序列，寻找King，King不会藏在序列首部或尾部，而且除了King，其他人的ID都是满足严格上升的。输出King的位置
思路：按照题意模拟即可。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1005;
int a[maxn];
int main()
{
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[I]);
}
int flag = 0;
for(int i = 2; i <= n; ++i) {
if(a[i] == a[i-1]) {
flag = I;
break;
}
else if(a[i]<=a[i-1] && i >=3 && a[i]>a[i-2]) {
flag = i-1;
break;
}
else if(a[i]<=a[i-1] && a[i] <= a[i+1]) {
flag = I;
break;
}
}
if(flag == 0) {
printf("2\n");
}
else {
printf("%d\n", flag);
}
}
return 0;
}
J - Progressive Scramble
Kattis - progressivescramble
题意：给一个字符串，由空格和小写字母组成。先输入一个字母，‘e’表示加密，‘d’表示解密，后面跟的是待处理的字符串。
加密方式：前缀和%27
思路：简单模拟。这个水题发现的晚了，第三个小时才出
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
string s;
int main()
{
// freopen("in.txt", "r", stdin);
int n, len, pre, now, ans;
bool flag;
char ch;
cin >> n;
getchar();
while(n--) {
ch = getchar();
getchar();
getline(cin, s);
len = s.size();
if(ch == 'e') {
pre = s[0] == ' ' ? 0 : s[0] - 'a' + 1;
for(int i = 1; i < len; ++i) {
now = s[i] == ' ' ? 0 : s[i] - 'a' + 1;
pre += now;
//cout << pre << " ";
ans = pre % 27;
s[i] = ans == 0 ? ' ' : ans + 'a' - 1;
}
cout << s << endl;
}
else {
pre = s[0] == ' ' ? 0 : s[0] - 'a' + 1;
for(int i = 1; i < len; ++i) {
now = s[i] == ' ' ? 0 : s[i] - 'a' + 1;
for(int k = 0; ; ++k) {
now += 27 * k;
if(now >= pre) {
ans = (now - pre) % 27;
s[i] = ans == 0 ? ' ' : ans + 'a' - 1;
//cout << ans << endl;
pre += ans;
break;
}
}
}
cout << s << endl;
}
}
return 0;
}
网友评论