Codeforces Round #547 (Div. 3) D. Colored Boots
2024-08-29 00:15:25
链接:https://codeforces.com/contest/1141/problem/D
题意:
给连个n长度的字符串。
求两个字符串相同字符对应位置的对数,并挨个打印。
字符:?可以代替任何字符。
思路:
对第一个字符串建立字符与位置的映射。
再处理第二个字符。
同时第二个字符中的‘?'不做处理。
全部遍历完了以后,再处理?的情况。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long LL; map<char, queue<int> > M;
vector<pair<int, int> > res;
queue<int> other; int main()
{
int n;
cin >> n;
string a, b;
cin >> a;
for (int i = 0;i < n;i++)
M[a[i]].push(i + 1);
cin >> b;
for (int i = 0;i < n;i++)
{
if (b[i] != '?')
{
if (M[b[i]].size() > 0)
{
res.push_back(make_pair(M[b[i]].front(), i + 1));
M[b[i]].pop();
}
else if (M['?'].size() > 0)
{
res.push_back(make_pair(M['?'].front(), i + 1));
M['?'].pop();
}
}
else
other.push(i + 1);
}
for (int i = 0;i <= 25;i++)
{
while (M[(char)(i + 'a')].size() && other.size())
{
res.push_back(make_pair(M[(char)(i + 'a')].front(), other.front()));
M[(char)(i + 'a')].pop();
other.pop();
}
}
while (M['?'].size() && other.size())
{
res.push_back(make_pair(M['?'].front(), other.front()));
M['?'].pop();
other.pop();
}
cout << res.size() << endl;
for (auto x : res)
cout << x.first << ' ' << x.second << endl; return 0;
}
最新文章
- Sql Server 内存相关计数器以及内存压力诊断
- VPB和OSGGIS安装
- Linux下查看版本号,查看存在的普通用户
- 初学java之菜单条,菜单,菜单项的设置
- C++为什么不支持某些东西
- HDU 5791 Two
- 解决ASP.NET Web API Json对象循环参考错误
- JavaScript学习笔记(一)数组排序
- TCP模型及其重点协议总结
- Maven 学习总结 (七) 之 灵活构建
- 【转】一文掌握 Linux 性能分析之网络篇
- Miller Robbin测试模板(无讲解)
- C语言 &#183; LOG大侠
- 20145207《Java程序设计》实验五(网络编程与安全)实验报告
- linux用户权限 ->; 系统特殊权限
- 服务器为什么这么慢?耗尽了CPU、RAM和磁盘I/O资源
- Centos7 Zabbix监控部署
- vue_ form表单 v-model
- redis key设计技巧
- KVM虚拟化学习记录
热门文章
- Linux下直接读写物理地址内存
- Java Web 项目打包脚本
- Gradle build-info.xml not found for module app.Please make sure that you are using gradle plugin &#39;2.0.0-alpha4&#39; or higher.
- bzoj1556 (DP)
- HihoCoder 1502 : 最大子矩阵 (双指针)
- BZOJ_3231_[Sdoi2008]递归数列_矩阵乘法
- 简单三步快速学会使用Mybatis-Generator自动生成entity实体、dao接口以及mapper映射文件(postgre使用实例)
- android自动化测试之uiautomator
- You Are the One
- 性能测试之Jmeter学习(三)