首页 > 其他分享 >一些贪心的解题报告

一些贪心的解题报告

时间：2024-05-05 16:44:05浏览次数：23  
标签：le frac 报告 int sum 解题 define 贪心

一些贪心的解题报告

贪心题一般来说都是观察结论远简单于严谨证明，所以不会过多的去证明。

1.Tree compass

题目来源

codeforces div1 934 C
https://codeforces.com/problemset/problem/1943/C

题面翻译

给定一棵节点数为\(n\)的树(\(1\le n \le 2\cdot 10^3\))，一开始节点都是白色的。我们可以做以下操作

  • 选择一个点\(u\in [1,n]\),选择一个距离\(d \in [0,n]\),将所有距离\(u\)恰好为\(d\)的点涂黑。点\(v\) 到点\(u\)的距离是 树上从 \(u\) 到 \(v\)所形成的简单路径中的边的数量。

问，想把树的所有节点涂黑，最少的操作数，并输出操作方案。

  • 数据范围:\(\sum n \le 2\cdot 10^3\)
  • 时空限制：时限2s,空间512MB

题外话

于我而言，这道题有一个很舒服的点，就是解法和证明是相辅相成的，最简单的贪心比较容易想，而在证明贪心的过程中真正的正确解法就呼之欲出。

解法

对于题目给出的操作，如果不固定\(u\)的话，操作相当眼花缭乱，只能想到一种非常简单粗暴的方式，就是我们固定\(u\)，取\(d=0,1,2,....,x\)。\(x\)为其他点到\(u\)的最远距离，然后我们再贪心的选择\(x\)最小的点，操作数就是\(x_{min}+1\)。

但是这么贪心正确性有待考察，因为树上情况还是太复杂，先从一般角度考虑。

首先考虑链上面的情况，方便起见，我们从链的一个端点到另一个端点依次递增的标号。也就是\(1 \lrarr 2\lrarr...\lrarr n。\)

链上操作显然我们一次操作最多只会给两个点染色，也就是说，想要涂黑一棵树，一次又最多只会涂黑两个点，我们的操作数至少为\(\lceil \frac n 2\rceil\)。

可以发现，如果我们有奇数个点，那么每次操作我们选择中心点\(\frac {n+1} 2\)，距离分别选\(0,1,2,...,\frac {n-1} 2\)，显然可以做到将链完全染色，而\(\frac {n+1} 2\)已经是操作次数的理论下限了，那么这一定就是最小操作次数。

再考虑偶数情况，事实上偶数仍然要分类讨论，就比如\(n=2\)时我们必须操作两次，达不到\(\frac n 2\)的下界，而\(n=4\)时我们只要\(u=2,d=1;u=3,d=1\)这般操作两次就可以，达到了下界。

对于\(n=4k,k\in N^+\),可以选择点\(\frac n 2\)与\(\frac n 2+1\),距离选择\(1,3,...,\frac n 2-1\),总共操作\(\frac n 2\)次，恰好将链涂黑。

对于\(n= 4k+2,k\in N\),可以证明\(\frac n 2\)次操作不可能将链涂黑。证明如下

  • 有\(2k+1\)个点，编号为奇数，也就是有奇数个编号是奇数。同理，有奇数个编号为偶数。如果一次操作涂黑了两个点，那么它们的编号就是\(u-d,u+d\)，可以发现这两个编号奇偶性一致，这说明了对奇数编号与偶数编号的操作是互相独立的。那么，\(2k+1\) 个奇数编号至少要\(k+1\)次操作，同理偶数编号也要\(k+1\)次,也就是至少要\(2k+2\),或者说\(\frac n 2+1\)次才能完全涂黑整条链。

那么我们选择\(u=\frac n 2\),距离分别为\(0,1,2,3,...,\frac n 2\),操作\(\frac n 2+1\)次即可。

接下来从链回归到树。可以把树看做一系列链的并，链的操作次数下界对树也是成立的，只是这个下界不一定能够达到了。

树上最长的链就是树的直径。长度记作\(len\),对于一棵树而言，涂黑一条直径需要的最小操作次数就是树的操作次数下界。

对于\(len=2k+1\ 或\ len=4k+2,k\in N\)我们可以像链一般选择一个直径的中心点，根据直径的性质，其他点到中心点的距离小于等于直径两个端点到中心点的距离的较大值,一定会被染黑。

对于\(len=4k,k\in N^+\),无非是选择了两个中心点，仍然能够保证在染黑直径的同时就能把整一棵树染黑。

所以最后染黑直径的最小操作次数就是答案。

代码就是找直径，记长度，找中心点。

