蔚来杯 2022牛客暑期多校训练营 部分题解
正睿前先提前入狱坐会牢。
Round 1
C
二维平面,屏幕是
(0, 1)–(0, m) 的线段有
n 行m 列座位在屏幕前面,是坐标范围1 ≤ x ≤ n, 1 ≤ y ≤ m 的整点有
k 个座位已经有人,求出到屏幕的视线不被任何人挡住的座位数量
q 次询问,每次修改一个人的坐标后求出答案
2 ≤ n, m ≤ 2 \times 10^5 , 1 ≤ k ≤ 2 \times 10^5 , 1 ≤ q ≤ 200
观察到范围,本题是想让我们在
我们先思考一下一个人能挡住他人的情况,记这个人在
-
当
y = 1 或者y = m 的时候,一个人只会挡住其右边的点,如下: - 当
1 < y < m 时,我们要考虑的可以分成两部分:从(0,1) 引出的射线涵盖的地方,从(0,m) 引出的射线涵盖的地方,求个并集就 OK。
这两种情况其实是对称的,一种的斜率大于
接下来我们发现,对于一行来说,我们只需要考虑最前面的
所以我们从小到大处理,维护最大斜率,我们就能得出每一列的答案,
这样的总时间复杂度为
const int N = 2e5 + 10;
int n,m,k,q;
int x[N],y[N],pos[N];
vector <int> buc[N];
bool cmp(int x1,int y1,int x2,int y2) {
return y2 * x1 < y1 * x2;
}
signed main() {
read(n,m,k,q);
for (int i = 1;i <= k;++i) read(x[i],y[i]);
for (int i = 1;i <= q;++i) {
int num;read(num);
read(x[num],y[num]);
for (int j = 1;j <= m;++j) buc[j].clear(),pos[j] = n + 1;
for (int j = 1;j <= k;++j) buc[y[j]].push_back(x[j]);
int xx = -1,yy = 0;
for (int j = 1;j <= m;++j) {
if (j == 1) {
for (auto x : buc[j]) {
pos[j] = min(pos[j],x);
}
continue;
}
for (auto x : buc[j]) {
if (cmp(xx,yy,j-1,x)) xx = j-1,yy = x;
}
if (yy) {
int nowx = (ll)((j - 1) * yy + xx - 1) / xx;
pos[j] = min(pos[j],nowx);
}
//puts("here");
}
xx = -1,yy = 0;
for (int j = m;j >= 1.;--j) {
if (j == m) {
for (auto x : buc[j]) {
pos[j] = min(pos[j],x);
}
continue;
}
for (auto x : buc[j]) {
if (cmp(xx,yy,m-j,x)) xx = m-j,yy = x;
}
if (yy) {
int nowx = ((m-j) * yy + xx - 1) / xx;
pos[j] = min(pos[j],nowx);
}
}
ll ans = 0;
for (int j = 1;j <= m;++j) ans += pos[j] - 1;
printf("%lld\n",ans);
}
return 0;
}
J
有一张
n 个点m 条边的无重边无自环的有向图初始时可以选择一个点染黑,其余点均为白点
若某个点所有入边的起点均为黑点,则该点可以被染黑
最大化图中黑点数量
1 ≤ ∑n ≤ 2 × 10^5 , 1 ≤ ∑m ≤ 5 × 10^5
这个题建反图会更加直观。
一个点覆盖意味着前驱点都被覆盖,考虑贪心,如果遇到一个点的入度是 1,那么我们把这相应的两个点进行缩点,把两个点的信息合在一起,最后统计最大的点的大小就能得出答案,这里我们采用并查集维护。
朴素合并的复杂度是
我们发现这里同样可以应用启发式合并,每次把大的集合信息同步到小的集合信息上,就可以把复杂度变为
题解还将了个随机化做法,这个比较逆天,不是很会,有兴趣可以自己研究(
const int N = 2e5 + 10;
int n,f[N],siz[N],cas;
set <int> G1[N],G2[N];
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void dfs(int u,int v) {
int fx = find(u),fy = find(v);
if (fx == fy) return ;
if (G2[fx].size() > G2[fy].size()) swap(fx,fy);
vector <pii> edg;
for (auto y : G2[fx]) {
G2[fy].insert(y);
G1[y].erase(fx);
G1[y].insert(fy);
if (G1[y].size() == 1) edg.push_back(mp(fy,y));
}
f[fx] = fy;
siz[fy] += siz[fx];
for (auto p : edg){
dfs(p.first,p.second);
}
}
void solve() {
read(n);++cas;
for (int i = 1;i <= n;++i) G1[i].clear(),G2[i].clear(),f[i] = i,siz[i] = 1;
for (int i = 1;i <= n;++i) {
int k;read(k);
for (int j = 1;j <= k;++j) {
int y;read(y);
G1[i].insert(y);G2[y].insert(i);
}
}
for (int i = 1;i <= n;++i) {
if (G1[i].size() == 1) {
dfs(i,*G1[i].begin());
}
}
int ans = 0;
for (int i = 1;i <= n;++i) ans = max(ans,siz[i]);
printf("Case #%d: %d\n",cas,ans);
}
signed main() {
int T;read(T);
while (T--) solve();
return 0;
}
Round 2
D
有一家商店,在这家商店里有
n 个物品和m 条交易方法,对于每条交易方法,你可以用k \times a_i 的b_i 类物品换到k\times w \times c_i 的d_i 类物品(其中k,w 是任意正实数)请求出最小的
w 使得不会产生无限个物品。
n \leq 1000,m \leq 2000
这个题比较 trivial,我们把图建出来,每一个方法对应
注意到直接套 SPFA 求的话精度上会寄(有人 -11 我不说是谁),所以运用一个常见技巧,也就是取
//Every night that summer just to seal my fate
//And I scream, "For whatever it's worth
//I love you, ain't that the worst thing you ever heard?"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const double eps = 1e-7;
const int N = 2e5 + 10;
int n,m;
int b[N],d[N];
double a[N],c[N];
vector <int> G[N];
vector<pair<int,double> > edges;
int cnt[N],tot[N];
double dis[N];
bool vis[N];
queue <int> q;
bool SPFA(int s,double val) {
q.push(s);
vis[s] = 1;dis[s] = 0.0;
while (!q.empty()) {
int x = q.front();q.pop();
vis[x] = 0;
for (auto i : G[x]) {
pair<int,double> e = edges[i];
int y = e.first;double w = e.second-log(val);
//printf("%Lf %Lf %Lf\n",dis[y],dis[x],w);
if (dis[y] > dis[x] + w) {
dis[y] = dis[x] + w;
if (!vis[y]) {
if (++cnt[y] >= n) return 1;
vis[y] = 1,q.push(y);
}
}
}
}
return 0;
}
bool check(double val) {
memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
for (int i = 1;i <= n;++i) dis[i] = 1e4;
bool flag =0;
for (int i = 1;i <= n;++i) {
if (dis[i] - 1e4 < eps) {
flag = SPFA(i,val);
//printf("%d:",i);
if (flag) return 1;
}
}
return 0;
}
signed main() {
read(n,m);
for (int i = 1;i <= m;++i) {
read(a[i],b[i],c[i],d[i]);
double aa = log(a[i]),cc = log(c[i]);
edges.push_back(mp(d[i],aa-cc));
G[b[i]].push_back(edges.size()-1);
}
double l = eps,r = 1.00000000;
while (r - l > eps) {
double mid = (l + r) / 2.0;
//printf("%lf\n",mid);
if (!check(mid)) l = mid;
else r = mid;
}
printf("%.8lf",l);
return 0;
}
L
有
n 个世界,每个世界是一张简单有向图。从这些世界中选择一个子段进行游戏,规则为从
1 出发,每个世界可以原地不动或经过一条边,到达点m 即为胜利。要求选出一个尽可能短的子段,使得存在至少一种方案可以胜利。
n \leq 10 ^4,m \leq 2\times 10^3 空间限制为32MB
有人是演员,我不说是谁
观察到这是个分层图,以及这个子段的限制乍看一下非常吓人。但是观察一下空间限制就能发现这个题实际上是个诈骗题(但是我场上没发现)
大力设计 DP 状态,定义
DP 的时候类似建反图(但是这里不需要建出显式图),有:
//Every night that summer just to seal my fate
//And I scream, "For whatever it's worth
//I love you, ain't that the worst thing you ever heard?"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int N = 1e4 + 10;
int f[2][N],n,m,ans;
signed main() {
read(n,m);
int now = 1,lst = 0;
ans = n + 1;f[0][1] = 1;
for (int i = 1;i <= n;++i) {
swap(now,lst);
for (int j = 1;j <= m;++j) f[now][j] = f[lst][j];
int l;read(l);
for (int j = 1;j <= l;++j) {
int x,y;read(x,y);
f[now][y] = max(f[now][y],f[lst][x]);
if (x == 1) f[now][y] = i;
}
if (f[now][m]) ans = min(ans,i - f[now][m] + 1);
}
if (ans == n+1) puts("-1");
else printf("%d\n",ans);
return 0;
}
H
k 层楼,n 个人,第i 个人想从a_i 楼到b_i 楼。电梯同一时间最多载
m 人,每一时间单位走一层,可以随时向下,但只能到1 楼才能向上。求最短时间使得所有人到达他/她想去的楼层。
n, m ≤ 2 × 10^5 , k ≤ 10^9
我们实际上只需要统计一个东西:一个楼层向上会被经过多少次,向下会被经过多少次。
对于向上来说,假设从
我们记第
总共要到达的次数就是一个后缀最大值,这个的意义是非常显然的,最后再对这个后缀最大值求一个前缀和,时间复杂度为
离散化一下,时间复杂度就变成了
//Every night that summer just to seal my fate
//And I scream, "For whatever it's worth
//I love you, ain't that the worst thing you ever heard?"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int N = 2e5 + 10;
int n,m,k,a[N],b[N],pre[N],suf[N],sufmax[N];
vector <int> c;
signed main() {
read(n,m,k);
for (int i = 1;i <= n;++i) read(a[i],b[i]),c.push_back(a[i]),c.push_back(b[i]),c.push_back(a[i]-1),c.push_back(b[i]-1);
c.push_back(1);
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
int tot = c.size();
for (int i = 1;i <= n;++i) {
int l = lower_bound(c.begin(),c.end(),a[i]-1) - c.begin() + 1;
int r = lower_bound(c.begin(),c.end(),b[i]-1) - c.begin() + 1;
if (l < r) pre[l]--,pre[r]++;
else suf[l]++,suf[r]--;
}
int now = 0;
int ans = 0;
for (int i = tot - 1;i >= 1;--i) {
ans += (c[i] - c[i-1] - 1) * now;
pre[i] += pre[i + 1];
suf[i] += suf[i + 1];
now = max(now,(max(pre[i],suf[i]) + m - 1) / m);
ans += now;
if (c[i-1] == 1) break;
}
printf("%d\n",2 * ans);
return 0;
}
I
每个功夫大师有能力值和技能值,都为向量;
功夫大师们要互相学习技能,一个功夫大师学习后的技能值为所有功夫 大师技能值的加权和;
两个功夫大师间的学习效率(学技能的加权权值)为能力值的余弦相似度;
求所有功夫大师学习后的技能值。
功夫大师的数量不超过
10^4 ,所有向量长度不超过50
考虑直接嗯做时间复杂度是
我们不妨把式子给展开一下:
我们注意到,
接下来需要做的工作就是求出这两个之后以
//Every night that summer just to seal my fate
//And I scream, "For whatever it's worth
//I love you, ain't that the worst thing you ever heard?"
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair
char buf[1 << 20], *p1, *p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
template <typename T> inline void read(T &t) {
int v = getchar();T f = 1;t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
read(t);read(args...);
}
const int N = 1e4 + 10;
const int M = 55;
int n,k,d;
double x[N][M],y[N][M],yy[N][M];
signed main() {
read(n,k,d);
for (int i = 1;i <= n;++i) {
double sum = 0;
for (int j = 1;j <= k;++j) {
read(x[i][j]);
sum += x[i][j] * x[i][j];
}
sum = sqrt(sum);
for (int j = 1;j <= k;++j) {
x[i][j] /= sum;
}
}
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= d;++j) {
read(y[i][j]);
}
}
for (int i = 1;i <= k;++i) {
for (int j = 1;j <= d;++j) {
for (int l = 1;l <= n;++l) {
yy[i][j] += x[l][i] * y[l][j];
}
}
}
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= d;++j) {
double ans = 0;
for (int l = 1;l <= k;++l) {
ans += x[i][l] * yy[l][j];
}
printf("%.10lf ",ans);
}
puts("");
}
return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
太强啦!