目录
B. Not Quite a Palindromic String
题目来源
难度：900
解题思路
本题是让我们找出k对回文字符，我们可以将‘1’和‘0’的数量记录下来，判断1和0个数的差值，如果<=k,则有可能组成，可以让多出来的那部分先组成回文字符，再判断k是否能整除4，如果能说明组成k对后，则剩下的0，1可以分配为10101010形式进而不在形成回文字符，这样，就能保证恰好k对了。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
int n,k;
string s;
void solve()
{
unordered_map<char,int>mp;
mp.clear();
cin>>n>>k;
cin>>s;
for(int i=0;i<n;i++)
mp[s[i]]++;
k*=2;
if(abs(mp['1']-mp['0'])<=k||mp['1']==mp['0'])
{
k-=abs(mp['1']-mp['0']);
if(k%4==0)
{
cout<<"YES"<<endl;
return ;
}
}
cout<<"NO"<<endl;
mp.clear();
}
signed main()
{
IOS;
int _=1;
cin>>_;
while(_--)
solve();
return 0;
}
A. Mix Mex Max
解题思路
我们可以通过判断一个数组是否能通过替换其中的-1（可替换为任意非负整数），使得数组中所有元素都相等且不为0。
- 所有非-1元素的值必须相同（否则无法通过替换-1让所有元素相等）。
- 这个相同的值不能是0（如果是0，即使替换-1也只能全为0）。
- 如果数组全是-1，则可以将所有元素替换为同一个非0值。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl
const int N=106;
int a[N];
void slove(){
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int f=-1; // 用于记录第一个非-1元素的值,初始-1
for(int i=1;i<=n;i++){
if(a[i]==-1) continue;
if(a[i]!=f&&f==-1) f=a[i];//更新
if(a[i]!=f)//只要有不相等就NO
{
cout<<"NO"<<endl;
return ;
}
}
if(f==0)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
cin>>_;
while(_--)
slove();
return 0;
}
B. Everyone Loves Tres
题目来源
难度：900
解题思路
这道题很简单，就是用打表法找到所有的只由3和6构成的33和66的倍数，我们可以发现只要能被66整除那么一定也可以被33整除，经过打表我总结出了下面的一组数据：
- -1
- 66
- -1
- 3366
- 36366
- 333366
- 3336366
- 33333366
- 333336366
总结出就是除了1和3没有符合情况的存在，其他都有，而且当n为奇数时，就让n-5这个长度的3加上后缀36366，当n为偶数时，我们就让n-4这个长度的3加上3366这个后缀。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e6+6;
void solve()
{
int n;
string s,s1,s2;
s1="3366";
s2="36366";
cin>>n;
if(n==1||n==3){
cout<<-1<<endl;
return ;
}
if(n==2)
{
cout<<66<<endl;
return ;
}
else
{
if(n%2==1)
{
for(int i=5;i<n;i++)
s+='3';
s+=s2;
}
else
{
for(int i=4;i<n;i++)
s+='3';
s+=s1;
}
}
cout<<s<<endl;
}
signed main()
{
IOS;
int _=1;
cin>>_;
while(_--)
solve();
return 0;
}
B. Farmer John’s Card Game
题目来源
难度：900
解题思路
因为每一头奶牛每一回合都只能按顺序出一张牌，所以根据这个规律，第一头奶牛一定能放置 0,n,2n,…0,n,2n,… ，第二头奶牛能放置 1,n+1,2n+1,…1,n+1,2n+1,… 以此类推，不难发现每头奶牛的数列两个相邻的数之间都差n，所以只要发现有奶牛的差不等于n那么直接输出-1，否则将每头奶牛的最小牌值记录一下，最后输出即可。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=2006;
int n,m,a[N][N],b[N];
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>a[i][j];
sort(a[i]+1,a[i]+1+m);
b[a[i][1]]=i;
}
int f=0;
for(int i=1;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
int ans=a[i][j]-a[i][j-1];
if(ans!=n)
{
f=1;
break;
}
}
if(f)
break;
}
if(f)
cout<<-1<<endl;
else
{
for(int i=0;i<n*m;i++)
if(b[i])
cout<<b[i]<<" ";
cout<<endl;
}
for(int i=0;i<n*m;i++)
b[i]=0;
}
signed main()
{
IOS;
int _=1;
cin>>_;
while(_--)
solve();
return 0;
}
B. Paint a Strip
题目来源
难度：1000
解题思路
这道题一开始给你一个n,也就是有一个长度为n的数组，初始时元素都为0，可以有两种操作方式：
问使所有元素都变为1，至少使用第一类操作多少次。
为了使第一类操作最小，我们可以选择总和不小于⌈r−l+12⌉一段的两个端点赋值为1，最初时1~4，给1，4用第一类操作赋值为1，这样区间【2，4】的操作次数就是2，然后再选择1 ~10，端点1，10赋值为1，因为1本来就赋值过了，而且1 ~4都是1，再给10 赋值为1后，和变为5，就可以选择区间【1，10】，这样区间【5，10】的操作次数为3，依次类推，下一个区间可以选择1 ~22,区间【11，22】的操作次数都是4。。。。后面依次类推。
AC代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=1e5+10;
int n;
void solve()
{
cin>>n;
if(n==1)
{
cout<<1<<endl;
return ;
}
int i=1,ans=1;
while(i<n)
{
i=(i+1)*2;
ans++;
}
cout<<ans<<endl;
}
signed main()
{
IOS;
int _=1;
cin>>_;
while(_--)
solve();
return 0;
}