草庐IT

CF1149E Election Promises

DCH233 2023-03-28 原文

CF1149E Election Promises

这个题目最难下手的地方在于：可以对相邻的城市进行任意修改，这导致难以确定后继状态。

但是还是可以使用 \(\operatorname{SG}\) 函数！

下面设 \(f_u = \operatorname{mex}\{f_v\}\)，这个可以直接拓扑排序求。

考虑这样一个状态：除点 \(u\) 外所有点的当前 \(h\) 均为 \(0\)，此时 \(\operatorname{SG}(x) = \omega_{f_u} \cdot h_u\)，其中 \(\omega_k\) 表示 \(k\) 阶无穷大。

先手必败当且仅当

\[S_k(x) = \bigoplus_{f_u=k}{h_u} = 0, \forall k \]

这个想法有点神秘和抽象，感觉非常的不对！所以现在我们抛弃掉 \(\operatorname{SG}\) 函数，来看看上面的想法是否可行。

  1. 首先，失败时所有 \(h\) 均为 \(0\)，满足上述条件。
  2. 当对于任意 \(k\)，使得 \(S_k(x) = 0\) 时，任意操作，由于相邻两点 \(f\) 值互异，只能得到 \(S(x) > 0\) 的局面。
  3. 当存在 \(k\)，使得 \(S(x) > 0\) 时，找到最大的 \(k\) 使得 \(S_k(x) > 0\)，一定存在一点 \(u\)，使得 \(S_k(k) \oplus h_u < h_u\)，于是可以减少这个点的 \(h\)，而通过修改这个点的相邻点，可以调整使得回到必败态。

于是，我们证明了上面的结论，得到了一个 \(O(n+m)\) 的算法，只需拓扑排序求出 \(f\) 即可。

ElectionPromisesspaninlineclassC++

