A. Round Down the PriceAC代码 #include bits/stdc++.h#define IOS \ std::ios::sync_with_stdio(false); \ std::cin.tie(0); \ std::cout.tie(0);using PII = std::pairint, int;using ll = long long;void solve(){ ll n, d = 0; std::cin n; for (ll m
#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
void solve()
{
ll n, d = 0;
std::cin >> n;
for (ll m = n; m; m /= 10)
++d;
ll x = (ll)pow(10, d - 1);
std::cout << n - x << '\n';
}
int main()
{
IOS;
int t;
std::cin >> t;
while (t--)
solve();
return 0;
}
#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
ll solve()
{
ll res = 0;
std::string s;
std::cin >> s;
int p = 0, n = s.length();
std::vector<int> hash(27);
while (p < n)
{
int cnt = 0;
while (p < n)
{
if (!hash[s[p] - 'a'])
{
++cnt;
if (cnt > 3)
break;
hash[s[p] - 'a'] = 1;
}
++p;
}
++res;
std::fill(hash.begin(), hash.end(), 0);
}
return res;
}
int main()
{
IOS;
int t;
std::cin >> t;
while (t--)
std::cout << solve() << '\n';
return 0;
}
#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
void solve()
{
int n, k;
std::cin >> n >> k;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::map<int, int> fa, la; // first appear, last appear
for (int i = 1; i <= n; ++i)
{
if (!fa.count(a[i]))
fa[a[i]] = i;
la[a[i]] = std::max(fa[a[i]], i);
}
for (int i = 1, u, v; i <= k; ++i)
{
std::cin >> u >> v;
if (!fa.count(u) || !fa.count(v))
{
std::cout << "No\n";
continue;
}
int st = fa[u], ed = la[v];
std::cout << (st < ed ? "Yes" : "No") << "\n";
}
}
int main()
{
IOS;
int t;
std::cin >> t;
while (t--)
solve();
return 0;
}
#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
void solve()
{
std::string s;
int p;
std::cin >> s >> p;
int n = s.length();
ll now = 0, x;
std::vector<std::pair<char, int>> a(n + 1);
for (int i = 1; i <= n; ++i)
{
a[i] = {s[i - 1], i};
now += (s[i - 1] - 'a' + 1);
}
std::sort(a.begin() + 1, a.begin() + n + 1);
std::vector<bool> vis(n + 1);
for (x = n; x && now > p; --x)
{
vis[a[x].second] = true;
now -= (a[x].first - 'a' + 1);
}
std::sort(a.begin() + 1, a.begin() + n + 1, [&](std::pair<char, int> lft, std::pair<char, int> rht)
{ return lft.second < rht.second; });
std::string ans;
for (int i = 1; i <= n; ++i)
if (!vis[i])
ans.push_back(a[i].first);
std::cout << ans << std::endl;
}
int main()
{
IOS;
int t;
std::cin >> t;
while (t--)
solve();
return 0;
}
现有 \(n\) 张牌，每张包含 \(1 \sim n\) 的两个整数 \(a_i,b_i\) ，问能否将这 \(n\) 张牌分成两组，使每组中牌上的数均不相同。
题目分析首先排除以下两种情况：
- 某张牌上的数字相同（即 \(a_i = b_i\) ）
- 存在两张以上的牌包含数 \(x\)
假设现在牌 \(i\) 和 \(j\) 包含数 \(x\) ，我们不妨在点 \(i\) 和点 \(j\) 之间连一条边，然后进行二分图染色判定即可。
AC代码#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
void solve()
{
int n, isok = 1;
std::cin >> n;
std::vector<int> a(n + 1), b(n + 1);
std::vector<std::vector<int>> e(n + 1), g(n + 1);
for (int i = 1; i <= n; ++i)
{
std::cin >> a[i] >> b[i];
if (a[i] == b[i])
isok = 0;
e[a[i]].push_back(i);
e[b[i]].push_back(i);
}
for (int i = 1; i <= n; ++i)
{
if (e[i].size() > 2)
{
isok = 0;
break;
}
if (e[i].size() == 2)
{
g[e[i][0]].push_back(e[i][1]);
g[e[i][1]].push_back(e[i][0]);
}
}
std::vector<int> v(n + 1, -1);
std::function<void(int, int)> dfs = [&](int x, int col)
{
v[x] = col;
for (auto y : g[x])
{
if (v[y] == -1)
dfs(y, col ^ 1);
else if (v[y] == col)
isok = 0;
}
};
for (int i = 1; i <= n; ++i)
if (v[i] == -1)
dfs(i, 1);
std::cout << (isok ? "YES\n" : "NO\n");
}
int main()
{
IOS;
int t;
std::cin >> t;
while (t--)
solve();
return 0;
}
定义一个点集为可连通的，当且仅当树上存在某条路径穿过这组顶点，而不经过任何一条边两次（这条路径可以访问该点集外的其它顶点）。
\(q\) 次询问。每次询问某个点集是否为可连通的。
题目分析观察到简单版本的 \(q\) 很小，先预处理出每个点的父节点与深度， 对每个询问将点集放优先队列中按深度排序，然后不断往上爬，同时记录父节点的子节点数，如果父节点不在队列中就入队。如果最后的根节点的子节点数 \(> 2\) 或是其它节点的子节点数 \(\geq 2\) 则说明不连通，否则连通。
AC代码#include <bits/stdc++.h>
#define IOS \
std::ios::sync_with_stdio(false); \
std::cin.tie(0); \
std::cout.tie(0);
using PII = std::pair<int, int>;
using ll = long long;
int main()
{
IOS;
int n;
std::cin >> n;
std::vector<std::vector<int>> g(n + 1);
std::vector<int> dep(n + 1), pa(n + 1);
for (int i = 1, u, v; i < n; ++i)
{
std::cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
std::function<void(int, int)> getDepth = [&](int u, int fa)
{
pa[u] = fa, dep[u] = dep[fa] + 1;
for (auto v : g[u])
if (v != fa)
getDepth(v, u);
};
auto solve = [&]()
{
int k;
std::cin >> k;
std::vector<int> inq(n + 1), son(n + 1);
std::priority_queue<PII, std::vector<PII>> q;
for (int i = 1, x; i <= k; ++i)
{
std::cin >> x;
inq[x] = 1;
q.push({dep[x], x});
}
while (q.size() > 1)
{
PII t = q.top();
q.pop();
int u = t.second, d = t.first;
if (son[u] > 1)
return false;
int fa = pa[u];
son[fa] += 1;
if (inq[fa])
continue;
inq[fa] = true;
q.push({dep[fa], fa});
}
PII t = q.top();
q.pop();
int u = t.second, d = t.first;
if (son[u] <= 2)
return true;
return false;
};
getDepth(1, 0);
int q;
std::cin >> q;
while (q--)
std::cout << (solve() ? "YES\n" : "NO\n");
return 0;
}