CF 461D Appleman and Complicated Task解题报告

题目


给你一个n*n网格，每一格要么是0要么是1要么为空，要求你用0或1填满所有空格，使得每个格子周围的0有偶数个。

题解

首先我们观察到这样一个事实：当第一行确定后，整个网格的填法就确定了。我们以N=8为例，把这种确定方法列出来：其中，“0246”这样的数的含义为，假设第一行为a[0..7]，它表示该格的值是a[0] xor a[2] xor a[4] xor a[6].



可以发现，这个形式是很规整的。都是“246”或者“1357”这种，连续的奇/偶数。

因此，我们的问题就变成了[……]

继续阅读

CF 449E Jzzhu and Squares解题报告

题目大意


给定一个N*M的网格。对一个顶点为格点的正方形R（不一定与格线平行），计算出其中有多少个单位格被R完全包含（记作F(R)）。求所有正方形的F(R)之和。

题解

首先画一个“勾股图”：



粉色是我们的正方形（不和格线平行），设其外接正方形的边长为L，四周直角三角形的短边为a，则长边为L-a。设其中完整包含了F(L,a)个单位格。

可以发现，其中完全包含的单位正方形分成两部分：第一部分是中间小正方形里的个，第二部分是周边直角三角形里包含的。

我们这么计算第二部分：一红一白两[……]

继续阅读

基于仿真模拟的弹道导弹封锁跑道效能分析

摘要

本文运用蒙特卡洛方法，对装备单弹头的弹道导弹攻击单条机场跑道的效能进行计算机仿真实验，研究了导弹在不同圆概率误差和瞄准策略下的毁伤效果。

简介

运用弹道导弹封锁机场，达成反介入效果，是现代战争中的重要议题。

不同的瞄准策略对封锁效果至关重要。例如，在马岛战争期间，英国空军进行了“黑鹿行动”，用火神式轰炸机挂载自由落体式炸弹对阿根廷斯坦利港机场进行轰炸，在该行动中，“火神”机组就选择了一条和跑道呈一定夹角的投弹航线，以保证至少有一枚炸弹命中。

对于弹道导弹而言，如果仅采用惯性制导，它的精度大致为百米级，而在运用各种中末端修正手段后，可以达到十米级，甚至米级精度。但这种制导系统价[……]

继续阅读

美军战略指导：《维持美国的世界领导力：21世纪国防的优先事项》

译者说明

本文译自http://archive.defense.gov/news/Defense_Strategic_Guidance.pdf，系美国国防部于2012年1月发表的一篇关于美国国防战略的文章，描述了美国在21世纪维护全球领导力所需的国防优先事项。译文略过了奥巴马和作者的序言。

如无公开说明，文中“我国/我军”均指美国/美军。本文不代表译者赞成或反对其中任何观点。

前言

六十五年来，美国一直在改造国际体系中起领导作用。美国与志同道合的国家携手并进，为我国，盟友及伙伴国家的人民创造了一个远比二战前更安全，更稳定，更繁荣的世界。在过去的十年间，我们在伊拉克和阿富汗进行了长期战争[……]

继续阅读

美国空军《2030年空中优势飞行规划》

译者说明

本文译自http://www.af.mil/Portals/1/documents/airpower/Air%20Superiority%202030%20Flight%20Plan.pdf，即美国空军《2030年空中优势飞行规划》的公开版本。

如无特殊说明，文中“我国/我军”均指美国/美军。

背景

空军参谋长已批准空中优势2030（Air Superiority 2030, AS 2030）事业能力协作小组（Enterprise Capability Collaboration Team, ECCT）发展能力选项，来确保联合部队在2030年及以后的高竞争环境下取得制空权。这些由空军[……]

继续阅读

海空一体战——军种协同应对反介入和区域拒止挑战

译者说明

本文译自http://archive.defense.gov/pubs/ASB-ConceptImplementation-Summary-May-2013.pdf，系“海空一体战”9.0版本的一份公开概要。

“海空一体战”是美军为应对（尤其是中国的）“反介入/区域拒止”，而提出的最新作战理论。一个悲伤的故事是：本文翻译完成时(2016.4)，美军似乎已经改用“全球公域介入与机动联合概念”了……

“反介入”和“区域拒止”分别指阻碍敌军向战区部署和阻碍敌军在战区内机动。它们威胁了美军“传统”的介入作战方式。“海空一体战”对此提出的解决方案是“网络化、整合化，纵深攻击来瓦解、摧毁[……]

继续阅读

反介入/区域拒止：现代战争的演变

译者说明

本文译自美国空军Christopher J. McCarthy少校的一篇文章，略去了原文最后的作者简介。

原文地址（可能需要科学上网）：

本文仅为翻译，不代表译者赞成或反对原文中任何观点。

摘要

在战争史上，对手总会尝试拒止另一方在战场上的行动自由。过去的反介入方式兼有保护己方力量和防止敌军获取优势的目的。作为远征部队，美军正依赖于安全地向战区部署，以及获取和维持制空、制天、制海权的能力。但是，中国作为一个区域大国，已显现出强壮的反介入/区域拒止（A2/AD）能力，用以瓦解美国[……]

继续阅读

[CodeChef FEB14]Graph Challenge解题报告（求半支配点）

题意

给一张有向图，使得从1开始按某种顺序DFS，可以让每个点的标号等于其DFS序号。求每个点的半支配点。

题解

使用Lengauer Tarjan算法，对这一算法的描述和证明见我的上一篇博文：

当然本题只需要求半支配点。
首先按照适当顺序DFS，还原题目描述中所称的DFS生成树。然后直接套算法。
代码如下，思路很简单。要点都写在注释中了。

#include
#incl[......]
继续阅读