SDNU_ACM_ICPC_2021_Winter_Practice_4th [个人赛]
D – Odd Divisor
题意：
给你一个n，问你n是否至少有一个奇数因子（这里题意没说清，没说是不是只有一个还是可以有多个！AC以后才发现是不止一个
思路：
如果这个数没有奇数因子，那它肯定是2^k
1.所以我就开始用循环除2，看看最后是不是奇数，1除外，因为2的k次方除到最后就剩下1，所以得特判。但是这个做法感觉还是不够妙
再两个妙的做法：
2.因为2^k是指数函数，而与指数函数互为反函数的对数函数，所以我们可以用对数函数来判断是不是2的k次方
if((int)log2(n) == log2(n))
cout<<"NO\n";
else
cout<<"YES\n";
3.因为是2的k次方，所以对于他的二进制来说，除了首位是1，其他位应该是0，所以可以利用n&(n – 1)来判断。如果是2的幂次，那么n-1的二进制应该是全是1，这与n是刚好相反的，所以取并，得到的肯定是0.
if(n & (n - 1))
cout<<"YES\n";
else
cout<<"NO\n";
下面是第一种做法的AC码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, m;
int main()
{
cin>>n;
while(n--)
{
scanf("%lld",&m);
//cout<<m<<endl;
while(m)
{
if(m % 2 == 0)
m /= 2;
else
break;
}
//cout<<m<<endl;
if(m % 2 == 1 && m != 1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
E – New Year’s Number
题意：
给你一个数，让你判断是不是由2020或2021组成的
思路：
因为2020与2021相差不大，2021可以看出2020 + 1，所以我们可以对2020取余，得到余数a，再用那个数除以2020，得到商b，只需要比较b是否大于等于a即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, k, m, ans;
int main()
{
cin>>n;
while(n--)
{
cin>>m;
k = m % 2020;
ans = m / 2020;
if(ans >= k)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
K – 取石子游戏
题意：
给你两堆石子，有两种取法，一是从任意一堆中取任意数量的石子，或者是同时对两堆取相同数量的石子，最后取完的人胜，你先手，如果最后是你赢就输出1，否则输出0
思路：
得先找到必败点，也就是奇异局势
（0,0）（1,2）（3,5）（4，7）……
这些都是必败点，可以发现数之间的差值是成等差数列的，而且所有的自然数都包含在所有的必败点上。
剩下的就是找规律了
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ni1Q3g24-1611845112193)(C:\Users\Administrator\AppData\Roaming\Typora\typora-user-images\image-20210126205904000.png)]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
int main()
{
while(cin>>a>>b)
{
if(a > b)
swap(a, b);
if((int)((b - a) * (sqrt(5.0) + 1.0) / 2.0) == a)
cout<<0<<endl;
else
cout<<1<<endl;
}
return 0;
}
a) * (sqrt(5.0) + 1.0) / 2.0) == a)
cout<<0<<endl;
else
cout<<1<<endl;
}
return 0;
}