复杂度\(O(n)\),但是\(n\le 2\cdot 10^3\),或许是出题人觉得想出思路才是重要的，不卡\(O(n^2)\)，太仁慈了。

点我查看代码 
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define pii std::pair<int,int>
typedef int LL;
const signed maxn=1e6+5;
inline LL Read(){
    LL x=0;char ch=getchar();bool f=0;
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    if(f) x=-x;return x;
}
struct Edge{
    int to,nxt;
}edge[maxn<<1];
int head[maxn],ecnt;
void Adde(int u,int v){
    edge[++ecnt]=(Edge){v,head[u]};
    head[u]=ecnt;
}
int d;
int fa[maxn],dep[maxn];
void dfs(int u,int Fa){
    fa[u]=Fa;dep[u]=dep[Fa]+1;
    if(dep[u]>dep[d]) d=u;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==Fa) continue;
        dfs(v,u);
    }
}
int chain[maxn],ccnt;
void get_chain(){
    ccnt=0;
    while(d) chain[++ccnt]=d,d=fa[d];
}
signed main(){
    LL T=Read();
    while(T--){
        int n=Read();
        for(int i=1;i<=n;++i) head[i]=0;ecnt=0;
        for(int i=1;i<n;++i){
            int u=Read(),v=Read();
            Adde(u,v),Adde(v,u);
        }  
        dep[0]=0;d=0;
        dfs(1,0);
        dfs(d,0);
        get_chain();
        if(ccnt%2==1||ccnt%4==2){
            int x=ccnt>>1,c=chain[x+1];
            printf("%d\n",x+1);
            for(int i=0;i<=x;++i){
                printf("%d %d\n",c,i);
            }
        }
        else{
            int x=ccnt>>1;
            int c1=chain[x],c2=chain[x+1];
            printf("%d\n",x);
            for(int i=1;i<x;i+=2){
                printf("%d %d\n",c1,i);
                printf("%d %d\n",c2,i);
            }
        }
    }
    return 0;
}

2.开灯

题目来源

中南大学第17届校赛
题目链接http://122.207.108.21:20080/csuoj/problemset/problem?pid=2520
题目挂在csuoj上，只有中南大学的网才能连上。

题目

中文题面直接截图
image

解法

首先，边上的灯泡可以分为三类：

  1. 最后状态要求是初始状态，即总共被反转偶数次。
  2. 最后状态要求是初始状态的反转，即总共被反转奇数次。
  3. 最后状态随意，可以反转任意次。

本题灯泡在边上，其实可以等价的修改为在点上，映射规则如下：

  • 选定一个点作为根，根没有边对应，然后作\(dfs\)，点与其入边对应。

做了映射后还要注意:对于路径\(u\) 到 \(v\)上的操作，不会对\(LCA(u,v)\)产生影响，因为其对应的边不在路径上。

那么，首先把路径看做一条或者由下而上拓展的链组成。因为LCA不被影响，链的顶端不受影响。贪心思路就是尽量把两条链组合为一条路径而不是单独一条链作路径。

在贪心之前要说明一些性质。

  1. 一定存在一种最优策略，任意两条路径没有边重复。
  2. 一个需要奇数反转的点，其一定恰好出现在一条向上拓展的链上(非顶端)，即其向上拓展一次也仅一次。

叶子节点策略：对于要求反转奇数次的点，向父亲节点传一个向上拓展计数，同时增加最终答案\(1\)。反转偶数的点和随意的点不传。

非叶节点：首先查看向上拓展计数，记为\(sum\),把尽量多的计数二合一减小答案。最终答案减小\(\frac {sum} 2\)。然后根据灯泡的类别分类讨论：

  1. 需要反转奇数次。一定会向上拓展。如果\(sum\)为奇数，恰好留了一条作为向上拓展的链，就不用额外再重新开一条，直接沿用。如果\(sum\)为偶数，就得像叶子结点一般，最终答案加\(1\)。
  2. 需要反转偶数次。一定不会向上拓展。
  3. 反转次数随意。如果\(sum\)为奇数，多余的一条作为向上拓展的链，记向上拓展计数。如果\(sum\)为偶数，不向上拓展。

\(1e5\)的\(O(n)\)，题目还是出的太保守了。

