写这篇题解花了我很多不少时间，希望能过 awa
题意：
有 个数，这 个数能否由另外 个数通过加减运算获得。
对于每一次加减的操作，结果不能小于 （角度不能小于 ）；
对于大于等于 的结果，对 取模。（大于 的角会转一圈后继续转）
能则输出 YES ，不能则输出 NO 。
思路：
（背包）、搜索都可以。dp 太难想 这里我只讲搜索。
对于每一个状态，只有加和减两种状态。所以只需要对每一个状态枚举每一个数的加或减。
记录已经过状态，枚举中遇到了要获得的数，就表明可以实现。枚举结束后还没有遇到，则不能实现。
实现：
对于状态 ，
拓展 且 且未被拓展过。
上代码！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #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);
}
}
}
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;
}
|
完结。
对于可以不枚举 的证明：
对于任意正整数 ，，，，证明：
。
指某一状态。意思就是，只用加 次 就可以枚举到 。
原式可转化为： ， 为任意正整数。
化简，得：。
所以，只需证明 恒为 倍数。
若 为 倍数，得证；
若 不为 倍数，
则若使 为 倍数， 即可。
又有 ，则 。
则 在满足 的条件下满足 ，所以无论 取多少都能满足 为 倍数。得证。
综上，。
第一次自己写 OI 证明题，有不对或不完善的地方请指出，谢谢qaq；
被打回x4 – 求过！