2020牛客国庆集训派对day6 部分题解
前言
- 好题很多
A Fractions
- 题意：给出一个n，构造两个数组满足
- 分析：
让我们推导一下，假设存在两个数x/a,y/b使得上式成立(为最简式)
那么可以得知 a * b = n,枚举n的因数，然后可以得到b，因为是分数，再通过枚举x来计算出y的结果，即for (ll i=2;i<=sqrt(n);i++) if(n%i==0)//枚举因子a for (ll j=1;j<i;j++) if((n-1-j*n/i)%i==0)//枚举分子x，求出y的值 { printf("YES\n2\n%lld %lld\n%lld %lld\n",j,i,(n-1-j*n/i)/i,n/i);//只需要两个即可 return 0; } - 代码
B Guest Student
题意：有多组数据，每一组数据，都有一周的课程安排，有七天，每一天有一个a[i]表示是否学习，再出入一个n，问如果总共要学习 n 天，最少要在学校待几天。
分析：
简单模拟就好(差点给我栽这儿了Qwq),因为只有七天，那就以每一天为起点，求出如果总共要学n天一共需要待多长时间。有一些细节要注意。因为这n天肯定不能直接循环去做，那么就将其分为整体和部分两种情况。
#include<bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
memset(a,0,sizeof(a));
scanf("%d",&n);int tot=0;
for (int i=1;i<=7;i++)
scanf("%d",&a[i]),tot+=a[i];
int ans=1e3;
for (int i=1;i<=7;i++)
{
int rem=n%tot+tot;
int res=0,now=0;
for (int j=i;;)
{
if(a[j]) res++;
now++;j++;
if(j==8) j=1;
if(res==rem) break;
}
ans=min(ans,now);
}
printf("%d\n",ans+(n/tot-1)*7);
}
return 0;
}E King Kog's Reception
题意：
国王的接待处会收到n个预约消息，第i个消息分为三种
1： + x y 表示第i个骑士在时刻 x 到来，国王处理这件事的持续时间为 y
2： - x 表示消息第 x 条预约作废
3： ？ x 询问如果公主从时刻 x 到来，直到之前所有事情被处理完的等待时间分析：
- 这一道题的内容与国庆day7 C很类似，但是处理方法却不同。对于一个时间点来说，他有一个初始等待时间与最终结束时间之分。而他的最开始的等待时间明显就是他来的时间。于是我们考虑如何求得他的最终结束时间。
- 一个点的最终结束时间是与他左边的预约有关的，因为只有左边的预约完成这个预约才会开始。也就是说我们的目的就是维护一个区间的最大的预约结束时间。
- 维护方法：
这一区间的预约结束时间就是 max (左区间的最终结束时间+右区间的预约处理时间 ， 右区间的最终结束时间 )
由此，就可以建立线段树维护区间的预约结束时间与处理预约的总时间，每次单点询问得到答案。
//区间修改+单点查询
#include<bits/stdc++.h>
#define ls now<<1
#define rs now<<1|1
#define ll long long
using namespace std;
const int N=1e6+10,M=1e6;
int q;ll ans;//加入的编号
int a[N],b[N];ll s[N<<2],w[N<<2];
char ins[5];
inline void upd(int now)
{
s[now]=s[ls]+s[rs];
w[now]=max(w[ls]+s[rs],w[rs]);
}
inline void build(int now,int l,int r)
{
if(l==r)
{
w[now]=l;
return ;
}
int mid=(l+r)>>1;
build(ls,l,mid);build(rs,mid+1,r);
upd(now);
}
inline void add(int now,int l,int r,int x,int z)
{
if(l==r)
{
w[now]+=z;s[now]+=z;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) add(ls,l,mid,x,z);
else add(rs,mid+1,r,x,z);
upd(now);
}
inline ll find(int now,int l,int r,int x)
{
if(r<=x)
{
ans=max(s[now]+ans,w[now]);
return ans;
}
int mid=(l+r)>>1;
find(ls,l,mid,x);
if(x>mid) find(rs,mid+1,r,x);
return ans;
}
int main()
{
scanf("%d",&q);build(1,1,M);
for (int i=1;i<=q;i++)
{
scanf("%s%d",ins,&a[i]);
if(ins[0]=='+')
{
scanf("%d",&b[i]);
add(1,1,M,a[i],b[i]);
}
else if(ins[0]=='?')
ans=0,printf("%lld\n",find(1,1,M,a[i])-(ll)a[i]);
else
add(1,1,M,a[a[i]],-b[a[i]]);
}
return 0;
}F Lazyland
题意：懒人国有n个乞丐，m份工作，每个人选择编号为 a [ i ] 的工作，然而有些工作没有人去做并且一份工作只能有一个人做。每一个乞丐都有一个 b [ i ] ，表示劝服其换一个工作的代价。问要使每一份工作有且只有一个人做的最小代价
分析：
- 这是一个贪心问题。记录一下每一份工作的人数，以及还需要多少份工作(假设为 y )。那么这做这 y 份工作的人只能从那些参与了同一份工作的人中选。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int n,ned,k;ll ans;
int num[N],a[N],b[N];
bool vis[N];
struct nkl
{
int id,per;
bool operator < (const nkl &b)const
{
return per>b.per;
}
nkl (int x,int y):id(x),per(y){}
};
priority_queue<nkl>q;
int main()
{
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);num[a[i]]++;
if(!vis[a[i]]) ned++,vis[a[i]]=1;
}
for (int i=1;i<=n;i++) scanf("%d",&b[i]);
for (int i=1;i<=n;i++)
q.push(nkl(a[i],b[i]));
ned=k-ned;
while(ned)
{
nkl u=q.top();q.pop();
if(num[u.id]==1) continue;
num[u.id]--;ned--;
ans+=u.per;
}
printf("%lld\n",ans);
return 0;
}H Archery Tournament
题意：现在有一个射箭比赛。由于靶场足够远，每一个靶子可以看做底面接触 y 轴的圆，像这样
一共有n个事件，分两种- 1 x y 表示出现了一个以(x,y)为圆心，y为半径的靶子
- 2 x y 表示朝点(x,y)射，求会射中哪一个靶子，射中的靶子会消失。在任何时刻，靶子不会相交(不包括边缘接触)
分析
- 第二次遇到这种题
- 这样想，如果我朝(x，y)射，有哪些靶子可能被射中——圆心在 [ x - y , x + y ] ，也就是说，我需要维护一下圆心在 [ x - y , x + y ] 的圆。
- 发现 x ， y 的范围较大，考虑动态开点线段树+vector。每当出现了一个靶子，便插入相应的节点中。如果要射箭，那就单点查询，对每一个节点中的圆都考虑一遍，如果找到了，就删除
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const int inf=1e9;
int n,cnt,rt,ans;
ll lx[N],ly[N];
int lc[N*30],rc[N*30];
vector<int>s[N*30];
inline void add(int &rt,int l,int r,int id,int x,int y)
{
if(!rt) rt=++cnt;
if(l>=x&&r<=y)
{
s[rt].push_back(id);
return ;
}
int mid=(l+r)>>1;
if(x<=mid) add(lc[rt],l,mid,id,x,y);
if(mid<y) add(rc[rt],mid+1,r,id,x,y);
}
inline void upd(int rt,int l,int r,ll x,ll y)
{
if(l>=x&&r<=y)
{
vector<int>tmp;int len=s[rt].size();
for (int i=0;i<len;i++)
if(s[rt][i]!=ans) tmp.push_back(s[rt][i]);
s[rt]=tmp;
return ;
}
int mid=(l+r)>>1;
if(x<=mid) upd(lc[rt],l,mid,x,y);
if(mid<y) upd(rc[rt],mid+1,r,x,y);
}
inline bool check(ll u,ll v,ll x,ll y)
{
if((x-u)*(x-u)+(y-v)*(y-v)<v*v) return 1;
return 0;
}
inline void find(int rt,int l,int r,ll x,ll y)
{
if(!rt) return ;
int len=s[rt].size();
for (int i=0;i<len;i++)
if(check(lx[s[rt][i]],ly[s[rt][i]],x,y))
{ans=s[rt][i];break;}
int mid=(l+r)>>1;
if(x<=mid) find(lc[rt],l,mid,x,y);
else find(rc[rt],mid+1,r,x,y);
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
int id;ll x,y;
scanf("%d%lld%lld",&id,&x,&y);
if(id==1)
{
lx[i]=x;ly[i]=y;
add(rt,-inf,inf,i,x-y,x+y);
}
else
{
ans=-1;
find(rt,-inf,inf,x,y);
//抽象为单点查询
printf("%d\n",ans);
if(ans!=-1)
upd(rt,-inf,inf,lx[ans]-ly[ans],lx[ans]+ly[ans]);
}
}
return 0;
}I Box
- 题意：能否用一个w*h的纸板制得大小为 a * b * c 的纸盒
- 分析：
- 一开始我直接求出不同的剪切方法能否构成 a * b * c 的纸盒，但是情况之多，复杂之极
- 换个方向，考虑这个 a * b * c 的纸盒能否以某种平铺方式放在这个纸板上面。发现题目下面给出了十一种平铺方式，没用他还给你放这里？于是我去把他列了下来(QwQ，中途还爆了)
发现这些图形中的平铺下来的宽与长只有三种不同的形式,那就直接分类讨论就行
- 代码：
#include<bits/stdc++.h>
using namespace std;
int a,b,c,w,h;
int k,p;
inline bool check(int x,int y,int z)
{
k=x+2*z,p=2*z+2*y;
if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
k=x+z,p=x+z+3*y;
if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
k=x+y+z,p=x+z+2*y;
if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
return 0;
}
int main()
{
scanf("%d%d%d%d%d",&a,&b,&c,&w,&h);
if(check(a,b,c)||check(a,c,b)||check(b,a,c)||check(b,c,a)||check(c,a,b)||check(c,b,a)) puts("Yes");
else puts("No");
return 0;
}J Connections
题意：有一个n个点m条有向边的强联通图，问能否删去(m-2n)条边(即只剩下2n条边)使得剩下的图仍然强联通
分析：
- 既然涉及到联通图，那就试试从tarjan的方向考虑。
- 首先回忆一下tarjan，在使用它的时候会形成一棵树，因为越先遍历到说明他的dfn越小。如果一条边能更新到一个点，说明他就是有用的。如果一条边能够使一个环闭合，他也是有用的。
于是需要在跑tarjan的过程中找到这些有用边
- 代码：
/*
在使用tarjan时会形成一棵搜索树,
越先遍历到说明dfn的值越小，因为节点
要相互到达，那么当找到一个环的时候
， 说明当前节点能到达下面所有的点，
那么这一条环的边也是需要的
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,tot,cnt,tp;
int h[N],nex[N],ver[N],re[N];
int dfn[N],low[N],stk[N];
bool vis[N],yep[N];
inline void add(int x,int y)
{
nex[tot]=h[x];
ver[tot]=y;re[tot]=x;
h[x]=tot++;
}
inline void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
stk[++tp]=u;vis[u]=1;
int rem=-1;//记录环边
for (int i=h[u];~i;i=nex[i])
{
int j=ver[i];
if(!dfn[j])
{
tarjan(j);yep[i]=1;
low[u]=min(low[u],low[j]);
}
else if(vis[j])
{
if(low[j]<low[u]) rem=i;
low[u]=min(low[u],dfn[j]);
}
}
if(rem!=-1) yep[rem]=1;
if(low[u]==dfn[u])
{
int y;
do
{
y=stk[tp--];
vis[y]=1;
}while(y!=u);
}
}
inline void Pre()
{
cnt=tot=0;
memset(h,-1,sizeof(h));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(vis,0,sizeof(vis));
memset(yep,0,sizeof(yep));
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
Pre();
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
add(x,y);
}
tarjan(1);
int rem=m;
for (int i=0;i<tot;i++)
{
if(rem<=2*n) break;
if(!yep[i])
{
rem--;
printf("%d %d\n",re[i],ver[i]);
}
}
}
return 0;
}比赛题解 文章被收录于专栏
牛客IOI周赛，团队赛，练习赛，挑战赛，各种模拟赛的部分题解
投递华为等公司10个岗位 >