2023牛客寒假算法基础集训营2
A
这个直接模拟找符合条件的数
#include <bits/stdc++.h>
using namespace std;
int l1,r1,l2,r2;
int t;
void solve()
{
int n;
cin>>n;
cin>>l1>>r1>>l2>>r2;
int ans=0;
for (int i=l1;i<=r1;i++)
{
int a=i;
int b=n-a;
if (b>=l2&&b<=r2)
{
ans++;
}
}
cout<<ans<<'\n';
return ;
}
int main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
B
这一个题大意是给你两个区间l,r和ll和rr,要我们分别从两个区间里找一个数，让a+b=n，问有多少对
这一道的lr范围很大，所以模拟是不太可能，对于一个区间，我们从里面选出一个a,那么我们就可以得到b的范围，然后我们在求取这个b的范围和另外一个区间的交集，然后交集的长度即为答案
注意答案一定要大于等于0（可能出现没有交集的情况）
#include <bits/stdc++.h>
using namespace std;
#define int long long
int l,r,ll,rr,L,R;
int t,n;
void solve()
{
cin>>n;
cin>>l>>r>>ll>>rr;
int L=n-r;
int R=n-l;
L=max(L,ll);
R=min(R,rr);
int ans=R-L+1;
ans=max(ans,0ll);
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
C
这个题目的答案和上面的A，B题是一样的，但是这一题加大了难度，我们的区间不只是一个了，而是有多个区间，我们还是只要两个不同区间满足a+b=n的数量
对于这一题，我第一想法就是我们用某个东西，把每一个区间里面的都加一，然后我们选择a在i个区间，把i区间的值都减一，那么后面我们求交集那一段的值时就不会加到和自己在同一区间的了
我一开始用树状数组，发现不太行，然后我又用了线段树，但是我之前写的那个线段树内存超限了，结果赛后自己重新写了个线段树
我的思路没问题，看来还是要自己准备一些模板
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lson root<<1
#define rson root<<1|1
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e9+7;
const int maxn=1e6+100;
struct segtree
{
int l,r,lazy,val;
}tr[maxn<<2];
int l[maxn],r[maxn];
pair<int,int> p[maxn];
int n,m;
void build(int root,int l,int r)
{
tr[root]={l,r,0,0};
if (l==r) return ;
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
return ;
}
void pushup(int root)
{
tr[root].val=(tr[lson].val+tr[rson].val)%mod;
return ;
}
void pushdown(int root)
{
if (tr[root].lazy)
{
int mid=(tr[root].l+tr[root].r)>>1;
tr[lson].lazy+=tr[root].lazy;
tr[rson].lazy+=tr[root].lazy;
tr[lson].val+=(mid-tr[root].l+1)*tr[root].lazy;
tr[rson].val+=(tr[root].r-mid)*tr[root].lazy;
tr[root].lazy=0;
}
return ;
}
void update(int root,int l,int r,int k)
{
if (l<=tr[root].l&&tr[root].r<=r)
{
tr[root].val=(tr[root].val+(tr[root].r-tr[root].l+1)%mod*k)%mod;
tr[root].lazy=(tr[root].lazy+k)%mod;
return ;
}
pushdown(root);
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);
return ;
}
int query(int root,int l,int r)
{
if (l<=tr[root].l&&tr[root].r<=r)
{
return tr[root].val;
}
pushdown(root);
int mid=(tr[root].l+tr[root].r)>>1;
int res=0;
if (l<=mid)
{
res=(res+query(lson,l,r))%mod;
}
if (r>mid)
{
res=(res+query(rson,l,r))%mod;
}
return res;
}
void solve()
{
cin>>n>>m;
build(1,0,4e5+10);
for (int i=1;i<=m;i++)
{
cin>>l[i]>>r[i];
update(1,l[i],r[i],1);
}
int ans=0;
for (int i=1;i<=m;i++)
{
if (l[i]>=n) continue;
int ll=n-r[i];
int rr=n-l[i];
update(1,l[i],r[i],-1);
ans=(ans+query(1,ll,rr))%mod;
update(1,l[i],r[i],1);
}
cout<<ans<<'\n';
}
signed main()
{
solve();
return 0;
}
D
这个题大意是我们每放置在一个节点x一个能量球，我们能获得的能量为此时自己包括x的子节点的能量和，问我们放完所有的能量球后我们可以获得的最大能量
这样一看，我们想到的是先放根节点，但是我们觉得对答案好像关系不太
然后我们再想想，如果按照这样的方式，那么某一个节点要加它的深度次的能量球
那么我们可以按照深度大小来分配能量球，并且可以直接得到答案
ans+=dep[i]*v[i],大的能量球和大的深度
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,f[maxn],c[maxn];
struct node
{
int next,to;
}e[maxn<<2];
int head[maxn],cnt;
int val[maxn];
int dep[maxn];
void add(int u,int v)
{
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
return ;
}
void dfs(int u,int fa)
{
dep[u]=dep[fa]+1;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (v==fa) continue;
dfs(v,u);
}
return ;
}
signed main ()
{
cin>>n;
for (int i=2;i<=n;i++)
{
int v;
cin>>v;
add(v,i);
}
for (int i=1;i<=n;i++)
{
cin>>c[i];
}
sort(c+1,c+1+n);
dfs(1,0);
sort(dep+1,dep+n+1);
int ans=0;
for (int i=1;i<=n;i++)
{
ans+=dep[i]*c[i];
}
cout<<ans<<'\n';
return 0;
}
E
有一个函数表达式
\[f(x)=\frac{n}{x} +x-1(其中\frac{n}{x}为向下取整) \]问在l到r中找到一个最小的t,让f(t)最小
如果不考虑向下取整，看到这个函数是不是很熟悉
对
就是我们高中所说的双勾函数（我们老师是这么叫的，因为他就像两把勾），在第一象限，它是先递减，再递增，其中最小值的点为根号n(sqrt(n))
但是这里面还有一个向下取整，所以最小的位置不一定是sqrt(n)
我们考虑三种情况
这个区间里只有递增（l>sqrt(n)),最小的为l，直接输出
如果是递减
那么最小的一定是f(r),但是因为要求最小的t让f(t)最小，有可能r前面也可能存在数等于f(r),我们的答案就是最小的一个f(t)=f(r)
如果r>m,那我们还要考虑sqrt(n)+1,如果f(sqrt(n)+1)更小，那么我们一定要让r=m+1,否则就是r=m,反正最小的一定是这两个之中
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,l,r;
int f(int x)
{
return n/x+x-1;
}
void solve()
{
cin>>n>>l>>r;
int m=sqrt(n);
if (l>m)//递增
{
cout<<l<<'\n';
return ;
}
if (r>m)//这个区间先降低再增加，那么我们最小的可能是m,或者是m+1，否则是递减，最小值是r
{
r=m;
if (f(m+1)<f(m))r++;
}
int ans=0,mi=f(r);
while (l<=r)
{
int mid=(l+r)>>1;
if (f(mid)<=mi)
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
F
这一个题是一个迷宫，每一个位置可能会有一个怪物，那么这个位置我们一定是不能走的，我们从1,1到n,3,我们可以走很多次，只要我们可以到达n,3，那么这一条路上的金币我们也可以获得（每一个位置只有一个金币），问我们最多可以得到多少个金币
我们有两个方向可以走，向下，向右
这个题目直接dfs,我们需要两个数组来记录
can来记录位置能不能走（有怪物就不能走）
vis记录的是可以走到目的地的位置
具体看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int t,n,k;
int can[maxn][5];
bool vis[maxn][5];
void init()//一开始都是可以走的
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=3;j++)
{
can[i][j]=1;
vis[i][j]=false;
}
}
return ;
}
bool dfs(int x, int y)
{
if(x < 1 || x > n || y < 1 || y > 3) return false;//如果走出去，那么这一条路不可以成功
if(vis[x][y] || can[x][y]==0) return can[x][y];//如果已经走过或者是有怪物，那么我们就直接判断可不可以走
vis[x][y] = true;//到了这儿，就可以走
if(x == n && y == 3) return true;//如果到了(n,3),那么就可以成功
can[x][y] = dfs(x + 1, y) | dfs(x, y + 1);//只要有一个成功，那么这一条路就成功了
return can[x][y];
}
void solve()
{
cin>>n>>k;
init();
for (int i=1;i<=k;i++)
{
int x,y;
cin>>x>>y;
can[x][y]^=1;//只有改变偶数次才可以可以走
}
dfs(1,1);
int ans=0;
vis[1][1]=false;//1,1是没有金币的
for (int i=1;i<=n;i++)
{
for (int j=1;j<=3;j++)
{
if (can[i][j]&&vis[i][j]) ans++;//要既没有怪物还要可以到达这一个点，那么得到的金币就加一
can[i][j]=1,vis[i][j]=false;
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
H
题目大意是把一个串分成x块，其中一块中，只出现一次的数的数量为这一块的价值，我们会有n个x,1到n,我们需要知道分成x块时的所有的价值
我们可以存下有出现一次的数的数量，出现二次的数的数量，出现三次的数的数量，出现四次的数的数量，等等
用siz存
对于分成一段，
ans=siz[1]
分成两段，
第一段，我们让所有的数都拿出一个放在里面，然后把剩下的放在第二段里 ,那么第二段里只有出现2次的拿出了一个后只剩下一个了
ans=r+siz[2]
分成三段
第一段还是所有的数都拿出一个放在里面，第二段还是把剩下的所有的数拿出一个放在里面，那么第三段里只有出现3次的拿出了一个后只剩下一个了
ans=r+r-siz[1]+siz[3]
分成四段
ans=r+r-siz[1]+r+r-siz[1]-siz[2]+siz[3]
那么，我们可以总结出
我们可以记录 siz的前缀和，然后记录一个last=r
ans[2]=last+siz[2]
last+=r-siz[i-1]
ans[i]=last+siz[i]
具体看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
#define int long long
int n,a[maxn];
int t;
bool cmp(int x,int y)
{
return x>y;
}
int siz[maxn];
int ans[maxn];
int sum[maxn];
void solve()
{
cin>>n;
map<int,int>cnt;
for (int i=1;i<=n;i++)
{
cin>>a[i];
cnt[a[i]]++;
siz[i]=0;
}
int r=cnt.size();//总共有r个不同的数
int tot=0;
for (auto [x,y]:cnt)
{
siz[y]++;
}
ans[1]=siz[1];
sum[1]=siz[1];
for (int i=2;i<=n;i++)
{
sum[i]=sum[i-1]+siz[i];
}
int x=r;
int last=r;
for (int i=2;i<=n;i++)
{
ans[i]=last+siz[i];
last=last+r-sum[i-1];
}
for (int i=1;i<=n;i++)
{
cout<<ans[i]<<'\n';
}
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
I
这个题大意就是有五个区间，每一个区间都有一个价值，然后有n个数x，我们可以让所有的x=x+h(h为任意数)，求最后得到最大的价值
我们先考虑让所有的数在第一个区间（此时h很小），让后我们遍历h，（从小到大），就好像让这n个数在数轴上往后移动，我们只要找到一个最大的价值即可
这具体操作就是我们一开始把所有的数在第一个区间，然后记录把xi移动到第二个区间，此时的h为l[2]-x[i],得到的价值为减去v[1]加上v[2],如果要达到第三个区间H=l[3]-x[i]，价值为v[3]-v[2],H一定大于h,那么我们之间一定已经-v[1]+v[2],然后我们在此时-v[2]+v[3]就实现了从第一个区间到第三个区间的价值的更新
我们只需要求这一段的最大值即可
注意第四个区间的右端点为闭区间
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
#define int long long
int t,n,x[maxn];
int l[10],v[10];
void solve()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x[i];
}
for (int i=1;i<=4;i++)
{
cin>>l[i];
}
l[4]++;
for (int i=1;i<=5;i++)
{
cin>>v[i];
}
//我们先假设加了一个很小的数，让所有的数都在第一个区间，那么初始条件为v[1]*n
//然后我们考虑x[i]要到某一个区
map<int,int>h;//寻找h
for(int i=1;i<=n;i++)
{
h[l[1]-x[i]]+=(v[2]-v[1]);//x[i]到达2区间最小的距离，那么此时的值由v[1]变成了v[2]
h[l[2]-x[i]]+=(v[3]-v[2]);//x[i]如果到3区间，前面的h一定比这一个h小，那么那么当此时的x[i]已经在2区间了，那我们就减去v[2]加v[3]
h[l[3]-x[i]]+=(v[4]-v[3]);//同上
h[l[4]-x[i]]+=(v[5]-v[4]);
}
int ans=max(v[1]*n,v[5]*n);
int now=v[1]*n;
for (auto [hh,vv]:h)//遍历h，从小到大，h慢慢增加，一直到所有x都到4区间，我们停止的位置一定是最大的获得能量，那么后面的变化我们都不作数了
{
// cout<<vv<<"\n";
now+=vv;
ans=max(ans,now);
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
J
我们可以知道一对i,j的价值为max(abs(a[i]+a[j]),abs(a[i]-a[j]))
问所有的i,j的和
如果a[i]和a[j]都大于0，那么这两个的贡献为 a[i],a[j]
如果一个大于0，一个小于0，那么abs(a[i]-a[j])更大，可以让那个负数的贡献为-a[i]
所以每一个数的贡献为那一个数的绝对值
对于所有的数，都会出现2n次，可以画出一个nXn的矩阵，我们可以看到，
i会出现2n次（题目中i可以等于j,那么i,i会出现两次）
#include <bits/stdc++.h>
using namespace std;
#define int long long
int t ,n;
void solve()
{
cin>>n;
int ans=0,x;
for (int i=1;i<=n;i++)
{
cin>>x;
x=abs(x);
ans+=x;
}
ans*=2*n;
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
return 0;
}
K
给n个数，m个关系，a和b可以得到一个高级的东西，然后有q次询问，每一次询问都会给我们k个数，我们可以得到多少个高级的东西
对于a和b可以得到一个一个高级的东西，我们可以用边连在一起，对于每一次询问，我们会遍历给我们的k个数，如果它的另外一半存在这个询问里，那么就可以得到一个高级的东西
对于怎么连边呢，我们让入度小的那一个数到达入度大的那一个数（这样他的边少，遍历的少，不会超时）
具体看代码
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int maxn=2e6+10;
int n,m,q;
vector<int>g[maxn<<2];
int vis[maxn];
int now[maxn];
int a[maxn],b[maxn],d[maxn];
signed main ()
{
cin>>n>>m>>q;
for (int i=1;i<=m;i++)
{
cin>>a[i]>>b[i];
d[a[i]]++;
d[b[i]]++;
}
for (int i=1;i<=m;i++)
{
if (d[a[i]]<d[b[i]])
{
g[a[i]].push_back(b[i]);
}
else
{
g[b[i]].push_back(a[i]);
}
}
while (q--)
{
// cout<<q<<'\n';
int k;
cin>>k;
int ans=0;
for (int i=1;i<=k;i++)
{
cin>>now[i];
vis[now[i]]=q+1;
}
for (int i=1;i<=k;i++)
{
int tnow=now[i];
for (auto ne:g[tnow])
{
if (vis[ne]==q+1) ans++;
}
}
cout<<ans<<'\n';
}
return 0;
}
L
给n个数，我们要知道有多少个三元组，i,j,k满足两两不同
(a[i]*a[j]+a[k])%p=x
有0到p-1的x,我们要知道x时的数量
对于 i,j,k，我们可以分为两份找，第一份找i,j的余数，第二部分找k的余数
然后我们先不管下标，直接求出所有余数的和
然后我们再考虑k和i,j其中一个相同，减去这种情况的数量
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5e3+10;
int n,p;
int a[maxn],add[maxn],mul[maxn];
int ans[maxn];
signed main ()
{
cin>>n>>p;
for (int i=1;i<=n;i++)
{
cin>>a[i];
a[i]%=p;
add[a[i]]++;
}
for (int i=1;i<=n;i++)
{
for (int j=i+1;j<=n;j++)
{
int now=(a[i]*a[j])%p;
mul[now]+=2;
}
}
for (int i=0;i<p;i++)//遍历两部分，求不管下标x的次数
{
for (int j=0;j<p;j++)
{
int now=(i+j)%p;
ans[now]+=mul[i]*add[j];
}
}
for (int i=1;i<=n;i++)//对于i,j，k和其中有一样的下标的
{
for (int j=1;j<=n;j++)
{
if (i==j) continue;
int now=((a[i]*a[j])%p+a[i])%p;//i j ,i j,i,i 两对
ans[now]-=2;
}
}
for (int i=0;i<p;i++)
{
cout<<ans[i]<<" ";
}
return 0;
}