A.Takahashi san 2#
题目描述#
判断字符串末尾是否有 san 这个后缀
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
std::string s;
std::cin >> s;
std::string t = s.substr(s.size() - 3);
std::cout << (t == "san" ? "Yes" : "No") << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}B.Unvarnished Report#
题目描述#
给定字符串 和 ,若字符串 和字符串 完全相等,则输出 否则输出 和 第一个不相同的位置.
解题思路#
首先判断两个字符串是否相同,
若相同直接输出
否则用 遍历一次字符串
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
std::string s, t;
std::cin >> s >> t;
if (s == t) {
std::cout << 0 << endl;
return;
}
for(int i = 0; i < std::max(s.size(), t.size()); i++) {
if (s[i] != t[i]) {
std::cout << i + 1 << endl;
break;
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}
C.Separated Lunch#
题目描述#
给出一个数 , 和一个长度为 的数组 , 将这个数组划分为 , 两个部分,使得这两个部分的和 和 中的最大值最小
数据范围: ,
解题思路#
瞄一眼中文题面, 有点像 背包, 但是你可以发现数据范围好像不能用背包，有没有其他方法呢?
好像 的范围比较小，我们可以使用 来搜索每一种情况，最多为 ,那么怎么判断哪种情况最优?只需要满足 和 的差值最小，答案即为差值最小时的最大值。
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
int n, w = 0;
std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i++) {
std::cin >> a[i];
w += a[i];
}
std::vector<int> f(n, 0);
int mi = inf, ans = inf;
std::function<void(int)> dfs = ([&](int u) {
if (u >= n) {
int s = 0;
for(int i = 0; i < n; i++) {
if (f[i]) {
s += a[i];
}
}
if (mi >= abs(w - s - s)) {
mi = abs(w - s - s);
ans = std::min(ans, std::max(s, w - s));
}
return;
}
f[u] = 1;
dfs(u + 1);
f[u] = 0;
dfs(u + 1);
});
dfs(0);
std::cout << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}D.Laser Marking#
题目描述#
在一个平面上给出 条线段的起始点和终点 现在要使用激光打印机打印这些线段,在打印线段时的移动速度为每秒 个单位长度, 不打印的时候的移动速度为每秒 个单位长度, 问打印这些线段的最短时间为多少？
解题思路#
由于一个线段可以从两个端点中的任意一个开始打印，看来这个题又和上面一个题一样使用 ,循环初始到达线段,先移动到其中一个端点,再移动到另一个端点，答案记录下来，再, 函数中的参数 , , , 表示在此之前是从点 移动到了 .其实 只传当前位置就行了,只是个人方便识别.
参考代码#
hypot()函数详解： hypot(x, y) 返回的是浮点型数据类型,值为 即将作为直角三角形的两条直角边的斜边。 hypot(x,y,z) 返回类型同上值为
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
int n, s, t;
std::cin >> n >> s >> t;
std::vector<int> A(n), B(n), C(n), D(n);
for(int i = 0; i < n; i++)
std::cin >> A[i] >> B[i] >> C[i] >> D[i];
std::vector<bool> vis(n, false);
double ans = INFINITY, w = 0;
auto check = [&]() -> bool {
for(int i = 0; i < n; i++) if (!vis[i]) return false;
return true;
};
std::function<void(int, int, int, int)> dfs = ([&](int x, int y, int u, int v) -> void {
if (check()) {
ans = std::min(ans, w);
// std::cout << ans << endl;
return;
}
for(int i = 0; i < n; i++) {
if (!vis[i]) {
vis[i] = true;
auto t1 = std::hypot(u - A[i], v - B[i]) / s;
auto t2 = std::hypot(u - C[i], v - D[i]) / s;
auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
w += tt, w += t1;
dfs(A[i], B[i], C[i], D[i]);
w -= t1, w += t2;
dfs(C[i], D[i], A[i], B[i]);
w -= t2, w -= tt;
vis[i] = false;
}
}
});
for(int i = 0; i < n; i++) {
vis[i] = true;
auto t1 = std::hypot(A[i], B[i]) / s;
auto t2 = std::hypot(C[i], D[i]) / s;
auto tt = std::hypot(A[i] - C[i], B[i] - D[i]) / t;
w = t1 + tt;
dfs(A[i], B[i], C[i], D[i]);
w = t2 + tt;
dfs(C[i], D[i], A[i], B[i]);
vis[i] = false;
}
std::cout << fix(16) << ans << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}