2019CCPC秦皇岛赛区（重现赛）AEK 题解

A. Angle Beats

题意：给定2000个二维点，有2000次查询，每次查询(x，y)问有多少种方案从点集中选出两个点能和(x，y)组成直角三角形

解法：我们离线一下，假设点集选择的点是$A，B$，查询的点是$C$，分两种情况。

第一种情况：$CA$垂直$AB$，那我们可以预处理所有以$A$为起点的斜率，然后查询时根据斜率$CA$推出我们所需要的斜率，我们可以把所有的$C_i$需要的斜率排序，所有的$A{B}_i$排好序，然后双指针一次性求出以$A{B}_i$为直角边对询问的总贡献。

第二种情况：$AC$垂直$BC$，我们枚举每个查询点$C$，存好所有$A_{i}C、B_{i}C$斜率，同时用另外一个数组存好与他们垂直的斜率，排好序，再一次双指针求出点集所有点对点$C$的贡献。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2001;
struct node {
int x, y, id;
bool operator < (const node &t) const {
if (x == t.x)
return y < t.y;
return x < t.x;
};
bool operator == (const node& t) const {
if (x == t.x && y == t.y)
return 1;
return 0;
}
};
node A[maxn], B[maxn], AA[maxn], BB[maxn];
int cnt[maxn], d[maxn], inf = 2e9 + 1;
int X[maxn], Y[maxn], ans[maxn], XX[maxn], YY[maxn];
node gao(int x, int y, int id) {
if (!x)
return node{0, inf, id};
if (!y)
return node{0, 0, id};
int gcd = __gcd(x, y);
x /= gcd, y /= gcd;
if (x < 0)
x = -x, y = -y;
return node{x, y, id};
}
int calc(int n) {
int P = 1, res = 0;
for (int i = 1; i <= n; i++) {
d[i] = 0;
while (P <= n && BB[P] < AA[i])
P++;
if (i > 1 && AA[i] == AA[i - 1])
d[i] = d[i - 1];
else
while (P <= n && AA[i] == BB[P])
d[i]++, P++;
res += d[i];
}
return res;
}
int main() {
int n, q, x, y;
while (~scanf("%d%d", &n, &q)) {
for (int i = 1; i <= n; i++)
scanf("%d%d", &X[i], &Y[i]);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &XX[i], &YY[i]);
for (int j = 1; j <= n; j++) {
int tx = XX[i] - X[j];
int ty = YY[i] - Y[j];
int ttx = tx, tty = ty;
AA[j] = gao(ttx, tty, 0);
if (!tx)
BB[j] = gao(1, 0, i);
else if (!ty)
BB[j] = gao(0, 1, i);
else
BB[j] = gao(-ty, tx, i);
}
sort(AA + 1, AA + 1 + n);
sort(BB + 1, BB + 1 + n);
ans[i] = calc(n) / 2;
}
for (int i = 1; i <= n; i++) {
int tot = 0;
for (int j =1; j <= n; j++)
if (i != j)
A[++tot] = gao(X[i] - X[j], Y[i] - Y[j], 0);
sort(A + 1, A + 1 + tot);
int sz = 0;
for (int j = 1; j < n; j++)
if (A[j] == A[j - 1] && j > 1)
cnt[sz]++;
else
cnt[++sz] = 1;
unique(A + 1, A + 1 + tot);
for (int j = 1; j <= q; j++) {
int tx = XX[j] - X[i];
int ty = YY[j] - Y[i];
if (!tx)
B[j] = gao(1, 0, j);
else if (!ty)
B[j] = gao(0, 1, j);
else
B[j] = gao(-ty, tx, j);
}
sort(B + 1, B + 1 + q);
int P = 1, Q = 1;
while (P <= sz && Q <= q) {
int cur = B[Q].id;
if (A[P] == B[Q])
ans[cur] += cnt[P], Q++;
else
if (A[P] < B[Q])
P++;
else
Q++;
}
}
for (int i = 1; i <= q; i++)
printf("%dn", ans[i]);
}
}

E.Escape

题意：中文题面有写

解法：仔细分析我们发现每个点水平方向上至多只有一个机器人能走，竖直方向也是如此，那我们对每个点拆为四个点水平入点，水平出点，竖直入点，竖直出点，入点全部连接对应出点，限流为1，对于左右相邻的两个合法点，把他们水平入点出点互相连接，对于上下相邻的两个合法点，把他们竖直入点出点互相连接，接下来将转弯，仔细分析，如果加了转弯操作，至多必定只能有一个机器人经过该点，因此我们只要将水平出点连接竖直入点，竖直入点连接水平出点即可，建完图跑最大流，如果最大流等于机器人数量就okk，否则就不行

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 100 * 100 * 4 + 210, inf = 1e9;
struct Edge
{
int from,to,cap,flow;
};
struct Dinic
{
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vis[maxn];
int d[maxn],cur[maxn];
void init(int n)
{
this->n=n;
for(int i=0;i<n;i++)
G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back((Edge){from,to,cap,0});
edges.push_back((Edge){to,from,0,0});
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool bfs()
{
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty())
{
int x=Q.front();Q.pop();
for(int i=0;i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a)
{
if(x==t||a==0)return a;
int flow=0,f;
for(int& i=cur[x];i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)break;
}
}
return flow;
}
int Maxflow(int s,int t)
{
this->s=s,this->t=t;
int flow=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
flow+=dfs(s,inf);
}
return flow;
}
} cat;
char s[101][101];
int n, m;
int id(int x, int y, int opt) {
return ((x - 1) * m + (y - 1)) * 4 + opt;
}
void link(int x1, int y1, int x2, int y2) {
if (x1 + 1 != x2) {
cat.AddEdge(id(x1, y1, 2), id(x2, y2, 1), 1);
cat.AddEdge(id(x2, y2, 2), id(x1, y1, 1), 1);
}
else {
cat.AddEdge(id(x1, y1, 4), id(x2, y2, 3), 1);
cat.AddEdge(id(x2, y2, 4), id(x1, y1, 3), 1);
}
}
string solve() {
int a, b, x;
scanf("%d%d%d%d", &n, &m, &a, &b);
cat.init(n * m * 4 + a + b + 3);
int S = 0, T = n * m * 4 + a + b + 1;
for (int i = 1; i <= n; i++) {
scanf("%s", s[i] + 1);
for (int j = 1; j <= m; j++) {
if (s[i][j] == '1')
continue;
if (i != 1 && s[i - 1][j] == '0')
link(i - 1, j, i, j);
if (j != 1 && s[i][j - 1] == '0')
link(i, j - 1, i, j);
// 1,2,3,4 分别表示水平水平入点，水平出点，竖直入点，竖直出点
cat.AddEdge(id(i, j, 1), id(i, j, 2), 1);
cat.AddEdge(id(i, j, 2), id(i, j, 3), 1);
cat.AddEdge(id(i, j, 3), id(i, j, 4), 1);
cat.AddEdge(id(i, j, 4), id(i, j, 1), 1);
}
}
int tot = n * m * 4;
for (int i = 1; i <= a; i++) {
scanf("%d", &x);
cat.AddEdge(++tot, id(1, x, 3), 1);
cat.AddEdge(S, tot, 1);
}
for (int i = 1; i <= b; i++) {
scanf("%d", &x);
cat.AddEdge(id(n, x, 4), ++tot, 1);
cat.AddEdge(tot, T, 1);
}
int ans = cat.Maxflow(S, T);
if (ans != a)
return "No";
else
return "Yes";
}
int main() {
int T;
scanf("%d", &T);
while (T--)
cout<<solve()<<'n';
}

L. MUV LUV UNLIMITED

解法：

1.整棵树是一条链的情况，长度为奇数okk，否则不行

2.存在一个叶子节点它的父亲出度大于1，一定okk。反证法，假设先手去掉了这个叶子，后手可以选择一些叶子集合$S$导致必胜，由于去掉这个叶子并没有产生新的叶子，那么先手一定可以去掉这个叶子的同时也去掉$S$

3.所有叶子父亲出度都为1，我们沿着所有叶子往上走，找到第一个出度大于1的节点，记录路径长度，若所有路径长度均为偶数，那先手必败。证明：情况2先手必胜的策略就是叶子距第一个出度大于1的节点长度为1，由于所有路径长度为偶数，那么一定是后手先遇到情况2。如果存在一些路径长度为奇数，一定先手必胜，因为先手可以把所有路径为奇数的叶子去掉，把它变成先手必败态。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 5;
int f[maxn], d[maxn];
string s[2] = { "Meiya", "Takeru"};
string solve() {
int n, u, v;
d[0] = 2;
f[0] = -1;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
f[i] = d[i] = 0;
for (int i = 2; i <= n; i++) {
scanf("%d", &u);
d[u]++;
f[i] = u;
}
int okk = 0;
for (int i = 1; i <= n && !okk; i++)
if (!d[i]) {
if (d[f[i]] > 1)
okk = 1;
int len = -1, v = i, cnt = 0;
while (v != -1 && d[v] <= 1) {
v = f[v];
cnt++;
if (d[v] > 1)
len = cnt;
}
if (len > 0 && len % 2)
okk = 1;
}
return s[okk];
}
int main() {
int T;
scanf("%d", &T);
while (T--)
cout<<solve()<<'n';
}

最后

以上就是笨笨过客为你收集整理的2019CCPC秦皇岛赛区（重现赛）AEK 题解的全部内容，希望文章能够帮你解决2019CCPC秦皇岛赛区（重现赛）AEK 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。