A ~ C
先声明，本人不是什么大佬，写这些题解只是面向刚打比赛的朋友，若题解存在问题，敬请指正！
A- 冰冰的正多边形
A题可能会不太理解自己错在哪里，题目要求解可以构成的多边形中最小周长，我们用map记录棒子的长度以及拥有的数量，然后遍历map，如果长度为 X 的木棒数量 >= 3，就记录一下答案，ans = min ( ans, X * 3 )，注意这里不是乘它的数量而是乘 3，因为题目要的是最小的周长，我们构造一个正三角形就够了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int t, n, m;
void solve()
{
cin>>n;
map<int,int>mp;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
mp[x]++;
}
bool sign=0;
int ans=1000000;
for(auto it:mp)
{
if(it.second>=3)
{
sign=1;
ans=min(ans,it.first);
}
}
if(sign)
{
cout<<"yes"<<endl;
cout<<ans*3<<endl;
}
else
cout<<"no"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
t = 1;
cin>>t;
while (t--)
{
solve();
}
return 0;
}
B-冰冰的电子邮箱
B题模拟，需要充分考虑字符的范围（字母 或 数字 或 ' . ' 或 ' - ' ）以及字符长度。
算长度的时候要是不太清楚要不要-1或者要不要取等，就自己举个例子吧，比如假设 index = 60 字符串长度为 65，也就是说下标最后会来到 65 的位置，那么 ' @ ' 后面的字符串长度就是 61 ~ 64 总共 4 个字符，也就是 i - index - 1，不能超过 255 ，也就是说如果 i - index -1 > 255 就输出 " no "
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int t, n, m;
void solve()
{
string s;
cin>>s;
int index=s.find('@');
if(index==-1 || index==0 || index==s.size()-1 || index>64)//这里已经判断了前半部分的字符串长度
{
cout<<"No"<<endl;
return;
}
if(s[0]=='.' || s[index-1]=='.' || s[index+1]=='.' || s[s.size()-1]=='.' || s[index+1]=='-' || s[s.size()-1]=='-')
{
cout<<"No"<<endl;
return;
}
int i=0;
for(i=0;i<index;i++)
{
if(!((s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z') || (s[i]>='0'&&s[i]<='9') || s[i]=='.'))
{
cout<<"No"<<endl;
return;
}
}
for(i=index+1;i<s.size();i++)
{
if(!((s[i]>='a'&&s[i]<='z') || (s[i]>='A'&&s[i]<='Z') || (s[i]>='0'&&s[i]<='9') || s[i]=='.' || s[i]=='-'))
{
cout<<"No"<<endl;
return;
}
}
if(i-index-1>255)
{
cout<<"No"<<endl;
return;
}
cout<<"Yes"<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
t = 1;
cin>>t;
while (t--)
{
solve();
}
return 0;
}
C-冰冰的异或
C题是找规律，但是我们首先要理解MEX，这个概念挺重要的，对于其他的MEX题目也通用。
给定一个序列 [ 1, 3, 2, 0, 5, 6 ]，对它从小到大排序后是这样的 [ 0, 1, 2, 3, 5, 6 ]，会发现这个排列少了4，那么这个序列的 MEX 就是4；再比如 [ 3, 1, 2 ]，排完序是 [ 1, 2, 3 ]，MEX 就是0。MEX就是从 0 开始，第一个没有在序列里出现的元素
好，再来讲一下异或 ⊕ ，异或就是将一个十进制的数转换为二进制，从右往左按照相同为0，不同为1的规则运算得到一个新的数，首先异或满足交换律，就是 a ⊕ b = b ⊕ a，还有 a ⊕ a = 0，所以我们选取两个数的时候不用考虑（i，j）、（j，i），这两种情况是一样的结果。
我们找几个例子来找规律
- n = 1，那只能取 1 了，而 1 ⊕ 1 = 0，从0开始，第一个没有出现的数是 1，所以MEX = 1；
- n = 2，我们可以取(1, 1), (1, 2), (2, 2), (2, 1)，但是因为 a ⊕ a = 0，以及 a ⊕ b = b ⊕ a，所以只有(1, 1), (1, 2) 这两种结果（当然你可以取其他组合，但结果只有两个），1 ⊕ 2 = 3，1 ⊕ 1 = 0 （这个结果你们可以在草稿纸上算出来，计算时心里默念：相同为0，不同为1，相同为0，不同为1...不容易懵圈），所以MEX = 1；
- n = 3，我们可以在 n = 2 的基础上取 (1, 3), (2, 3)，1 ⊕ 3 = 2， 2 ⊕ 3 = 1，现在我们有了 0， 1， 2， 3（3是 n = 2 时 (1, 2): 1 ⊕ 2 的结果， 所以 MEX = 4；
依次列举 n = 4, 5, 6, 7, 8，你会发现，n = 4, MEX = 4; n = 5, n = 6, n = 7, n = 8, MEX都等于 8，也就是说 1 ~ 8的数的任意组合的异或都不会得到 8 ，但是 n = 9 的时候，1 ⊕ 9 = 8，好，我们有 8 了，我们就去尝试 n = 9 ~ 16能不能得到9 ~ 15这些数，发现都可以得到，但怎么都得不到 16， 只有 n = 17时，1 ⊕ 17 = 16，把1 ⊕ 3 = 2， 1 ⊕ 5 = 4， 1 ⊕ 9 = 8， 1 ⊕ 17 = 16，这些式子放在一起，我们发现 MEX 都会卡在 2的幂次方的地方，而且当 n > 2^x 时，1 ⊕ n 就会得到 2^x，这样就会解锁MEX，MEX翻倍，这样我们就找到规律了
另外 n = 1, 2 时要特判一下
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL t, n, m;
void solve()
{
cin>>n;
if(n<3)
{
cout<<1<<endl;
return;
}
LL temp=1;
while(1)
{
temp*=2;
if(temp>=n)
{
cout<<temp<<endl;
return;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
t = 1;
cin>>t;
while (t--)
{
solve();
}
return 0;
}
京公网安备 11010502036488号