数字反转
将一个数反转之后输出，不能有前导零。
题解
模拟。
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
int m = 0;
int x = (n < 0);
n = abs(n);
while (n > 0) {
m = m * 10 + n % 10;
n /= 10;
}
if (x) {
m = -m;
}
cout << m << endl;
}
统计单词数
给一个单词和一段文章，输出单词在文章中出现的次数和第一次出现的位置，不区分大小写。
题解
模拟。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s, p;
int main() {
getline(cin, s);
getline(cin, p);
s += ' ';
p += ' ';
for (int i = 0; i < s.length(); i++) {
if ('A' <= s[i] && s[i] <= 'Z') {
s[i] = 'a' + s[i] - 'A';
}
}
for (int i = 0; i < p.length(); i++) {
if ('A' <= p[i] && p[i] <= 'Z') {
p[i] = 'a' + p[i] - 'A';
}
}
int count = 0, pos = -1;
for (int i = 0; i < p.length(); i++) {
if ((i == 0 || p[i-1] == ' ') && p[i] != ' ') {
int flag = 1;
for (int j = 0; j < s.length(); j++) {
if (p[i + j] != s[j]) {
flag = 0;
break;
}
}
count += flag;
if (flag && pos < 0) {
pos = i;
}
}
}
if (pos >= 0) {
cout << count << ' ' << pos << endl;
} else {
cout << -1 << endl;
}
}
瑞士轮
给$2n$个整数对$(s_i,w_i)$（$w_i$唯一），有以下操作：
先将整数对按照$s_i$从大到小排序，之后将$2k-1$，$2k$($1<=k<=n$)分为一组，
如果$w_{2k-1} < w_{2k}$，$s_{2k}$加1，否则$s_{2k-1}$加1。
问进行以上操作$R$次之后按照$s_i$排序的第$Q$个整数对在未操作之前的编号是多少。
题解
直接暴力模拟的时间复杂度$O(nr\log{n})$。
每次操作之后将加1的分为一组，加0的分为一组，显然这样分组可以保证每组中依然是按照$s_i$排序的，
这样只要进行一次归并排序的合并操作，就能保证全部按照$s_i$排序。时间复制度$O(nr+n\log{n})$。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, r, q;
struct P {
int s, w, i;
friend int operator<(P a, P b) {
return a.s > b.s || a.s == b.s && a.i < b.i;
}
} a[N], b[N];
int main() {
cin >> n >> r >> q;
for (int i = 1; i <= n * 2; i++) {
scanf("%d", &a[i].s);
}
for (int i = 1; i <= n * 2; i++) {
scanf("%d", &a[i].w);
a[i].i = i;
}
sort(a + 1, a + n * 2 + 1);
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= 2 * n; j += 2) {
if (a[j].w > a[j + 1].w) {
a[j].s += 1;
} else {
a[j + 1].s += 1;
swap(a[j], a[j+1]);
}
}
int m = 0;
for (int j = 1, k = 2; j <= 2 * n || k <= 2 * n;) {
if (k > 2 * n || j <= 2 * n && a[j] < a[k]) {
b[++m] = a[j];
j += 2;
} else {
b[++m] = a[k];
k += 2;
}
}
for (int j = 1; j <= 2 * n; j++) {
a[j] = b[j];
}
}
cout << a[q].i << endl;
}
表达式的值
定义新运算
×运算优先于⊕运算。
给一个由×⊕()组成的表达式，填入0或1使得成为一个合法的表达式，问有多少种填法使得最后算出的值为0。
题解
先要会表达式求值。
转换为后缀表达式之后dp，后缀表达式计算的过程就是dp的过程。
每次取出栈顶的两个dp的状态进行运算，得到新的状态再放回栈顶。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 10007;
char s[N];
int n;
stack<pair<int,char>> st;
stack<pair<int,int>> f;
int main() {
cin >> n;
scanf("%s", s + 1);
int cnt = 1;
f.push(make_pair(1, 1));
int k = 0;
s[n+1] = ')';
for (int i = 1; i <= n + 1; i++) {
if (s[i] == '(') {
cnt += 1;
continue;
}
int val = 0;
if (s[i] == '*') {
val = cnt * 3 + 2;
}
if (s[i] == '+') {
val = cnt * 3 + 1;
}
if (s[i] == ')') {
val = cnt * 3;
cnt -= 1;
}
while(!st.empty()&&st.top().first >= val) {
pair<int,int> f1 = f.top();
f.pop();
pair<int,int> f2 = f.top();
f.pop();
pair<int,int> g;
if (st.top().second == '+') {
g.first = f1.first * f2.first % M;
g.second = (f1.first * f2.second + f1.second * f2.first + f1.second * f2.second) % M;
} else {
g.first = (f1.first * f2.first + f1.first * f2.second + f1.second * f2.first) % M;
g.second = f1.second * f2.second % M;
}
f.push(g);
st.pop();
}
if (s[i] != ')') {
st.push(make_pair(val, s[i]));
f.push(make_pair(1, 1));
}
}
cout << f.top().first << endl;
}