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;
}
- Beginner AtCoder Contest 307 abcbeginner atcoder contest 307 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332