点我查看代码 
#include<bits/stdc++.h> 
#define ll long long 
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f 
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL Read(){
	char ch=getchar();bool f=0;LL x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
std::vector<int> g[maxn];
int type[maxn],sum[maxn],fa[maxn];
char ori[maxn],now[maxn];
int fin=0;
void dfs(int u){
    for(auto v:g[u]){
        dfs(v);
    }
    if(type[u]==1){
        fin-=sum[u]>>1;
        if(sum[u]&1^1) ++fin;
        ++sum[fa[u]];
    }
    else if(type[u]==0){
        fin-=sum[u]>>1;
    }
    else{
        fin-=sum[u]>>1;
        if(sum[u]&1) ++sum[fa[u]];
    }
}
signed main(){	 
		
        int n=Read();
        for(int i=1;i<n;++i){
            int Fa=Read();
            fa[i]=Fa;
            g[Fa].push_back(i);
        }
       scanf("%s%s",ori,now);
       for(int i=0;i<n;++i){
        if(now[i]=='1') type[i+1]=now[i]-ori[i];
        else type[i+1]=-1;
       }
        dfs(0);
        printf("%d\n",fin);
	return 0;

}

3. ina of the mountain

题目来源

codefores div1 887 C
https://codeforces.com/contest/1943/problem/C

题目翻译

巨山下有一排不朽章鱼，编号为\(1\sim n\)。每个章鱼有初始生命值\(a_i\)，\(1\le a_i \le k\)。我们可以选择一个区间\([l,r]\),通过一次扔石头伤害编号在\([l,r]\)之间的章鱼，使他们生命值减\(1\)。不朽章鱼是不朽的，当他们生命值归零，他们会以生命值为\(k\)的状态复活。

问，最少需要扔多少次石头才能使所有章鱼生命值变为\(k\)。

  • 数据范围:\(1\le n \le 2\cdot 10^5,1\le k \le 10^9\)
  • 时空限制:时限2s,空间512MB

解法

显然\(a_i=a_{i+1}\)这种相邻相同的两只章鱼可以当做一只考虑，所以接下来不考虑相邻位置相等的情况(\(a_i\ne a_{i+1}\))。
首先假设我们找到了最少的操作情况。这种情况下，第\(i\)只章鱼被砸了\(c_i\)次，显然有\(|c_i-a_i|\%k=0\)。

我们以区间的左端点计算贡献,考虑最优情况下可以有的性质。

  1. 贡献计算：如果\(c_{i+1}< c_i\),位置\(i\)不提供贡献。\(c_{i+1}>c_i\),提供\(c_{i+1}-c_i\)的贡献。
  2. \(c_{i+1}<c_i+k\)。若\(c_{i+1}> c_i+k\),取\(c'_{i+1}=c_{i+1}-k\)不会使答案更劣。同理有\(c_{i+1}>c_i-k\)。

由第一点，我们得到贪心的总原则:最小化\(\sum_{i=1}^{n-1} max(0,c_{i+1}-c_i)\)。
由第二点，可以发现\(c_i\)与\(c_{i+1}\)的关系，当\(c_{i+1}\)作贡献时，当\(c_i<c_{i+1}<c_i+k\),\(c_{i+1}\)其实是确定的，那么一个位置的贡献是确定的。当不作贡献时，\(c_i-k<c'_{i+1}<c_i\),有\(c'_{i+1}=c_{i+1}-k\)。每一个位置只有做贡献与不做贡献两种情况。

接下来讲贪心的策略。

考虑每一位都作贡献，然后选择一些位置不作贡献，使被减去的贡献最大。

一开始每一位都做贡献，也就是\(c_{i+1}\ge c_i\)始终成立。

然后选择一些位置位置不作贡献。若位置\(i\)不作贡献,位置\(i\)及之后的\(c_j\)都少一个\(k\)。即\(\forall j\ge i,c_j-=k\)。
那么\(c_i=A*k+B(0\le B<k)\),\([1,i]\)之间最多有\(A\)个位置不作贡献。
\(c_i\)是递增的，可以不作贡献的位置量在增加。从左向右遍历，开一个优先队列记录\([1,i]\)位置的贡献中最大的几个，时刻保持队列大小和\(c_i/k\)相符合。最后把这些贡献减去就得到了答案。

遍历\(O(n)\),优先队列\(O(\log n)\),总复杂度\(O(n\log n)\)

点我查看代码 
#include<bits/stdc++.h> 
#define ll long long 
//#define int long long
#define mid ((l+r)>>1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define inf 0x3f3f3f3f 
typedef int LL;
const signed maxn=(signed)1e6+5;
inline LL Read(){
	char ch=getchar();bool f=0;LL x=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f) x=-x;return x;
}
int n,m,k;
ll ar[maxn];
std::priority_queue<int,std::vector<int>,std::greater<int> >q; 
signed main()
	{	 
		LL T=Read();
		while (T--){
			int n=Read(),k=Read();
			for(int i=1;i<=n;i++) ar[i]=Read();
			ar[0]=0;
			ll sum=0;int c=0,d=0;
			for(int i=1;i<=n;i++){
				ll b=(ar[i]+k-ar[i-1])%k;
				sum+=b;c=sum/k;
				q.push(b);d++;
				while(d>c){
					q.pop();d--;
				}
			}
			while(!q.empty()){
				sum-=q.top();
				q.pop();
			}
			printf("%lld\n",sum);
		}
		return 0;
	}

标签：le,frac,报告,int,sum,解题,define,贪心
From： https://www.cnblogs.com/LOOP-0/p/18173618

相关文章

  • 【专题】2024年4月消费趋势报告合集汇总PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=36089原文出处：拓端数据部落公众号随着科技的不断进步和全球化的深入发展，各行各业都面临着前所未有的机遇与挑战。从零售业的变革到美妆行业的崛起，从消费者行为的转变到营销策略的创新，每一个领域都在不断地演进和重塑。在快速变化的市场环境中，消费......
  • 二叉树笔试题解题思路
    数据结构二叉树笔试题：解题思路：1.判断是否为空树，若为空树，则返回0；2.定义两个指针备份根结点地址，定义两个整型变量a,b并初始化为0，记录左右子树的深度；先对根结点的左子树进行遍历，若根结点的左结点不为NULL，则a++，把根结点的左结点赋值为新的根结点，再进行上述操作，若根结点的左结点......
  • 实验报告3
    #include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#defineN80voidprint_text(intline,intcol,chartext[]);//函数声明voidprint_spaces(intn);//函数声明voidprint_blank_lines(intn);//函数声明int......
  • 说说你对贪心算法、回溯算法的理解？应用场景？
    一、贪心算法贪心算法，又称贪婪算法，是算法设计中的一种思想其期待每一个阶段都是局部最优的选择，从而达到全局最优，但是结果并不一定是最优的举个零钱兑换的例子，如果你有1元、2元、5元的钱币数张，用于兑换一定的金额，但是要求兑换的钱币张数最少如果现在你要兑换11元，按照贪心算法......
  • 【专题】消费品行业的5G新时代：2024年消费品行业趋势洞察报告合集PDF分享（附原数据表）
    原文链接：https://tecdat.cn/?p=36059原文出处：拓端数据部落公众号2023年，我国社会消费品零售总额同比增长7.2%，呈现出稳健而强劲的增长态势。与此同时，最终消费支出对经济增长的贡献率显著提升，达到了82.5%，比去年提高了3.1个百分点，这进一步凸显了消费在驱动我国经济发展中的核心作用......
  • 保护企业财务报告，这几款防泄密软件做得到！
    在日益增长的金融欺诈和网络攻击中，保护企业的财务报告是维持公司声誉和稳定运营的关键。财务报告包含了公司的敏感信息，如利润、收入、财务结构等，一旦泄露，可能会对公司造成不利影响。华企盾DSC数据防泄密系统为企业提供了全面的解决方案，确保财务报告的安全性和机密性。华企盾DSC......
  • XMU《UNIX 系统程序设计》第五次实验报告（编制模拟“五个哲学家”问题的程序）
    想知道第三、四次实验去哪儿了吗？我也想知道。实验五编制模拟“五个哲学家”问题的程序一、实验内容描述编制模拟“五个哲学家”问题的程序目的学习和掌握并发进程同步的概念和方法。要求程序语法philosopher[-t<time>]<time>是哲学家进餐和沉思的持续时间值，......
  • XMU《UNIX 系统程序设计》第六次实验报告（信号处理）
    实验六信号处理完整程序可以在这里下载：点击下载。一、实验内容描述实验目的学习和掌握信号的处理方法，特别是sigaction，alarm，sigpending，sigsetjmp和siglongjmp等函数的使用。实验要求编制具有简单执行时间限制功能的shell：myshell[-t<time>]这个测试程序的功......
  • XMU《计算机网络与通信》第二次实验报告
    实验二实验报告一、个人信息姓名：XXX学号：XXXXXXXXXXXXXX二、实验目的学习捕获和分析网络数据包掌握以太网MAC帧、802.11数据帧和IPv4数据包的构成，了解各字段的含义掌握ICMP协议，ping和tracert指令的工作原理掌握ARP协议的请求/响应机理三、实验内容与结果分析......
  • XMU《计算机网络与通信》第四次实验报告
    计算机网络实验四通信这次实验的话，我的报告参考意义不大，毕竟这次实验的主要难点是完成那两个代码，但是我报告中没有任何对于代码的解释。大家如果需要的话，我的两个代码可以在这里下载，仅供参考：点击下载。一、个人信息姓名：XXX学号：XXXXXXXXXXXXXX二、实验目的理解和掌握ARP......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99