2025年洛谷 P7774 KUTEVI 题解

科技前沿 • 2025-02-19 15:58 • 阅读 78

大家好，我是讯享网，很高兴认识大家。

写这篇题解花了我很多不少时间，希望能过 awa

题意：

有 $m$ 个数，这 $m$ 个数能否由另外 $n$ 个数通过加减运算获得。

对于每一次加减的操作，结果不能小于 $0$ （角度不能小于 $0$ ）；
对于大于等于 $360$ 的结果，对 $360$ 取模。（大于 $360^{\circ}$ 的角会转一圈后继续转）

能则输出 YES ，不能则输出 NO 。

思路：

$\texttt{dp}$ （背包）、搜索都可以。~~dp 太难想~~ 这里我只讲搜索。

对于每一个状态，只有加和减两种状态。所以只需要对每一个状态枚举每一个数的加或减。

记录已经过状态，枚举中遇到了要获得的数，就表明可以实现。枚举结束后还没有遇到，则不能实现。

实现：

对于状态 $x$ ，

拓展 $(x\pm a[i]) \bmod 360$ 且 $x\pm a[i]\ge0$ 且未被拓展过。

上代码！

#include<bits/stdc++.h> using namespace std; int n,m; int a[11],b; bool vis[361]; bool bfs(int end) { 
    memset(vis,0,sizeof(vis)); queue<int> q; q.push(0); vis[0]=true; while(!q.empty()) { 
    int t=q.front();q.pop(); if(t==end) { 
    return true; } for(int i=1;i<=n;i++) { 
    int cg=(t+a[i])%360; if(cg>=0&&(!vis[cg])) { 
    vis[cg]=true; q.push(cg); } //可以不枚举减法，文后给出证明过程 /*cg=(t-a[i])%360; if(cg>=0&&(!vis[cg])) { vis[cg]=true; q.push(cg); }*/ } } return false; } int main() { 
    cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=m;i++) { 
    cin>>b; if(bfs(b)) puts("YES"); else puts("NO"); } return 0; }

讯享网

完结。

对于可以不枚举 $x - a$ 的证明：

讯享网

对于任意正整数 $x$ ， $a$ ， $k$ ， $p$ ，证明：

$\bmod 360 = x-ap$ 。

$x$ 指某一状态。意思就是，只用加 $k$ 次 $a$ 就可以枚举到 $x - a p$ 。

原式可转化为： $360 t + x - a p = x + a k$ ， $t$ 为任意正整数。

化简，得： $360 t = a (p + k)$ 。

所以，只需证明 $a (p + k)$ 恒为 $360$ 倍数。

若 $a$ 为 $360$ 倍数，得证；

若 $a$ 不为 $360$ 倍数，

则若使 $(p + k)$ 为 $360$ 倍数， $k = 360 - p$ 即可。

又有 $x-ap\ge0$ ，则 $p\le \frac{x}{a}<360$ 。

则 $k$ 在满足 $k = 360 - p$ 的条件下满足 $k > 0$ ，所以无论 $p$ 取多少都能满足 $(p + k)$ 为 $360$ 倍数。得证。

综上， $\bmod 360 = x-ap$ 。

第一次自己写 OI 证明题，有不对或不完善的地方请指出，谢谢qaq；

被打回x4 – 求过！

2025年洛谷 P7774 KUTEVI 题解

相关推荐