目录
T1 计算表达式
题意
表达式的形式如:3+5 * 6 - 4
其中, 运算数为一位整数,运算符为 +、-、* 三种,且运算符没有优先级的区分,一律自左向右计算。
如上例的计算过程为:3+5 * 6-4=8 * 6-4=48-4=44
分析 模拟题,找到一种固定输入格式:a[+b] [+b] [+b] ...
对于后面的一个操作符和操作数,可以看做一个整体进行输入。
连续输入,cin以空格,制表符(\t),换行(\n) 作为分割,当读入 EOF=End Of File时结束。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int main() {
int a, c; char b; cin >> a;
while (cin >> b >> c) {
if (b == '+') a += c;
if (b == '-') a -= c;
if (b == '*') a *= c;
}
cout << a;
return 0;
}
T2 查找子串并替换
题意
对输入的一句子实现查找且置换的功能(找到某个子串并换成另一子串),比如:
将“abcf abdabc”中的“abc”,替换为“AA”,则替换结果为“AAf abdAA”;
将“abcf abdabc”中的“abc”替换为“abcabc”,则替换结果为“abcabcf abdabcabc”。
本题查找子串时注意,大小写完全一致,才能作为子串,比如:在“Abcf abd Abc”中,如果找字符串“abc”是不存在的。
子串中可能包含空格,制表符等
分析 字符串模拟,利用string成员函数解决较为简单,这里复习一下string的常见函数;
int n=s.size(); 获得字符串的长度
int n=s.length(); 获得字符串的长度
int id=s.find("nos"); 如果在字符串s中找到"nos",则返回第一次出现的位置;否则返回string::npos;
int id=s.find(a); 返回字母在 s[0...n]中的第一个位置(下标),如果没有,返回npos,在int下可以看做-1。
int id=s.find(a, i); 返回字母在 s[i...n]中的第一个位置(下标),如果没有,返回npos,在int下可以看做-1。
s.substr(i, n); 是获得字符串中下标从 i 开始的连续 n 个字符的一段子串
s.append(a); 在字符串s后追加字符串 a
s.append(n, c); 在字符串s后追加 n 个字符 c
s.insert(开始位置,字符串); 指定字符串插入到字符串中的指定位置,把字符串插入指定位置
s.erase(开始位置a,长度b); 删除字符串中从开始位置起,长度为b的字符串
s.replace(i, k, b); 替换 s 从下标 i开始连续 k个字符为 b
s.replace(1,3,"title"); 将字符串s位置1开始,长度为3的字符串替换成字符串"title"的内容
to_string(b); 将数字 b 转为 string 类型
stoi(s), stod(s) 将字符串转为数字
sort(s.begin(),s.end()); 排序(首地址,末地址的后一位);
reverse(s.begin(),s.end()); 翻转(首地址,末地址的后一位);
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int main() {
string s, a, b;
getline(cin, s), getline(cin, a), getline(cin, b);
int i = s.find(a);
while (i != -1) {
s.replace(i, a.size(), b);
i = s.find(a, i + b.size());
}
cout << s;
return 0;
}
T3 AtoB
题意
给定一个 a 进制数 c,将它变成 b 进制并输出。
分析 很好的一个模拟题,学习加深对进制转换的理解和实现,需要注意的是当进制数大于10 时使用字母替代数字,另外需要注意的是数据范围。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int N = 1e6 + 10;
string AtoB(string c, int a, int b) {
LL t = 0;
for (int i = 0; i < c.size(); i++) {
if (c[i] <= '9') t = t * a + c[i] - '0';
else t = t * a + c[i] - 'a' + 10;
}
string s;
if (t == 0) s = "0";
while (t) {
LL r = t % b;
if (r < 10) s.append(1, r + '0');
else s.append(1, r - 10 + 'a');
t /= b;
}
reverse(s.begin(), s.end());
s = "(" + s + ")" + to_string(b);
return s;
}
int main() {
LL a, b; string c;
cin >> c >> a >> b;
cout << AtoB(c, a, b) << endl;
return 0;
}
T4 回形取数
题意
回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度(推导一下发现是逆时针)。一开始位于矩阵左上角,方向向下。
分析 直接模拟,按照下右上左的顺序一直取数,直到取到边界或者下一个数已经取过就切换方向。
有一个类似的题目,「NOIP2015」神奇的幻方,建议做一下
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210;
int n, m, s[N][N], res[N * N];
bool st[N][N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &s[i][j]);
int x = 1, y = 1, p = 0;
res[++p] = s[x][y], st[x][y] = 1;
while (p < n * m) {
while (x + 1 <= n && !st[x + 1][y]) res[++p] = s[++x][y], st[x][y] = 1;
while (y + 1 <= m && !st[x][y + 1]) res[++p] = s[x][++y], st[x][y] = 1;
while (x - 1 >= 1 && !st[x - 1][y]) res[++p] = s[--x][y], st[x][y] = 1;
while (y - 1 >= 1 && !st[x][y - 1]) res[++p] = s[x][--y], st[x][y] = 1;
}
for (int i = 1; i <= p; i++) printf("%d ", res[i]);
return 0;
}
T5 算24点
题意
给出 n 个整数,请问这 n 个数字在不改变顺序且不加入括号的情况下,有多少种运算能得到 24(运算符号只使用三种:+-*)。
比如:4 10 2 4 8,有如下3种运算能够得到24。
4+10-2+4+8=24
4-10-2+4*8=24
4*10-2*4-8=24
分析 搜索,运算符只有3个,那么可以将所有的运算符组合先dfs打表,最后带入计算即可。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 11, M = 3268800 + 10;
int n, a[N], cnt;
string s[M], op = "+-*";
// 生成一个长度 n-1 的op字符串
void dfs(string a) {
if (a.size() == n - 1) {
s[++cnt] = a; return;
}
for (int i = 0; i < 3; i++)
dfs(a + op[i]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(""); int ans = 0;
while (cnt--) {
stack<int> st; st.push(a[1]);
for (int i = 0, j = 2; i < n; i++, j++) {
char op = s[cnt + 1][i];
if (op == '+') st.push(a[j]);
if (op == '-') st.push(-a[j]);
if (op == '*') {
int tt = st.top(); st.pop();
st.push(tt * a[j]);
}
}
int res = 0;
while (st.size()) res += st.top(), st.pop();
if (res == 24) ans++;
}
cout << ans;
return 0;
}