20160730 训练记录
1.point
【题目大意】
求一个凸多边形内部（包括边界）的点，使得这个点到n个点的距离平方和最小。给定n个点的坐标以及凸多边形m个点的坐标。
$ n \leq 10^5, m \leq 5 \times 10^3$
【题解】
很明显推推公式我们发现，当点在(px, py)时，距离和最小，其中px为这n个点x坐标平均值，py为y坐标平均值。
那么我们判断这个点是否在凸多边形内
如果不在，我们求这个点到凸多边形各条边的距离，取最小值。那么所交的点即为最终答案的点。
# include <stdio.h>
# include <cmath>
# include <algorithm>
using namespace std;
const long double eps = 1e-10, meps = -eps;
int X, Y;
struct points {
long double x, y;
points () {}
points (double _X, double _Y) : x(_X), y(_Y) {}
points operator - (points A) {
return points(x - A.x, y - A.y);
}
long double operator * (points A) {
return x * A.y - y * A.x;
}
}p[100010], q[6060], pnt, pnt2;
int n, m;
long double sx, sy;
long double dist = 1e90;
inline long double sqr(long double x) {
return x*x;
}
inline long double getdis(points a, points b) {
return sqr(a.x - b.x) + sqr(a.y - b.y);
}
inline long double ldmin(long double a, long double b) {
return a<b?a:b;
}
inline long double ldabs(long double x) {
return x<0?-x:x;
}
inline bool iszero(long double x) {
return fabs(x) < eps;
}
int main() {
freopen("point.in", "r", stdin);
freopen("point.out", "w", stdout);
sx = 0, sy = 0;
scanf("%d", &n);
for (int i=1; i<=n; ++i) {
scanf("%d%d", &X, &Y);
p[i].x = (long double)X, p[i].y = (long double)Y;
sx = sx + X, sy = sy + Y;
}
scanf("%d", &m);
for (int i=1; i<=m; ++i) {
scanf("%d%d", &X, &Y);
q[i].x = (long double)X, q[i].y = (long double)Y;
}
pnt.x = 1.0 * sx / n; pnt.y = 1.0 * sy / n;
bool ok=1;
for (int i=1; i<=m; ++i) {
int next = i%m+1;
double res = (q[i] - q[next]) * (pnt - q[next]);
if(res < 0) {
ok=0;
break;
}
}
if(ok) {
long double S = 0;
for (int i=1; i<=n; ++i)
S += getdis(pnt, p[i]);
printf("%.10lf\n", (double)S);
} else {
for (int i=1; i<=m; ++i) {
int next = i%m+1;
points a = q[i], b = q[next];
long double A = getdis(a, pnt), B = getdis(b, pnt), C = getdis(a,b);
if(A >= B+C || B >= A+C) {
if(A < dist) dist = A, pnt2 = a;
if(B < dist) dist = B, pnt2 = b;
continue;
}
points pnt3;
if(iszero(a.x - b.x)) {
pnt3.y = pnt.y;
pnt3.x = a.x;
} else if(iszero(a.y - b.y)) {
pnt3.x = pnt.x;
pnt3.y = a.y;
} else {
long double kx = (b.y - a.y) / (b.x - a.x), ky = (-1.0)/kx;
long double bx = a.y - kx * a.x, by = pnt.y - ky * pnt.x;
pnt3.x = (by - bx) / (kx - ky);
pnt3.y = kx * pnt3.x + bx;
}
long double Dist = getdis(pnt3, pnt);
if(Dist < dist) {
dist = Dist;
pnt2 = pnt3;
}
}
long double S = 0;
for (int i=1; i<=n; ++i)
S += getdis(pnt2, p[i]);
printf("%.10lf\n", (double)S);
}
return 0;
}
2.table
【题目大意】
给出一个n*m只包含01的矩阵，给出一个数k。
求当改变次数不超过k的时候，最少花多少次改变能使得这个矩阵的任意一个0或1的极大联通块都是矩形。改变意为，把一个元素0变为1,1变为0.
多组数据，$ T \leq 50, n,m \leq 100, k \leq 10$
【题解】
观察到k很小，那么我们假设k<n，那么一定有一行没有被改变。我们枚举哪一行没有被改变，然后往上往下贪心寻找（因为要使得极大连通块为矩形，第i行和枚举的那行要么相等要么互反）即可。如果k>=n那么我们枚举第一行的情况贪心往下推也可以
时间复杂度$O(n^3)$或$O(n^2 \times n!)$
# include <stdio.h>
# include <algorithm>
# include <iostream>
using namespace std;
int T, n, m, K, map[110][110], mp2[110][110], ans;
int a[110];
inline void greedy() {
int cur = 0;
for (int i=1; i<=m; ++i)
cur += (a[i] != map[1][i]);
if(cur > K || cur > ans) return ;
for (int i=2; i<=n; ++i) {
int s1=0, s2=0;
for (int j=1; j<=m; ++j)
s1 += (map[i][j] != a[j]), s2 += (map[i][j] == a[j]);
cur += min(s1, s2);
}
if(cur < ans)
ans = cur;
}
inline void dfs(int step, int end) {
if(step == end+1) {
greedy();
return ;
}
a[step] = 1;
dfs(step+1, end);
a[step] = 0;
dfs(step+1, end);
}
int main() {
freopen("table.in", "r", stdin);
freopen("table.out", "w", stdout);
scanf("%d", &T);
while(T--) {
ans = 0x7fffffff;
scanf("%d%d%d", &n, &m, &K);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
scanf("%d", &map[i][j]);
if (n < m) {
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
mp2[j][i] = map[i][j];
swap(n, m);
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
map[i][j] = mp2[i][j];
}
if (n > K) {
for (int i=1; i<=n; ++i) {
int cur = 0;
for (int j=1; j<=n; ++j) {
int s1=0, s2=0;
for (int k=1; k<=m; ++k)
s1 += (map[j][k] != map[i][k]);
for (int k=1; k<=m; ++k)
s2 += (map[j][k] == map[i][k]);
cur += min(s1, s2);
}
if(cur < ans) ans = cur;
}
if(ans != 0x7fffffff && ans <= K) printf("%d\n", ans);
else puts("-1");
} else {
dfs(1, m);
if(ans != 0x7fffffff && ans <= K) printf("%d\n", ans);
else puts("-1");
}
}
return 0;
}
3. company
【题目大意】
zy有一个公司，有n个员工，m条指令。一开始所有员工没有上级。
指令分为：
1. 1 x y：使y成为x的直接上司（保证之前x没有直接上司），且关系不构成环。
2. 2 x：zy发给员工x一份文件，员工x阅读完会传给他的直接上司阅读，他的直接上司阅读完会继续往上传，以此类推。
3. 3 x i：询问第i份文件是否被第x个人阅读过。
$ n \leq 2 \times 10^5, m \leq 4 \times 10^5$
【题解】
很明显离线处理
我们发现询问结果为YES，只有可能是满足下列两个条件
1. 在第i份文件传下去的时刻，传下去的人y和被询问的人x联通
2. 被询问的人x是传下去的人y的上司
第一个关系我们用并查集维护即可。第二个关系我们可以用LCA维护。
时间复杂度$O((n+m)logn)$。
当然我们可以用更快捷的DFS序维护。
# include <stdio.h>
# include <algorithm>
using namespace std;
int n, m;
struct quest {
int opt, q1, q2, id;
}q[666666], p[666666];
int gn=0, pn=0;
int fa[666666];
int head[1666666],next[1666666],to[1666666],tot=0;
int f[666666][20];
int level[666666];
int ans[666666];
bool havess[666666];
int root;
inline int getf(int x) {
return x == fa[x] ? fa[x] : fa[x] = getf(fa[x]);
}
inline bool cmp(quest a, quest b) {
return a.q2 < b.q2;
}
inline void add(int x,int y) {
tot++;
next[tot]=head[x];
head[x]=tot;
to[tot]=y;
}
void dfs(int x,int lev) {
level[x]=lev;
for (int i=1;i<=19;++i)
f[x][i]=f[f[x][i-1]][i-1];
for (int i=head[x];i;i=next[i]) {
if(!level[to[i]]) {
f[to[i]][0]=x;
dfs(to[i],lev+1);
}
}
}
inline int lca(int u,int v) {
if (level[u]>level[v]) {int t=u;u=v;v=t;}
for (int i=19;i>=0;--i)
if(level[f[v][i]]>=level[u])
v=f[v][i];
if(u==v) return v;
for (int i=19;i>=0;--i)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
int main() {
freopen("company.in", "r", stdin);
freopen("company.out", "w", stdout);
scanf("%d%d", &n, &m);
pn=0;
for (int i=1; i<=n; ++i) fa[i] = i, level[i] = 0;
for (int i=1; i<=m; ++i) {
q[i].id = i;
scanf("%d", &q[i].opt);
if(q[i].opt == 3) {
scanf("%d%d", &q[i].q1, &q[i].q2);
p[++pn] = q[i];
p[pn].id = pn;
ans[pn] = 0;
}
if(q[i].opt == 2) {
scanf("%d", &q[i].q1);
q[i].id = ++gn;
}
if(q[i].opt == 1) {
scanf("%d%d", &q[i].q1, &q[i].q2);
havess[q[i].q1] = 1;
//printf("%d\n", q[i].q1);
add(q[i].q1, q[i].q2);
add(q[i].q2, q[i].q1);
}
}
root = n+1;
for (int i=1; i<=n; ++i)
if(!havess[i]) {
add(root, i);
add(i, root);
}
dfs(root, 1);
sort(p+1, p+pn+1, cmp);
int cur = 1;
for (int i=1; i<=m; ++i) {
if(q[i].opt == 1)
fa[q[i].q1] = q[i].q2;
if(q[i].opt == 2) {
for (; cur <= pn && p[cur].q2 == q[i].id; ++cur) {
if(getf(p[cur].q1) == getf(q[i].q1)) {
int LCA = lca(p[cur].q1, q[i].q1);
if(LCA == p[cur].q1) ans[p[cur].id] = 1;
}
}
}
}
for (int i=1; i<=pn; ++i)
if(ans[i]) puts("YES");
else puts("NO");
return 0;
}
2023年6月17日 13:54
When I applied for internet banking, I supplied my phone number. However, nothing has changed in my account. My e-banking account was temporarily frozen, and I needed to change my password.Overseas Indian Bank My mobile edutec.in number is being updated, and online banking is enabled on my account. When I applied for internet banking, I supplied my phone number. However, nothing has changed in my account. My e-banking account was temporarily frozen, and I needed to change my password. Overseas Indian Bank My mobile number is being updated, and online banking is enabled on my account.