首页 > 其他分享 >可持久化可反悔贪心

可持久化可反悔贪心

时间:2024-08-13 10:07:35浏览次数:10  
标签:int 化可 改对 反悔 ans 思路 check 贪心

接到上级通知,贪心思路假了,紧急需要调整思路

思路假了?考虑反悔

while(思路==false){
    cout<<"思路假了"<<endl;
    思路=true;
    cout<<"改对了"<<endl;
}

Sample Output

思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了
思路假了 改对了

改成二分答案。

考虑到设当前答案为 \(x\),正确答案上界为 \(y\),则有

\[x\ge ans \ge y \]

只需要写一个 check() 即可

不难发现 check() 非常好写:

bool check(int x){
    if(ans>=x) return true;
    return false;
}

二分答案即可求出答案。

代码实现过程:

#include<bits/stdc++.h>
using namespace std;
int x,ans;
bool check(int x){
    if(ans>=x) return true;
    return false;
}
int main(){
    cin>>x>>ans;
    int l=x,r=ans;
    while(1){
        int mid=(l+r)/2;
        if(check(mid)){
            l=mid+1;
            ans=mid;
        }
        else{
            r=mid-1;
        }
    }
    cout<<ans;>>
}

编译失败
/tmp/compiler_x4t_lflm/src: In function ‘int main()’:
/tmp/compiler_x4t_lflm/src:21:15: 错误:expected primary-expression before ‘>>’ token
21 | cout<<ans;>>
| ^~
/tmp/compiler_x4t_lflm/src:22:1: 错误:expected primary-expression before ‘}’ token
22 | }
| ^

你是不是忘记关尖括号自动补全了

哦还真是

考虑反悔,考虑到可以对反悔进行可持久化,建立贪心决策树,每次在决策树上暴力跳 fa

void init(){
    for(int i=1;i<=n;++i>){
        fa[i]=i;
    }
}
void solve(int x){
    int now=x;
    while(now) solve(fa[now]);
}

你是不是忘记关尖括号自动补全了

哦还真是

Sample oUTPUT

13
10
7
6
4
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Runtime Error: Process exited after 1.712 seconds with return value 3221225725

请按任意键继续...

考虑对反悔进行可持久化。

假了!这一步贪心!

反悔。

假了!反悔假了!

撤销。

哦不对,哦这个反悔思路是对的,对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

哦不对不对不对不对

撤销。

哦对的对的对的对的

反悔。

噫嘘唏,维护高在!疏导指南,南屿伤情田。迩来四碗坝前岁,刻意横绝峨眉殿。

反悔。

确认要将博文“可持久化可反悔贪心”放入回收站吗?

撤销。

确认要将博文“可持久化可反悔贪心”恢复吗?

莫队的起源:

考虑刚才的二分答案:

#define import include
import <bits/stdc++.h>
def check(x):
    if ans>=x:
        return True;
    else:
        return False;
    #endif

守序善良

这才是莫队

for(int i=1;i<=m;++i){
	while(nowl<q[i].l) reduce(nowl++);
	while(nowl>q[i].l) add(--nowl);
	while(nowr<q[i].r) add(++nowr);
	while(nowr>q[i].r) reduce(nowr--);
	anss[q[i].id]=ans;
}

中立善良

强制在线也是莫队

x0=(x0+lastans-1+MOD1)%MOD1+1,
x1=(x1+lastans-1+MOD1)%MOD1+1;
y0=(y0+lastans-1+MOD2)%MOD2+1,
y1=(y1+lastans-1+MOD2)%MOD2+1;

中立邪恶

二分答案也是莫队

int l=1,r=n;
while(l>=r){
    if(check(l)) l++;
    else l--;
    if(check(r)) r++;
    else r--;
}

混乱邪恶

DP 版莫队

f[i][j]=max({f[i-1][j],f[i+1][j],f[i][j-1],f[i][j+1]});

兄弟们有没有还能上传题解的入门题呀,跪求(本人才学编程2个月)

