题目传送门

题面过于抽象，受笔者语文水平所限，就不在此翻译了，烦请各位读者自行理解。

探索

这是笔者第一道自己做的构造题。

我们不妨采用如下的顺序接吻：（用 C++ 语言表示）

void kiss(int Boy,int Girl){}

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        kiss(i,j);

其中 $Boy$ 表示男生编号，$Girl$ 表示女生编号。下面分别简称编号为 $i$ 的男生和女生为“男 $i$”和“女 $i$”。

笔者首先依次思考了 $n=3$ 和 $n=4$ 的情况，很快就想了出来。但是发现相同的方法对 $n=5$ 和 $n=6$ 的情况不适用（总是少一张纸）。因此，我重新思考了 $n=5$ 时的构造方案：

在开始安排之前，算一算，有 $\lfloor\frac{3\times 5}{2}\rfloor=7$ 张纸可以用。然后，思考亲吻的具体流程。

首先还是男 $1$ 亲遍所有女生。显然在男 $1$ 亲遍前 $(n-1)$ 个女生之前，男 $1$ 亲的那张纸的反面是不能动的。所以前 $(n-1)$ 个女生总是隔着（每次都不同）的一张纸巾和男 $1$ 接吻。如下：（蓝笔写的编号代表男生，红笔写的编号代表女生，黑笔写的编号为纸巾编号，灰线连接的两个面为接触面）

最初尝试的时候发现如果女 $n$ 直接和男 $1$ 用同一张纸亲会出问题，所以这次我们让女 $n$ 和前面 $(n-1)$ 名女生一样，也隔着一张纸巾和男 $1$ 接吻：

轮到男 $2$ 了。发现如果男 $2$ 如果直接用男 $1$ 用过的那张纸反面去亲遍女生会出大问题，让男 $2$ 新拿一张纸的话……没想过。（AC 掉这道题之后发现可以实现，只不过是顺序上的差异）所以，干脆大胆一点，直接让男 $2$ 和各位女生都只用一张纸巾亲吻！（这么说可能会引起误会，以下图所描述的情况为准）便宜男 $2$ 了

轮到男 $3$。发现男 $3$ 如果用男 $1$ 用过的那张纸反面的话会出大问题，所以要让男 $3$ 拿一张没用过的纸巾。但是……（本题解最关键的部分来了）男 $3$ 的亲法很有讲究。先用他亲的这张纸反面接触男 $1$ 亲过的那张纸反面（都是空白），然后让男 $1$ 亲过的那面与男 $2$ 亲过的那面接触，男 $2$ 亲过的那面的反面就是女生们亲的面了。

感觉没看懂？看下面这张图就明白了：

太乱了？看看这个局部图：

图中紫色的两个（空白）面相互接触，蓝灰色的两个面相互接触。这样，男 $3$ 和女生之间，就隔了 $3$ 张纸。

轮到男 $4$。男 $4$ 肯定不能拿男 $3$ 亲过的那张纸的反面去亲（男 $3$ 的细菌蹭到别的空白面上，浪费了），但是……他可以拿男 $1$ 亲过的那张纸的反面去亲！如下图：

最后是男 $5$。这次，男 $5$ 终于可以用男 $3$ 用过的那张纸的反面去亲女生了！

整体的纸巾使用情况如图：

正好一面不落，全都用过了！

对于 $n=6$ 的情况。我们发现，可以“浪费”掉男 $1$ 亲过的那张纸的反面，最终情况如下图：

按照这个思路，我们很快就能构造出 $n=7,8,9,...$ 的方案。

感觉正解已经出来了，那么总结一下规律吧。

规律及正确性证明

不妨设 $m=\lfloor\frac{3n}{2}\rfloor$，即纸的总张数。

则整个方案如下图所示（注意顺序）：

（第五步中，编号 $1$ 的纸巾的两个面标反了；这一步实际上可以通过省去 $1$ 号纸巾简化为两张纸，下文中提到的我的提交记录中使用的就是两张纸的亲法）

我们来证明一下这个方案的正确性。

除了男 $2$ 外，其余男生用的编号最大的纸巾的编号为

$$\bigg\lfloor\frac{n-2}{2}\bigg\rfloor+1$$

它等于

$$\bigg\lfloor\frac{n}{2}-1\bigg\rfloor+1$$

也就是

$$\bigg\lfloor\frac{n}{2}\bigg\rfloor-1+1$$

最后两项抵消，得

$$\bigg\lfloor\frac{n}{2}\bigg\rfloor$$

