A - Weekly Records
题目大意
小莫每天跑步, 输入n周每天的步数, 输出每周跑的总步数;
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k, idx;
signed main() {
cin >> n;
int sum = 0;
for (int i = 1; i <= 7 * n; i++) {
int x;
cin >> x;
sum += x;
if (i % 7 == 0) {
cout << sum << ' ';
sum = 0;
}
}
return 0;
}
B - racecar
题目大意
给定n个字符串, 问能不能从中找出两个字符串拼成一个回文串
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 5000;
int n, m, k, idx;
vector<string> v;
bool check(string s1,string s2) {
string s = s1 + s2;
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
if (s[i] != s[j]) return false;
}
return true;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
v.push_back(s);
}
for (int i = 0; i < v.size(); i++) {
for (int j = i + 1; j < v.size(); j++) {
if (check(v[i], v[j])||check(v[j],v[i])) {
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
return 0;
}
C - Ideal Sheet
题目大意
给定两个图A B, 它们都是由黑色快和透明色块组成的; 现在给出无限大的平面和一个图C, 要求用A和B在平面上拼成C, A和B都只能用一次且可以重叠, 不能剪裁不能旋转, 但是在平面的位置可以随意选择; 注意A和B必须全部用上, 不能只用A不用B;
解题思路
这个题我是真不想写...光是读题就读了好久, 思路不难但是很复杂...;
因为A和B不能旋转和剪裁, 所以我们只要知道一个黑色快的位置, 就能知道其他所有黑色快的位置; 所以我们先取出A和B中的一个点作为参照点; 这个题数据很小, 直接考虑暴力; 我们可以找到C中一个黑色块的位置作为C的参照点, 把A的参照点放在C的参照点上, 然后再遍历C中除了参照点以外的黑色快的位置, 然后算出这个点和C的参照点之间的相对位置, 然后用A的参照点加上这个相对位置, 看看A中有没有黑色快在这个位置上 ( 可以用map存A中黑色块位置 ) , 如果有则标记一下C中这个点的位置 ( 注意是要标记C中的位置, 不要记成A中的 ) , 没有则只能留给B了; 每找完一个C个参照点我们都要算一下 C中有多少个标记的点, 如果数量小于A中黑色块的数量, 那肯定是不符合要求; 如果符合要求就继续再看B, 过程是一样的, 区别只是每次找完C的参照点之后就要看看当前的标记能不能满足题目要求;
因为A和B可以在平面上随意移动, 所以黑色块在A和B上的坐标是没有意义的, 只能用相对位置的坐标;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N =15;
int n, m, k, idx;
map<PII, int> mp1;
map<PII, int> mp2;
map<PII, int> mp3;
vector<PII> v1;
vector<PII> v2;
vector<PII> v3;
bool st1[N][N];
bool st2[N][N];
signed main() {
idx = 3;
while (idx--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
if (s[j] == '#') {
if (idx == 0) {
v3.push_back({ i,j+1 });
mp3[{i, j+1}] = 1;
}
else if (idx == 1) {
v2.push_back({ i,j+1 });
mp2[{i, j+1}] = 1;
}
else if (idx == 2) {
v1.push_back({ i,j+1 });
mp1[{i, j+1}] = 1;
}
}
}
}
}
int ax = v1[0].first, ay = v1[0].second;
int bx = v2[0].first, by = v2[0].second;
for (int i = 0; i < v3.size(); i++) {
bool f = true;
memset(st1, false, sizeof st1);
int cx = v3[i].first, cy = v3[i].second;
st1[cx][cy] = true;
int num1 = 1;
for (int j = 0; j < v3.size(); j++) {
if (j == i) continue;
int dx = v3[j].first - cx, dy = v3[j].second - cy;
if (mp1[{ax + dx, ay + dy}]) {
st1[v3[j].first][v3[j].second] = true;
num1++;
}
}
if (num1 < v1.size()) continue;
for (int k = 0; k < v3.size(); k++) {
bool f = true;
memset(st2, false, sizeof st2);
int cx2 = v3[k].first, cy2 = v3[k].second;
st2[cx2][cy2] = true;
int num2 = 1;
for (int j = 0; j < v3.size(); j++) {
if (j == k) continue;
int dx = v3[j].first - cx2, dy = v3[j].second - cy2;
if (mp2[{bx + dx, by + dy}]) {
st2[v3[j].first][v3[j].second] = true;
num2++;
}
}
if (num2 < v2.size()) continue;
for (auto t : mp3) {
int a = t.first.first, b = t.first.second;
if ((!st1[a][b])&&(!st2[a][b])) {
f = false;
break;
}
}
if (f) {
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
return 0;
}
D - Mismatched Parentheses
题目大意
给定一个字符串, 将字符串中被' ( '和' ) '包裹起来的子串和括号一起删除, 输出剩余字符串;
解题思路
用堆来存' ( '的位置, 每找到一个' ) '就删除最顶层左括号的位置, 将其匹配; 最后再遍历字符串, 跳过被标记的区间即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e6+10;
int n, m, k, idx;
vector<int> v;
map<int, int> mp;
signed main(){
string s;
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] == '(') {
v.push_back(i);
}
else if (s[i] == ')') {
if (v.size() == 0) continue;
int x = v.back();
v.pop_back();
mp[x] = i;
}
}
for (int i = 0; i < n; i++) {
if (mp[i]) i = mp[i];
else cout << s[i];
}
return 0;
}
E - Distinct Adjacent
题目大意
n个编号为1~n的人按照数字大小做成一圈, 1与n相邻; 现在有0~m-1总共m个数字, 每个人从中选择一个数字; 问有多少选择方式使得没有相邻的两个人选择的数字相同;
解题思路
这个题比较容易想到是一个dp问题; 而难点在于判断第n个人的状态, 而第n个人的状态计算时要考虑第( n-1 )个人和第1个人; 所以我们状态表示为f[i][1]和f[i][0], 前者表示前i个人中, 第1个人和第i个人数字相同的选择方式, 后者则是不同; 所以我们状态计算时, f[i][1] = f[i-1][0], f[i][0] = f[i - 1][0] * (m - 2) + f[i - 1][1] * (m - 1); 很明显f[i][1]是不合法的, 他只是运算过程中所需要的中间量, 所以结果就是f[n][0];
别忘了初始化, f[1][1] = m, f[1][0] = 0;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10, mod = 998244353;
int n, m, k, idx;
int f[N][2], q[N];
signed main(){
cin >> n >> m;
f[1][1] = m;
for (int i = 2; i <= n; i++) {
f[i][1] = f[i - 1][0];
f[i][0] = (f[i - 1][0] * (m - 2) + f[i - 1][1] * (m - 1)) % mod;
}
cout << f[n][0];
return 0;
}