- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
比赛链接 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1;i <= n;i++) {
int a, b;
cin >> a >> b;
if (a > b) cnt++;
}
cout << cnt << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char dt[4][4];
bool solve() {
for (int i = 1;i <= 3;i++)
for (int j = 1;j <= 3;j++)
cin >> dt[i][j];
for (int i = 1;i <= 3;i++) {
if (dt[i][1] == '.') continue;
bool ok = 1;
for (int j = 1;j <= 3;j++) ok &= dt[i][1] == dt[i][j];
if (ok) {
cout << dt[i][1] << '\n';
return true;
}
}
for (int j = 1;j <= 3;j++) {
if (dt[1][j] == '.') continue;
bool ok = 1;
for (int i = 1;i <= 3;i++) ok &= dt[1][j] == dt[i][j];
if (ok) {
cout << dt[1][j] << '\n';
return true;
}
}
if (dt[1][1] != '.') {
bool ok = 1;
for (int i = 1;i <= 3;i++) ok &= dt[1][1] == dt[i][i];
if (ok) {
cout << dt[1][1] << '\n';
return true;
}
}
if (dt[1][3] != '.') {
bool ok = 1;
for (int i = 1;i <= 3;i++) ok &= dt[1][3] == dt[i][3 - i + 1];
if (ok) {
cout << dt[1][3] << '\n';
return true;
}
}
return false;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "DRAW" << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
pair<int, ll> res[200007];
bool solve() {
int n, m, h;
cin >> n >> m >> h;
for (int i = 1;i <= n;i++) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int j = 1;j <= m;j++) {
int x;
cin >> x;
pq.push(x);
}
int sum = 0;
int point = 0;
ll penalty = 0;
while (pq.size()) {
int t = pq.top();
pq.pop();
if (sum + t > h) break;
sum += t;
point++;
penalty += sum;
}
res[i] = { point,penalty };
}
auto tar = res[1];
auto cmp = [&](pair<int, ll> a, pair<int, ll> b) {return a.first == b.first ? a.second<b.second : a.first>b.first;};
sort(res + 1, res + n + 1, cmp);
int id = lower_bound(res + 1, res + n + 1, tar, cmp) - res;
cout << id << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int y[200007] = { (int)2e9 };
bool solve() {
int n;
double d, h;
cin >> n >> d >> h;
for (int i = 1;i <= n;i++) cin >> y[i];
sort(y + 1, y + n + 1, greater<int>());
double ans = 0;
for (int i = 1;i <= n;i++) {
double delta = min(h, 0.0 + y[i - 1] - y[i]);
ans += (2 - delta / h) * d * delta / 2;
}
cout << fixed << setprecision(6) << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
给定一个 \(n\) ,问是否存在 \(k \geq 2 ,s \geq 2\) ,使得 \(\displaystyle n = \sum_{i=0}^s k^i\) .
知识点:数学,枚举.
实际上, \(\displaystyle k^s < \sum_{i=0}^s k^i < (k+1)^{s}\) ,因此一定有 \(\displaystyle\left\lfloor \sqrt[s]{\sum_{i=0}^s k^i} \right\rfloor = k\) .
因此,我们枚举 \(s\) ,令 \(k = \left\lfloor \sqrt[s]{n} \right\rfloor\) ,然后验证这一对 \(s,k\) 。若 \(n\) 可行,那么一定有 \(\displaystyle \sum_{i=0}^s k^i = n\) .
其中开根号用的是 pow ,这个函数精度很差,但是这里是没有问题的,因为上下界都离得很远.
时间复杂度 \(O(60)\) 。
空间复杂度 \(O(1)\) 。
知识点:数学,二分,枚举.
注意到, \(s\) 不会太大,最大只可能 \(60\) ,考虑枚举 \(s\) .
对于一个 \(s\) ,由于 \(\displaystyle \sum_{i=0}^s k^i\) 是关于 \(k\) 单调的,我们可以二分 \(k\) ,找到使得 \(\displaystyle \sum_{i=0}^s k^i\) 小于等于 \(n\) 的最后一个 \(k\) ,随后验证这个 \(k\) 是否是答案即可.
注意到, \(k\) 也不会超过 \(10^9\) ,这个结论能降低常数.
时间复杂度 \(O(60 \times \log 10^9)\) 。
空间复杂度 \(O(1)\) 。
知识点:数学,二分,枚举.
对于 \(s \geq 3\) 的情况, \(k\) 不会超过 \(10^6\) ,因此可以枚举 \(k \leq 10^6\) ,对每个 \(k\) 预处理出 \(s \in[3,60]\) 的所有答案.
对于 \(s = 2\) 的情况,和方法一一样直接二分即可.
时间复杂度 \(\displaystyle O\left( \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) \cdot \log \left(\sum_{k=2}^{10^6}\log_k 10^{18}\right) + \log 10^9 \right)\) 。
空间复杂度 \(\displaystyle O\left(\sum_{k=2}^{10^6}\log_k 10^{18}\right)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
i128 qpow(i128 a, ll k) {
i128 ans = 1;
while (k) {
if (k & 1) ans *= a;
k >>= 1;
a *= a;
}
return ans;
}
bool solve() {
ll n;
cin >> n;
for (int i = 2, k;(k = pow(n, 1.0 / i)) >= 2;i++) {
i128 res = (1 - qpow(k, i + 1)) / (1 - k);
if (res == n) {
cout << "YES" << '\n';
return true;
}
}
return false;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2e18;
ll calc(int x, int s) {
ll sum = 0;
__int128_t mul = 1;
for (int i = 0;i <= s;i++) {
if (sum + mul > INF) return INF;
sum += mul;
mul *= x;
}
return sum;
}
bool solve() {
ll n;
cin >> n;
for (int i = 2;i <= 60;i++) {
int l = 2, r = 1e9;
while (l <= r) {
int mid = l + r >> 1;
if (calc(mid, i) <= n) l = mid + 1;
else r = mid - 1;
}
if (r >= 2 && calc(r, i) == n) {
cout << "YES" << '\n';
return true;
}
}
return false;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
set<ll> st;
void init() {
for (int i = 2;i <= 1000000;i++) {
ll sum = 1 + i + 1LL * i * i;
while (1 + (__int128_t)sum * i <= INF) {
sum = 1 + sum * i;
st.insert(sum);
}
}
}
ll calc(int x) {
return 1 + x + 1LL * x * x;
}
bool solve() {
ll n;
cin >> n;
if (st.count(n)) {
cout << "YES" << '\n';
return true;
}
int l = 2, r = 1e9;
while (l <= r) {
int mid = l + r >> 1;
if (calc(mid) <= n) l = mid + 1;
else r = mid - 1;
}
if (r >= 2 && calc(r) == n) {
cout << "YES" << '\n';
return true;
}
return false;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
init();
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
房间里有 \(n\) 个物品,每个物品的种类为 \(a_i\) 。这些物品中,有一个是模仿者伪装的.
现在可以进行一场最多 \(5\) 轮的实验去找出它,每一轮按顺序发生如下事件:
给出操作,找到模仿者.
知识点:枚举.
一开始可以不移出物品,这样若模仿者发生变化,则最多两轮一定有一个类型的物品多了一个.
移出除了多出来物品的类型以外类型的所有物品.
剩下的一定是包括模仿者的同一类型的物品,再最多不超过一轮,一定会出现一个不同类型的物品,就是模仿者.
时间复杂度 \(O(n)\) 。
空间复杂度 \(O(n)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
int a[207];
int cnt1[10], cnt2[10];
void query(const vector<int> &del) {
cout << "- " << del.size() << " ";
for (auto x : del) cout << x << " ";
cout << endl;
n -= del.size();
for (int i = 1;i <= n;i++) cin >> a[i];
}
void answer(int x) {
cout << "! " << x << endl;
}
bool solve() {
for (int i = 1;i <= 9;i++) cnt1[i] = cnt2[i] = 0;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i], cnt1[a[i]]++;
query({});
for (int i = 1;i <= n;i++) cnt2[a[i]]++;
int type = 0;
for (int i = 1;i <= 9;i++) {
if (cnt1[i] < cnt2[i]) {
type = i;
break;
}
}
if (!type) {
for (int i = 1;i <= 9;i++) cnt2[i] = 0;
query({});
for (int i = 1;i <= n;i++) cnt2[a[i]]++;
for (int i = 1;i <= 9;i++) {
if (cnt1[i] < cnt2[i]) {
type = i;
break;
}
}
}
vector<int> del;
for (int i = 1;i <= n;i++) if (a[i] != type) del.push_back(i);
query(del);
bool ok = 0;
for (int i = 1;i <= n;i++) {
if (a[i] != type) {
answer(i);
ok = 1;
break;
}
}
if (!ok) {
query({});
for (int i = 1;i <= n;i++) {
if (a[i] != type) {
answer(i);
ok = 1;
break;
}
}
}
return true;
}
int main() {
//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
有 \(n\) 种症状和 \(m\) 个药品,症状的情况通过一个长为 \(n\) 的 \(01\) 串给出.
每种药品治疗效果是可以使特定的一些症状消失,但副作用是使得特定的症状出现.
每种药有一个疗程 \(d\) ,疗程之内不允许使用其他药.
现在给出初始症状情况,问最少需要多少天才能使得症状全部消失.
知识点:最短路,状压dp,拓扑序dp.
考虑状压,将症状压缩为一个整数.
随后,我们将 \(2^n\) 种症状情况看作点, \(m\) 种药看作边。显然,每个点都可以有 \(m\) 条出边.
假设当前的症状是 \(st\) ,将要使用的药品的效果是 \(e\) ,副作用是 \(se\) ,那么使用后的症状为 (st & ~e) | se ,这样就构建了一条边,权值为疗程时间.
问题就变成,从初始状态到 \(0\) 状态的最短路,直接跑最短路即可.
求最短路的本质就是在最短路图这个DAG上进行拓扑序dp,因此一些dp可以考虑抽象成图的形式跑最短路.
时间复杂度 \(O(m2^n \log (m2^n))\) 。
空间复杂度 \(O(2^n + m)\) 。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int d[1007], e[1007], se[1007];
bool vis[1 << 10 + 1];
int dis[1 << 10 + 1];
struct node {
int v, w;
friend bool operator<(const node &a, const node &b) { return a.w > b.w; }
};
priority_queue<node> pq;
void dijkstra(int st) {
for (int i = 0;i < (1 << n);i++) dis[i] = 1e9, vis[i] = 0;
dis[st] = 0;
pq.push({ st,0 });
while (!pq.empty()) {
int u = pq.top().v;
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = 1;i <= m;i++) {
int v = (u & ~e[i]) | se[i];
int w = d[i];
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
pq.push({ v,dis[v] });
}
}
}
}
bool solve() {
cin >> n >> m;
int st = 0;
for (int i = 0;i < n;i++) {
char ch;
cin >> ch;
st |= (ch == '1') << i;
}
for (int i = 1;i <= m;i++) {
cin >> d[i];
e[i] = 0, se[i] = 0;
for (int j = 0;j < n;j++) {
char ch;
cin >> ch;
e[i] |= (ch == '1') << j;
}
for (int j = 0;j < n;j++) {
char ch;
cin >> ch;
se[i] |= (ch == '1') << j;
}
}
dijkstra(st);
cout << (dis[0] >= 1e9 ? -1 : dis[0]) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
最后此篇关于CodeforcesRound#883(Div.3)A-G的文章就讲到这里了,如果你想了解更多关于CodeforcesRound#883(Div.3)A-G的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我是一名优秀的程序员,十分优秀!