题目1
题目链接
题目大意：
给出一个字符串（由26个大写字母组成），询问这个字符串中，是否相同的字母都连在一起。
输入：
第一行整数t，表示有t个样例（1≤𝑡≤1000）
每个样例两行，第一行是整数n，表示字符串长度 (1≤𝑛≤50)
第二行是字符串
输出：
如果满足要求，则输出YES；
如果不满足要求，则输出NO；
Examples
input
5
3
ABA
11
DDBBCCCBBEZ
7
FFGZZZY
1
Z
2
AB
output
NO
NO
YES
YES
YES
题目解析：
用一个数组记录已经出现的字符串，从左到右枚举字符串；
对于第i个字符，如果和第i-1个字符不相同，则判断是否出现过：
已出现过则不满足要求；
未出现则标识该字符已出现。
class Solution {
static const int N = 100010;
public:
int n, m;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> str;
int a[256] = {0}, ok = 1;
a[str[0]] = 1;
for (int i = 1; i < n; ++i) {
if (str[i] == str[i-1]) {
continue;;
}
else {
if (a[str[i]]) {
ok = 0;
}
else {
a[str[i]] = 1;
}
}
}
if (ok) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
}
}
ac;
题目2
题目链接
题目大意：
给出一个数字n，求出[1,n]的区间中，有多少整数是可以满足，所有数字都是相同的。
输入：
第一行是整数t，表示有t个样例(1≤𝑡≤1e4).
每个样例一行，第一行是整数n(1≤𝑛≤1e9).
输出：
每个样例一行，输出1到n的整数中，有多少个由相同数字组成的数。
Examples
input
6
1
2
3
4
5
100
output
1
2
3
4
5
18
题目解析：
如果直接遍历数字1到n，可以算出来有多少个整数满足要求。
因为n比较比较大，这种做法会超时。
注意到满足要求的数字应该不多，我们可以直接满足要求的数字：
先看一位数的有多少个数字；
再看二位数的有多少个数字；
...
直到枚举出来的数字，比n还要大。
class Solution {
static const int N = 100010;
public:
int n, m;
string str;
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
int ans = 0;
int current = 1, cnt = 1;
while (current * cnt <= n) {
++ans;
++cnt;
if (cnt > 9) {
current = current * 10 + 1;
cnt = 1;
}
}
cout << ans << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
给出一个数字n，构造n * n的矩阵，要求：
相邻的数字，绝对值之差要大于1；
每个数字可以和上下左右，四个方向的数字相邻；
矩阵中的数字是1~n * n，没有重复；
输入：
第一行是整数t，表示有t个样例 (1≤𝑡≤100).
每个样例第一行是整数𝑛 (1≤𝑛≤100).
输出：
如果有解，则输出n行，每行n个整数；
如果无解则输出-1；
Examples
input
3
1
2
3
output
1
-1
2 9 7
4 6 3
1 8 5
题目解析：
1只有一个解，2无解；
从3开始，可以采用间隔的方式先填充数字；
1 0 2
0 3 0
4 0 5
如上，先从上到下，从左到右填充；
最后补齐
1 5 2
6 3 7
4 8 5
因为我们都是间隔着填充，相邻的数字只差，肯定大于1，满足要求。
class Solution {
static const int N = 100010;
public:
int n, m;
int a[101][101];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
if (n == 1) {
cout << 1 << endl;
}
else if (n == 2) {
cout << -1 << endl;
}
else {
int cnt = 1, x = 0, y = 0;
while (cnt <= n*n) {
a[x][y] = cnt;
++cnt;
y += 2;
if (y >= n) {
x += 1;
y -= n;
}
if (x >= n) {
x = 0;
y = 1;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << a[i][j] << " ";
}
cout << endl;
}
}
}
}
}
ac;
题目4
题目链接
题目大意：
给出n个数字的数组，问数组中存在多少个(i, j)的组合，满足i<j 且 a[j]-a[i]=j-i；
输入：
第一行是整数t，表示t个样例(1≤𝑡≤1e4).
每个样例有2行，第一行是整数n (1≤𝑛≤2⋅1e5)
第二行是n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤𝑛)
输出：
输出满足要求的组合数量。
Examples
input
4
6
3 5 1 4 6 6
3
1 2 3
4
1 3 3 4
6
1 6 3 4 5 6
output
1
3
3
10
题目解析：
将题目要求的 a[j]-a[i]=j-i 换一下位置，得到 (a[j] - j)= (a[i] - i)；
那么将所有的数字，减去当前的位置，然后排序，即可知道每一组数字的数量；
每一组数字假设有k个，那么就有k*(k-1)/2的可能。
class Solution {
static const int N = 200010;
public:
int n, m;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] -= i;
}
a[n] = 0;
sort(a, a + n);
lld ans = 0, cnt = 1;
for (int i = 1; i<= n; ++i) {
if (a[i] != a[i - 1]) {
ans += cnt * (cnt - 1) / 2;
cnt = 1;
}
else {
++cnt;
}
}
cout << ans << endl;
}
}
}
ac;
题目5
题目链接
题目大意：
给出长度为n的字符串，'*'表示绵羊， '.'表示空地；
每次可以把绵羊移动到相邻的空地，问需要移动多少次，才能将所有的绵羊赶在一起。
输入：
第一行是整数t，表示t个样例(1≤𝑡≤1e4).
每个样例有2行，第一行是整数n (1≤𝑛≤2⋅1e5)
第二行是字符串
输出：
最小的移动次数。
Examples
input
5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**
output
1
0
0
0
9
题目解析：
方法1：
暴力，假设羊最终集中在区间[left, right]上面，枚举left的位置，再用贪心从左到右匹配羊的位置。
方法2：
动态规划
dpLeft[i]表示，前i个位置中的所有羊，都集中在位置i左边；
dpRight[i]表示，[i, n]的位置中所有羊，都集中在位置i的右边；
这样只要得到结果之后，只要枚举每一个位置即可。
数据范围较大，没用long long 错了2次。
class Solution {
static const int N = 1000010;
public:
int n, m;
string str;
pair<lld, lld> dpLeft[N], dpRight[N]; // first 是最小代价，second的当前绵羊数量
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> n;
cin >> str;
dpLeft[0] = make_pair(0, 0);
for (int i = 1; i <= n; ++i) {
char c = str[i - 1];
if (c == '*') {
dpLeft[i].first = dpLeft[i-1].first;
dpLeft[i].second = dpLeft[i-1].second + 1;
}
else {
dpLeft[i].first = dpLeft[i-1].first + dpLeft[i-1].second;
dpLeft[i].second = dpLeft[i-1].second;
}
}
dpRight[n+1] = make_pair(0, 0);
for (int i = n; i > 0; --i) {
char c = str[i - 1];
if (c == '*') {
dpRight[i].first = dpRight[i+1].first;
dpRight[i].second = dpRight[i+1].second + 1;
}
else {
dpRight[i].first = dpRight[i+1].first+dpRight[i+1].second;
dpRight[i].second = dpRight[i+1].second;
}
}
lld ans = dpRight[1].first;
for (int i = 0; i <= n; ++i) {
ans = min(ans, dpLeft[i].first + dpRight[i + 1].first);
}
cout << ans << endl;
}
}
}
ac;
