题解2023牛客寒假算法基础集训营1
本人能力有限，有些题做不来，也在补，求大佬指点。也欢迎大家讨论。
A World Final? World Cup! (I)
简单题，根据题意模拟，记录现有情况和还剩多少场可以踢。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
int a[2][2];
char ch[100];
int main() {
int T = read();
while(T--) {
int f = 0;
cin >> ch + 1;
a[0][0]=a[1][0]=0;
a[0][1]=a[1][1]=5;
for(int i = 1;i <= 10;i++) {
if(ch[i] == '1') {
a[i & 1][0] += 1;
a[i & 1][1] -= 1;
}
else {
a[i & 1][1] -= 1;
}
if(a[i & 1][0] > a[(i - 1) & 1][1] + a[(i - 1) & 1][0]) {
f = 1;
cout << i << endl;
break;
}
if(a[(i - 1) & 1][0] > a[i & 1][1] + a[i & 1][0]) {
f = 1;
cout << i << endl;
break;
}
}
if(!f) {
cout << "-1" << endl;
}
}
}
B World Final? World Cup! (II)
留坑
C 现在是，学术时间 (I)
简单题，根据有这句话至少H篇论文的引用量大于等于H"这一命题成立的最大的H所以其实一篇论文最大的贡献也就是1，考虑到论文数目和人数是一样的，每个人分配一篇论文就好了，记录0的个数。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
int main() {
int T = read();
while(T--) {
int n = read();
int ans = 0;
for(int i = 1;i <= n;i++) {
ans += (read() != 0);
}
cout << ans << endl;
}
}
D 现在是，学术时间 (II)
简单题，给出的初始矩形，大体把平面分为了四个部分每一个部分讨论一下取最大值就好了。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
int x,y,a,b,tot;
int main() {
int T = read();
while(T--) {
x = read();y = read();a = read();b = read();
tot = x * y;
if(a <= x && b <= y) {
int res = max(max(a*b,(y-b)*a),max((y-b)*(x-a),(x-a)*b));
cout << 1.0 * res / tot << endl;
}
if(a <= x && b > y) {
double ans = 0;
ans = max(ans,y * a * 1.0 / (x * y + (b - y) * a));
ans = max(ans,y * (x - a) * 1.0 / (x * y + (b - y) * (x - a)));
cout << ans << endl;
}
if(a > x && b <= y) {
swap(x,y);swap(a,b);
double ans = 0;
ans = max(ans,y * a * 1.0 / (x * y + (b - y) * a));
ans = max(ans,y * (x - a) * 1.0 / (x * y + (b - y) * (x - a)));
cout << ans << endl;
}
if(a > x && b > y) {
cout << 1.0 * (x * y) / (a * b) << endl;;
}
}
}
E 鸡算几何
中档题，主要题意就是说，是否进行了翻转操作。对于这个我们最好的办法就是判断叉积的正负。但是要选取一个标准，我这里选取的是长边向短边做叉积，要注意等腰的图形翻转依旧不能判断，需要特判。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
struct Tri{
int rnk[4];
double id[4][3];
double val[100];
int top;
double pd[100];
bool cmp(int x,int y) {
return pd[x] < pd[y];
}
double dist(double x,double y,double a,double b) {
return sqrt((x-a)*(x-a)+(b-y)*(b-y));
}
double clac(int a,int b,int c) {
double x = id[b][0] - id[a][0],y = id[b][1] - id[a][1];
double X = id[c][0] - id[a][0],Y = id[c][1] - id[a][1];
return x * Y - y * X;
}
void solve() {
for(int i = 0;i < 3;i++) {
int tot = 0;
for(int j = 0;j < 3;j++) rnk[j] = j;
for(int j = 0;j < 3;j++) {
pd[tot++] = dist(id[i][0],id[i][1],id[j][0],id[j][1]);
}
for(int j = 0;j < 3;j++){
for(int k = j + 1;k < 3;k++){
if(pd[rnk[j]]>pd[rnk[k]]) swap(rnk[j],rnk[k]);
}
}
// cout << "Woce nima " << endl;
// for(int i = 0;i < 3;i++) cout << pd[rnk[i]] <<" ";
// cout << " ce " << endl;
val[++top] = clac(i,rnk[1],rnk[2]);
}
sort(val + 1,val + 1 + top);
}
bool caoni() {
if(fabs(dist(id[0][0],id[0][1],id[1][0],id[1][1])-dist(id[2][0],id[2][1],id[1][0],id[1][1])) < 1e-8) {
return 1;
}
return 0;
}
}a,b;
int main() {
int T;cin >> T;
while(T--) {
for(int i = 0;i < 3;i++) {
for(int j = 0;j < 2;j++) {
cin >> a.id[i][j];
}
}
for(int i = 0;i < 3;i++) {
for(int j = 0;j < 2;j++) {
cin >> b.id[i][j];
}
}
a.solve();b.solve();
if(a.caoni()) {
printf("NO\n");
}
else {
int f = 0;
for(int i= 1;i <= a.top;i++) {
// cout <<"woc:: "<< a.val[i] <<" " << b.val[i] << endl;
if(fabs(a.val[i] - b.val[i]) > 1e-8) {
f = 1;
}
}
if(!f) {
cout << "NO" << endl;
}
else cout << "YES" << endl;
}
a.top = b.top = 0;
}
}
F 鸡玩炸蛋人
中档题，如果没有下蛋的要求，那么就是输出每个连通块的大小的平方。有下单的要求的话，我们容易知道，如果两个需要下单的地方不在一个连通块，那么答案显然是0。那么现在就是考虑一个连通块内的下蛋地方有什么影响，因为可以选择下蛋和不下蛋，所以其实完全没有影响。我们可以把连通块抽离出一棵树，先去叶节点下蛋便是。所以答案是下蛋连通块大小的平方，用并查集维护。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 3e5 + 10;
int n,m;
int f[N],si[N],u,val[N];
int find(int x) {
if(f[x] == x) return x;
else return f[x] = find(f[x]);
}
int main() {
n = read();m = read();
for(int i = 1;i <= n;i++) f[i] = i,si[i] = 1;
for(int i = 1;i <= m;i++) {
int a = read(),b = read();
a = find(a);
b = find(b);
if(a == b) continue;
f[a] = b;si[b] += si[a];
}
for(int i = 1;i <= n;i++) {
val[i] = read();
if(val[i]) u = i;
}
ll ans = 0;
if(!u) {
for(int i = 1;i <= n;i++) {
if(find(i) == i) {
// cout << i << " " << find(i) << " " << si[i] << endl;
ans += si[i] * 1ll * si[i];
}
}
cout << ans << endl;
}
else {
for(int i = 1;i <= n;i++) {
if(val[i] && find(i) != find(u)) {
cout << "0" << endl;
return 0;
}
}
u = find(u);
ll ans = si[u] * 1ll * si[u];
cout << ans << endl;
}
return 0;
}
G 鸡格线
中档题，有根号的区间操作，很容易想到以前做的一道线段树的题目。性质利用的是根号操作收敛的非常快。但是这道题有系数10，我们通过打表可以知道所有的数字通过这个操作，只会收敛于0，99，100这三个数字，所以我们线段树维护一下区间这三个数字的个数就好。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
int f(ll x) {
return int(10 * sqrt(x) + 0.5);
}
const int N = 5e5 + 10;
ll m99[N],m100[N],m0[N],t[N],n,a[N];
void build(ll u,ll l,ll r) {
if(l == r) {
t[u] = a[l];
if(t[u] == 0) m0[u] = 1;
if(t[u] == 99) m99[u] = 1;
if(t[u] == 100) m100[u] = 1;
return ;
}
ll mid = l + r >> 1;
build(u<<1|1,mid + 1,r);build(u<<1,l,mid);
t[u]=t[u<<1]+t[u<<1|1];
m0[u]=m0[u<<1]+m0[u<<1|1];
m100[u]=m100[u<<1]+m100[u<<1|1];
m99[u]=m99[u<<1]+m99[u<<1|1];
}
void ask(ll u,ll l,ll r,ll L,ll R,ll k) {
if(L <= l && r <= R && (m0[u]+m99[u]+m100[u]==r-l+1)) return;
if(r < L || R < l) return;
if(l == r) {
for(ll i = 1;i <= k;i++) {
t[u] = f(t[u]);
if(t[u] == 99 || t[u] == 100 || t[u] == 0) break;
}
if(t[u] == 0) m0[u] = 1;
if(t[u] == 99) m99[u] = 1;
if(t[u] == 100) m100[u] = 1;
return ;
}
ll mid = l + r >> 1;
ask(u<<1|1,mid + 1,r,L,R,k);ask(u<<1,l,mid,L,R,k);
t[u]=t[u<<1]+t[u<<1|1];
m0[u]=m0[u<<1]+m0[u<<1|1];
m100[u]=m100[u<<1]+m100[u<<1|1];
m99[u]=m99[u<<1]+m99[u<<1|1];
}
int main() {
n = read();ll T = read();
for(ll i = 1;i <= n;i++) a[i] = read();
build(1,1,n);
while(T--) {
ll opt = read();
if(opt == 1) {
ll l = read(),r = read(),k = read();
ask(1,1,n,l,r,k);
}
else {
cout << t[1] << endl;
}
}
}
H 本题主要考察了DFS
简单题，考虑到拼图的特性，我们并不在意缺少的位置，我们只关心有几个凹陷和凸起。所以记录1，2的个数就好。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 40;
int n,vis[N * N],id[N][N],ans;
char ch[N * N][6];
int main() {
int T = read();
while(T--) {
n = read();
ans = 0;
for(int i = 1;i <= n * n - 1;i++) {
cin >> ch[i];
for(int j = 0;j < 4;j++) {
if(ch[i][j] == '1') ans += 1;
if(ch[i][j] == '2') ans -= 1;
}
}
cout << ans + 10 << endl;
}
}
I 本题也主要考察了DFS
难题，我先留。
J 本题竟也主要考察了DFS
嘿，再留。
K 本题主要考察了dp
简单题，主要考虑1，0的关系，我们是尽量不想出现坏区间，所以我们发现100100100...这种构造可以在不出现坏区间的情况下尽可能的填入最多的1。而对于实在要出现坏区间的情况，我们就构造11111...11100这样的，用最多的1去构造坏区间。所以答案就是一部分111..11100100100...构成的，枚举一下断点就好。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 20004;
int n,m;
int main() {
cin >> n >> m;
int ans = 100000;
if(n <= 2) {
cout << 0 << endl;
return 0;
}
if(n == m) {
cout << n - 2 << endl;
return 0;
}
if(n - 1 == m) {
cout << n - 2 << endl;
return 0;
}
if((n - 1) / 3 + 1 >= m) ans = 0;
for(int i = 4;i <= n;i++) {
int res = 0,rm = m;
rm -= (i - 2);
if((n - i - 1) / 3 + 1 >= rm) {
ans = min(ans,i - 3);
}
}
// ans = max(ans,0);
cout << ans << endl;
}
L 本题主要考察了运气
简单题，数学题目。组和第几个人本质是一样的。除了最后只剩2组或者2人只需要问一次，其余的都是等概率事件，1/4，1/5。加起来就好了。最后的期望次数是 5.05。就是 i = 32 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
int main() {
cout << "32" << endl;
}
M 本题主要考察了找规律
简单题，一个简单的 的动态规划， 表示考虑到第 个人，现在还有 个仙贝的最大收益。那么转移就是， 。
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
int x = 0,f = 0;char ch = getchar();
while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
return f ? -x : x;
}
const int N = 1005;
double f[N][N];
int n,m;
int main() {
cin >> n >> m;
if(n >= m) n = m;
for(int i = 1;i <= m;i++) f[1][i] = 1;
for(int i = 2;i <= n;i++) {
for(int j = 1;j <= m;j++) {
for(int x = 0;x <= j;x++) {
f[i][j] = max(f[i][j],f[i - 1][j - x] + 1.0 * x / j);
}
}
}
printf("%.6f",f[n][m]);
return 0;
}