女生和男 $2$ 一共用过 $n$ 张纸，我们发现

$$\bigg\lfloor\frac{n}{2}\bigg\rfloor+n=\bigg\lfloor\frac{n}{2}\bigg\rfloor+\frac{2n}{2}=\bigg\lfloor\frac{3n}{2}\bigg\rfloor$$

一张不多，一张不少！

再来看看一共输出了多少个数。

满打满算，因为在我们的方案中，每对男女接吻至多需要用三张纸，所以我们大胆一点，不妨假设每对男女都用了三张纸。

一共 $n^2$ 对男女，每对所需输出的数的个数为 $2+1+2\times 3=9$，一共需要 $9\times 1000^2=9\times 10^6$ 张纸，远小于题目要求的 $5\times 10^7$，所以是完全合法的！

AC 代码

总结了规律后，我们就有了这个提交记录中的那份代码（完全可以把 $n=2$ 的特判给删掉，因为算出来的 $p=q=0$；$n=1$ 的特判不能删，删了还得加其他特判）。代码仅供参考，方案中存在可以改动的地方，所以请不要抄袭代码。

再次提醒，代码中第五步的操作只用了两张纸，与上文图中所示方法有所不同（省去了 $1$ 号纸巾）。

建议使用较快的输出，毕竟输出量还是挺大的。

尾声

感谢您的阅读，若有不妥之处还请批评指正。

#219. PIN

时间限制：200ms

空间限制：256MB

题意简述

给定正整数 $n$，求满足以下所有条件的整数三元组 $(a,b,c)$ 的数量：

• $0\lt a\lt b\lt c$；
• $a+b+c=n$；
• 设 $b=k_1a$，$c=k_2a=k_3b$，则 $k_1,k_2,k_3$ 均为整数。

输入格式

一行一个正整数 $n$（$1\le n\le 10^9$）。

输出格式

一行一个整数，表示满足条件的三元组数量。

输入输出样例

样例输入

35

样例输出

2

说明/提示

样例解释

两个三元组分别为 $(1,2,32)$ 和 $(5,10,20)$。

探索

显然 $k_2=k_3\times k_1$。

所以 $b=k_1a$，$c=(k_1\times k_3)a$。

进一步得 $n=(1+k_1+k_1\times k_3)a$。

由于 $a\lt b\lt c$，所以 $k_1,k_3\ge 2$。

设 $k=k_1\times k_3+k_1+1$，则 $k\ge 7$。

同时，$k-1=k_1\times k_3+k_1=k_1\times(k_3+1)$，故 $k-1$ 也要能够被表示为一个不小于 $2$ 的正整数和一个不小于 $3$ 的正整数的积才行。

所以，当 $k$ 确定时，满足条件的二元组 $(k_1,k_3)$ 个数即为 $k-1$ 的因数个数减二（不是 $1\times (k-1)$）再减一（如果 $(k-1)$ 是偶数那么 $k_3+1\ge 3$）。

再来看一下样例。

$n=35=35\times 1=7\times 5$。由于这两组反过来都会有 $k\lt 7$，所以只有这两种拆分方案。

$35-1=34=2\times 17$，$7-1=6=2\times 3$，两个数都具有唯一拆法，所以答案为 $2$。

考虑首先把 $n$ 的所有因子找出来，找完后暴力枚举所有大于等于 $7$ 的因子，将他们减一后算出各自的合法拆分数就可以了。

至于时间复杂度？一个数的因子少之又少，所以根本不需要花什么时间。实际上，不考虑排序，复杂度大概为 $\sqrt{n}$ 乘上一个常数（量级与 $n$ 的因子个数相同）。相信自己，勇敢尝试，不断进步，让我们体验成功带来的自信，从而走向自强吧！

AC 代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long

#define N 100007
int cnt,a[N];

inline bool check(int v,int k){//对于k3的判定
    return v!=1&&v!=k&&v!=2;
}

inline int Count(int k){//计算 k-1 的合法拆分方案数
    int res=0;
    for(int i=1;i*1ll*i<=k;i++)
        if(!(k%i)){
            res+=check(i,k);
            if(i*i!=k) res+=check(k/i,k);//注意平方数的判断（比如说9）
        }
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    int n,ans=0;
    cin>>n;
    if(n<7){cout<<0<<'\n';return 0;}//特判：无方案
    for(int i=1;i*1ll*i<=n;i++)//根号复杂度筛因子
        if(!(n%i)){
            a[++cnt]=i;
            if(i*i!=n) a[++cnt]=n/i;
        }
    sort(a+1,a+cnt+1);//将所有因子从小到大排序
    for(int i=cnt;i&&a[i]>=7;i--)
        ans+=Count(a[i]-1);//检查每个因子是否能作为 k
    cout<<ans<<'\n';

    return 0;
}

