A Tobaku Mokushiroku Kaiji
水。
#include <bits/stdc++.h>
using namespace std; int a[], b[]; void Run()
{
while (scanf("%d", a) != EOF)
{
for (int i = ; i < ; ++i) scanf("%d", a + i);
for (int i = ; i < ; ++i) scanf("%d", b + i);
printf("%d\n", min(a[], b[]) + min(a[], b[]) + min(a[], b[]));
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
B Attack on Titan
留坑。
C Utawarerumono
思路：好像暴力就能过。
#include <bits/stdc++.h>
using namespace std;
using ll = long long; ll a, b, c, p1, p2, q1, q2; int main()
{
while (scanf("%lld%lld%lld", &a, &b, &c) != EOF)
{
scanf("%lld%lld", &p1, &p2);
scanf("%lld%lld", &q1, &q2);
ll res = 0x3f3f3f3f3f3f3f3f;
for (ll x = -; x <= ; ++x)
{
if ((c - a * x) % b) continue;
ll y = (c - a * x) / b;
res = min(res, p2 * x * x + p1 * x + q2 * y * y + q1 * y);
}
if (res == 0x3f3f3f3f3f3f3f3f)
{
puts("Kuon");
continue;
}
printf("%lld\n", res);
}
return ;
}
D Love Live!
思路：将边按权值从小到大排序，一条一条往里加，每加入一条边要合并两个联通块，用并查集维护，然后开n棵trie树维护异或最大，简单路径上的异或和可以理解为两个点到根节点的前缀异或再异或，合并的时候启发式合并，查询的时候一定要经过那条边，那就是用一个联通块里的元素查找在另一个联通块对应的trie树里面查找，启发式查找
#include <bits/stdc++.h>
using namespace std; #define N 100010 struct Edge
{
int u, v, nx, w;
Edge() {}
Edge(int u, int v, int nx, int w) : u(u), v(v), nx(nx), w(w) {}
Edge(int u, int v, int w) : u(u), v(v), w(w) {}
bool operator < (const Edge &r) const
{
return w < r.w;
}
}edge[N << ], G[N]; int n;
int head[N], pos;
int prefix[N], fa[N], sz[N];
vector <int> v[N]; void addedge(int u, int v, int w)
{
edge[++pos] = Edge(u, v, head[u], w); head[u] = pos;
} void DFS(int u, int fa)
{
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].v;
if (v == fa) continue;
prefix[v] = prefix[u] ^ edge[it].w;
DFS(v, u);
}
} struct TRIE
{
int cnt;
int T[N];
struct node
{
int son[];
node()
{
memset(son, , sizeof son);
}
}a[N * ]; void Init()
{
cnt = n + ;
} void Insert(int root, int x)
{
bitset <> b; b = x;
for (int i = ; i >= ; --i)
{
if (!a[root].son[b[i]])
a[root].son[b[i]] = ++cnt;
root = a[root].son[b[i]];
}
} int query(int root, int x)
{
bitset <> b; b = x;
int res = ;
for (int i = ; i >= ; --i)
{
int id = b[i] ^ ;
bool flag = true;
if (!a[root].son[id])
{
flag = false;
id ^= ;
}
if (flag) res += << i;
root = a[root].son[id];
}
return res;
}
}trie; int find(int x)
{
if (x != fa[x])
fa[x] = find(fa[x]);
return fa[x];
} void Init()
{
memset(head, -, sizeof head); pos = ;
prefix[] = ;
trie.Init();
} void Run()
{
while (scanf("%d", &n) != EOF)
{
Init();
for (int i = , u, v, w; i < n; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
addedge(v, u, w);
G[i] = Edge(u, v, w);
}
DFS(, );
for (int i = ; i <= n; ++i)
{
fa[i] = i;
sz[i] = ;
trie.T[i] = i;
trie.Insert(trie.T[i], prefix[i]);
v[i].push_back(prefix[i]);
}
sort(G + , G + n);
for (int i = ; i < n; ++i)
{
int x = G[i].u, y = G[i].v;
int fx = find(x), fy = find(y);
if (sz[fx] > sz[fy]) swap(x, y), swap(fx, fy);
int res = ;
for (auto it : v[fx])
{
res = max(res, trie.query(trie.T[fy], it));
}
for (auto it : v[fx])
{
trie.Insert(trie.T[fy], it);
v[fy].push_back(it);
}
printf("%d%c", res, " \n"[i == n - ]);
fa[fx] = fy;
sz[fy] += sz[fx];
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
E Eustia of the Tarnished Wings
思路：排序，然后贪心合并即可
#include <bits/stdc++.h>
using namespace std; #define N 1000010 int n, m;
int arr[N]; void Run()
{
while (scanf("%d%d", &n, &m) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
sort(arr + , arr + + n);
int res = ;
for (int i = ; i <= n; ++i) if (arr[i] - arr[i - ] > m)
++res;
printf("%d\n", res);
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
F Baldr Sky
留坑。
G Kimi to Kanojo to Kanojo no Koi
留坑。
H One Piece
留坑。
I Steins;Gate
留坑。
J Princess Principal
思路：用栈维护括号序列
其实假设存在合法文档 那么每一个括号都有一个唯一的对应括号
比如说 (()) 肯定是中间两个匹配，再外面两个匹配
那么我们直接用栈维护一下，找到每个左括号的右匹配，以及找到每个有括号的左匹配，然后RMQ倍增维护最括号的最大右匹配，右括号的最小左匹配，如果最大值超过r 或者 最小值小于l 那么是不合法的
还有一种情况 就是 ([) 那么这三个括号都是不合法的
#include <bits/stdc++.h>
using namespace std; #define N 1000010
#define INF 0x3f3f3f3f int n, m, q;
int arr[N], L[N], R[N];
int mm[N];
stack <int> sta; void Init()
{
mm[] = -;
for (int i = ; i <= n; ++i)
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
} struct RMQ
{
int dp[N][]; // 1 max 0 min
void Init(int n, int b[], int vis)
{
for (int i = ; i <= n; ++i)
dp[i][] = b[i];
for (int j = ; j <= mm[n]; ++j)
for (int i = ; i + ( << j) - <= n; ++i)
{
if (vis)
dp[i][j] = max(dp[i][j - ], dp[i + ( << (j - ))][j - ]);
else
dp[i][j] = min(dp[i][j - ], dp[i + ( << (j - ))][j - ]);
}
} int query(int x, int y, int vis)
{
int k = mm[y - x + ];
if (vis)
return max(dp[x][k], dp[y - ( << k) + ][k]);
else
return min(dp[x][k], dp[y - ( << k) + ][k]);
}
}rmq[]; bool ok(int x, int y)
{
if (rmq[].query(x, y, ) < x) return false;
if (rmq[].query(x, y, ) > y) return false;
return true;
} void Run()
{
while (scanf("%d%d%d", &n, &m, &q) != EOF)
{
memset(L, -, sizeof L);
memset(R, 0x3f, sizeof R);
for (int i = ; i <= n; ++i) scanf("%d", arr + i);
for (int i = ; i <= n; ++i)
{
if (arr[i] & )
{
if (!sta.empty())
{
int top = sta.top(); sta.pop();
if (arr[i] / == arr[top] / ) L[i] = top;
}
}
else
sta.push(i);
}
while (!sta.empty()) sta.pop();
for (int i = n; i >= ; --i)
{
if (arr[i] % == )
{
if (!sta.empty())
{
int top = sta.top(); sta.pop();
if (arr[i] / == arr[top] / ) R[i] = top;
}
}
else
sta.push(i);
}
for (int i = ; i <= n; ++i)
{
if (arr[i] & ) R[i] = -;
else L[i] = INF;
}
Init();
rmq[].Init(n, L, );
rmq[].Init(n, R, );
for (int i = , x, y; i <= q; ++i)
{
scanf("%d%d", &x, &y);
puts(ok(x, y) ? "Yes" : "No");
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
K Tengen Toppa Gurren Lagann
留坑。
L New Game!
思路：分别处理 直线到圆的最短距离，圆到圆的最短距离，直线到直线的最短距离，然后跑最短路即可
#include <bits/stdc++.h>
using namespace std; #define N 1010
#define INF 0x3f3f3f3f const double eps = 1e-; int sgn(double x)
{
if (fabs(x) < eps) return ;
if (x < ) return -;
else return ;
} struct Point
{
double x, y;
Point() {}
Point(double _x, double _y)
{
x = _x; y = _y;
}
double operator ^(const Point &b) const { return x * b.y - y * b.x; }
double distance(Point p) { return hypot(x - p.x, y - p.y); }
Point operator - (const Point &b) const { return Point(x - b.x, y - b.y); }
}; struct Line
{
Point s, e;
Line() {}
Line(double a, double b, double c)
{
if (sgn(a) == )
{
s = Point(, -c / b);
e = Point(, -c / b);
}
else if (sgn(b) == )
{
s = Point(-c / a, );
e = Point(-c / a, );
}
else
{
s = Point(, -c / b);
e = Point(, (-c - a) / b);
}
}
double length() { return s.distance(e); }
double dispointtoline(Point p) { return fabs((p - s) ^ (e - s)) / length(); }
}L[]; struct circle
{
Point p;
double r;
circle() {}
circle(double x, double y, double _r)
{
p = Point(x, y);
r = _r;
}
}arr[N]; int n, A, B, C1, C2;
double x, y, r;
double G[N][N]; void work0(int x, int y)
{
double dis = arr[x].p.distance(arr[y].p);
G[x][y] = max(0.0, dis - arr[x].r - arr[y].r);
G[y][x] = G[x][y];
} void work1(int x, int y)
{
double dis = L[x].dispointtoline(arr[y].p);
G[x][y] = max(0.0, dis - arr[y].r);
G[y][x] = G[x][y];
} double dis[N];
bool used[N]; void Dijkstra ()
{
for (int i = ; i <= n + ; ++i) dis[i] = INF * 1.0, used[i] = false;
dis[] = ;
for (int j = ; j <= n + ; ++j)
{
int k = -;
double Min = INF * 1.0;
for (int i = ; i <= n + ; ++i)
{
if (!used[i] && dis[i] < Min)
{
Min = dis[i];
k = i;
}
}
used[k] = ;
for (int i = ; i <= n + ; ++i)
if (!used[i] && dis[k] + G[k][i] < dis[i])
dis[i] = dis[k] + G[k][i];
}
} void Run()
{
while (scanf("%d%d%d%d%d", &n, &A, &B, &C1, &C2) != EOF)
{
memset(G, 0x3f, sizeof G);
L[] = Line(A, B, C1);
L[] = Line(A, B, C2);
for (int i = ; i <= n + ; ++i)
{
scanf("%lf%lf%lf", &x, &y, &r);
arr[i] = circle(x, y, r);
G[i][i] = ;
}
for (int i = ; i <= n + ; ++i)
for (int j = i + ; j <= n + ; ++j)
work0(i, j);
for (int i = ; i < ; ++i)
for (int j = ; j <= n + ; ++j)
work1(i, j);
G[][] = abs(C1 - C2) / sqrt(A * A + B * B);
G[][] = G[][];
Dijkstra();
printf("%.10f\n", dis[]);
}
} int main()
{
Run();
return ;
}