2023牛客寒假算法基础集训营1
A
题目大意是AB两个个人点球，给你一个长度为10的字符串，1即为成功，否则失败，问多少场可以结束（得出谁输谁赢），否则输出-1
我们可以记录到某一点的胜利场数和还有几场比赛可以打，如果此时的胜利场数加上让后面的场数都赢了，还是不能战胜另外一个人，即可以确定一定是输，输出此时的位置
代码直接模拟
#include <string>
#include <bits/stdc++.h>
using namespace std;
string s;
int t;
void solve()
{
cin>>s;
s=" "+s;
int cnt1=0,cnt2=0;
int last1=5,last2=5;
for (int i=1;i<=10;i++)
{
if (i&1)
{
if (s[i]=='1') cnt1++;
last1--;
}
else
{
if (s[i]=='1') cnt2++;
last2--;
}
if (cnt1==cnt2) continue;
if (cnt1<cnt2)
{
if (cnt1+last1>=cnt2) continue;
else
{
cout<<i<<'\n';
return ;
}
}
else
{
if (cnt2+last2>=cnt1) continue;
else
{
cout<<i<<'\n';
return ;
}
}
}
cout<<-1<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
C
这题大意是给我们n个数，我们如果选择了x个数，且其中x个数都大于等于x，那么我们的贡献就是1，我们想要知道这n个数的最大贡献
对于n个数，每一个非0的贡献为1（这样才是最大，每一个数的贡献也只可以是1），那么我们把每一个非0的放在一个集合里，那么每一个都会大于等于1，所以最大贡献就是非0的个数
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int t,n;
void solve()
{
cin>>n;
vector<int>a(n+1,0);
int ans=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
if (a[i]) ans++;
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
D
这个题目大意是给你一个已知的长方形区域，两个点（0,0和x,y)还给出一个px,py，我们需要找到另外一点，让px,py和这一个点形成的长方形区域的和之前的交集除并集的最大值
对于这一个要找的点，一定是在已知长方形的四个点里面找，具体是哪个，还需要分情况
然后取最大值
#include <bits/stdc++.h>
using namespace std;
int t,x,y,px,py;
pair<int,int>a,b,c,d,e;
int get(pair<int,int>s,pair<int,int>t)
{
int ss=abs(s.first-t.first)*abs(s.second-t.second);
return ss;
}
void solve()
{
cin>>x>>y>>px>>py;
a={0,0};
b={x,y};
c={0,y};
d={x,0};
e={px,py};
double ans=0;
int bin=0,jiao=0;
if (px<x&&py<y)
{
bin=get(a,b);
jiao=0;
jiao=max(jiao,get(e,a));
jiao=max(jiao,get(e,b));
jiao=max(jiao,get(e,c));
jiao=max(jiao,get(e,d));
ans=1.0*jiao/bin;
}
else if (px<x)
{
bin=get(a,b)+get(e,c);
jiao=get({px,y},a);
ans=1.0*jiao/bin;
bin=get(a,b)+get(e,b);
jiao=get({px,y},d);
ans=max(ans,1.0*jiao/bin);
}
else if (py<y)
{
bin=get(a,b)+get(d,e);
jiao=get({x,py},a);
ans=1.0*jiao/bin;
bin=get(a,b)+get(b,e);
jiao=get({x,py},c);
ans=max(ans,1.0*jiao/bin);
}
else
{
bin=get(a,e);
jiao=get(a,b);
ans=1.0*jiao/bin;
}
printf ("%.9lf\n",ans);
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
E
这个题大意是给你六个点，问前面三个点形成的一个图形是否只需要经过平移和旋转才可以变成后面的图形，如果不可以，那么就需要题目中给出的拿起来改变位置的操作
这一题，我们用到了叉积
对于这样两个图形
不可以是前面旋转得到后面的，一定是拿起来了，我们可以观察到两条向量之间的角度由锐角变成了钝角，那么叉积就有正数变成了负数，所以我们可以得出符号变化的就一定是进行了拿起来的操作
但是，还有一个就是两条边都一样长的，那么不管怎样，都可以用旋转，我们不能确定那一条边是之前的那一条边变出来的
//判断有没有进行第三个操作，我们只需要这DEF是否可以是ABC通过前面两个操作得来的，可以就不需第三个操作，否则就需要第三操作了
//怎么判断是否可以通过前两个操作得来的，对于AB,BC的方向和DE,EF的方向一样，长度差都一样，那么就只需第一个操作，
//否则，我们就判断它有没有进行过拿起旋转操作，这里需要判断这两对向量的叉积，叉积的大小可以改变，但是正负不会改变
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-3;
struct node
{
double x,y;
};
struct lin
{
double x,y;
};
lin getlin(node i, node j)
{
lin z;
z.x=i.x-j.x;
z.y=i.y-j.y;
return z;
}
double getlen(lin i)
{
double res=i.x*i.x+i.y*i.y;
return res;
}
double cross(lin i,lin j)
{
double res=0;
res=i.x*j.y-i.y*j.x;
return res;
}
void solve()
{
node A,B,C,D,E,F;
cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y;
cin>>D.x>>D.y>>E.x>>E.y>>F.x>>F.y;
lin BA=getlin(B,A);
lin BC=getlin(B,C);
lin ED=getlin(E,D);
lin EF=getlin(E,F);
if (getlen(BA)==getlen(BC))//对于两个边都是一样的，那么不管从那个边出发，和另外一个边的角不管多大都可以旋转，不需要第三个操作
{
cout<<"NO\n";
return ;
}
//如果两个边不同，那么我们从小边到大边的叉积
if (getlen(BA)-getlen(BC)<eps)//BA为大边
{
swap(BA,BC);
}
double a=cross(BC,BA);
if (getlen(ED)-getlen(EF)<eps)//ED为大边
{
swap(ED,EF);
}
double b=cross(EF,ED);//我们从小边到大边的正负如果相同，那就是没有进行第三操作的，第二个操作没有改变角度，那么这个叉积一定是同一个符号的，否则就是不同的
if (a*b<0)
{
cout<<"YES\n";
}
else cout<<"NO\n";
return ;
}
int main ()
{
int t;
cin>>t;
while (t--)
{
solve();
}
return 0;
}
F
题目大意是有一个人，他既可以走（连通），又可以放置一个东西，最后我们需要把n个点需要放置几个东西的条件满足后面的c,i点必须有ci个东西，我们可以从s到t,只要满足条件，我们需要知道这样的路径有多少条。
题目不保证这里的所有的东西都在一个连通块里，如果不在，那么就是不可能的（当有东西的时候）
对于一个连通块，我们的s可以是siz里的任意一个，t也可以是任意一个，那么数量就有siz*siz个
如果没有一个东西（没有限制条件），我们在任意一块连通块里行走，siz*siz
对于连通块的数量，以及siz，用并查集来维护
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define int long long
int n,m;
int siz[maxn];
int f[maxn];
int c[maxn];
void init()
{
for (int i=1;i<=n;i++)
{
f[i]=i;
siz[i]=1;
}
return ;
}
int find(int x)
{
if (x==f[x]) return f[x];
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int tx=find(x),ty=find(y);
if (tx==ty) return ;
f[ty]=tx;
siz[tx]+=siz[ty];
siz[ty]=0;
return ;
}
signed main ()
{
int ans=0;
cin>>n>>m;
init();
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
merge(u,v);
}
int u=0;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
c[i]=x;
if (x)u=i;
}
if (u==0)//不放蛋，随便走，都可以
{
for (int i=1;i<=n;i++)
{
ans+=siz[i]*siz[i];
}
}
else
{
for (int i=1;i<=n;i++)
{
if (c[i])
{
if (find(i)!=find(u))//不可以让两个蛋在不同的连通块，走不到
{
cout<<0<<'\n';
return 0;
}
}
}
u=find(u);//所有的蛋在一块，我们随便找两个点，可以同一个点，要选两次，所以siz[u]*siz[u]
ans=siz[u]*siz[u];
}
cout<<ans<<'\n';
return 0;
}
G
我们知道一个公式
\[f(x)=round(10\sqrt{x}) \]然后有两个操作，一个是对l,r的数进行上面的公式k次，得出最后的值
第二个操作是输出这n个数此时的和
对于一直在改变的sum,我们可以用线段树
其实对于这一个公式 f(0)=0,f(99)=99,f(100)=100,他们不管进行了多少次f(x)，答案都不变，其他的数变成这三个数也是同样的，那么后面就不用了进行k次操作了，如果没有想到，可以直接对f(x)和x之间的关系进行判断
线段树我们定义一个flag,如果它的flag为true,那么说明他的值一定是不会再改变了，那么如果l,r中还需要k次操作，我们可以直接忽略。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
#define int long long
#define lson root<<1
#define rson root<<1|1
int n,m;
int a[maxn];
int f(int x)
{
double y = 10 * sqrt(x);
x = round(y);
return x;
}
bool getflag(int x)//会出现循环，0,99,100就是那个循环的位置f(10)=10,这种
{
int now=x;
if (f(now)==now) return true;
return false;
// if(x == 0 || x == 99 || x == 100) return 1;
//return 0;
}
struct tree
{
int sum,l,r;
bool flag;
}tr[maxn<<2];
void pushup(int root)
{
tr[root].sum=tr[lson].sum+tr[rson].sum;
tr[root].flag=tr[lson].flag&tr[rson].flag;
return ;
}
void build(int root,int l,int r)
{
tr[root].l=l;
tr[root].r=r;
if (l==r)
{
tr[root].sum=a[l];
tr[root].flag=getflag(a[l]);
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(root);
return ;
}
void fun(int root,int k)
{
int res=0;
if (tr[root].flag) return ;
int now=tr[root].sum;
while (k--)
{
now=f(now);
if (getflag(now))
{
tr[root].sum=now;
tr[root].flag=true;
return ;
}
}
tr[root].sum=now;
return ;
}
void update(int root,int l,int r, int k)
{
if(tr[root].flag) return ;
if(tr[root].l == tr[root].r)
{
fun(root,k);
return ;
}
int mid = (tr[root].l + tr[root].r) >> 1;
if(l <= mid) update(lson, l, r, k);
if(r > mid) update(rson, l, r, k);
pushup(root);
}
signed main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while (m--)
{
int op;
cin>>op;
if (op==1)
{
int l,r,k;
cin>>l>>r>>k;
update(1,l,r,k);
}
else
{
int ans=tr[1].sum;
cout<<ans<<'\n';
}
}
return 0;
}
H
这个是有一个拼图，一个拼图有四边，有突出的，我们记为2，凹陷的，我们记为1，直的，我们记为0，这一块拼图的面积为10+x(突出的数量）-y (凹陷的数量）
然后有一个nXn的拼图，但只给了我nXn-1块拼图，我们需要知道那缺失的那一块拼图的面积
我一开始还真信了题目，用dfs，后来才知道
对于这些所有的拼图，突出的数量和凹陷的数量是一样的，如果，已有的突出和凹陷的数量是一样的，那么确实的那一块拼图也是一样的，否则，缺哪块补哪块
那么我们可以如果出现了一个1，那么我们就加一，否则就减一
最后加上10，输出答案
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int ans=0;
string s;
int n;
cin>>n;
for (int i=1;i<n*n;i++)
{
cin>>s;
for (int j=0;j<=3;j++)
{
if (s[j]=='1') ans++;
if (s[j]=='2') ans--;
}
}
ans+=10;
cout<<ans<<'\n';
return ;
}
int main ()
{
int t;
cin>>t;
while (t--)
{
solve();
}
return 0;
}
I
我们需要构造一个矩阵，有两种要求
ax,y=z
ax,y是x行中最大的一个，y列中最小的一个
这里我们用到的是拓扑排序的思维
如果是ax,y是最大的那一个，那么从x,y可以到达x,ty，从tx,y到达x,y(较大的值的边可以到达较小的值的边)
然后根据拓扑的入度，可以得到一个初始的值，（如果连出入度都不满足的话，就已经确定不可以构造出来，直接把所有位置都变成0）
然后，我们还需要满足第二个要求，u到v，大边到小边，则让v取min，f不一定是具体的值
然后我们在遍历所有的数，如果这一位数已经找到他的位置了，那么我们就把原来的位置不变，否则，我们就把那个较小的f的位置给这一个值（较小的是因为我们遍历的值也是从小到大的），如果给不了，那么就不可以构造出来，确定了这一个的位置，与之相连的入度也要减去，如果入度为0，假如优先队列（这个过程和拓扑排序一样）
#include <bits/stdc++.h>
using namespace std;
int n,m;
int t;
void solve()
{
cin>>n>>m;
//cout<<n<<"\n";
vector<int>a(n*n+10,n*n+10);//a代表i行j列的值,i*n+j,后面会求min，所以n*n+10,而不是0
vector<int>pos(n*n+10,-1);//x的位置，同上，不可以是0,0有位置是这个数值
vector<int>in(n*n+10,0);//每一个位置的入度，从大到小
vector<vector<int>>g(n*n+10);
for (int i=1;i<=m;i++)
{
int op,x,y,z;
cin>>op;
if (op==1)
{
cin>>x>>y>>z;
x--,y--;//0到n*n-1
a[x*n+y]=z;
pos[z]=x*n+y;
}
else
{
cin>>x>>y;
x--,y--;
int now=x*n+y;
for (int j=0;j<n;j++)
{
int tx=j;
int ty=j;
if (tx!=x)//列一样，为这一列最小值，从这一个到其他的点(x,y)<(x+1,y)
{
int p=tx*n+y;
g[now].push_back(p);
in[p]++;
}
if (ty!=y)//now为最大的那一个，(x,y+1)<(x,y)
{
int p=x*n+ty;
g[p].push_back(now);
in[now]++;
}
}
}
}
vector<int>q;//已确定的位置
for (int i=0;i<n*n;i++)
{
if(in[i]==0)
{
q.push_back(i);
}
}
bool yes=true;
for (int i=0;i<n*n;i++)
{
if (q.size()<=i)
{
yes=false;
break;
}
int now=q[i];
for (auto v:g[now])
{
in[v]--;
if (in[v]==0)
{
q.push_back(v);
}
}
}
if (yes)//如果是yes，那么q里面一定有n*n个位置初始的，不一定正确，只是根据位置和位置之间的关系，后面我们还要维护牛牛点的大小关系
{
vector<int>f=a;//对于a里面的数,都是确定的数，都是操作1赋予的，我们可以根据后面的来得出和a有关的位置应该是什么数
for (int i=n*n-1;i>=0;i--)
{
int x=q[i];
for (auto y:g[x])
{
f[x]=min(f[x],f[y]);
in[y]++;
}
}
priority_queue<pair<int,int>>h;//第一位是值，第二位是位置,我们需要的是最小的数，所以是负数
for (int i=0;i<n*n;i++)
{
if (a[i]>n*n&&in[i]==0)//那么这个点一定是没有任何要求的点
{
h.push({-f[i],i});
}
}
for (int i=1;i<=n*n;i++)//遍历值
{
int ppos;
if (pos[i]!=-1)
{
ppos=pos[i];
if (in[ppos])//如果这一个值都已经确定了，但是入度还不等于0，那么就是不可
{
yes=false;
break;
}
}
else
{
if(h.empty())
{
yes=false;
break;
}
ppos=h.top().second;//较小的那一个f[i]就对应较小的值
h.pop();
}
a[ppos]=i;
for (auto ne:g[ppos])
{
in[ne]--;
if (in[ne]==0&&a[ne]>n*n)//入度为0且没有确定位置
{
h.push({-f[ne],ne});
}
}
}
}
if (!yes)
{
a.assign(n*n+10,0);
}
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
int now=i*n+j;
cout<<a[now]<<" ";
}
cout<<'\n';
}
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
K
这道题大意是一个01串，有m个1，三个连续字符里1的个数大于0，那么就是一个坏区间，问我们最少可以有多少个坏区间
这个我在比赛时用的是dp,但是很不幸的是我错了
先所简单的吧
就是我们都知道100100100都没有坏区间，那么如果有多出来的1，就把所有的1聚集在后面，不要让1来破坏前面的好区间，然后最后直接求出坏区间的数量（此时坏区间是最少的）
#include <bits/stdc++.h>
using namespace std;
int n,m;
int main ()
{
cin>>n>>m;
int cnt1=m,cnt0=n-m;
string s=" ";
while (cnt1&&cnt0>=2)
{
s+="100";
cnt1--;
cnt0-=2;
}
if (cnt1==0)
{
cout<<0<<'\n';
return 0;
}
if (cnt0)
{
s+="10";
cnt1--,cnt0--;
}
while (cnt1)
{
s+="1";
cnt1--;
}
int ans=0;
for (int i=1;i+2<=n;i++)
{
int t=0;
if (s[i]=='1')t++;
if (s[i+1]=='1') t++;
if (s[i+2]=='1') t++;
if (t>=2) ans++;
}
cout<<ans<<'\n';
return 0;
}
下面一种是状压dp
dp[i][j][k]//有i个符号，j个1，k是最后两个字符的状态，有00,01,10,11（0,1,2,3表示）
//初状态把所有的dp赋为最大值，然后把dp[2][0][0]=0,dp[2][1][1]=0,dp[2][1][2]=0,dp[2][2][3]=0,这些都是有用的状态
for (int k=0;k<4;k++)//枚举四个状态
{
for (int x=0;x<=1;x++)//第i位是1还是0，添加0还是1
{
int t = x + (k&1) + (k>>1&1);//1的数量
int add = t>=2;//如果1的数量大于2，那么就可以增加一个坏区间
int now=((k&1)<<1)|x;
dp[i][cnt+x][now]=min(dp[i][cnt+x][now],dp[i-1][cnt][k]+add);
}
}
下面是具体代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int dp[maxn][maxn][4];//dp[i][j][k]，长度为i,1的数量为k,后面两位变成二进制的数，00,01,10,11
int n,m;
int main ()
{
cin>>n>>m;
memset(dp,0x3f,sizeof(dp));
for(int i = 0; i < 4; ++i)//找正确的初始状态
{
int cnt = (i&1) + (i>>1&1);
dp[2][cnt][i] = 0;
}
for (int i=3;i<=n;i++)
{
for (int cnt=0;cnt<=m;cnt++)
{
for (int k=0;k<4;k++)
{
for (int x=0;x<=1;x++)//第i位是1还是0
{
int t = x + (k&1) + (k>>1&1);//1的数量
int add = t>=2;
int now=((k&1)<<1)|x;
dp[i][cnt+x][now]=min(dp[i][cnt+x][now],dp[i-1][cnt][k]+add);
}
}
}
}
int ans=dp[n][m][0];
for (int i=1;i<=3;i++)
{
ans=min(ans,dp[n][m][i]);
}
cout<<ans<<'\n';
return 0;
}
L
这是一个关于期望的题，不过一开始没想到这儿
#include <bits/stdc++.h>//和题目中提到的概率期望最接近的一项
using namespace std;
int main ()
{
//猜团体，第一个人猜对的概率是0.2，然后二次是0.2 三次 0.2 四次0.4(最后一次可以猜对，还可以是和前面的都不同的一个，也是0.2）
//猜人 我们最多需要猜三次 （）0.25 0.25 0.5（1,2,3次）
//期望 1*0.2+2*0.2+3*0.2+4*0.4+1*0.25+2*0.25+3*0.5=5.05=3.45+0.05*32
//即答案为32
cout<<32<<'\n';
return 0;
}
M
m个仙贝分给n个人，如果此时有x个仙贝，分给一个人z个，得到的值为z/x，我们需要知道分完仙贝后最大的值
直接用dp
dp[i][j];//j个仙贝分给了i个人后的值
dp[i][j]=max(dp[i][j],dp[i-1][j-x]+1.0*x/(m-(j-x)));
具体代码
//线性dp ,我还以为是真的找规律
#include <bits/stdc++.h>
using namespace std;
int n,m;
double dp[510][510];//dp[i][j]，j块已经分给了i个小朋友，可以让某些分到0个，只要让答案最大即可
int main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=0;j<=m;j++)
{
for (int k=0;k<=j;k++)//上一个是j，那么这一个可以从j中拿出k个出来
{
dp[i][j]=max(dp[i][j],dp[i-1][j-k]+1.0*k/(m-(j-k)));
}
}
}
printf ("%.9lf\n",dp[n][m]);
// cout<<dp[n][m]<<'\n';
return 0;
}