2023牛客寒假算法基础集训营6
A
直接判断
#include <bits/stdc++.h>
using namespace std;
#define int long long
int x;
signed main ()
{
cin>>x;
if (x<=7)
{
cout<<"very easy\n";
}
else if (x<=233)
{
cout<<"easy\n";
}
else if (x<=10032)
{
cout<<"medium\n";
}
else if (x<=114514)
{
cout<<"hard\n";
}
else if (x<=1919810)
{
cout<<"very hard\n";
}
else
{
cout<<"can not imagine\n";
}
return 0;
}
B
题目大意是给你n个数，我们有两种操作，一是在数组的最后面加上x,还有一种是查询x后面有多少的数是ax的倍数
当时想的是我们可以记录在ai时记录从1到ai的以a[i]为因子的数，放进sum数组里面
然后我们查询的时候我们就可以拿上以ax为因子的数的数量，但是我们此时得到的是所有的数，但是题目要求是x后面的数量，那么我们减去前面以ax为因子的数（这个数一定是ax的倍数），这个我们记录在sum里
有点像前缀和
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,q;
int a[maxn<<1];
vector<int>factor[maxn];
int sum[maxn<<1];
int cnt[maxn];
void init()
{
for (int i=1;i<=2e5;i++)
{
for (int j=i;j<=2e5;j+=i)
{
factor[j].push_back(i);
}
}
return ;
}
signed main ()
{
init();
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
for (auto d:factor[a[i]])
{
cnt[d]++;
}
sum[i]=cnt[a[i]];
}
while (q--)
{
int op,x;
cin>>op>>x;
if (op==1)
{
n++;
a[n]=x;
for (auto d:factor[x])
{
cnt[d]++;
}
sum[n]=cnt[x];
}
else
{
int ans=cnt[a[x]]-sum[x];
// cout<<cnt[a[x]]<<" "<<sum[x]<<" ";
cout<<ans<<'\n';
}
}
return 0;
}
C
这个是我们要给出一个排序，我们会让两个相邻的数变成一个新的数，值为这两个数之和，弄完后长度减一。我们需要知道最后得到的一个数为最大值，并且知道这个排列是怎样的
我发现某一个位置离端点最近的那个距离最小的那个值越大，（越靠中间），那么那个数的利用次数就越大，然后我用了一个结构体求出每一个位置的那个值，排序，最后得到一个排序
那么值怎么求
我看了下那个数据不是很大，就是1e3,所以我就直接模拟了
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int mod=1e9+7;
const int maxn=1e3+10;
struct node
{
int pos,val;
}a[maxn];
int ans[maxn],now[maxn];
bool cmp(node x,node y)
{
return x.val<y.val;
}
signed main ()
{
cin>>n;
for (int i=1;i<=n;i++)
{
a[i].pos=i;
a[i].val=min(i-1,n-i);
}
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;i++)
{
ans[a[i].pos]=i;
now[a[i].pos]=i;
}
int sum=0;
int r=n-1;
while (r>=1)
{
for (int i=1;i<=r;i++)
{
now[i]=(now[i]+now[i+1])%mod;
}
r--;
}
cout<<now[1]<<"\n";
for (int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}
D
题目是给你一个字符串，我们只可以改变一个字符，让udu的子序列变得更加少
我是觉得要改变的那一个字符，一定是其中最关键的字符（可以组成udu最多的字符）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
string s;
int pre[maxn],suf[maxn];//i前面的u的数量，i后面的u的数量,udu d可以组成的数量为pre[i]*suf[i]，乘法分步
int ud[maxn],du[maxn];//i前面ud的数量，i后面面的du, u作为前面那个有du[i],作为后面的那个有ud[i],分类加法
int n;
signed main ()
{
cin>>s;
int u=0,d=0;
int n=0;
for (int i=0;i<s.size();i++)
{
if (s[i]=='u')
{
pre[i]=u;
ud[i]=ud[i-1];
u++;
}
else if (s[i]=='d')
{
d++;
pre[i]=u;
ud[i]=ud[i-1]+u;
}
else
{
pre[i]=u;
ud[i]=ud[i-1];
}
}
u=0,d=0;
for (int i=s.size()-1;i>=0;i--)
{
if (s[i]=='u')
{
suf[i]=u;
du[i]=du[i+1];
u++;
}
else if (s[i]=='d')
{
d++;
suf[i]=u;
du[i]=du[i+1]+u;
}
else
{
suf[i]=u;
du[i]=du[i+1];
}
}
int ans=-1;
int sum=0;
for (int i=0;i<s.size();i++)
{
if (s[i]=='u')
{
int now=du[i]+ud[i];
if (now>sum)
{
ans=i;
sum=now;
}
}
else if (s[i]=='d')
{
int now=pre[i]*suf[i];
if (now>sum)
{
sum=now;
ans=i;
}
}
}
if (ans!=-1)
{
s[ans]='a';
}
cout<<s<<'\n';
return 0;
}
E
题目大意是有1到n个节点，两个节点i,j 差值小于等于k,边权为lcm(i,j),否则就是gcd(i,j)，我们要知道这个图的最小生成树
1是一个特殊的点，对于任何数，gcd(1,x)都是1，那么我们把那些和1的距离大于k的点的边权为1
那么对于那些和1的距离小于等于k的点，先和1连，d[i]=i,lcm(1,i),d存的是i点的边权
后面我们再考虑那些和1的距离大于k的距离的点（那些点已经确定和1连了），如果有更少，那就更新边权
这里面还有一个出现了质数的情况
具体操作看代码
#include <bits/stdc++.h
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,k;
bool isprime(int x)
{
for (int i=2;i*i<=x;i++)
{
if (x%i==0) return false;
}
return n>1;
}
int d[maxn];
signed main ()
{
cin>>n>>k;
for (int i=2;i<=k+1;i++)//和1的距离小于k,和1的lcm为i
{
d[i]=i;
}
for (int i=k+2;i<=n;i++)//和1的距离大于k,gcd和1为1
{
d[i]=1;
}
for (int i=n;i>=k+2;i--)//我们需要利用那些和1连接起来可以让j的点的权值变少
{
for (int j=2;i-j>k;j++)//用gcd,需要距离大于k
{
d[j]=min(d[j],__gcd(i,j));
}
if (isprime(i))//但是如果出现了质数，那么前面的都已经变成了1，
//两个质数之间的距离最大是100，所以应该不会大于100
//比如当i为n时
// j可以为 2 3 4 n-k n-k+1
//i为n-1时
//j可以为 2 3 4 n-k
//我们可以看到越前面的影响越大，如果这一个是质数的话，前面的都会变成1，那么我们就不需要再来取最小权值了，因为1已经是最小的了
{
break;
}
}
int ans=0;
for (int i=2;i<=n;i++)
{
ans+=d[i];
}
cout<<ans<<'\n';
return 0;
}
F
题目大意是给你n个数，我们可以进行k个操作，让x变成f(x)
f(x)是x二进制中1的个数
我们需要知道k个操作后，最大值最小是多少
对于每一个操作，要想改变最大值，最直接的方法就是把当前的最大值变小，我们可以知道x=f(x)操作一定会变小的
一开始我没有看到k还比较大，超时了
后来看到这个k有点小的，我发现如果最大值是小于等于1的时候，不管怎么变都还是1，所以我进行一个ans,记录进行了i个操作时的答案，如果已经存在，就直接输出，否则就更新，还要注意如果此时已知的最多操作的最小值已经小于等于1的话，不用到k了，直接就输出此时的最小值，不会再变化了，我觉得有点像记忆化的过程
对于此时的最大值，我用到了优先队列
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,q;
int a[maxn];
int k;
map<int,int>ans;
priority_queue<int>Q;
int r;
int f(int x)
{
int cnt= 0;
while (x)
{
x = x & (x - 1);
cnt++;
}
return cnt;
}
bool cmp(int x,int y)
{
return x>y;
}
void solve()
{
cin>>k;
if (k<=r)
{
cout<<ans[k]<<'\n';
return ;
}
while (r<k&&ans[r]>1)
{
int now=Q.top();
Q.pop();
now=f(now);
Q.push(now);
ans[++r]=Q.top();
if (ans[r]<=1)
{
break;
}
}
cout<<ans[r]<<'\n';
return ;
}
signed main ()
{
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i];
Q.push(a[i]);
}
ans[0]=Q.top();
while (q--)
{
solve();
}
return 0;
}
G
对于n个数，我们需要k对数，我们要求这k对数乘的和最大，每一对数的值为两个数相乘
对于同号，大的和大的，小的和小的，对于假如同号的配对完成，异号也要配对（这个一定要记得），此时一定是正数只剩1个，负号只剩一个，都是绝对值小的（题目说一定可以凑齐k对数）
然后直接模拟
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
int sum=0;
priority_queue<int>q1,q2,q;
int a,b;
signed main ()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
if (x>=0)
{
q1.push(x);
}
else
{
q2.push(-1*x);
}
}
while (q1.size()>=2)
{
int x=q1.top();
q1.pop();
int y=q1.top();
q1.pop();
q.push(x*y);
}
if (q1.size())
{
a=q1.top();
q1.pop();
}
while (q2.size()>=2)
{
int x=q2.top();
q2.pop();
int y=q2.top();
q2.pop();
q.push(x*y);
}
if (q2.size())
{
b=q2.top();
q2.pop();
}
while (k&&q.size())
{
sum+=q.top();
q.pop();
k--;
}
if (k)
{
sum-=a*b;
}
cout<<sum<<'\n';
return 0;
}
H
这个不用说了，直接判断求值
#include <bits/stdc++.h>
using namespace std;
#define int long long
int x,l,r;
signed main ()
{
cin>>x>>l>>r;
double ans=0.0;
if (x>r)
{
ans=1;
}
else if (l>=x)
{
ans=0;
}
else
{
int sum=r-l+1;
int cnt=x-l;
ans=1.0*cnt/sum;
}
printf ("%.16lf",ans);
return 0;
}
I
题目大意是我们有m条边，原本每一条边都有一个权值，但是我们可以牺牲一条边来让一条边的权值变成1
那么这样，如果从1到n这样路只有一条路，而且没有其他没用的路了（所有的路都用到了），那么我们就只有第一条边要用权值，其他的边都是1，（走到第二条路我们牺牲第一条路，反正用不到了），ans=w+cnt-1,w是第一条边的权值，cnt是这一条路除了1之外的点
否则，还存在其他可以不用的路，那么第一条边也可为1，那么ans=cnt
那么我们不用管那些权值，只需记录一下和1连接的权值，可能会用到
每一条边的权值就是1，然后用最短路的方法求出1到n的最路径，然后再这一条路径中，判断有没有可能出现有没有第一种情况
怎么才会出现上面说的第一种情况呢
所有在这一条路径里面的点除了1和n的入度都要等于2,1和n要为1（这个是双向的）
还要其他不在这一条路径里面的点不能出现路径
这种就是第一种情况，其他都是第二种情况
具体看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,m,in[maxn];
int mi=1e9;
int f[maxn];
int siz[maxn];
int dis[maxn];
int pre[maxn];
vector<int>g[maxn<<2];
bool vis[maxn];
struct node
{
int pos,dis;
friend bool operator < (const node x,const node y)
{
return x.dis>y.dis;
}
};
void dijkstra( )
{
for (int i=1;i<=n;i++)
{
dis[i]=1e9;
vis[i]=false;
}
priority_queue<node>q;
q.push({1,0});
dis[1]=0;
vis[1]=true;
while (!q.empty())
{
int now=q.top().pos;
q.pop();
for (auto v:g[now])
{
if (vis[v]) continue;
if (dis[v]>dis[now]+1)
{
dis[v]=dis[now]+1;
q.push({v,dis[v]});
vis[v]=true;
pre[v]=now;
}
}
}
return ;
}
signed main ()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g[u].push_back(v);
g[v].push_back(u);
in[u]++,in[v]++;
if (u==1||v==1)
{
mi=w;
}
}
dijkstra();
int now=n;
int cnt=0;
for (int i=1;i<=n;i++)
{
vis[i]=false;
}
bool yes=false;
if (in[1]>1) yes=true;
while (now!=1)
{
if (now==n||now==1)
{
if (in[now]>1) yes=true;
}
else
{
if (in[now]>2) yes=true;
}
cnt++;
vis[now]=true;
now=pre[now];
}
if (yes)
{
cout<<cnt<<'\n';
return 0;
}
for (int i=2;i<=n;i++)
{
if (!vis[i]&&in[i])
{
cout<<cnt<<'\n';
return 0;
}
}
cout<<mi+cnt-1<<'\n';
return 0;
}
J
这个题，大意是有两个网站，pro,rank,我们有两个操作，
1 查询rank中name的做题量
2 name做x个题，pro更新
rank每t时间都会进行一次更新（每个人），还有在查询某人r时间后更新这个人的题量
我感觉pro可以实时更新每个人的题量，rank要在pro后面，还有规定时间需要更新
然后我们差不多那题目意思来，按照时间的 顺序来
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e4+10;
struct node
{ //type 1是更新pro,2是更新rank,3是查询
int type,t,w,id;
string name;
friend bool operator < (const node x,const node y)
{
if (x.t==y.t)
{
return x.type>y.type;
}
return x.t>y.t;
}
}a[maxn];
int n,t,r;
priority_queue<node>q;//按照时间顺序来更新两个网站的数据
int ans[maxn];
signed main ()
{
cin>>n>>t>>r;
map<string,int>cnt1,cnt2;//pro的题量，rank的题量
for (int i=1;i<=n;i++)
{
cin>>a[i].type>>a[i].t>>a[i].name;
a[i].id=i;
if (a[i].type==2)
{
cin>>a[i].w;
a[i].type=1;
q.push(a[i]);
}
else //查询
{
a[i].type=3;
q.push(a[i]);
//查询时,rank也需要更新，t间隔，本来是需要更新所有人的题量，
//但是此时我们只要询问这一个人，所以我们只更新这个人的,rank每t时间都会更新一下，
//我们只需要最近的时间更新一下就可以了，那么最近的一次时间是a[i].t/t*t
//还有在r时间后还需要更新这个人的题数，a[i].t+r
q.push({2,a[i].t/t*t,a[i].w,a[i].id,a[i].name});
q.push({2,a[i].t+r,a[i].w,a[i].id,a[i].name});
}
}
while (!q.empty())
{
auto x=q.top();
q.pop();
if (x.type==1)//我们做的题只在pro上实时更新，然后我们rank是有两种更新时间，询问的是rank上面的题量
{
cnt1[x.name]+=x.w;
}
else if (x.type==2)
{
cnt2[x.name]=cnt1[x.name];
}
else
{
ans[x.id]=cnt2[x.name];
}
}
for (int i=1;i<=n;i++)
{
if (a[i].type==3)
{
cout<<ans[i]<<"\n";
}
}
return 0;
}
K
玩游戏，有一个n，有两个人，如果谁不可以操作谁就输了
两种操作
x变成x+1
x变成x/2
x不可以变成0，也不可以变成之前出现过的数
这里我们记录了一个状态
x y z
x是此时的数
y是如果我们左边的那一个区间 1到y（左闭右开），这个算是除二的极限，这个是递减的，单看减少的话，如果出现了y,那么它下次除二的话，一定不可以比y大
z是右边的那个区间 x只加到z ,第一个操作是连续的递增的，那么如果z已经出现过了，那么后面的也一定是不可以的了
然后大体操作就是求每一个状态的状态，如果出现必败，那么就可以得到结果了
#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int,bool>vis;
int n;
int get(int x,int y,int z)
{
return 1000000*x+1000*y+z;
}
bool dfs(int x,int y,int z)
//此时数字为x,后一个操作可以变成的数为比y小的数（这个是除二操作可以得到的最大极限），
//小于z,这个是加一操作的最大极限
{
int id=get(x,y,z);
if (vis.count(id))
{
return vis[id];
}
if (x+1<z&&!dfs(x+1,y,z))//加一操作，极限都没有变化
{
return vis[id]=true;
}
if (x/2&&x/2<y&&!dfs(x/2,x/2,y))//除二操作，那么那么除二的极限不要大于x/2,除二是一个变小的
{
return vis[id]=true;
}
return vis[id]=false;
}
signed main ()
{
cin>>n;
for (int i=n;i<2*n;i++)
{
if (i/2&&!dfs(i/2,i/2,n))//i/2是必败状态，那么我们要判断i/2这个状态是谁变得，
{
if ((i-n)%2==0)//先加到i,再除2，加法进行了偶数次，那么变成i/2是小宁操作后，小红必败
{
cout<<"ning\n";
return 0;
}
else //加了奇数次，那么变成i/2是小红操作后，小宁必败
{
cout<<"red\n";
return 0;
}
}
}
cout<<"draw\n";//如果前面的都没有出现，那么是平手
return 0;
}
L
题目是有一个像一个倒放的楼梯行的网格，我们需要知道从1,1到每一层的最后一个的总数量
但是
还有一些格子是不能走的
我一开始直接来，后来超时了
然后看了题解
注意到m是很小的（m是不能走的位置），m<=10
那么我们不能走的路径里面一定包括这m里面的任意个
怎么选，我们就用到了二进制的方式
遍历1到1<<m（如果这一位是1，那么这条路里面包括这一个障碍）
然后我们会知道对于这些情况，可能会有重复的路径
这里我们就可以考虑到容斥（其实我也有点不太理解)
我们不可以的路径的数量
一个块，就是包括这个块的数量
两个块，要减去这种情况的数量
三个块，就是包括这个块的数量
四个块，要减去这种情况的数量
奇数个障碍，减法，偶数个，加法（对于没有障碍的总路径数）
没有障碍的总路径数有2^n-1 有n-1步，一定可以到达我们想要的位置，有两种方向，所以总数为2^n-1
那么对于那些障碍点，要怎么计算出那些搭配的路径时的数量
我们可以看到
这个箭头方向，转移的是不是和杨辉三角有点相似
所以
对于x,y和xx,yy之间的连线方式有
c(dx+dy-2,dx-1),dx,dy为两点之间的差值
还要注意，这些点的连接一定是按照我们下一步可以走的
xx>=x,yy>=y,我们可以先把x排序一下，然后再判断y是否符合条件，如果不符合条件，那么直接为0，不用管，break
然后就没什么了，具体看代码吧
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int maxn=4e5+10;
int inv[maxn],fac[maxn],invfac[maxn],pow2[maxn];
struct node
{
int x,y;
friend bool operator < (const node i,const node j)
{
return i.x>j.x;
}
};
node a[20];
node b[20];
bool cmp(node i,node j)
{
return i.x<j.x;
}
int n,m;
void init()
{
inv[1]=1;
fac[1]=1;
invfac[1]=1;
fac[0]=1;
invfac[0]=1;
for (int i=2;i<=n*2;i++)
{
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
fac[i]=(fac[i-1]*i)%mod;
invfac[i]=(invfac[i-1]*inv[i])%mod;
}
pow2[0]=1;
for (int i=1;i<=n;i++)
{
pow2[i]=(pow2[i-1]*2)%mod;
}
return ;
}
int c(int n,int m)
{
int res=fac[n]*invfac[m]%mod*invfac[n-m]%mod;
// cout<<n<<" "<<m<<" "<<res<<'\n';
return res;
}
signed main ()
{
cin>>n>>m;
init();
for (int i=1;i<=m;i++)
{
cin>>a[i].x>>a[i].y;
}
int ans=pow2[n-1];
for (int i=1;i<(1<<m);i++)
{
int cnt=0;
b[++cnt]={1,1};
for (int j=0;j<m;j++)
{
if (i>>j&1)
{
b[++cnt]=a[j+1];
}
}
int flag=-1;
if (cnt&1)
{
flag=1;
}
sort(b+1,b+1+cnt,cmp);
int tmp=pow2[n-1-(b[cnt].x+b[cnt].y-2)];
for (int i=2;i<=cnt;i++)
{
int x=b[i-1].x;
int y=b[i-1].y;
int xx=b[i].x;
int yy=b[i].y;
if (xx>=x&&yy>=y)
{
int tx=xx-x+1;
int ty=yy-y+1;
tmp=(tmp*c(tx+ty-2,tx-1))%mod;
}
else
{
tmp=0;
break;
}
}
cout<<flag<<" ";
ans=(ans+flag*tmp)%mod;
}
ans=(ans%mod+mod)%mod;
cout<<ans<<'\n';
return 0;
}