https://codeforces.com/contest/1884/problem/0
Codeforces Round 905 (Div. 3) B
不需要真的判断是否回文,本身删除字符的个数和位置就有很多可能性,删除后剩下的字符也可以随意排列,所以回文是不可控,但如果所有出现的字母均出现了偶数次,则一定可以构成回文
若只有一个字母出现奇数次,其余均出现偶数次,则可以把奇数次放中间可以构成回文
(orz这代码太智慧了)
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
void solve()
{
int n,k;
cin>>n>>k;
string s;
cin>>s;
int ji=0,ou=0;
int a[26]={0};//初始化使数组中每个元素为0
int len=s.length();
for(int i=0;i<len;i++)
a[s[i]-'a']+=1;
//s[i]-'a'为遍历字符串得到从a开始在字母表顺序中的位次
//这句语句即为对字母表的每个字母计数,使得a数组内存放每个字母出现的总次数
for(int i=0;i<26;i++)//遍历a数组
if(a[i]%2==1)ji++;//计数出现次数为奇数的字母的个数
if(ji-k<=1)cout<<"YES"<<endl;
//对于使计数器++的奇数次字母:若次数是1,那么只需删除这个字母,否则只需减1将其出现次数凑偶数
//要删除字符的数量为k,由上分析知删除时是将出现次数为奇数个的字母均删去一个,如果删去k个之后还剩一个奇数次可以把它放在中间位置构成回文,如果删去k个之后恰好能将奇数次全部减1也能构成回文
else cout<<"NO"<<endl;//否则无法构成回文输出No
}
signed main()
{
int t;
cin>>t;
while(t--)
solve();
}
https://codeforces.com/contest/1884/problem/0
Codeforces Round 904 (Div. 2) A
(奇怪 这道题是什么时候补好的 怎么一点印象都无 怎么22号就补交成功了一遍)
#include<iostream>
using namespace std;
//需要两个函数:一个用来求整数各位数之和,一个用来返回符合具体题目要求的值
int fun1(int a){
int b=0;
if(a<10) b=a;
else
{
while(a)
{
int right=a%10;
b+=right;
a/=10;
}//求出sum
}
return(b);//返回值是各位数之和
}
int fun2(int x,int k){
if(fun1(x)%k==0)
return x;
else{
while(fun1(x)%k){
x++;
int sum=fun1(x);
if(sum%k==0)
return x;
}
}
}
int main(){
int t,x,k,sum;
cin>>t;
for(int i=0;i<t;i++){
cin>>x>>k;
cout<<fun2(x,k)<<'\n';}
return 0;
}
https://codeforces.com/contest/1890/problem/0
Codeforces Round 906 (Div. 2) A
总结经验:读题时需要着重注意“可以任意排列数组中的元素(改变元素的顺序)”这种话,然后观察找到底层实现规律,在此题的背景下,奇偶性相同的位置应该包含相同的值。即b1=b3=b5=⋯,b2=b4=b6=⋯
我们知道在 [1,n]中有 [n/2] 个奇数和 [n/2]个偶数。因此,当且仅当我们能找到 ⌊n/2⌋
个相同的数,并且其余的也是相同的数时,答案就是 “是”。所有情况都可以分为这几类:
1.所有数字都相同,如 [3,3,3,3,3,3]。答案是 “是”。
2.有两个不同的数字,如 [1,2,1,2,1]。当且仅当其中一个数字恰好出现[n/2]
次时,答案是 “是”。如[1,2,1,2,1]和 [2,3,2,3]
3.有三个或三个以上不同的数字,答案是 “否”。
法1:
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int t;
cin>>t;
while(t--){
int n;
int a[110];
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);//排序使相同数字挨在一起
int x=0,y=0;
for(int i=1;i<=n;i++){
if(a[i]==a[1])x++;//记录和第一个数相等的数的个数
else if(a[i]==a[n])y++;//记录和最后一个数相等的数的个数
}
if((x+y)==n||a[1]==a[n]){//除了等于第一个就是等于最后一个,或者全是同一个数
if(x==0||y==0)cout<<"Yes\n";
else if(abs(x-y)==1||abs(x-y)==0)cout<<"Yes\n";//这两数的数量均占总数一半
else cout<<"No\n";
}
else cout<<"No\n";
}
return 0;
}
法2:stl操作
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
map<int ,int> occ;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
occ[x]++; //记录每个整数出现的次数
}
if (occ.size() >= 3) puts("No");//出现的数字种类大于等于3时
else {
if (abs(occ.begin()->second - occ.rbegin()->second) <= 1)puts("Yes");
//计算最高和最低出现次数的差
else puts("No");
}
}
return 0;
}
需要注意 occ 中元素是有序的(因为 std::map 是基于红黑树的),这样才能保证 begin() 和 rbegin() 分别指向最高和最低出现次数的元素
https://codeforces.com/contest/1883/problem/A
Codeforces Round 905 (Div. 3) A
这题是相对来说最应该做出来的,思路想到每次到“0”就自动更新成“10”即把0当10看,却一直在纠结这一步怎么操作(??)
看完AC的代码直接一整个醍醐灌顶的大动作
//关键一步(纠结点)
//
for(int i=0;i<4;i++)
{
if(a[i]==0)a[i]=10;
}
然后发现和我的很大的一个区别在于从设置函数功能的思路上,确实可以学着逐渐习惯利用函数完成从输入到输出的完整过程,这样每次都可以直接将函数定义为空类型void,在主函数中只需要完成样例个数的输入、循环的设置(如果需要的话),以及函数的引用(之前没意识到的一点:函数需要用到的相关字符串可以设置为在函数内部输入)
(看了好几个通过的代码都是直接用string)
完整代码:
#include<iostream>
using namespace std;
void solve()
{
string s;
cin>>s;
int a[4];
for(int i=0;i<4;i++)
{
a[i]=s[i]-'0';
if(a[i]==0)a[i]=10;//此处需要注意:是判断转换完成为整型数字的数组里各个元素是否为0,顺序一定不能颠倒
}
cout<<4+abs(a[0]-1)+abs(a[1]-a[0])+abs(a[2]-a[1])+abs(a[3]-a[2])<<endl;
}
signed main()
{
int turn=1;
cin>>turn;
while(turn--)
{
solve();
}
}
也可以在循环中直接ans+=abs(a[i+1]-a[i])+1来计算答案