cf--思维训练
目录
- B. Not Quite a Palindromic String
- 解题思路
- AC代码
- A. Mix Mex Max
- 解题思路
- AC代码
- B. Everyone Loves Tres
- 解题思路
- AC代码
- B. Farmer John's Card Game
- 解题思路
- AC代码
- B. Paint a Strip
- 解题思路
- AC代码
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元素的值,初始-1for(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;
}