当前位置：网站首页>2022牛客多校第一场解题报告
2022牛客多校第一场解题报告
2022-07-28 06:38:00 【野指针*】
A.Villages: Landlines
思路:签到,直接划分区间,然后计算这些区间的距离之和即可
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
int x = 0, y = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x *= y;
}
inline void wt(int x) {
if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
const int N = 2e5 + 10;
int n;
struct rec {
int l, r;
bool operator< (const rec& i) {
return l < i.l;
}
} cor[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, r;
cin >> x >> r;
cor[i].l = x - r, cor[i].r = x + r;
}
sort(cor + 1, cor + 1 + n);
vector<PII> seg;
int cur, l_;
for (int i = 1, j = 0; i <= n; ++i) {
l_ = cor[i].l;
cur = cor[i].r;
while (j + 1 <= n && cor[j + 1].l <= cur) {
cur = max(cur, cor[j + 1].r);
++j;
}
seg.emplace_back(l_, cur);
i = j;
}
int ans = 0;
for (int i = 1; i < SZ(seg); ++i) {
ans += seg[i].first - seg[i - 1].second;
}
cout << ans << "\n";
}
signed main() {
IOS;
// cin >> T;
while (T--) solve();
}C-Grab the Seat!
思路:
我们要求被留下的格子,可以对每一行单独求,注意到,每一行最多留下的格子取决于上边界延申的直线与这行的交点最左边与下边界延申的直线与这行的交点的最左边的靠左边的点决定(图中该行是蓝色部分).然后我们对每一行直线上下边界延申的直线求交点,然后取最左边的值,最后累加起来就是答案了.
技巧:分开枚举
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
int x = 0, y = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x *= y;
}
inline void wt(int x) {
if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
const int N = 2e5 + 10;
int n;
struct rec {
int l, r;
bool operator< (const rec& i) {
return l < i.l;
}
} cor[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
int x, r;
cin >> x >> r;
cor[i].l = x - r, cor[i].r = x + r;
}
sort(cor + 1, cor + 1 + n);
vector<PII> seg;
int cur, l_;
for (int i = 1, j = 0; i <= n; ++i) {
l_ = cor[i].l;
cur = cor[i].r;
while (j + 1 <= n && cor[j + 1].l <= cur) {
cur = max(cur, cor[j + 1].r);
++j;
}
seg.emplace_back(l_, cur);
i = j;
}
int ans = 0;
for (int i = 1; i < SZ(seg); ++i) {
ans += seg[i].first - seg[i - 1].second;
}
cout << ans << "\n";
}
signed main() {
IOS;
// cin >> T;
while (T--) solve();
}D-Mocha and Railgun
思路:注意到,当AB方向平行与OQ方向时,答案最大.
然后用简单的勾股定理和三角函数知识可以解得ans
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 998244353
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
int x = 0, y = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x *= y;
}
inline void wt(int x) {
if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
void solve() {
double rc, x, y, d;
scanf("%lf %lf %lf %lf", &rc, &x, &y, &d);
double n = sqrt(x * x + y * y);
double l = n - d, r = n + d;
double d1 = sqrt(rc * rc - l * l), d2 = sqrt(rc * rc - r * r);
double dd = abs(d1 - d2), len = sqrt(d * d * 4 + dd * dd);
double cost = len / (rc * 2.0), theta = acos(cost);
theta = pi - theta * 2.0;
printf("%.6f\n", rc * theta);
}
signed main() {
// IOS;
// cin >> T;
T = rd();
while (T--) solve();
}G.签到题
I.Chiitoitsu
思路:设
为还剩
张牌没拿,手中还剩
张单牌,然后有一个贪心策略就是,如果拿到跟手上配对以后就配对,没配对直接扔掉.有状态转移
然后用记忆化搜索实现(期望dp倒着来)
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
int x = 0, y = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x *= y;
}
inline void wt(int x) {
if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
int qmi(int a, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int f[150][30];
int dp(int i, int j) {
if (j == -1) return 0;
if (f[i][j] != -1) return f[i][j];
int ans = 0;
ans += (i - j * 3) * inv(i) % MOD * dp(i - 1, j) % MOD;
ans += (j * 3) * inv(i) % MOD * dp(i - 1, j - 2) % MOD;
return f[i][j] = (ans + 1) % MOD;
}
void solve() {
string s;
cin >> s;
map<string, int> cnt;
int cc = 0;
for (int i = 0; i < SZ(s); i += 2) {
string ts;
ts += s[i]; ts += s[i + 1];
if (cnt[ts]) ++cc;
++cnt[ts];
}
cout << (dp(123, 13 - cc * 2) + MOD) % MOD << '\n';
}
signed main() {
IOS;
mem(f, -1);
cin >> T;
// T = rd();
for (int i = 1; i <= T; ++i) {cout << "Case #" << i << ": "; solve();}
}J.Serval and Essay
思路:如果发现一个集合只有两个元素,直接合并两个点能通向的点,然后修改那个点的from点,然后每次从小集合合并到大集合,也就是启发式合并,时间复杂度是O(nlogn)级别的.
代码:
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <assert.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define ll long long
#define ull unsigned long long
#define PII pair<int, int>
#define PDI pair<double, int>
#define PDD pair<double, double>
#define debug(a) cout << #a << " = " << a << endl
#define all(x) (x).begin(), (x).end()
#define mem(x, y) memset((x), (y), sizeof(x))
#define lbt(x) (x & (-x))
#define SZ(x) ((x).size())
#define wtn(x) wt(x), printf("\n")
#define wtt(x) wt(x), printf(" ")
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define eps 1e-8
int T = 1;
using namespace std;
inline int rd() {
int x = 0, y = 1; char c = getchar();
while (!isdigit(c)) { if (c == '-') y = -1; c = getchar(); }
while (isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
return x *= y;
}
inline void wt(int x) {
if (x < 0)x = -x, putchar('-'); ll sta[100], top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) putchar(sta[--top] + '0');
}
//记录每个点的入点和出点
//当一个点的入点只有一个时,就合并两个出点的集合,最后最大的集合的大小就是能到达的点的最大数量
const int N = 2e5 + 10;
set<int> from[N], to[N];
int n, fa[N], sz[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (SZ(to[x]) < SZ(to[y])) swap(x, y);
fa[y] = x, sz[x] += sz[y];
vector<PII> meg;
for (auto t : to[y]) {
to[x].insert(t);
from[t].erase(y);
from[t].insert(x);
if (SZ(from[t]) == 1) meg.emplace_back(t, x);
}
for (auto [x, y] : meg) merge(x, y);
}
void solve() {
n = rd();
for (int i = 1; i <= n; ++i) {
int k = rd();
for (int j = 1, x; j <= k; ++j) {
x = rd();
to[x].insert(i);
from[i].insert(x);
}
}
for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
for (int i = 1; i <= n; ++i) if (SZ(from[i]) == 1) merge(i, *from[i].begin());
int ans = 0;
for (int i = 1; i <= n; ++i) ans = max(ans, sz[i]);
wtn(ans);
for (int i = 1; i <= n; ++i) to[i].clear(), from[i].clear();
}
signed main() {
// IOS;
// cin >> T;
T = rd();
for (int i = 1; i <= T; ++i) { printf("Case #%d: ", i); solve();}
}边栏推荐
- Google and Stanford jointly issued a document: why do we have to use large models?
- sql server时间字段排序
- [leetcode] 24. Exchange nodes in the linked list in pairs
- [chart component kit] Shanghai daoning provides developers with steema download, trial and tutorial
- 聊一聊数据库的行存与列存
- Get the clicked line number in qtablewidget
- PMP practice once a day | don't get lost in the exam -7.13
- EMC EMI磁珠的特性
- What if the computer file cannot be deleted?
- Talk about synchronous, asynchronous, blocking and non blocking
猜你喜欢
Chairman tree review
Understand the propagation process of EMI electromagnetic interference through five diagrams - the influence of square wave steepness on high-frequency components, the spectrum graph from time sequenc
【300+精选大厂面试题持续分享】大数据运维尖刀面试题专栏（八）
单片机IO口控制12V电压通断，MOS和三极管电路
![MySQL query error [err] 1046 - no database selected](/img/32/7d877571397c1e2024ec488b783e87.png)
MySQL query error [err] 1046 - no database selected
【13】 Adder: how to build a circuit like Lego (Part 1)?
Rk3568 development board installation system startup
Understand CDN
五张图看懂EMI电磁干扰的传播过程-方波陡峭程度对高频成分的影响，时序到频域频谱图形，波形形状对EMI辐射的影响。
数字签名和CA证书
随机推荐
[chart component kit] Shanghai daoning provides developers with steema download, trial and tutorial
Tell you step by step what you need to do to apply for PMP? What should I do?
Can the variable modified by final be modified
[leetcode] 24. Exchange nodes in the linked list in pairs
Record a MYCAT connection and solve the problems of communications link failure
Talk about synchronous, asynchronous, blocking and non blocking
Creation of status bar (29)
Window 1 - > main window of the application (27)
本人男，27岁技术经理，收入太高，心头慌得一比
Brief introduction to ThreadLocal class
In QT multithreading, in which thread does the slot function perform analysis
js糖果消消乐小游戏源码
Draw.io image saving path settings
Characteristics of EMC EMI beads
DCL singleton mode
[environment configuration] ppyoole trains its own data set (for its own use)
百度智能云九州区县大脑，描绘城乡新蓝图！
Freezing and thawing of pytoch
js卡通英文字母打字小游戏源码
QT 怎么删除布局里的所有控件？