有关CF1149E Election Promises的更多相关文章

  1. javascript - 使用 javascript 获取 Cloudflare 的 HTTP_CF_IPCOUNTRY header ？ - 2

    有很多关于如何使用javascript获取httpheader的问题，但由于某些原因，它们没有显示HTTP_CF_IPCOUNTRYheader。如果我尝试使用phpecho$_SERVER["HTTP_CF_IPCOUNTRY"];，它会工作，所以CF工作得很好。是否可以使用javascript获取此header？ 最佳答案 @Quentin的回答是正确的，适用于任何试图访问服务器header的javascript客户端。但是，由于这个问题特定于Cloudlfare，并且特定于在HTTP_CF_IPCOUNTRYheader中正常

  2. javascript - CF连接到云 Controller - 2

    我使用以下库连接到云Controllerhttps://github.com/prosociallearnEU/cf-nodejs-clientconstendpoint="https://api.mycompany.com/";constusername="myuser";constpassword="mypass";constCloudController=new(require("cf-client")).CloudController(endpoint);constUsersUAA=new(require("cf-client")).UsersUAA;constApps=new

  3. linux - 构建 cf-cli : go build runtime: linux/386 must be bootstrapped using make. bash 时出错 - 2

    CloudFoundry的CLI工具位于cloudfoundry/cli是用围棋写的。我正在尝试构建CLI工具但出现此错误:gobuildruntime:linux/386必须使用make.bash引导如何解决这个问题？下面是cli/bin/build-all.sh脚本的内容:#!/bin/bashset-eset-xOUTDIR=$(dirname$0)/../outGOARCH=amd64GOOS=windows$(dirname$0)/build&&cp$OUTDIR/cf$OUTDIR/cf-windows-amd64.exeGOARCH=386GOOS=windows$(di

  4. 【JTAG】1149.1协议详解 - 2

    目录一、简介二、测试访问端口2.1端口说明2.2TAP控制器2.3指令、数据寄存器三、边界扫描结构3.1结构概览3.2 BSR基本结构类型3.3EXTEST指令四、多TAP扫描链一、简介    1149.1协议定义了可包含在集成电路中的测试逻辑，以提供标准化的方法，其主要包含以下两点：    1.测试板级（PCB）或其他基层上的不同芯片间的互联；    2.测试芯片内部自身逻辑，可用于控制信号，也可用于观测信号。    如下图所示，1149.1测试逻辑主要由边界扫描寄存器（boundary-scanregister，BSR）、其他内建的控制或观测寄存器（TestDataRegister，TDR

  5. c# - XmlSerializer 在 .NET 3.5 和 CF.NET 3.5 之间有所不同 - 2

    我有一个在CF.NET和.NET下运行的库，但两者之间的序列化不同。因此，在CF.NET下生成的XML文件在.NET下不可读，这对我来说是个大问题!这里是代码示例:[Serializable,XmlRoot("config")]publicsealedclassRemoteHost:IEquatable{//...}publicclassProgram{publicstaticvoidMain(){RemoteHosthost=newRemoteHost("A");Listhosts=newList();hosts.Add(host);XmlSerializerser=newXmlSe

  6. Windows CF_DIB 到剪贴板中的 CF_BITMAP - 2

    我完全没有使用过Windows编程，但现在我有一个问题想在某个程序中修复。我需要将图像放置到Windows剪贴板，并且我有指向有效DIB(设备独立位图)的原始指针(在我的实验中，dibheader版本为3)。该程序使用具有延迟剪贴板渲染的模型，这意味着首先我们使用SetClipboardData(CF_DIB,NULL)然后在WM_RENDERFORMAT消息上程序将实际数据放入剪贴板使用SetClipboardData(format,dibDataPointer)。当我打开clipbrd.exe(在windowsxp上)并选择DIBView时，我可以毫无问题地看到图像。但是在msdn

  7. c# - 序列在 EF CF 迁移中包含多个元素错误 - 2

    我创建了一些模型，添加了迁移，然后执行了更新数据库操作，但在我最后一次更新数据库操作时，我收到了错误消息:Sequencecontainsmorethanoneelement您可以在下面找到我的迁移配置:context.Categories.AddOrUpdate(p=>p.CategoryName,newCategory{CategoryName="Sport"},newCategory{CategoryName="Music"});context.Subcategories.AddOrUpdate(p=>p.SubcategoryName,newSubcategory{Subcat

  8. c# - ZXing.Net 在 CF 中将字符串编码为二维码 - 2

    如何使用ZXing.Net将我的字符串编码为二维码？我已经可以解码了，但是编码有问题。它有一条错误消息:没有可用于AZTEC格式的编码器。这是我的代码:IBarcodeWriterwriter=newBarcodeWriter();BitmapbarcodeBitmap;varresult=writer.Encode("Hello").ToBitmap();barcodeBitmap=newBitmap(result);pictureBox1.Image=barcodeBitmap; 最佳答案 您没有完全初始化BarcodeWrit

  9. c# - 检测 USB 连接——C# .Net CF 3.5 - 2

    我有一个应用程序(.NetCompactFramework3.5)在WindowsMobile6.1设备上运行，我想检测USB连接何时发生变化(连接或断开连接)。我最初使用SystemProperty.CradlePresent属性来触发事件，但我想知道这是否仅在连接的设备具有ActiveSync时才有效？我将通过USB从未运行ActiveSync的Linux设备接收连接。我仍然可以使用SystemProperty.CradlePresent来检测USB的连接/断开连接吗？或者我是否需要探索其他选项来检测USB事件？谢谢。 最佳答案

  10. c# - 如何在 c# .net CF 3.5 中使用 XmlDocument 向 xml 添加属性 - 2

    我需要为元素“aaa”创建一个前缀为“xx”的属性“abc”。以下代码添加了前缀，但它也将namespaceUri添加到元素。要求的输出:我的代码:XmlNodenode=doc.SelectSingleNode("//mybody");XmlElementele=doc.CreateElement("aaa");XmlAttributenewAttribute=doc.CreateAttribute("xx","abc",namespace);newAttribute.Value="ddd";ele.Attributes.Append(newAttribute);node.Inser

随机推荐