纯纯乐子题的乐子题解，看着玩就好。如果有什么不妥之处还请批评指正。

题目传送门

题目描述

给定一张含有 $N$ 个节点的 有向无环图（题中没有明说，但是由于没有不合法情况，故可以知道），节点编号从 $1$ 到 $N$。只有编号在 $1$ 到 $L$ 之间的 $L$ 个节点出度不为 $0$。保证编号在 $L+1$ 到 $N$ 之间的 $N-L$ 个节点入度均不为 $0$。

现在，将点 $1$ 的点权设为 $1$，并重复执行以下操作，直至编号在 $1$ 到 $L$ 中的所有节点点权均为 $0$ 为止：

• 选出点 $x$，满足 $1\le x\le L$，且点 $x$ 的点权大于 $0$。
• 对于每一条从 $x$ 出发的有向边，将到达的节点的点权加上 $x$ 的点权。
• 将点 $x$ 的点权设为 $0$。

在所有操作结束后，回答下面两个问题：

• 编号在 $L+1$ 到 $N$ 之间的所有点的点权和是多少？由于结果可能很大，输出其对 $10^9+7$ 取模的结果；
• 编号在 $L+1$ 到 $N$ 之间的所有点中，点权不为 $0$ 的点的个数是多少？

解析

很简单的一道题。

考虑拓扑排序，这样可以将同一节点上的所有操作一次性处理完。

记 $dp_i$ 为点 $i$ 的点权（对于编号在 $1$ 到 $L$ 之间的所有节点，其点权为操作期间所有下放到该点的点权之和），$vis_i$ 表示点 $i$ 由点 $1$ 出发是否可达。初始时 $dp_i$ 为 $1$，$vis_i$ 为 true。

显然，$dp_i$ 为所有有边连向点 $i$ 的点的 $dp$ 值之和，$vis_i$ 为所有有边连向点 $i$ 的点的 $vis$ 值的逻辑或。

然后就是一道简单的拓扑排序+递推了。时间复杂度 $\mathcal{O}(N+\sum K)$。

代码参见这个提交记录，请勿抄袭！

别把 e[x].size() 写成 e[i].size() 啊

谢谢阅读，点个赞吧~

题目传送门

题意简述

给定一个仅由 E 和 P 构成的环形字符串 $B$（$B$ 的串尾和串首相连）。询问 $B$ 中有多少连续子串同时满足：

• 长度不大于 $S$；
• 串中含有至少一个 E。

解析

正解是非常好想的咕！

首先，看到“环形”之后，立刻要想到展开咕！下面的数组都要开两倍长度咕！

然后思路就很清晰了咕！就是依次统计以第 $i$（$1\le i\le |B|$）位开始的，长度不超过 $S$ 的所有字符串中，有多少含有 E 就好了咕！

这个问题很显然可以使用滑动窗口咕！

首先扫一遍 $B$，在 $pos$ 数组中按顺序记录下其中为 E 的所有位置咕！

然后对 $pos$ 数组中当前已有的所有元素 $+|B|$ 后的值也按顺序放进 $pos$ 数组里咕！

最后用滑动窗口扫一遍就好了咕！答案要开 long long 咕！

扫滑动窗口的具体步骤为：

• 先将所有 $1\le pos_i\lt S$ 的位置按顺序放入一个队列中。
• 按照 $i$ 从 $1$ 到 $|B|$ 的顺序，执行：
• • 判断 $i+S-1$ 的位置上是否为 E。若是，则放入队列尾部；
• • 判断队列是否非空且 $i-1$ 的位置是否还在队列中。若是，弹出队首（易证，如果 $i-1$ 在队中，则它一定在队首）；
• • 判断队列是否非空。若是，将答案加上 $($队首 $-i)$ 的值。（末尾在队首之前的子串一定一个 E 都没有，末尾在队首及之后的子串一定有队首位置上的 E）

如果不在第二步判断队列是否非空，下面这组数据会卡掉你的代码（同时，你会喜提 WA on test #18）：

PEP
1

答案显然为 $1$。

滑动窗口时间复杂度 $\mathcal{O}(|B|+S)$，完全不需要担心 TLE 的问题咕！

代码参见这个提交记录咕！不要抄袭咕！

谢谢阅读咕！