1021. 皇后问题
和数据结构没太大关系，主要是一道找规律题
需要注意的是，不只是共同处于两条最长的对角线上的皇后会冲突，只要是“处在同一条斜线上”都会冲突，比如10*10的棋盘，一个皇后在（2，3），另一个在（3，4），这两个就是冲突的
很多人一开始的思路可能是开一个二维数组模拟棋盘，存入所有棋子坐标，再枚举每颗棋子和哪些冲突
但是n的范围最大可以到1e5，显然空间和时间复杂度都不对，所以我们需要更高效的做法
解决方案是可以开一个数组col，col[i]表示第i行上有多少个棋子，同理有row、diag1、diag2，一共四个数组，后面两个表示正、反对角线，需要注意前两个数组长度为n（为了方便从1开始计数，建议开到n+1），后两个是2 * n - 1（同理代码里可以开到2*n或者更大），因为正反对角线的数量都等于2 * n - 1（比如3*3的棋盘有5条正对角线和5条反对角线）
在读入棋子(x,y)时，我们需要：
col[x] += 1row[y] += 1diag1[x + y - 1] += 1（最左上角的一个棋子看作第一条正对角线，以此类推，如果不理解可以代入几个(x,y)试一下）diag2[x - y + n] += 1（最右上角的一个棋子看作第一条反对角线）
计算完之后，每个数组里的值k其实都代表一条线（横线/竖线/对角线）上有k个皇后，那么其实也就是有k * (k - 1) / 2对皇后冲突（组合数学问题，n个人两两握手，相同两个人只握一次，一共握n*(n-1)/2次）
所以写个循环累加就可以啦，还需要注意对角线需要遍历到2 * n - 1，以及ans别忘了开long long
时间复杂度O(N)
#include <bits/stdc++.h>
using namespace std;
#define MAXX 100005
// #define int long long
int c[MAXX] = {0};
int r[MAXX] = {0};
int p1[2 * MAXX] = {0};
int p2[2 * MAXX] = {0};
int main() {
int n;
cin >> n;
int x,y;
for (int i = 0;i < n;i++) {
cin >> x >> y;
c[x] += 1;
r[y] += 1;
p1[x + y - 1] += 1;
p2[x - y + n] += 1;
}
long long ans = 0;
for (int i = 1;i <= n;i++) {
if (r[i] > 0) ans += 1LL * r[i] * (r[i] - 1) / 2; //这里要乘1LL，不然可能会爆long long
if (c[i] > 0) ans += 1LL * c[i] * (c[i] - 1) / 2;
}
for (int i = 1;i <= 2 * n - 1;i++) {
if (p1[i] > 0) ans += 1LL * p1[i] * (p1[i] - 1)/2;
if (p2[i] > 0) ans += 1LL * p2[i] * (p2[i] - 1)/2;
}
cout << ans << endl;
return 0;
}1022. 字串排序
仔细读题，考虑清楚各种特殊情况即可，后面字符串的题目都建议使用C++完成，可以依靠string类写出很多简洁好看的代码，不用和C语言的那坨指针斗智斗勇
#include <bits/stdc++.h>
using namespace std;
vector<string> strings;
int getNum(const string& str) {
int num = 0;
bool flag = false;
for (char ch : str) {
if (isdigit(ch)) {
flag = true;
num = num * 10 + (ch - '0');
}
}
return flag ? num : -1; //如果没有数字，返回-1，在之后的比较里相当于是小于一切有数字的字符串了，即使那个字符串里的数字是0
}
bool cmp(const string& str1, const string& str2) {
int num1 = getNum(str1), num2 = getNum(str2);
if (num1 != -1 || num2 != -1) { //如果有至少一个有数字，那就可以用数字比较
if (num1 != num2) {
return num1 < num2; //两个字符串里的数字不相等，返回比较结果
}
}
return str1 < str2; //两个都没数字，或者两个都有数字但相等，只能字符串比较
}
int main() {
string str0;
while (cin >> str0) {
strings.push_back(str0);
}
sort(strings.begin(), strings.end(), cmp);
for (const string& s : strings) {
cout << s << " ";
}
return 0;
}
1023. 删除子串
字符串匹配的暴力算法模板题，建议纸上模拟一下以防边界问题
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s,s0;
cin >> s >> s0;
int i = 0,j = 0; //一开始能匹配的长度为0
while (i < s.length() && j < s0.length()) {
if (s[i] == s0[j]) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
if (j == s0.length()) { //能匹配的长度达到了s0的长度
for (int k = i - j;k < i;k++) { //从i-j到i的前一个都打上标记
s[k] = '#';
}
j = 0; //因为后面还要继续匹配，所以j要置为0
}
}
string ans = "";
for (char ch:s) {
if (ch != '#') { //有标记的说明要被删除
ans += ch;
}
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
for (int cas = 0;cas < t;cas++) {
printf("case #%d:\n",cas);
solve();
}
return 0;
} 1024. 字符串的交织
先交替逐字符输出，直到两字符串中较短的那个被输出完，再输出较长字符串剩下的部分
建议使用C++
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1,s2;
cin >> s1 >> s2;
int len1 = s1.size(),len2 = s2.size();
int len = len1 <= len2 ? len1:len2;
int i;
for (i = 0; i < len;i++) {
cout << s1[i] << s2[i];
}
if (len1 < len2) {
cout << s2.substr(i);
}else if (len2 < len1) {
cout << s1.substr(i);
}
return 0;
}1025. 字符串替换
字符串匹配板题2.0，使用了C语言
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define N 80
void replace(char s[], char x[], char y[]);
void replace(char s[], char x[], char y[]) { //TODO: your function definition
int lens = strlen(s),lenx = strlen(x),leny = strlen(y);
// printf("%d %d %d\n",lens,lenx,leny);
char* buffer = (char*)malloc(sizeof(lens+1));
for (int i = 0;i <= lens - lenx;i++){
int cnt = 0;
while (s[i + cnt] == x[cnt] && cnt < lenx){
cnt++;
}
// printf("%d %d\n",i,cnt);
if (cnt == lenx){
s[i] = '#';
}
}
int i = 0,pnt = 0;
// printf("%s\n",s);
while (i < lens) {
if (s[i] != '#') {
buffer[pnt] = s[i];
pnt++;
i++;
}else {
for (int j = 0; j < leny; j++){
buffer[pnt] = y[j];
pnt++;
}
i += lenx;
}
}
buffer[pnt] = '\0';
strcpy(s,buffer);
}
int main() {
char s[3 * N + 1], x[N + 1], y[N + 1];
scanf("%s%s%s", s, x, y);
replace(s, x, y);
printf("%s\n", s);
return 0;
}