896. 圈奶牛 题解

题意描述

给定有 n 头奶牛，要把这些奶牛用栅栏围起来，栅栏的总长度即为花费，求花费的最小值。

题解

例如有这么几头牛：

显然，一个想法是用一个圈把这些牛全部围起来：

但是这样显然不是花费最小的，那我们就让这个椭圆一直缩小，直到和边缘上的点碰触就停止缩小：

这样就是花费最小的啦！

如果再往里缩小的话，花费就会反而变长！

如图，在 $\triangle GHI$ 中，根据三边关系显然有 $GI + IH \gt GH$，所以 $GH$ 就是 $G$ 到 $H$ 花费最小的连接方式。

注意到这个连接方式的顶点连线的斜率是递减的

即：

$$

k_{HG} > k_{GE} > k_{ED} > k_{HD}

$$

那么，我们如何找到这个连接方式呢？

首先找到一个 $x$ 坐标或 $y$ 坐标最大/最小的点，例如图中的点 $H$、点 $G$、点 $E$、点 $D$。

我们以点 $H$ 为例，将这些点排序，按照其他点与点 $H$ 的连线的斜率降序排序（从小到大也可以，只不过实现略有不同）：

struct NODE {
    double x, y;
} node[MAXN];

double getk(NODE x, NODE y) {
    return (x.y - y.y) / (x.x - y.x);
}

int main() {
    ... // 读入
    sort(node + 1, node + n + 1, [](NODE x, NODE y) {
        if (x.x != y.x) return x.x < y.x;


........................................................................
该题解待审
........................................................................(剩余 8295 个中英字符)

#include<iostream>

using namespace std;

int find(int x,int y,int n){

int num=x;

if(n-x+1<num) n

........................................................................

该题解待审

有一说一，其实挺水

做一个以身高为关键字的单调栈储存每个奶牛的序号，再单独以一个数组存储身高，在弹出时处理它对答案的贡献，显然为当前序号到它的序号的差减一

最后注意一下数据大小开个longlong

#include<bits/stdc++.h>
using namespace std;

int n,a[110086],tmp,c[110086],num;

int main () {
    freopen("hair.in","w",stdin);
    freopen("hair.out","r",stdout);

    cin>>n;
    
    for(int i = 1; i<=n; i++){
        int y;
        cin>>y;
        
        while(y>=c[a[tmp-1]]&&tmp>0){
            num+=i-a[tmp-1]-1;
            tmp--;
        }
        c[i]=y;
        a[tmp++]=i;
    }
    while(tmp>0){
    if(a[tmp-1]!=n)num+=n-a[tmp-1];
    tmp--;
    }
    cout<<num;
    return 0;
}

先创建一个map，使m[队列元素]=队列编号，这样后面好查找元素的组别；

再创建一个队列q[301]，q[i]表示队列编号为i的排队情况。q[0]表示小组的排序；

队列输入不用多说，只需要注意一个新小组的人入队要给新小组排上队；

队列输出时查看q[0]队头，看到小组编号后查该小组的队头，再输出，注意小组的人全部出队后要把空小组删掉。

考场一个小时切不出来T1于是暴力及时止损，看题解才想到的贪心，，

首先我们要知道，对任意数列进行有限次邻项交换后，必定能得到该数列的全排列。这样你就拿到了 $n\leq10$ 的20分。

如果你能想到在 $t_1$ 和 $t_2$ 中的由连续的1组成的连通块内，对应的 $s_1$ 与 $s_2$ 的部分可以任意排列，那你就拿到了 $t_1=t_2$ 的20分。

如果你能想到当 $s_1$ 全是0或1的时候不管 $s_2$ 如何排列答案都不会变，那你就拿到了性质A的20分。

（性质C太难了不讨论了）（）（）

暴力的60分该拿还是得拿的）

然后是正解

从前往后扫，如果这个位置 $s_1$ 和 $s_2$ 有一个不能能换，那就从对应连通块内挑一个数放上去配对就好了

如果都能换，同上，挑0挑1都一样

如果都不能换，直接算答案

感性地贪一下，如果这个位置不配对，那就是给后面的位置留了一个0或1，但这个数在后面至多也只有1的贡献，还不如拿到就马上配了（

换之前记得先看看这个块剩下的0和1数量还够不够

（其实用并查集维护会方便一点）

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof a)
#define rev(x) reverse(x.begin(),x.end())
using namespace std;
struct node{
	int n0,n1;
	node operator+(const node&q)const{return (node){n0+q.n0,n1+q.n1};}
}siz[100010][2];
int fa[100010][2];
inline int find(int x,int p){
	if(x==fa[x][p]) return x;
	return fa[x][p]=find(fa[x][p],p);
}
inline void merge(int x,int y,int p){
	x=find(x,p),y=find(y,p);
	if(x!=y) siz[y][p]=siz[y][p]+siz[x][p],fa[x][p]=y;
}
int main(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		string s1,s2,t1,t2;cin>>s1>>s2>>t1>>t2;
		for(int i=0;i<n;i++) fa[i][0]=fa[i][1]=i;
		for(int i=0;i<n;i++){
			siz[i][0].n0=s1[i]=='0';
			siz[i][0].n1=s1[i]=='1';
			siz[i][1].n0=s2[i]=='0';
			siz[i][1].n1=s2[i]=='1';
		}
		for(int i=1;i<n;i++){
			if(t1[i]=='1'&&t1[i-1]=='1') merge(i-1,i,0);
			if(t2[i]=='1'&&t2[i-1]=='1') merge(i-1,i,1);
		}
		

		int ans=0;
		for(int i=0;i<n;i++){
			int p1=find(i,0);
			int p2=find(i,1);
			if(siz[p1][0].n0>0&&siz[p2][1].n0>0) siz[p1][0].n0--,siz[p2][1].n0--,ans++;
			else if(siz[p1][0].n1>0&&siz[p2][1].n1>0) siz[p1][0].n1--,siz[p2][1].n1--,ans++;
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}

挺不错的题，原题是 CF 的某个题，但我找不到题号了，所以写个比较易懂的题解方便补，可能废话很多。

首先要有一点初步的观察，可以发现 $\max$ 的求解是很方便的，我们只需要找出所有 $k$ 的倍数，这样一定能让 $\gcd$ 尽可能为 $k$，并且使取的数的个数最多。

然后是最小值。这仍然需要一些观察和经验。我们想要每个取的数都不是 "无用" 的，也就是说，它必须能帮我们 "赶出去" 某些没有用的素因子。

下面是一些经验。假设一开始随便选了一个数 $x(k|x)$，再选一个数 $y(k|y)$，那么必然有 $\gcd(x, y)<x$，否则 $y$ 不如不选。那么有 $\frac{x}{\gcd(x, y)}\ge 2$，因为最小的素因子是 2。

于是我们知道，选数的最小个数其实是 $\mathcal O(\log \max(S_i))$ 级别的，在这道题里面也就 18 个左右。

面对最优化问题关于答案范围的极强约束，一般地，直接枚举答案，转化为 $\forall s\in [1, 18]$，对于 $1\sim n$ 的每个 $k$ 判断是否 "存在" 一种取出 $s$ 个数使得 $\gcd$ 为 $k$ 的方案。

然后是这道题非常巧妙的一个点，一般我们很少遇到判定比计数还困难的题目，这道题就是一个例子。

那怎么办？直接换成计数来做。意识到这一点需要有莫比乌斯反演的功底，这样才能在面对着一个和计数没有关系的题目时，通过诸如 $\gcd = k$ 这样的条件感受出做法。这也给我们启示，有时我们需要用这样的数学直观刺激直觉。

于是我们先枚举 $s$，计算 $F(k,s)$ 表示选 $s$ 个数使得 $\gcd$ 是 $k$ 的倍数，这是简单的，假设原序列有 $p$ 个数是 $k$ 的倍数，那么 $F(k,s)=\mathrm C_{p}^{s}$。$p$ 的计算可以使用狄利克雷后缀和解决，实质上就是高维前缀和的一种拓展。

接下来的操作很平凡，使用莫比乌斯反演，得 $G(k,s)$，即原本要求的方案数，为 $\sum\limits_{k|x}F(x,s)\times \mu(x/k)$。

时间复杂度 $\mathcal O(m\ln m\log m)$。题解好像写的有点魔怔，可能是文化课学多了导致思维也比较呆。