训练时间：2019-04-05
一场读错三个题，队友恨不得手刃了我这个坑B。
A I J 简单，不写了。
C - Cleaning Pipes (Gym - 101485C)
对于有公共点的管道建边，然后染色判是否是二分图。
注意线段判相交的时候，除了两个线段交于起点之外，都要视为相交。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = + ;
const double eps = 1e-; int dcmp(double x)
{
if (x > eps) return ;
return x < -eps ? - : ;
} struct Point
{
double x, y;
Point() {}
Point(double _x, double _y) { x = _x, y = _y; }
Point operator - (const Point &b) const
{
return Point(x-b.x, y-b.y);
} bool operator == (const Point& b) const
{
return dcmp(x - b.x) == && dcmp(y - b.y) == ;
}
};
typedef Point Vector;
struct Seg
{
Point st, ed;
Seg() {};
Seg(Point a, Point b) { st = a, ed = b; }
}; double Cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }
double Dot(Vector a, Vector b) { return a.x*b.x + a.y*b.y; } bool OnSegment(Point p, Point a1, Point a2)
{
return dcmp(Cross(a1-p, a2-p)) == && dcmp(Dot(a1-p, a2-p)) < ;
} bool SegmentIntersection(Point a1, Point a2, Point b1, Point b2)
{
if (a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2) return true; if (OnSegment(a1, b1, b2) || OnSegment(a2, b1, b2)
|| OnSegment(b1, a1, a2) || OnSegment(b2, a1, a2)) return true; double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1),
c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
} vector<int> v[maxn];
int vis[maxn]; void build(int x, int y)
{
v[x].push_back(y); v[y].push_back(x);
} bool dfs(int x)
{
for (int y : v[x])
{
if (vis[y] == vis[x]) return false;
if (vis[y] == -)
{
vis[y] = !vis[x];
if (!dfs(y)) return false;
}
}
return true;
} Point st[maxn];
Seg s[maxn];
int n, p;
int main()
{
scanf("%d%d", &n, &p);
for (int i = ; i <= n; i++) scanf("%lf%lf", &st[i].x, &st[i].y);
for (int i = ; i <= p; i++)
{
double x, y;
int id;
scanf("%d%lf%lf", &id, &x, &y);
s[i] = Seg(st[id], Point(x, y));
} for (int i = ; i <= p; i++)
for (int j = i+; j <= p; j++)
{
if (s[i].st == s[j].st) continue;
if (SegmentIntersection(s[i].st, s[i].ed, s[j].st, s[j].ed)) build(i, j);
} memset(vis, -, sizeof(vis)); for (int i = ; i <= p; i++)
if (vis[i] == -)
{
vis[i] = ;
if (!dfs(i)) return printf("impossible\n"), ;
} printf("possible\n");
}
D - Debugging (Gym - 101485D)
对于任何一个n行的代码块，可以由长度为n/2 n/3 n/4 ... n/n的代码块的答案更新。所以可以用dp做。
然而这个题没找到很好的递推顺序，窃以为递推为O(n^2)的。
如有合理递推方式，欢迎并感激指出！
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6 + ;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-; LL dp[maxn]; int n, r, p; LL d(int n)
{
if (n == ) return ;
if (dp[n] != INF) return dp[n];
for (int i = ; i < n; i++)
dp[n] = min(dp[n], d( (int)ceil(1.0*n/(i+)) )+1ll*p*i+r);
return dp[n];
} int main()
{
scanf("%d%d%d", &n, &r, &p);
for (int i = ; i <= n; i++) dp[i] = INF;
printf("%lld\n", d(n));
}
E - Elementary Math (Gym - 101485E)
把每组数字三种运算的结果计算出来，然后把结果和每组数字做一下二分图匹配。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = * + ;
const int maxm = * + ; int n;
map<LL, int> M;
LL x[maxn], y[maxn];
LL tmp[maxn];
int v[maxm], last[maxm], nxt[maxm];
int lnk[maxn], vis[maxn], ans[maxn];
int cnt, tot; void build(int x, int y)
{
++tot;
v[tot] = y;
nxt[tot] = last[x];
last[x] = tot;
} bool dfs(int x)
{
for (int i = last[x]; i; i = nxt[i])
{
int y = v[i];
if (!vis[y])
{
vis[y] = ;
if (lnk[y] == - || dfs(lnk[y]))
{
lnk[y] = x;
ans[x] = y;
return true;
}
}
}
return false;
} int hungary()
{
int res = ;
memset(lnk, -, sizeof(lnk));
for (int i = ; i <= n; i++)
{
memset(vis, , sizeof(vis));
if (dfs(i)) res++;
}
return res;
} char get(LL sum, int id)
{
if (sum == x[id] + y[id]) return '+';
if (sum == x[id] - y[id]) return '-';
if (sum == x[id] * y[id]) return '*';
} int main()
{
scanf("%d", &n);
cnt = n;
for (int i = ; i <= n; i++)
{
scanf("%lld%lld", &x[i], &y[i]);
LL a = x[i] + y[i], b = x[i] - y[i], c = x[i] * y[i]; if (!M.count(a)) M[a] = ++cnt;
build(i, M[a]); tmp[M[a]] = a; if (!M.count(b)) M[b] = ++cnt;
build(i, M[b]); tmp[M[b]] = b; if (!M.count(c)) M[c] = ++cnt;
build(i, M[c]); tmp[M[c]] = c;
} if (hungary() != n) return printf("impossible\n"), ; for (int i = ; i <= n; i++)
printf("%lld %c %lld = %lld\n", x[i], get(tmp[ans[i]], i), y[i], tmp[ans[i]]);
}
G - Guessing Camels (Gym - 101485G)
求一个三位偏序。
CDQ分治裸题，然而我不会。
看题解发现可以两两求二维偏序求出不合法的数目来，然后用总数目减去不合法数目。
二维偏序可以把一个序列的先后顺序映射到另一个中，然后求逆序对。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + ; int n;
int a[maxn], b[maxn], c[maxn];
int T[maxn], A[maxn];
LL cnt = ; void merge_sort(int x, int y)
{
if (y-x > )
{
int m = x + (y-x)/;
int p = x, q = m, i = x;
merge_sort(x, m);
merge_sort(m, y);
while(p < m || q < y)
{
if (q >= y || (p < m && A[p] <= A[q])) T[i++] = A[p++];
else T[i++] = A[q++], cnt += m-p;
}
for (i = x; i < y; i++) A[i] = T[i];
}
} void mapping(int a[], int b[])
{
int m[maxn];
for (int i = ; i <= n; i++) m[a[i]] = i;
for (int i = ; i <= n; i++) A[i] = m[b[i]];
merge_sort(, n+);
} int main()
{
scanf("%d", &n);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i <= n; i++) scanf("%d", &b[i]);
for (int i = ; i <= n; i++) scanf("%d", &c[i]); mapping(a, b);
mapping(a, c);
mapping(b, c); printf("%lld\n", (1ll * n * (n-) - cnt) / );
}