atcoder补题题解 abc_292 a~e
2023-04-18 15:26:59 时间
A - CAPS LOCK
题意:
将输入字母转成大写
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
string temp;
cin >> temp;
transform(temp.begin(), temp.end(), temp.begin(), ::toupper);
cout << temp << endl;
return 0;
}
总结:
如题
B - Yellow and Red Card
题意:
"1 x"是玩家x吃到黄牌, "2 x"是玩家x吃到红牌, "3 x"是询问玩家x是否被逐出游戏. 吃到2次黄牌或者一次红牌的玩家会被逐出游戏
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int n, q;
cin >> n >> q;
map<int, int> cnt;
for (int i = 1; i <= q; ++i)
{
int n1, n2;
cin >> n1 >> n2;
if (n1 == 3)
{
cout << (cnt[n2] >= 2 ? "Yes" : "No") << endl;
}
else
{
cnt[n2] += n1;
}
}
return 0;
}
总结:
如题
C - Four Variables
题意:
给一个正整数N, 求出符合 (AB+CD=N) 形式的 (A, B, C, D) 有几种
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxN = 2e5 + 10;
map<int, int> cnt;
void init()
{
for (int i = 1; i <= maxN; ++i)
{
for (int j = 1; j * j <= i; ++j)
{
if (i % j == 0)
{
++cnt[i];
if (i / j != j)
{
++cnt[i];
}
}
}
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
init();
int n;
cin >> n;
int ans = 0;
for (int i = 1; i < n; ++i)
{
ans += cnt[i] * cnt[n - i];
}
cout << ans << endl;
return 0;
}
总结:
求出1到2e5每个数能分解成几对2个因数相乘, 复杂度 nlogn
从1到N-1, 累加一下相乘的结果得到答案
D - Unicyclic Components
题意:
给出一个无向图, 问无向图的每一个连通块是否是满足点数等于边数
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxN = 2e5 + 10;
vector<int> son[maxN];
map<pair<int, int>, int> cnt1;
map<int, int> cnt2;
map<int, bool> vis;
map<pair<int, int>, bool> vis2;
int num1, num2;
void dfs(int now)
{
++num1;
num2 += cnt2[now];
vis[now] = 1;
int len = son[now].size();
for (int i = 0; i < len; ++i)
{
int v = son[now][i];
if (!vis2[make_pair(now, v)] && !vis2[make_pair(v, now)])
{
vis2[make_pair(now, v)] = 1;
num2 += cnt1[make_pair(now, v)];
num2 += cnt1[make_pair(v, now)];
}
if (!vis[v])
{
dfs(v);
}
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
if (u == v)
{
++cnt2[u];
}
else
{
son[u].push_back(v);
son[v].push_back(u);
++cnt1[make_pair(u, v)];
}
}
for (int i = 1; i <= n; ++i)
{
num1 = 0, num2 = 0;
if (!vis[i])
{
dfs(i);
}
if (num1 != num2)
{
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}
总结:
如题, 感觉写的不好.
E - Transitivity(补)
题意:
给出一个有向图, 问对于每三个不同的点若满足 (若顶点A指向顶点B, 顶点B指向顶点C, 则顶点A指向顶点C) 需要添加几条边.
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxN = 2010;
int n, m;
vector<int> son[maxN];
int ans;
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
son[u].push_back(v);
}
map<int, bool> vis;
for (int i = 1; i <= n; ++i)
{
vis.clear();
vis[i] = 1;
queue<int> q;
q.push(i);
while (q.size())
{
int now = q.front();
q.pop();
int len = son[now].size();
for (int i = 0; i < len; ++i)
{
int v = son[now][i];
if (vis[v])
{
continue;
}
vis[v] = 1;
++ans;
q.push(v);
}
}
}
cout << ans - m << endl;
return 0;
}
总结:
题目条件可以转换为一个顶点和它可以去到的每一个顶点之间都要有一条边, 那这样的话就可以对每一个点跑一遍bfs, 累加每个点的边数, 最后在边的总数量中减掉一开始就有的M条边就是答案了
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击