AtCoder Beginner Contest 252 A - F 题解
传送门
A - ASCII code
输出
#include
#include
#include
#include
#include
#include
#include
#include B - Takahashi's Failure
找最大值，然后找是否有讨厌的
#include
#include
#include
#include
#include
#include
#include
#include C - Slot Strategy
题意罗里吧嗦的
以数字 0-9 枚举，判断一下所在位置（对应需要的时间），如果对应时间出现了多次，得相应地补若干个 10 秒，维护最大值，找最大值的最小值就好
#include
#include
#include
#include
#include
#include
#include
#include D - Distinct Trio
先处理两个的，算出前 i 个两两不同组合起来有多少种
对于第 i + 1 个的三个数字组合，无非就加多一个数字，就判断一下前面两两组合中，不包含当前数字的有多少种：可以维护一个 cnt 数字，代表 x 在前面出现了 cnt[x] 次，则 x 与剩下的两两组合，就有 (i - cnt[x]) * cnt[x] 种组合，减去这些就可以了
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll num[maxn], cnt[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> num[i];
ll ans = 0, pre = num[1] != num[2];
cnt[num[1]]++;
cnt[num[2]]++;
for(int i=3; i<=n; i++)
{
ans += pre - cnt[num[i]] * (i - 1 - cnt[num[i]]);
pre += i - 1 - cnt[num[i]];
cnt[num[i]]++;
}
cout << ans << endl;
return 0;
}
E - Road Reduction
dijstra
要求 1 到其他结点的路径和最短，说明是 1 到其他结点的最短路径建树
这么一想就发现是迪杰斯特拉的方式构建树
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct node
{
int u, v, id;
ll val;
node(int _u, int _v, ll _val, int _id){u = _u; v = _v; val = _val; id = _id;}
bool operator < (const node& a) const
{
return val > a.val;
}
};
vectorgra[maxn];
vectorans;
int vis[maxn];
void dijstra(int n)
{
priority_queueq;
q.push(node(1, 1, 0, 0));
while(q.size() && ans.size() < n)
{
node now = q.top();
q.pop();
if(vis[now.v]) continue;
vis[now.v] = 1;
ans.push_back(now.id);
for(int i=0; i> n >> m;
for(int i=1; i<=m; i++)
{
int x, y, z;
cin >> x >> y >> z;
gra[x].push_back(node(x, y, z, i));
gra[y].push_back(node(y, x, z, i));
}
dijstra(n);
for(int i=1; i F - Bread
哈夫曼编码
考虑反向合成上去，就会发现是哈夫曼编码的方式构造
因为最后砍完之后还可能剩下一段是没人要的，我们把这一段也视为是需要的，加入起始中去通过哈夫曼编码合成
#include
#include
#include
#include
#include
#include
#include
#include