「公告」博客搬迁

置顶 | 发表于 2019-03-07 | 「公告」博客搬迁"> | 阅读次数:

字数统计: 109 字

新博客地址：orzsiyuan.com

Siyuan’s Blog已经从 hydingsy.github.io / old.orzsiyuan.com 搬迁到 orzsiyuan.com。本博客仅作为副本保留在此（这意味着今后可能删除），这里的文章将会陆续搬运到新博客中。

~~换过友链的大佬们可以考虑换个域名啦！新博客也继续资瓷换友链！QAQ~~

新的博客使用 Typecho 搭建，欢迎大家访问！

Siyuan

2019.03.07

「Codeforces 402E」Strictly Positive Matrix

发表于 2019-03-02 | | 阅读次数:

字数统计: 604 字

Description

题目链接：Codeforces 402E

你有一个 $n\times n$ 的矩阵 $a$。它满足如下性质：

对于任意的 $i,j$（$1\le i,j\le n$）都有 $a_{i,j}\ge 0$。
$\sum_{i=1}^n a_{i,i}=0$

矩阵 $b$ 是严格正矩阵当且仅当对于任意的 $i,j$（$1\le i,j\le n$）都有 $b_{i,j}>0$。

求是否存在整数 $k\ge 1$ 使得 $a^k$ 是一个严格正矩阵。

数据范围：$2\le n\le 2\times 10^3$，$0\le a_{i,j}\le 50$，$\sum_{i=1}^n a_{i,i}=0$

阅读全文 »

「Codeforces 1131D」Gourmet Choice

发表于 2019-03-02 | | 阅读次数:

字数统计: 774 字

Description

题目链接：Codeforces 1131D

美食家 Apple 先生是一家美食杂志的主编。他会用一个正整数来评价每一道菜。

美食家在第一天品尝第 $n$ 道菜，第二天品尝了 $m$ 道菜。他制作了一张 $n\times m$ 的表格，记录了他对菜肴的评价。如果第一套中的第 $i$ 道菜比第二套中的第 $j$ 道菜好，那么 $a_{i,j}$ 等于 >；如果要差，那么 $a_{i,j}$ 等于 <。菜肴可能同样美味，那么 $a_{i,j}$ 等于 =。

现在 Apple 先生想让你帮他评价每道菜。由于他是非常严格的，他会对菜肴进行评估，以便使用的最大整数尽可能小。但是 Apple 先生也很公平，如果 $a_{i,j}$ 为 <，那么给第一套中第 $i$ 道菜的评价一定小于第二套中第 $j$ 道菜。如果 $a_{i,j}$ 是 > 那么应该要更大。如果 $a_{i,j}$ 为 =，那么这两个数字要相等。

帮助 Apple 先生评价这两套中的每一道菜，使之符合他的感受，并满足最大数字尽可能小。如果有解则输出 Yes 和评价的数字；否则输出 No。

数据范围：$1\le n,m\le 10^3$。

阅读全文 »

「Codeforces 788E」New Task

发表于 2019-02-28 | | 阅读次数:

字数统计: 1.2k 字

Description

题目链接：Codeforces 788E

在第 228 届国际 Uzhlyandian 战略比赛中，各队均由 $5$ 名队员组成。

Masha 是新的国防部长，这位部长的主要职责是计算军队的效率。军队由 $n$ 名士兵组成，标号为 $1$ 到 $n$，第 $i$ 个士兵的技能值为 $a_i$。

这个队伍将由 $3$ 名队员和 $2$ 名助手组成，队员的技能值是相同的，助手的技能值不大于队员的技能值。对于 Masha 而言，助手应该分别站在队员的最左侧和最右侧。形式化地说，一个队伍有 $5$ 名士兵，下标为 $i,j,k,l,p$ 满足 $1\le i<j<k<l<p\le n$ 并且 $a_i\le a_j=a_k=a_l\ge a_p$。

军队的效率是 Masha 可以选择的不同队伍的数量。两个队伍是不同的当且仅当有至少一个人不同。