你说的对,但你为什么做出了3道黑题

而且一次就过!

解释一下

@wzt2012 让我老师帮我打的,装杯用

You are so smart!

标签:int,化可,改对,反悔,ans,思路,check,贪心
From: https://www.cnblogs.com/HaneDaCafe/p/18356193

相关文章

  • 贪心法-一般背包问题
    一般背包问题问题描述想象你有一个背包,它最多可以放M公斤的物品。你面前有n个物品,每个物品的重量是Wi,如果将这个物品完全放入背包,你将获得Pi的收益。问题目标你需要决定如何放置这些物品,以便在不超过背包容量的前提下,获得最大的收益。问题类型0/1背包问题:每个......
  • Day27 贪心算法part1
    任务455.分发饼干假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子i,都有一个胃口值g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干j,都有一个尺寸s[j]。如果s[j]>=g[i],我们可以将这个饼干j分配给孩子i,这......
  • 【EI复现】梯级水光互补系统最大化可消纳电量期望短期优化调度模型(Matlab代码实现)
    ......
  • 贪心
    有些题dp是难做的或做不了的,这个时候可以去设计一种策略使得决策尽可能最优,也就是贪心。可以说贪心有时候是一种乱搞,但乱搞也能搞出出题人想不到的正解。反悔贪心有些题中直接dp的复杂度很高并且很难优化或者有后效性无法dp,朴素贪心考虑可以做到\(O(n)\)但是无法保证正确......
  • 贪心系列专题篇四
    目录整数替换解法一解法二俄罗斯套娃信封问题堆箱子可被三整除的最大和距离相等的条形码重构字符串声明:接下来主要使用贪心法来解决问题!!!整数替换题目思路下面将使用两种方法来解决这道题,第一种方法是递归+记忆化搜索;第二种方法是贪心。解法一使用递归+记忆......
  • 贪心算法-活动安排问题
    贪心算法贪心算法总是选择当前看起来最优的选择(局部最优解),希望得到的结果是一个整体最优解。但是,并非总是选择局部最优解就能够得到整体最优解,这一点需要在问题具有贪心选择性和优化子结构时才成立。贪心选择性贪心选择性:第一次做出贪心选择是正确的。优化子结构问题......
  • 「Day 2—贪心问题&分治&前缀和」
    贪心问题定义顾名思义,越贪越好。。。习题P1094[NOIP2007普及组]纪念品分组思路简单来说:最少的+最多的,利用双指针。代码#include<algorithm>#include<iostream>usingnamespacestd;intw,n;intp[30005];intmain(){cin>>w;cin>>n;for(inti=1;i......
  • 贪心·区间问题
    区间问题Whatis贪心贪心:每一次只在当前这一块选择局部最优解,但最后可以走到全局最优解,只有一个问题是单方的,才可以使用贪心算法题目Acwing.905区间选点905.区间选点-AcWing题库举例:如图,需要选两个点,每个区间都有一个点,第1、2、3个区间内有第一个点,第4个区间包......
  • CF1883E+CF1995C-对数+贪心
    CF1883E+CF1995C对数+贪心CF1883ELookBack大致题意给你一个整数数组$a_1,a_2,…,a_n$。你需要用最少的运算次数使数组不递减。在一次操作中,您需要执行以下操作:选择一个索引\(1\leqi\leqn\)、设置$a_i=a_i⋅2$.数组\(b_1,b_2,…,b_n\)在所有$1\leqi\l......
  • 解密编程的八大法宝(三)(附贪心算法、动态规划和字符串匹配算法详解)
    算法题中常见的几大解题方法有以下几种:暴力枚举法(BruteForce):这是最基本的解题方法,直接尝试所有可能的组合或排列来找到答案。这种方法适用于问题规模较小的情况,但在大多数情况下效率不高。贪心算法(GreedyAlgorithm):贪心算法在每一步都选择当前看起来最优的解,希望最终能......