20160730 训练记录

tonyfang posted @ 2016年7月30日 21:12 in 随笔 with tags c++ OI , 228 阅读

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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter