贪心

根本不会贪心 🤡，比赛里根本做不出来。🤡👈🤣

洛谷 P4105 [HEOI2014] 南园满地堆轻絮

以后见到这种排序类的题一定要往逆序对方向想。

结论：答案为 $\lceil \frac{\Delta}{2}\rceil​$，其中 $\Delta​$ 为值相差最大的逆序对。

考虑这个玩意为什么对，首先设 $mid​$ 为 $\lfloor\frac{a_i+a_j}{2}\rfloor​$，即 $b_i​$ 和 $b_j​$ 的值，假设是 $a_i-a_j​$ 最大，那么$[i,j]​$ 内部的数的变化值一定是在 $\lceil \frac{\Delta}{2}\rceil​$ 中间的。

因为不存在 xj \and a_y-a_x > a_i-a_j ，所以其实我们是可以把 $[1,i)$ 和 $(j,n]$ 分开考虑的，这两段是本质相同的，所以我们只考虑 $[1,i)$ 就可以了。

假设 $[1,i)$ 中 $\Delta$ 最大的逆序对坐标为 $x,y$。

首先如果 $a_x > mid$ 的话，我们可以直接将这个子问题的 $mid$ 设为上一层的 $mid$，然后继续递归下去。

如果现在 $a_x \le mid$ 的话，我们设当前层的 $mid$ 为 $\lfloor\frac{a_x+a_y}{2}\rfloor$，这个也直接递归下去。

上面的递归是和归纳法类似的，所以我们就可以直接证明这个是对的了。

P8365 洛谷 [LNOI2022] 吃

首先有一些显然的结论：

• 首先会吃掉所有 $a_i=1$ 的食物

  证明：废话，乘 $1$ 毛线用没有 😂

• 对于任意的加，一定在所有乘前面

  证明：没有负数，加法往前移动一定不劣。

• 最多只会有一个 $a_i\not= 1 $ 的物品选加

  证明：假设 $i,j$ 两个物品选加，不失一般性的设 $b_i\ge b_j$，不难发现 $b_i\times a_j \ge b_i+b_j$，因为 $a_j\not=1$ 且 $b_i\ge b_j$。

假设我将所有 $a_i=1$ 的食物全吃掉后体重为 $x$，剩下的食物乘起来的值是 $y$，我选了加第 $i$ 个食物，其他都是乘，那么贡献应该是 $\frac{y\times (x+b_i)}{a_i}$，等于是我要找一个 $\frac{x+b_i}{a_i}$ 的最大值，这个是可以直接存下来的，所以是好做的，注意我可以不选任何 $a_i\not=1$ 的食物为加，即答案要与 $\frac{y\times (x+b_i)}{a_i}$ 取 $\max$。

code:

typedef long long LL;
typedef long double LD;
typedef pair<int,int> PII;
const int P=1e9+7;
const int N=5e5+7;
int n;
PII x[N];
int main(){
	rd(n);
	for(int i=1;i<=n;i++) rd(x[i].first);
	for(int i=1;i<=n;i++) rd(x[i].second);
	LL ans=1;
	for(int i=1;i<=n;i++){
		if(x[i].first==1) ans+=x[i].second;
	}
	LD mx=0; int id=0;
	for(int i=1;i<=n;i++){
		if(x[i].first==1) continue;
		LD val=(LD)(ans+x[i].second)/(LD)x[i].first;
		if(val>mx) mx=val,id=i;
	}
	if(mx<ans) id=0;
	ans=(ans+x[id].second)%P;
	for(int i=1;i<=n;i++){
		if(x[i].first==1||i==id) continue;
		ans=ans*x[i].first%P;
	}
	wt('\n',ans);
	return 0;
}

洛谷 P8162 [JOI 2022 Final] 让我们赢得选举 (Let’s Win the Election)

感觉很喵的一道题。

我们称只得到选票的州为支持州，得到协作者的州为协作州。

首先发现一个性质，写作者肯定是一块演讲的，因为这样不劣，但是比·分开考虑简单很多。😆😆😆

首先有一个贪心，我们枚举有 $k​$ 个协作州，然后选 $b_i​$ 前 $k​$ 小作为协作州，剩余的 $a_i​$ 前 $K-k​$ 小作为支持州。

但是这玩意很假，下面这个就能叉掉

2
2
100 114514
114513 114515

显然最优解是第二个州成为协作州，第一个州为支持州，但是根据刚才那个贪心我们会把第一个州当成协作州，这个假的原因是可能有的州 $a_i$ 太小了导致成为协作州反而亏。

虽然这个贪心假了，但是我们还是能借鉴到一些东西的，比如演讲顺序一定是协作州在支持州前面，协作州的顺序一定是按 $b_i$ 从小到大的。

注意到 $b_i​$ 从小到大是一个很关键的性质，这样我们就能确定演讲顺序了，至于支持州，这是不用管的，因为他们一定在协作州后面，所以演讲人数一定是固定的。

现在有顺序了，并且贪心也搞不了了，那么就上一个 dp，我们设 $f_{i,j,k}$ 表示考虑到前 $i$ 个州，现在有 $j$ 个协作州，$k$ 个支持州的最小时间，转移就是枚举第 $i$ 个州到底是什么州，注意这里州的顺序是按上面说的排过序的。

但是因为我还要枚举有几个协作者，这个复杂度是不可以接受的 😔😔😔（这里要枚举的原因是支持州顺序是不能确定的，我们只能满足协作州的顺序，而支持州所耗时间是 $\frac{a_i}{m+1}$，其中 $m$ 是协作州数量，这个的计算是要提前知道的。）

然后就是一个 👍 性质了。

假设第 $i$ 个州是我选的最后一个协作州，那么 $[1,i]$ 的州一定是支持州或协作州

那么怎么证明呢，其实也很简单，假设有一个州 $j$ 啥也不是，$b_j$ 肯定是小于 $b_i$ 的，不如直接不选 $i$，选 $j$ 作为协作州。

现在 $dp$ 就可以直接省略掉最后一维了。

现在 $f_{i,j}$ 表示表示考虑到前 $i$ 个州，现在有 $j$ 个协作州的最小时间。

转移：

$$\begin{aligned} \begin{cases} f_{i,j}=\min(f_{i-1,j-1}+\frac{b_i}{j},f_{i-1,j}+\frac{a_i}{m+1}) &b_i\not=-1 \\ f_{i,j}=f_{i-1,j}+\frac{a_i}{m+1} & b_i=-1 \end{cases} \end{aligned}$$

其中 $m$ 为协作州个数。

最后统计答案时候我们枚举 $i$ 表示前 $i$ 个州都选，然后从后 $n-i$ 个州中找到 $a$ 前 $m-i$ 小的州，把他们拼起来就是答案了。

code:

typedef double DB;
const int N=507;
const int INF=1e9;
int n,m;
struct city{
	int x,y;
	city(){ x=y=0; }
	city(int X,int Y){ x=X,y=Y; }
	bool operator <(const city A) const{ return y!=A.y?y<A.y:x<A.x; }
}c[N];
DB f[N][N];
DB ans=INF;
DB tem[N];
inline void solve(int K){
	for(int i=0;i<=n;i++){
		for(int j=0;j<=K;j++) f[i][j]=INF;
	}
	f[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=K;j++){
			if(c[i].y!=INF&&j) f[i][j]=min(f[i-1][j-1]+1.0*c[i].y/j,f[i-1][j]+1.0*c[i].x/(K+1));
			else f[i][j]=f[i-1][j]+1.0*c[i].x/(K+1);
		}
	}
	int cnt=0;
	for(int i=n;i>=0;i--){
		DB sum=0;
		for(int j=1;j<=m-i;j++) sum+=tem[j];
		ans=min(ans,f[i][K]+sum);
		tem[++cnt]=1.0*c[i].x/(K+1),sort(tem+1,tem+1+cnt);
	}
}
int main(){
	rd(n,m);
	for(int i=1;i<=n;i++) rd(c[i].x,c[i].y),c[i].y=c[i].y==-1?INF:c[i].y;
	sort(c+1,c+1+n);
	for(int i=0;i<=m;i++) solve(i);
	printf("%.6lf\n",ans);
	return 0;
}

洛谷 P8207 [THUPC2022 初赛] 最小公倍树

别人是亚瑟王，我是 🤡 王！

直接做肯定直接寄，但是题目中就只只剩一个最小公倍数的性质了，所以肯定是从这里入手。

又是结论 🤡👈🤣

设 $x<y$，我们只连 $\gcd(x,y)=x$ 的边，然后跑最小生成树就是答案。

知道这个结论就可以直接做了，那么这个结论怎么证明呢？

假设现在有一条 $(y,z),z\le y$ 的边，我们假设 $\gcd(z,y)\not=z$，我们设 $x=\gcd(z,y)$，现在有 $(y,x)$ 的权值加 $(x,z)$ 的权值小于等于 $(y,z)$ 的权值，因为 $(y,z)$ 的权值为 $\frac{y\times z}{x}$，$(y,x)+(x,z)$ 的权值为 $\frac{x\times y}{\gcd(x,y)}+\frac{x\times z}{\gcd(x,y)}$，因为 $x$ 是 $y,z$ 的约数，所以原式可以化简成 $y+z$，又因为 $\frac{z}{x} \ge 2,y > z$，所以 $(y,x)+(x,z)<(y,z)$，既然两条边都比一条边优了，还不如直接加入这两条边，这肯定比加一条边那个优。

code:

typedef long long LL;
const int N=1e6+7,M=3e7+7;
struct edges{
	int u,v; LL w;
	edges(){;}
	edges(int U,int V,LL W){ u=U,v=V,w=W; }
	bool operator <(const edges A) const{ return w<A.w; }
}e[M]; int cnt=0;
int p[N];
inline int find(int x){ return x==p[x]?x:p[x]=find(p[x]); }
int main(){
	int l,r; rd(l,r);
	for(int i=1;i<=r;i++) p[i]=i;
	for(int i=1;i<=r;i++){
		for(int j=i,u=0;j<=r;j+=i){
			if(!u&&j>=l){ u=j; continue; }
			e[++cnt]=edges(u,j,1ll*u/__gcd(u,j)*j);
		}
	}
	sort(e+1,e+1+cnt);
	LL ans=0;
	for(int i=1;i<=cnt;i++){
		int u=find(e[i].u),v=find(e[i].v); LL w=e[i].w;
		if(u==v) continue;
		ans+=w,p[u]=v;
	}
	wt('\n',ans);
	return 0;
}

洛谷 P3646 [APIO2015] 巴厘岛的雕塑

一道二合一。🙄🙄🙄

第一问：$n \le 100,1 \le A \le B \le n$

首先因为是按位或，所以按位考虑，从高位往低位做，我们枚举第 $i$ 位能不能填 $1$，比第 $i$ 位高的一定要按之前的限制来做，比第 $i$ 位低的的随便填，这怎么做呢？考虑 dp，设 $f_{i,j}$ 表示将前 $i$ 个雕塑断成 $j$ 段是否可行，转移就枚举一个 $k$，看一下 $val_{i+1,k} \mid x$ 是否等于 $x$ 就行了，其中 $val_{l,r}$ 表示 $[l,r]$ 的雕塑年龄和。

code:（和上面说的写的不太一样

bool f[N][N];
inline int chk(LL x){
    memset(f,0,sizeof(f));
    f[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=r;j++){
            for(int k=1;k<i;k++){
                if(((sum[i-1]-sum[k-1])|x)==x) f[j+1][i]|=f[j][k];
            }
        }
    }
    int ans=0;
    for(int j=l;j<=r;j++){
        for(int k=1;k<=n;k++){
            if(((sum[n]-sum[k-1])|x)==x) ans|=f[j][k];
        }
    }
    return ans;
}
inline void sub1(){
    LL ans=0;
    for(int i=41;i>=0;i--){
        if(!chk(ans|((1ll<<i)-1))) ans+=1ll<<i;
    }
    wt('\n',ans);
}

第二问：$n \le 2000,A=1,1\le B \le n$

现在等于是没有了下界，考虑怎么利用这个性质优化 $dp$，因为没有了下界，所以我们用的段数越少越好，所以可以直接设进 $dp$ 状态里面，就是设 $f_i$ 表示将前 $i$ 段划分合法用的最小段数，转移同样是枚举一个 $j$ 让 $(i,j]$ 在一段。

code:

int f[N];
inline int chk(LL x){
    for(int i=1;i<=n;i++){
        f[i]=INF;
        for(int j=0;j<i;j++){
            if(((sum[i]-sum[j])|x)==x) f[i]=min(f[i],f[j]+1);
        }
    }
    return f[n]<=r;
}
inline void sub2(){
    LL ans=0;
    for(int i=41;i>=0;i--){
        if(!chk(ans|((1ll<<i)-1))) ans+=1ll<<i;
    }
    wt('\n',ans);
}

洛谷 P3644 [APIO2015] 八邻旁之桥

没看见 $k\le 2$，🤡 了。🤡👈🤣

先排除掉不用过河的居民，这是不用管的。

首先先考虑 $k=1$，这个很简单，就是将所有起点和重点都扔进一个数组里面，然后取中位数做建桥的位置，就是仓库选址。

现在考虑 $k=2$ 怎么做。

假设现在有两座桥，坐标为 $a,b​$（设 $a \le b​$），考虑我一个从 $x​$ 到 $y​$（设 $x\le y​$）的居民走哪座桥更优，首先如果有一座桥在 $x,y​$ 中间，那么就直接走这座桥，这样是没有额外的贡献的，那么如果没有呢？那么我们就要取 $\min(|a-x|,|a-y|)​$ 和 $\min(|b-x|,|b-y|)​$ 较小值了，通俗来讲，我们要选的桥就是离线段 $[x,y]​$ 最近的点，但是现在有两个端点，我们还要取 $\min​$，很麻烦，考虑怎么化简一下，其实这个很简单，因为是要找离线段最近的点，那么就是找离线段中点最近的点。

那么现在就很好做了，我们按照线段中点排序，就一定能找到一个点 $x$ 使得 $[1,x]$ 的居民走第一个桥，$(x,n]$ 的居民走第二个桥，现在就是两个分开的 $k=1$，我们要求出所有前后缀的中位数，即要动态维护中位数，直接用对顶堆即可。

code:

typedef long long LL;
typedef pair<int,int> PII;
const int N=1e5+7;
const LL INF=1e18;
int n,m,K;
int x[N],y[N];
PII a[N];
LL pre[N],suf[N];
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
LL sum1,sum2;
inline void push(int val){
	q2.push(val),sum2+=val;
	while(q1.size()<q2.size()){
		int x=q2.top();
		sum1+=x,sum2-=x;
		q2.pop(),q1.push(x);
	}
	while(q1.size()&&q1.top()>q2.top()){
		int x=q1.top(),y=q2.top();
		q1.pop(),q2.pop(),sum1-=x,sum2-=y;
		q1.push(y),q2.push(x),sum1+=y,sum2+=x;
	}
}
int main(){
	rd(K,n);
	LL ans=0;
	for(int i=1;i<=n;i++){
		char s[2],t[2]; int A,B;
		scanf("%s",s),rd(A),scanf("%s",t),rd(B);
		if(!strcmp(s,t)) ans+=abs(A-B);
		else x[++m]=A,y[m]=B,a[m]={A+B,m};
	}
	n=m,sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		push(x[a[i].second]),push(y[a[i].second]);
		pre[i]=sum2-sum1;
	}
	sum1=sum2=0;
	while(q1.size()) q1.pop();
	while(q2.size()) q2.pop();
	for(int i=n;i>=1;i--){
		push(x[a[i].second]),push(y[a[i].second]);
		suf[i]=sum2-sum1;
	}
	if(K==1) wt('\n',ans+pre[n]+n);
	else{
		LL res=INF;
		for(int i=1;i<=n;i++) res=min(res,pre[i]+suf[i+1]+n);
		if(!n) res=0;
		wt('\n',ans+res);
	}
	return 0;
}

洛谷 P3462 [POI2007] ODW-Weights

首先题目中给出了重量成倍数关系这个性质，我们是肯定要利用上的。

我们考虑维护一个类似于进制数的东西，我们将重量 $w$ 从大到小排序，处理一下能放几个 $w_1$，然后用余数算一下能放几个 $w_2$，以此类推。

因为每个砝码的贡献都为 $1$，所以肯定是从小到大填，考虑如果我当前进制位没有数了，我要从前面借位，不难发现这个过程一定是不劣的，因为我这个数在高位也只能放进去一个砝码，但是我现在已经填了一个了，所以不劣。

code:

typedef long long LL;
const int N=1e5+7;
int n,m;
int a[N],b[N],c[N];
LL sum[N];
int main(){
	rd(n,m);
	for(int i=1;i<=n;i++) rd(a[i]);
	for(int i=1;i<=m;i++) rd(b[i]),c[i]=b[i];
	sort(b+1,b+1+m),sort(c+1,c+1+m);
	int cnt=unique(c+1,c+1+m)-c-1;
	for(int i=1;i<=n;i++){
		for(int j=cnt;j>=1;j--) sum[j]+=a[i]/c[j],a[i]%=c[j];
	}
	int now=1,ans=0;
	for(int i=1;i<=m;i++){
		while(c[now]!=b[i]) now++;
		if(!sum[now]){
			for(int j=now+1;j<=cnt;j++){
				if(sum[j]){
					for(int k=j-1;k>=now;k--) sum[k+1]--,sum[k]+=c[k+1]/c[k];
					break;
				}
			}
		}
		if(sum[now]) sum[now]--,ans++;
	}
	wt('\n',ans);
	return 0;
}

洛谷 P5659 [CSP-S2019] 树上的数