草庐IT

Codeforces 1672 E. notepad.exe

4VDP 2023-03-28 原文

题意

这是一道交互题，有n个字符串，每个字符串长度:0-2000, n :0-2000
有一个机器对他进行排版，你可以给他一个每行的最大宽度w，那么每行只能放长度为w的字符；
每行相邻两个字符串之间至少有一个空格，每行结尾可以不用，机器会按照贪心原则进行排版，保证排版后的高度尽量小。
你可以进行n+30次询问，每次询问你可以给个w，他会给你排版后高度h，让你求出w*h的最小值。

做题吐槽

这题很典型的构造题，不会就是不会，会了一下子就会做了，这种题感觉就是要一下子找到题目的突破点，挖掘出这类题目的特征，感觉自己还是菜，每个突破点想到了，但是没串连起来，继续加油！

提示

1. 答案的范围变化是很小的，变化范围只有0-2000
2. 当 h= 1 的时候，很显然是最优的w是每个字符空一格
3. 当求出h = 1时候的答案h*w = s时，在h改变时，最多就是换行符号替换了空格，s变化为s-(h-1),并且需要整除h，那么只有一个点 s/h 满足
4. 这样就做出来了，先二分找出h=1时，w的最小值，对后续每个h高度询问一次检查一下就可得到最终解

反正很玄妙，如何想到变化范围小，如何想到整除，我感觉只能这种题只能从极值考虑，例如h=1，h=n这些点看看有没有什么特征，根据特征再去推理过程

代码

#include<bits/stdc++.h>

using namespace std;

