问题 A: 字符串加密
直接模拟即可
点击查看代码
void bu_f(){
string s;
getline(cin,s);
LL ans=0;
for(int i=0;i<s.size();i++){
if(s[i]>='a'&&s[i]<='z') ans+=s[i]-'a';
else if(s[i]>='0'&&s[i]<='9') ans+=i*(s[i]-'0');
else ans++;
}
cout<<ans;
}
问题 B: k步排序
目标是:1-n的升序
需理解:相差为k的倍数的位置可以任意交换
如果该位置与目标位置不符且不满足相差为k的倍数,那么就预交换,如果预交换的次数大于2(预交换一次相当于改变两次),就不能。
点击查看代码
void bu_f(){
int n=read(),k=read();
vector<int> a(n+1);
for(int i=1;i<=n;i++) a[i]=read();
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]!=i){
if(abs(a[i]-i)%k!=0) ans++;
}
}
if(ans>2){
write(-1);
}
else write(ans/2);
printf("\n");
}
问题 C: 兔兔的快餐店
模拟即可
因为输入是升序的,只要连续的前后一样就要增加一个
点击查看代码
void bu_f(){
int n=read();
vector<int> a(n+1),b(n+1);
a[0]=b[0]=-1;
int ans=0,sum=1;
for(int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
if(a[i]==a[i-1]&&b[i]==b[i-1]){
sum++;
}
else{
ans=max(ans,sum);
sum=1;
}
}
write(ans);
printf("\n");
}
问题 D: 解锁
咋一看,好难,一看长度不超过4,直接暴力
对于初始状态的每一个位置改变一次,如果改变后的状态与爆破状态一样,则跳过
点击查看代码
set<string> sb;
string st,sd;
struct D
{
string s;
int step;
};
map<string,int> mp;//相当于vis
void bfs(){
queue<D> q;
q.push({st,0});
while(!q.empty()){
D t=q.front();
q.pop();
if(t.s==sd){
write(t.step);
return;
}
if(mp.count(t.s)) continue;
mp[t.s]=1;
if(!sb.count(t.s)){//不是爆破状态
for(int i=0;i<t.s.length();i++){
//特处理两个特殊状态
//每个位置可加可减
if(t.s[i]=='0'){
string s=t.s;
s[i]++;
q.push({s,t.step+1});
s[i]='9';
q.push({s,t.step+1});
}
else if(t.s[i]=='9'){
string s=t.s;
s[i]--;
q.push({s,t.step+1});
s[i]='0';
q.push({s,t.step+1});
}
else{
string s=t.s;
s[i]--;
q.push({s,t.step+1});
s[i]+=2;
q.push({s,t.step+1});
}
}
}
}
}
void bu_f(){
cin>>st>>sd;
int w=st.length();
string ss;
cin>>ss;
int t=0;
//截取爆破状态
for(int i=0;i<ss.length();i++){
if(ss[i]==',') {
string s=ss.substr(t,i-t);
sb.insert(s);
t=i+1;
}
}
//还有一个状态
sb.insert(ss.substr(t,ss.length()-1));
bfs();
}
问题 E: 相似数组
比较两数组的最大元素,如果相等不需要变化,然后从数组中移除
如果不相等,那么把最大元素修改,ans++
点击查看代码
int lens(int x){
int t=0;
while(x){
t++;
x/=10;
}
return t;
}
void bu_f(){
int n=read();
multiset<int> s1,s2;//mulset允许重复
for(int i=1;i<=n;i++){
int x=read();
s1.insert(x);
}
for(int i=1;i<=n;i++){
int x=read();
s2.insert(x);
}
int ans=0;
while(!s1.empty()&&!s2.empty()){
auto x=*s1.rbegin();
auto y=*s2.rbegin();
if(x==y){//相等。从数组中移除
s1.erase(s1.find(x));
s2.erase(s2.find(y));
}
else{
ans++;
//判断谁大
if(x>y){
s1.erase(s1.find(x));//先删除
int len=lens(x);
s1.insert(len);//然后再加入修改后的元素
}
else{
s2.erase(s2.find(y));
int len=lens(y);
s2.insert(len);
}
}
}
write(ans);
printf("\n");
}
问题 F: 兔兔的平均值
emmm,直接猜结论
1.如果x==y,那么无论先选择那个,平均值之和都不变,那么先输入1保证字典序最小
2.越小的集合选择越大的数,保证平均值最大
点击查看代码
struct F
{
int sum,id;
}a[N];
bool cmp1(F x,F y){
return x.sum==y.sum?x.id<y.id:x.sum>y.sum;
}
bool cmp2(F x,F y){
return x.sum==y.sum?x.id>y.id:x.sum>y.sum;
}
void bu_f(){
int n=read();
int x=read(),y=read();
for(int i=1;i<=n;i++){
a[i].sum=read();
a[i].id=i;
}
vector<int> b(n+1);
if(x==y){
for(int i=1;i<=n;i++){
if(i<=n/2) write(1),printf(" ");
else write(2),printf(" ");
}
printf("\n");
return;
}
else if(x<y){
sort(a+1,a+1+n,cmp1);
for(int i=1;i<=x;i++){
b[a[i].id]=1;
}
for(int i=x+1;i<=n;i++) {
b[a[i].id]=2;
}
}
else{
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=y;i++){
b[a[i].id]=2;
}
for(int i=y+1;i<=n;i++) {
b[a[i].id]=1;
}
}
for(int i=1;i<=n;i++) write(b[i]),printf(" ");
printf("\n");
}