潍坊信息网网站建设,icp备案 网站首页,网站做关键词首页,个人旅游网站模板传送门
A - Count Takahashi
时间限制#xff1a;2秒 内存限制#xff1a;1024MB
分数#xff1a;100分
问题描述
给定 N 个字符串。
第 i 个字符串 () 要么是 Takahashi 要么是 Aoki。
有多少个 i 使得 等于 Takahashi #xff1f;
限制
N 是整数。每个…传送门
A - Count Takahashi
时间限制2秒 内存限制1024MB
分数100分
问题描述
给定 N 个字符串。
第 i 个字符串 () 要么是 Takahashi 要么是 Aoki。
有多少个 i 使得 等于 Takahashi
限制
N 是整数。每个字符串 是 Takahashi 或者 Aoki。()
输入格式 输出格式 输出 等于 Takahashi 的数量。
样例输入输出
样例输入1 样例输出1 和 等于 Takahashi而 不等于 Takahashi。
因此输出 2。
样例输入2 样例输出2 没有 等于 Takahashi。
样例输入3 样例输出3 代码
#include bits/stdc.h
using namespace std;inline int read() {int x 0, f 1; char c getchar();while (c 0 || c 9) { if (c -) f -1; c getchar(); }while (c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}int main () {int n read(), cnt 0;while (n--) {string s;cin s;if (s[0] T) cnt;}cout cnt;return 0;
}
B - Couples
时间限制2秒 内存限制1024MB
分数150分
问题描述
有 2N 个人站成一排位于第i个位置的人穿着颜色为 的衣服。这里衣服有 N 种颜色每种颜色正好有两个人穿。
找出满足以下条件的整数 的数量
颜色为 i 的两个人之间正好有一个人。
限制
每个从 1 到 N 的每个整数在 A 中恰好出现两次。所有输入值都是整数。
输入格式 输出格式 输出答案
样例输入输出
样例输入1 样例输出1 有两个 i 值满足条件1 和 3。
实际上穿着颜色为 1 的衣服的人分别在从左数第 1 和第 3 的位置中间正好有一个人。
样例输入2 样例输出2 没有 i 值满足条件。
样例输入3 样例输出3 代码
#include bits/stdc.h
using namespace std;inline int read() {int x 0, f 1; char c getchar();while (c 0 || c 9) { if (c -) f -1; c getchar(); }while (c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}int main () {int n read(), a[205], cnt 0;for (int i 1; i 2 * n; i) a[i] read();for (int i 1; i 2 * n; i) {for (int j i 1; j 2 * n; j) {if (a[i] a[j] j i 2) {cnt;break;}}}cout cnt;return 0;
}
C - Tile Distance 2
时间限制2秒 内存限制1024MB
分数350分
问题描述
坐标平面被 2 × 1 的瓷砖覆盖。瓷砖的铺设遵循以下规则
对于整数对 (i, j)方块 包含在一块瓷砖中。当 i j 是偶数时 和 包含在同一块瓷砖中。
瓷砖包括它们的边界并且没有两块不同的瓷砖共享正面积。
在靠近原点的地方瓷砖的铺设如下 Takahashi 从坐标平面上的点 ( 0.5, 0.5) 开始。
他可以重复以下移动操作任意次数
选择一个方向上下左右和一个正整数 n。向该方向移动 n 个单位。 每次他进入一个瓷砖他需要支付 1 的费用。
求他到达点 ( 0.5, 0.5) 所需支付的最少费用。
限制
所有输入都是整数。
输入格式 输出格式 输出 Takahashi 需要支付的最少费用。
样例输入输出
样例输入1 样例输出1 例如Takahashi 可以通过以下移动支付 5 的费用 向左移动 1。支付 0 的费用。向上移动 1。支付 1 的费用。向左移动 1。支付 0 的费用。向上移动 3。支付 3 的费用。向左移动 1。支付 0 的费用。向上移动 1。支付 1 的费用。
无法将费用减少到 4 或更少因此输出 5。
样例输入2 样例输出2 有些情况下不需要支付任何费用。
样例输入3 样例输出3 注意输出的值可能会超过 32 位整数的范围。
思路
将移动分为竖直方向跟水平方向来考虑。
任何情况下在竖直方向上的移动需要支付 。与此同时也能在水平方向上移动 个单位所以要给 加上 。如果在此之后水平方向依旧无法到达则需要加上 。
代码
#include bits/stdc.h
using namespace std;
#define int long long
signed main () {int a, b, c, d;cin a b c d;if (a c) swap(a, c), swap(b, d);if ((c d) 1) c--;if ((a b) % 2 0) a;int ans abs(b - d);a ans;if (a c) ans (c - a 1) / 2;cout ans;return 0;
}
E - Water Tank
时间限制2秒 内存限制1024MB
分数500分
问题描述
给定一个长度为 N 的正整数序列 。
有一个长度为 N 1 的非负整数序列 初始时 。
重复执行以下操作直到结束
1. 将 的值增加 1。 2. 对于每个 按顺序执行以下操作 如果 并且 则将 的值减少 1同时将 的值增加 1。
对于每个 找出在 首次成立之前执行了多少次操作。
限制
所有输入都是整数。
输入格式 输出格式 将对于每个 的答案输出在一行上以空格分隔。
样例输入输出
样例输入1 样例输出1 前五次操作如下。
这里每一行对应一次操作最左边的列代表步骤 1其余的代表步骤 2。 从这个图表中可以看出 首次在第4次操作后成立而 首次在第5次操作后成立。
类似地 的答案分别是 131426。
因此你应该输出 4 5 13 14 26。
样例输入2 样例输出2 请注意输出的值可能超出 32 位整数的范围。
样例输入3 样例输出3 思路
先说歪解看样例猜答案
我们很容易能发现每一个输出第第一项都是 。当 的时候如果 那么 否则 。
至于为什么各位先别急 是因为 才能将大于 的部分转移到 上
每次操作第二步的转移题目意思是从 上连续转移到最右边可以转移的位置上但这个也等价于在任意 上加 1再向右转移
如果 那么在这个条件下只需要在 上加 1再将这个 1 转移到 上去即可1步操作所以 。
代码
#include bits/stdc.h
using namespace std;
#define int long long
const int N 2e5 10;
int n, h[N], a[N], maxid 1;
inline int read() {int x 0, f 1; char c getchar();while (c 0 || c 9) { if (c -) f -1; c getchar(); }while (c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}
stackint s;
signed main () {n read();for (int i 1; i n; i) h[i] read();for (int i 1; i n; i) {while (s.size() h[s.top()] h[i]) s.pop();if (s.size()) a[i] a[s.top()] (i - s.top()) * h[i];else a[i] i * h[i] 1;s.push(i);}for (int i 1; i n; i) printf(%lld , a[i]);return 0;
}
F - Tree Degree Optimization
时间限制2秒 内存限制1024MB
分数550分
问题描述
你有一个整数序列 。对于一棵有 N 个顶点的树 T定义函数 f(T) 如下
令 为顶点 i 在树 T 中的度数。那么 。
找出 f(T) 的最小可能值。
约束条件保证答案小于 。
限制
所有输入都是整数。
输入格式 输出格式 输出答案
样例输入输出
样例输入1 样例输出1 考虑一棵树 T一条边连接顶点 1 和顶点 2一条边连接顶点 2 和顶点 4一条边连接顶点 4 和顶点 3。
那么。 可以证明这是 f(T) 的最小值。
样例输入2 样例输出2 样例输入3 样例输出3 思路
由于是一棵树所以树中总共有 N - 1 条边那么每个节点的度的范围为 每个节点的度的和 。
最开始的时候把每个节点的度初始化为 1。接着再用一个优先队列维护每一个节点的度加一后f(T) 增加的最小值。因为 所以只需要把 放入优先队列在维护一个小根堆即可。
代码
#include bits/stdc.h
using namespace std;
#define int long long
const int N 2e5 10;
int n, a[N], d[N], ans 0LL;
priority_queuepairint, int, vectorpairint, int, greaterpairint, int q;
inline int read() {int x 0, f 1; char c getchar();while (c 0 || c 9) { if (c -) f -1; c getchar(); }while (c 0 c 9) x x * 10 c - 0, c getchar();return x * f;
}
signed main () {n read();for (int i 1; i n; i) a[i] read();for (int i 1; i n; i) {d[i] 1, ans a[i];q.push({3 * a[i], i});}for (int i 1; i n - 2; i) {int x q.top().first, y q.top().second;q.pop();ans a[y] * (2 * d[y] 1);d[y];q.push({a[y] * (2 * d[y] 1), y});}printf(%lld, ans);return 0;
}