void run() {
    int n;
    cin >> n;
    int l = 2 * n - 1, r = n * 2000 + n, flag = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        int x;
        cout << "? " << mid << endl;
        cin >> x;
        if (x == 1) {
            flag = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    int s = flag;
//    cout<<s<<endl;
    int ans = s;
    for (int i = 2; i <= n; i++) {
        cout << "? " << s / i << endl;
        int x;
        cin >> x;
        if (x)
            ans = min(ans, x * (s / i));
    }
    cout << "! " << ans << endl;
}

int main() {
    run();
    return 0;
}
E.Codeforcesfontlt求出算法与数据结构

有关Codeforces 1672 E. notepad.exe的更多相关文章

  1. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  2. Ruby，使用包含 TK GUI 的 ocra 部署一个 exe - 2

    Ocra无法处理需要“tk”的应用程序require'tk'puts'nope'用奥克拉http://github.com/larsch/ocra不起作用(如链接中的一个问题所述)问题:https://github.com/larsch/ocra/issues/29(Ocra是1.9的"new"rubyscript2exe，本质上它用于将rb脚本部署为可执行文件)唯一的问题似乎是缺少tcl的DLL文件我不认为这是一个问题据我所知，问题是缺少tk的DLL文件如果它们是已知的，则可以在执行ocra时将它们包括在内有没有办法知道tk工作所需的DLL依赖项？ 最佳答

  3. ruby-on-rails - 尝试登录和使用 heroku 时无法识别 ruby​​.exe - 2

    当尝试创建一个heroku应用程序并通过git推送到它时，我收到以下错误:$herokucreate'"C:\ProgramFiles\ruby-1.9.2\bin\ruby.exe"isnotrecognizedasaninternalorexternalcommand,operableprogramorbatchfile.但是，$ruby-vruby1.9.3p125[i386-mingw32]我已经检查了PATH环境，它肯定包含“C:\ProgramFiles(x86)\ruby-1.9.2\bin”。同样有趣的是，当导航到该目录时，它实际上并不包含名为ruby​​.exe的文件

  4. ruby - Git Bash 给出 sh.exe : ruby: command not found - 2

    我在WindowsVistaBusiness上使用GitBash。我正在尝试安装Redmine。基本上在第4步，我需要在安装bundler之前安装RubyGem作为依赖项安装的一部分(http://www.redmine.org/projects/redmine/wiki/RedmineInstall)。我从https://rubygems.org/pages/download下载了ruby​​gems-2.2.2.zip.然后我将文件解压缩到桌面上的一个文件夹中。在GitBash中，我输入了rubysetup.rb，我得到了sh.exe:ruby​​:commandnotfound。

  5. ruby - rbenv — 'find_spec_for_exe':找不到带有可执行包的 gem 打包器 (>= 0.a) (Gem::GemNotFoundException) - 2

    我是rbenv的新手(长期使用RVM)。今天我彻底卸载了我的RVM并安装了rbenv。我成功安装了Ruby2.5.1，没有任何问题。但是，当我今天尝试为一个项目运行bundleinstall时，出现了以下错误:'find_spec_for_exe':找不到带有可执行包(Gem::GemNotFoundException)的gem打包器(>=0.a)我的bundler安装似乎出了点问题，但我不确定哪里出了问题。使用sudo运行geminstallbundler无法解决问题。这是完整的轨迹:$echo$SHELL/bin/zsh$cat~/.gemrcgem:--no-documentin

  6. ruby - 为 Notepad++ 的 Ruby 语法突出显示添加关键字 - 2

    我正在尝试添加require和include作为Notepad++的Ruby关键字，但我遇到了一些麻烦。我修改了langs.model.xml文件的ruby​​语言标签如下:__FILE__anddefendinorselfunless__LINE__begindefined?ensuremoduleredosuperuntilBEGINbreakdofalsenextrescuethenwhenENDcaseelsefornilretrytruewhilealiasclasselsififnotreturnundefyieldrequireinclude但是，即使在更新此requir

  7. Educational Codeforces Round 146 (Rated for Div. 2)（B，E详解） - 2

    题外话：抑郁场，开局一小时只出A，死活想不来B，最后因为D题出锅ura才保住可怜的分。但咱本来就写不到DB-LongLegs（数论）本题题解法一学自同样抑郁的知乎作者幽血魅影的题解，有讲解原理。法二来着知乎巨佬cup-pyy（大佬说《不难发现》呜呜）题意三种操作：向上走mmm步向右走mmm步给自己一次走的步数加111，即使得m=m+1m=m+1m=m+1问从(0,0)(0,0)(0,0)走到(a,b)(a,b)(a,b)的最小操作次数，值得注意的是操作三不可逆。解析假设我们最终一步的大小增长到mmm，那么在这个过程中我能以[1,m][1,m][1,m]（当步数增长到该数时）之间的任何数字向上或

  8. ruby - 将ruby脚本编译成exe？ - 2

    是否可以在Windows上将ruby​​脚本编译成.exe文件？我到处搜索并尝试了以下方法(看起来RubyScript2EXE、Shoes和Crate似乎都死了或被遗弃了。):http://ocra.rubyforge.org/http://exerb.sourceforge.jp/index.en.html我在Windows7Ultimate(64位)上使用Ruby1.8.7从一个干净的系统我这样做:从ruby​​installer.org安装RubyInstaller1.8.7-p358gem安装watirgem安装ocragitclonegit://github.com/snau

  9. RubyGems + Cygwin : POSIX path not found by ruby. exe - 2

    我是Windows上的Ruby程序员，试图从Wincmd切换到Cygwin，但无法执行Rubygems的批处理文件。我已经将任何bin目录填充到WindowsPATH环境中。变量，包括存储可执行文件的Rubybin。然而，gems是由ruby​​.exe本身调用的，这会导致以下POSIX路径问题:duddle@duddledan/cygdrive/c/Ruby/ruby-186-398/bin$gem-vC:\Ruby\ruby-186-398\bin\ruby.exe:Nosuchfileordirectory--/cygdrive/c/Ruby/ruby-186-398/bin/g

  10. ruby - Notepad++ 只是调用 "ANSI"的编码，有谁知道在 Ruby 中如何调用它？ - 2

    我有一堆.txt，Notepad++说(在其下拉“编码”菜单中)是“ANSI”。它们中有德语字符[äöüß]，在Notepad++中显示良好。但是当我File.read'thisisaGermantextexample.txt'它们时，它们并没有正确显示在irb中。那么有人知道我应该给Encoding.default_external=什么参数吗？(我假设这就是解决方案，对吧？)当'utf-8'或'cp850'时，它读取带有“äöüß”的“ANSI”文件为“\xE4\xF6\xFC\xDF”...(请不要犹豫，在你的回答中提及明显“显而易见”的事情；我和你一样新手，但仍然知道足以问这个

随机推荐