A题 World Final? World Cup! (I)(条件判断)
链接：https://ac.nowcoder.com/acm/contest/46800/A
in
3
1111111111
1111111110
0101011010
out
-1
10
6
说明
对于第二组样例，踢完前9球时双方比分5:4，此时最后一球若不进则比分是5:4且A赢、若进则比分是5:5进入加踢，因此9球时不能判断最终结果，踢完10球才确定B输。
对于第三组样例，踢完六球时比分为0:3，此时可以确定B一定会赢。
题意是给出一个长度为10的字符串，奇数位是A的获胜情况，偶数位是B的获胜情况
如果到哪一局可以确定有一支球队必胜，那么输出当前局数
我们可以分成奇数局和偶数局来判断
第 \(t\) 局 ( \(t\) 是 奇数 )
如果\(A\)赢了这一局且胜负已分 那么可知\(A\)已经赢了的局数>\(B\)已经赢了的局数 + \(B\)还未开始的局数
如果\(A\)输了这一局且胜负已分 那么可知\(B\)已经赢了的局数>\(A\)已经赢了的局数+ \(A\)还未开始的局数
if(s[o]=='1'){
t1++;
if(t1>t2+(n-o)/2+1){
cout<<o<<endl;
return;
}
}
else{
if(t2>t1+(n-o)/2){
cout<<o<<endl;
return;
}
}
第 \(t\) 局 ( \(t\) 是 偶数 同上可以推出)
key code
void solve(){
//try it again.
string s;
cin>>s;
int n=10;
s="?"+s;
int cnt1=0,cnt2=0;
int t1=0,t2=0;
up(1,10){
if(o&1){
if(s[o]=='1'){
t1++;
if(t1>t2+(n-o)/2+1){
cout<<o<<endl;
return;
}
}
else{
if(t2>t1+(n-o)/2){
cout<<o<<endl;
return;
}
}
}
else{
if(s[o]=='1'){
t2++;
if(t2>t1+(n-o)/2){
cout<<o<<endl;
return;
}
}
else{
if(t1>t2+(n-o)/2){
cout<<o<<endl;
return;
}
}
}
}
cout<<-1<<endl;
return;
}
C题现在是，学术时间 (I)(贪心)
链接：https://ac.nowcoder.com/acm/contest/46800/C
in
2
3
6 5 4
2
10 0
out
3
1
说明
对于样例一，一种可能的方案是把三篇论文（引用量分别为6,5,4）都让第一个教授发表，这样第一个教授有三篇引用量大于等于三而没有四篇引用量大于等于四，因此有h1=3,h2=0,h3=0，可以证明此时有\(\Sigma_{i=1}^nh_i\)最大，其值为3。
题目中说有\(n\) 篇论文，有\(n\)个教授
\(h_i\)的值是该教授发表的所有论文中，有至少\(H\)篇论文的引用量大于等于\(H\)这一命题成立的最大的\(H\)
有点抽象哈哈
不过我们构思一种思路，就是让一个教授发表一篇论文，这样除了引用量为0的论文都可以被记一次数
key code
int ans=0;
cin>>n;
int tt;
up(1,n)cin>>tt,ans+=tt!=0;
puts(ans);
D题现在是，学术时间 (II)(计算)
链接：D-现在是，学术时间 (II)_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
3
3 4 1 2
3 4 5 5
3 4 1 5
out
0.333333333
0.480000000
0.571428571
说明
链接：https://ac.nowcoder.com/acm/contest/46800/D
来源：牛客网为了评价程序的精确度，常常使用IOU这一标准来判断。定义两个矩形A,BA,BA,B的IOU为两个矩形交集部分的面积除以两个矩形并集部分的面积。例如，对于平面直角坐标系中\((0,0),(3,3)\)所确定的矩形与\((−1,1),(4,2)\)所确定的矩形，两矩形交集面积为3，并集面积为11，因此IOU为\(\frac{3}{11}\)。显然，IOU越大代表程序预测越精确。
现在，给出一个由平面上两点\((0,0),(x,y)\)所确定的GT目标框和一个点\(P(x_p,y_p)\)。请你求出在所有以P点作为其中一个顶点且边都平行于坐标轴的预测目标框中，可以使其与GT目标框取到的最大IOU为多少。
题目中说有给出一个\(x,y\)与原点构成一个矩形
再给出\(x_p,y_p\) 请你求出在所有以P点作为其中一个顶点且边都平行于坐标轴的预测目标框中与矩形的交集和并集的最大比
就是简单的计算面积
key code
void solve(){
//try it again.
int x,y,a,b;
cin>>x>>y>>a>>b;
if(a>=x&&b>=y){
int S1=abs(x)*abs(y);
int S2=abs(a)*abs(b);
printf("%.9f\n",1.0*S1/S2);
}
else if(a<x&&b>=y){
int tt=x-a;
printf("%.9f\n",max(a*y*1.0/(a*b*1.0+(x-a)*y*1.0),tt*y*1.0/(tt*b*1.0+(x-tt)*y*1.0)));
}
else if(a>=x&&b<y){
int tt=y-b;
printf("%.9f\n",max(b*x*1.0/(a*b*1.0+(y-b)*x*1.0),tt*x*1.0/(tt*a*1.0+(y-tt)*x*1.0)));
}
else{
int S1=x*y;
int S2=max({a*b,a*(y-b),b*(x-a),(x-a)*(y-b)});
printf("%.9f\n",1.0*S2/S1);
}
}
E 鸡算几何 (计算几何)(先空下，回来补题解)
链接：E-鸡算几何_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
4
0 1 0 0 1 0
1.000000000 0.000000000 0.000000000 0.000000000 0.000000000 1.000000000
1 0 0 0 0 2
2.000000000 0.000000000 0.000000000 0.000000000 0.000000000 1.000000000
45 67 0 0 26 -24
3.021000000 47.390000000 -41.979000000 -19.610000000 -74.030581210 -4.620132023
50 -58 0 0 65 88
75.106000000 -9.735000000 25.106000000 48.265000000 -71.510643929 -3.059693042
out
NO
YES
YES
YES
说明
具体来说，二维平面上有一根\(L\)型的铁丝，由AB和BC两条线段组成，鸡可以用以下三种操作玩铁丝：
1、在平面内任意地平移铁丝，即铁丝上每一个点横坐标都变化\(\Delta x\)、纵坐标都变化\(\Delta y\)；
2、以B点为轴，任意地旋转铁丝，旋转是在平面上进行的（即旋转过程中铁丝不能离开地面）；
3、鸡是三维生物！鸡将该铁丝拿起，在自己手里任意的调整铁丝的姿态后（鸡不能使铁丝发生形变）再随意放回平面上任意位置。
鸡可以任意（任意顺序、任意次数、不同的操作可以交替使用）使用上述三种操作来操作铁丝，经过一段时间的操作后，得到新铁丝的位置可以用线段DE和EF描述。注意DE并不保证与AB对应，EF同理，即DEF只描述操作后铁丝的形状。
现在，你想知道只根据ABC与DEF的信息，是否可以断言鸡一定使用过至少一次第三种操作。
key code
G 鸡格线 (线段树)
链接：G-鸡格线_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
3 5
0 2 114514
2
1 1 2 2
2
1 1 3 1
2
out
114516
114551
3445
说明
你有一个长为\(n\)的数组\(a\)，你需要支持以下两种操作：
1、输入\(l,r,k\)，对区间\([l,r]\)中所有数字执行\(a_i =f(a_i)\)操作\(k\)次（式中等号表示赋值操作），之中\(f(x)=round(10\sqrt x)\)，\(round\)为四舍五入函数。
2、输出当前数组所有数字的和。
你需要正确处理\(m\)次这样的操作。
这个题当时看到的时候口嗨说可以用线段树做
但还是有些无从下手哈哈，所以赛后补的
key code
const int N=1<<18;
int n,m;
int maxl[N],minn[N];
int sum[N];
void pull(int p){//更新
maxl[p]=max(maxl[p*2],maxl[p*2+1]);
minn[p]=min(minn[p*2],minn[p*2+1]);
sum[p]=sum[2*p]+sum[2*p+1];
}//修改携带值
void build(int p,int l,int r,auto &a){
if(r-l==1){
maxl[p]=minn[p]=sum[p]=a[l];
if(a[l]==0)maxl[p]=minn[p]=100;
return;
}//最低层
int m=l+r>>1;
build(2*p,l,m,a);
build(2*p+1,m,r,a);//分治
pull(p);//更新
}
void modify(int p,int l,int r,int x,int y,int k){
if(maxl[p]<=100&&minn[p]>=99)return;//为0跳过
if(l>=y||r<=x)return;//不在区间内
if(r-l==1){//单点更新
while(k&&maxl[p]!=100&&maxl[p]!=99){
maxl[p]=sqrtl(maxl[p])*10+.5;
k--;
}
minn[p]=sum[p]=maxl[p];
return;
}
int m=l+r>>1;
modify(2*p,l,m,x,y,k);
modify(2*p+1,m,r,x,y,k);
pull(p);
}
void solve(){
//try it again.
cin>>n>>m;
vector<int>a(n);
cvec(a);
build(1,0,n,a);
while(m--){
int o;cin>>o;
if(o==1){
int l,r,k;
cin>>l>>r>>k;
l--;
modify(1,0,n,l,r,k);//1是第一个节点 0 n是从0到n-1 l r是从l到r修改 k次
}
else{
cout<<sum[1]<<endl;//总段
}
}
}
H-本题主要考察了DFS (观察)
链接：H-本题主要考察了DFS_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
1
2
0001
0000
0210
out
11
说明
有1就加一
有2就减一
观察 没什么好说的
key code
void solve(){
//try it again.
cin>>n;
m=n*n;
int ans=10;
fup(i,1,m-1){
fup(j,1,4){
char tt;
cin>>tt;
if(tt=='1')ans++;
else if(tt=='2')ans--;
}
}
puts(ans);
}
K-本题主要考察了dp(DP)
链接：K-本题主要考察了dp_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
4 3
out
2
in
10 4
out
0
in
10 5
out
2
说明
你需要写出一个仅有000和111组成的长为nnn的字符串，要求之中恰有mmm个字符是111。
现在，规定对于原序列中一个长恰好为333的子区间（子区间是连续的），若之中111的个数多于000的个数，则这个区间是坏的。
请求出满足条件的字符串中，坏区间总数最少的字符串中有几个坏区间。
根据判断可知每两个\(1\)之间间隔两个\(0\)的时候这样不会产生坏区间
因此我们可以拿一个\(1\)再拿两个\(0\)这样安排区间
如果\(num_1<=num_0*2\)那么就不会有坏区间的产生
否则多出来的\(1\)，每一个\(1\)会产生一个坏区间
还要注意一个边界，观察到长度为\(n\)的字符串只有\(n-2\)个长度为\(3\)的窗口
所以要特判一下
key code
void solve(){
//try it again.
cin>>n>>m;
int t1=m;
int t2=n-m;
if(t1<=t2/2){
cout<<0<<endl;
return;
}
else{
t1-=t2/2;
t2%=2;
cout<<min(n-2,t1-1)<<endl;
}
puts("");
}
L-本题主要考察了运气(瞎猜)
链接：L-本题主要考察了运气_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
本题无输入
out
50
说明
如题面所述，本题很好心，是个选择题，共有100个选项（最多99发罚时就可以保证通过此题辣），选项编号为1至100，第i个选项为3.45+0.05*i，如第1个选项为3.50，第10个选项为3.95。
你需要选择出与答案最接近的选项的编号（一个1至100的正整数）。
瞎猜就是了，反正不会做hh (于是PHP爆WA50发)
key code
32
M-本题主要考察了找规律(背包)
链接：M-本题主要考察了找规律_2023牛客寒假算法基础集训营1 (nowcoder.com)
in
3 3
out
1.833333333
说明
若小波奇当前还剩下\(x(x>0)\)个仙贝，并给了一位朋友\(y\)个仙贝（\(x,y\)都为整数），则这位朋友对小波奇的好感度将增加\(y/x\)（这个值可以为小数）。
一道典型的背包可惜我个智障不会做哈哈
key code
void solve(){
//try it again.
cin>>n>>m;
vector<db>dp(m+1);
fup(i,1,n)
fup(j,0,m)
fup(k,1,j)
dp[j-k]=max(dp[j-k],dp[j]+1.*k/j);
printf("%.9f\n",dp[0]);
}