最初，所有的士兵都可以成为队员。由于某些原因，有时一些士兵不能成为队员或可以成为队员；但是所有士兵在任何时候都可以成为助手。Masha 有 $m$ 次操作，每次可以令第 $x$ 个士兵可以成为队员或不能。她需要你求出每次操作后可以选择的队伍数量，答案对 $10^9+7$ 取模。

数据范围：$1\le n,m\le 10^5$，$1\le a_i\le 10^9$

阅读全文 »

「UOJ 454」打雪仗

发表于 2019-02-27 | | 阅读次数:

字数统计: 787 字

Description

题目链接：UOJ 454

这是一道通信题。

小 A 有一个长度为 $2n$ 的 $01$ 字符串 $S$，小 B 有 $\{1,\dots,2n\}$ 这些下标中的 $n$ 个：$p_1,\dots,p_n$。小 A 和小 B 可以相互之间可以发送字符（但只能发送 0 或者 1 两种）。请为小 A 和小 B 设计一种通信方式，使得小 B 最终能知道这 $n$ 个下标所对应的字符 $S[p_1],S[p_2],\dots,S[p_n]$。两人中发送字符数较多的那一个不应发送超过 $m$ 个字符。

数据范围：$n=1000$，$m=1350$

阅读全文 »

「APIO 2016」Gap

发表于 2019-02-27 | | 阅读次数:

字数统计: 1.1k 字

Description

题目链接：UOJ 206

这是一道交互题。

有 $n$ 个严格递增的非负整数 $a_1,a_2,\dots,a_n$（$0\le a_1<a_2<\dots<a_n\le 10^{18}$）。你需要找出 $a_{i+1}−a_i$（$1\le i\le n-1$）里的最大的值。

你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。

你需要实现一个函数，该函数返回 $a_{i+1}−a_i$（$1\le i\le n-1$）中的最大值。

实现细节（C/C++）

你需要包含头文件 gap.h。

你需要实现一个函数 $\text{findGap}(T,N)$，该函数接受下面的参数，并返回一个 $\text{long long}$ 类型的整数：

$T$：子任务的编号（$1$ 或者 $2$）
$N$：序列的长度

你的函数 $\text{findGap}$ 可以调用系统提供的查询函数 $\text{MinMax}(s,t,\&mn,\&mx)$，该函数的前两个参数 $s$ 和 $t$ 是 $\text{long long}$ 类型的整数，后两个参数 $\&mn$ 和 $\&mx$ 是 $\text{long long}$ 类型的整数的指针（$mn$ 和 $mx$ 是 $\text{long long}$ 类型的整数）。当 $\text{MinMax}(s,t,\&mn,\&mx)$ 返回时，变量 $mn$ 将会存储满足 $a_i\in [s,t]$ 中 $a_i$ 的最小值，变量 $mx$ 将会存储满足 $a_i\in[s,t]$ 中 $a_i$ 的最大值。如果区间 $[s,t]$ 中没有序列中的数，则 $mn$ 和 $mx$ 都将存储 $-1$。在查询时需要满足 $s\le t$，否则程序将会终止，该测试点计为 $0$ 分。

限制与约定

对于所有的测试点，有 $2\le n\le 10^5$。

每一个测试点开始测试之前，$M$ 都将被初始化为 $0$。

子任务 $1$（$30$ 分）：每一次调用 $\text{MinMax}$ 都将使 $M$ 加 $1$。为了获得所有分数，需要满足对于该子任务下的所有测试点，都有 $M\le \frac{n+1}{2}$。

子任务 $2$（$70$ 分）：定义 $k$ 为调用 $\text{MinMax}$ 时，区间 $[s,t]$ 中的序列中数的数量。每次调用 $\text{MinMax}$，将使 $M$ 加上 $k+1$。对于每一个测试点，如果 $M\le 3n$，你将得到 $70$ 分，否则将得到 $\frac{60}{\sqrt{\frac{M}{n}+1}-1}$ 分。你的该子任务的得分是其下所有测试点中的最低分。