给一个赞吧!!!❤️
Atcoder-abc374 (0 ~ 4题)
题意:
阿帽先生特别喜欢”san”这个字符串所以希望你能告诉他一个字符串的后3位是否是san, 若是输出Yes, 否则输出No
约束:
-
字符串的长度介于 $[4, 30]$ 之间，由小写英文字母组成。
水题一道啦
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
if (s.substr(s.size() - 3, 3) == "san") cout << "Yes";
else cout << "No";
return 0;
}
不加原皮了
题意:
给定两个字符串A, B, 若A=B输出0, 否则输出第一个不相同的位置;
若长度不一且$A为B的前缀或B为A的前缀$, 输出最短字符串的长度
约束:
-
$A$ 和 $B$ 是长度介于 $[1, 100]$ 之间的字符串，由小写英文字母组成。
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> s >> t;
if (s != t)
{
if (s.size() != t.size())
{
int len = min(s.size(), t.size()) + 1;
for (int i = 0; i < len; i++)
if (s[i] != t[i])
{
cout << i + 1;
break;
}
}
else
{
int len = s.size();
for (int i = 0; i < len; i++)
if (s[i] != t[i])
{
cout << i + 1;
break;
}
}
}
else cout << 0;
return 0;
}
题意:
给定 $N$ 组原石, 每组原石的数量为$K_i (1≤i≤n)$, 若要将这些原石分成两组.
最优方案下, 两组中数量最小的一组原石, 最大是多少?
约束:
-
$2 \leq N \leq 20$
-
$1 \leq K_i \leq 10^8$
-
所有输入值均为整数。
思路:
由于n的范围, 所以可以暴搜.
每次选择一部分原石为一组, 剩下的原石就是第二组, 取最小的一组的数量更新答案即可;
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int a[N];
int st[N];
int n, sum;
int ans = 2e9;
void dfs(int u)
{
if (u > n)
{
int res = 0;
for (int i = 1; i <= n; i++)
if (st[i] == 1) res += a[i];
ans = min(ans, max(res, sum - res));
return;
}
st[u] = 1;
dfs(u + 1);
st[u] = 0;
st[u] = 2;
dfs(u + 1);
st[u] = 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
}
dfs(1);
cout << ans;
return 0;
}
题意:
又有一期深渊了, 已知有n堆丘丘人
每堆丘丘人在一个线段上(我们愿称为丘丘人线段), 第i段线段连接($A_i, B_i$)和($C_i, D_i$).
旅行者需要消灭这些丘丘人, 最开始旅行者在($0, 0$)的位置上
当旅行者不攻击丘丘人时, 旅行者可以以每秒$S$个单位的速度向任何方向上移动
否则,旅行者可以以每秒$T$个单位的速度向任意方向上移动.
一些丘丘人线段可能会重叠，在这种情况下，他需要分别攻击每个线段的重叠部分。当他以最佳方式刷怪时，消灭所有丘丘人所需的最小秒数是多少？
思路:
由于n的范围, 我们可以考虑对n个线段的顺序进行排列
每一种排列情况中, 进行选择, 使用dfs, 此时设两个参数记录当前线段是那个端点在使用
每次选择前往下一个线段的哪一个端点(注意, 若是第一个线段需要考虑从第一个线段的哪一个端点开始连接)
dfs要需要记录当前所的耗时
关于计算当前连接耗时的函数
刚开始记录当前线段所需要的耗时, 再计算到达下一个端点所需要移动距离的时间
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
long double s, t;
long double res = 1e9;
int n;
struct Cow
{
long double a, b, c, d;
int cmp;
bool operator< (const Cow &u) const
{
return cmp < u.cmp;
}
} g[N];
long double get_distance(long double xa, long double ya, long double xb, long double yb)
{
return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}
long double cal(int u, int op, long double x, long double y)
{
Cow now = g[u];
long double ans = get_distance(now.a, now.b, now.c, now.d) / t;
if (!op) ans += get_distance(now.c, now.d, x, y) / s;
else ans += get_distance(now.a, now.b, x, y) / s;
return ans;
}
void dfs(int u, int op, long double sum)
{
if (u >= n)
{
res = min(res, sum);
return;
}
// 这里的op记录的是计算当前线段是从哪一个端点开始的
dfs(u + 1, 0, sum + cal(u, op, g[u + 1].a, g[u + 1].b));
dfs(u + 1, 1, sum + cal(u, op, g[u + 1].c, g[u + 1].d));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> s >> t;
long double a, b, c, d;
for (int i = 0; i < n; i++)
{
cin >> a >> b >> c >> d;
g[i] = {a, b, c, d, i};
}
do
{
dfs(0, 1, 0); // 改一个后门都变
dfs(0, 0, 0); // 最开始考虑第一个线段
}
while (next_permutation(g, g + n));
cout << fixed << setprecision(8) << res;
return 0;
}
