2020牛客寒假算法基础集训营6 题解
A
solution:
一开始题目读错，乱写二分，看到了一 一映射这几个大字，推了一下是前n个数相加，如何使得最小值最大，必然A集合第一个加B集合最后一个，依次类推，倒序相加
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int a[maxn],b[maxn];
int c[maxn];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
sort(a+1,a+1+n);
sort(b+1,b+1+n);
int j = n-k+1,cnt = 0;
for(int i=n;i>=n-k+1;i--){
c[++cnt] = a[i] + b[j++];
}
sort(c+1,c+1+cnt);
printf("%d\n",c[1]);
return 0;
}B
soluiton：
有向图，并且每一个点都仅有一条出边，问题在于可能存在环，仔细想一下，环上的每个点都可以遍历一遍环，所以以他们为起点的路径长度都是环的长度，这样说还不理解就看图，我们考虑遍历每一个节点，遍历过的vis数组标记一下，不再重新访问，当遍历到访问过的节点后，如果构成了环，我们就要将环上所有点的最大路径长度都记为环的长度
-下面我们模拟一下图上的dfs情况
遍历1号节点 1 - 2 - 3 - 1 构成了环，我们将123号节点的路径长度都记为3
遍历2号节点 vis[2] = 1 ， 继续下一个节点
遍历3号节点 vis[3] = 1 ， 继续下一个节点
遍历4号节点 4 - 2 ,2号节点vis[2] = 1,但没构成环，4号节点路径长度 = 1 + 2号节点长度
遍历5号节点 5 - 4 ,4号节点vis[4] = 1,但没构成环，5号节点路径长度 = 1 + 4号节点长度
遍历结束~
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1000005;
vector<int> v[maxn];
int flag[maxn],ans[maxn],a[maxn];
int maxx = 0;
void dfs(int x,vector<int> &ve)
{
flag[x] = 1;
int nex = v[x][0];
ve.push_back(x);
if(flag[nex] == 1){
int x = ans[nex];
int siz = ve.size(),sign = 0,pos = 0;
for(int i=0;i<ve.size();i++)
{
if(ve[i] == nex){
sign = 1;
pos = i;
}
}
if(sign == 0){
for(int i=0;i<ve.size();i++){
ans[ve[i]] = x + siz - i;
}
}else{
int k = ve.size() - pos;
for(int i=pos;i<ve.size();i++){
ans[ve[i]] = x + k;
}
for(int i=0;i<pos;i++){
int kk = ve.size();
ans[ve[i]] = x + kk - i;
}
}
return ;
}
dfs(nex , ve);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i] == i){
flag[i] = 1;
ans[i] = 1;
}
v[i].push_back(a[i]);
}
vector<int> ne;
for(int i=1;i<=n;i++)
{
if(flag[i] == 1){
continue ;
}
ne.clear();
dfs(i , ne);
}
for(int i=1;i<=n;i++){
maxx = max(maxx , ans[i]);
}
cout<<maxx<<endl;
return 0;
}
C
soluiton：
其实求的就是个定理-Dilworth定理
一个序列最少可以分成n个上升非连续子序列 = 这个序列最长不上升子序列长度
一个序列最少可以分成n个下降非连续子序列 = 这个序列最长不下降子序列长度
然后我们就可以非常愉快的解决这一道题了
首先固定一条边按照升序排列，然后我们要找的就是另一条边的最少可以分成多少个上升非连续子序列，其实局势求这个序列的最长不上升子序列长度
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
struct node{
int x,y,id;
}a[maxn];
bool cmp(node p1,node p2)
{
return p1.x < p2.x;
}
int ans[maxn],dp[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].x,&a[i].y);
a[i].id = i;
}
sort(a+1,a+1+n,cmp);
int len = 1;
for(int i=1;i<=n;i++){
int l = 1,r = len;
while(l <= r){
int mid = (l+r)>>1;
if(a[i].y <= dp[mid])
l = mid + 1;
else
r = mid - 1;
}
dp[l] = a[i].y;
len = max(len , l);
ans[a[i].id] = l;
}
printf("%d\n",len);
for(int i=1;i<=n;i++){
if(i != 1)
printf(" ");
printf("%d",ans[i]);
}
return 0;
}D
soluiton：
其实就是让你找B的每一个位置能有多少个A数组的数比他小
看样例
b[1] = 1 ,比b[1] 小的数有1 1
b[2] = 2 ,比b[1] 小的数有1 1 2
b[3] = 3 ,比b[1] 小的数有1 1 2 3
b[4] = 4 ,比b[1] 小的数有1 1 2 3
枚举每一个位置能取的数，b[1]可以取任意一个1，b[2]能取除了b[1]选择的任意其余的两个数，b[3]能取除了b[1],b[2]的任意两个数，b[4]只能取一个数答案 = 2×2×2×1
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int a[maxn],b[maxn],c[maxn];
const ll mod = 1e9 + 7;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int maxx = a[n];
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
if(b[i] >= maxx){
c[i] = n;
}
else{
c[i] = upper_bound(a+1,a+1+n,b[i]) - a;
c[i] -= 1;
}
}
sort(c+1,c+1+n);
ll ans = 1,k = 0;
for(int i=1;i<=n;i++)
{
ans *= (1ll*c[i] -k);
k++;
ans %= mod;
}
cout<<ans<<endl;
return 0;
}
E
soluiton：
嘻嘻嘻嘻，我被卡常卡到自闭了
花了半天终于写对了
讲一下这一题，首先你要直到整数唯一分解定理and线性筛！
首先考虑三分之一N时间复杂度的做法，考虑枚举1e6以内的质数的三次方是否可以被N整除，如果能整除对答案产生贡献，但是这种做*超时~
接下来就是神奇的四分之一时间复杂度的做法，考虑枚举4e4内的素数，如果有N里x个质数p相乘，那么对答案的贡献就是p^(x/3)，然后剩下的N肯定最大最大是3个质数相乘，因为数据范围是1e18呀，所以我们二分最后的余数，考虑是否是一个三次方的数（对答案产生贡献）**
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 40000;
int cnt = 0;
int pri[maxn],prime[maxn];
ll pris[maxn],priss[maxn];
//prime数组的值代表下标是否为素数，0代表素数，1代表非素数
//pri数组存放的是素数，从下标0开始
void init()
{
int cnt =0;
for(int i=2;i<=maxn;i++){
if(!prime[i]){
pri[cnt] = i;
for(int j=i*2;j<maxn;j+=i)
prime[j] = 1;
}
}
}
int solve(ll x)
{
int ans = 1;
for(int i=0;priss[i] <= x;i++){
if(x%pri[i] == 0){
while(x%(pris[i]) == 0){
x /= pris[i];
ans *= pri[i];
}
while(x%pri[i] == 0){
x /= pri[i];
}
}
}
int l = 1,r = 1e6;
while(l <= r){
int mid = (l+r)>>1;
if((1ll*mid*mid*mid) < x)
l = mid + 1;
else
r = mid - 1;
}
if(1ll*l*l*l == x)
ans *= l;
return ans;
}
int main()
{
int t;
init();
scanf("%d",&t);
while(t--){
ll x;
scanf("%lld",&x);
printf("%d\n",solve(x));
}
return 0;
}
F
soluiton：
我们可以考虑拆分公式
考虑每次施放一次魔法，横纵坐标对答案的贡献
我们只需要算出横纵的坐标(xi,yi)的和（注意要减去中间的坐标，因为被重复计算了一次），乘以魔法值，累加答案即可
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
int main()
{
ll n , m , h;
ll x , y , z;
n = read(),m = read() , h= read();
ll k1 = (1 + n)*n/2;
ll k2 = (1 + m)*m/2;
ll ans = 0;
for(int i=1;i<=h;i++)
{
x=read(),y=read(),z=read();
ll cnt1 = m*x*z;
ll cnt2 = n*y*z;
ll cnt3 = k1*z;
ll cnt4 = k2*z;
ll cnt5 = x*z + y*z;
ans += (cnt1 +cnt2 + cnt3 + cnt4 - cnt5);
ans %= mod;
}
cout<<ans<<endl;
return 0;
}G
soluiton：
怎么好几场都是括号题
用stack模拟进栈出栈过程，碰到一个'('就加入栈中，碰到一个')'就消去栈顶的一个'('，如果栈中没有没有'('则这个')'必须要删去。最后答案就是栈的大小
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
stack< char > sta;
string s;
cin>>n>>s;
int cnt = 0;
for(int i=0;i<n;i++){
if(sta.empty()){
sta.push(s[i]);
}
else{
if(s[i] == '('){
sta.push(s[i]);
}
if(s[i] == ')'){
if(sta.top() == '('){
sta.pop();
cnt += 2;
}
else{
sta.push(s[i]);
}
}
}
}
cout<<sta.size()<<endl;
}
return 0;
}H
solution:no solution ，菜
I
soluiton：
这一题考的基础的最小生成树,不知道为什么这么多人不写
题目意思就是问你这是不是一个最短路的图，那么如果数据合法，原树就是这张新图的最小生成树。
我们只需要用kruskal算法求出来最小生成树和给出的最短路径比较
n = 500 ，所以floyd也没超时
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 505;
int f[maxn];
ll dis[maxn][maxn],dis2[maxn][maxn];
int n,cnt = 0;
struct node{
int u,v;
ll val;
friend bool operator < (node p1,node p2){
return p1.val < p2.val;
}//从小到大
}a[maxn*maxn];
int find(int x){
return f[x] == x ? f[x] :f[x] = find(f[x]);
}
void add(int u,int v,ll val){//添加边
a[++cnt].u = u;
a[cnt].v = v;
a[cnt].val = val;
}
void init(){//初始化并查集以及dis数组
memset(dis2,0x3f,sizeof(dis2));
for(int i=1;i<=n;i++)
f[i] = i,dis2[i][i] = 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%lld",&dis[i][j]);
if(i < j)
add(i,j,dis[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j] != dis[j][i]){
printf("No\n");
return 0;
}
}
}
init();
sort(a+1,a+1+cnt);
vector<ll> ve;
int sum = 0;
for(int i=1;i<=cnt;i++)
{
int u = a[i].u;
int v = a[i].v;
ll val = a[i].val;
int x = find(u),y = find(v);
if(x == y)
continue ;
dis2[u][v] = dis2[v][u] = val;
f[x] = y;
sum++;
ve.push_back(val);
}
if(sum != n-1){ //无法构成一棵树
printf("No\n");
return 0;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(dis2[i][j] > dis2[i][k] + dis2[k][j])
dis2[i][j] = dis2[i][k] + dis2[k][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j] != dis2[i][j]){
printf("No\n");
return 0;
}
}
}
printf("Yes\n");
sort(ve.begin(),ve.end());
int siz = ve.size();
for(int i=0;i<siz;i++){
printf("%lld\n",ve[i]);
}
return 0;
}J
soluiton：
解方程,设三个圆的半径分别为r1 , r2 , r3,三角形边长为a ，b ，c
三条边之和2×r1 + 2×r2 + 2×r3 = a + b + c
r1 + r2 = a
abc都已知
std：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
double ans[5];
int main()
{
double a,b,c;
cin>>a>>b>>c;
if(a + b > c && a + c > b && b + c > a){
double x,y,z;
z = (a+b+c)/2 - a;
y = b - z;
x = a - y;
ans[0] = z;
ans[1] = y;
ans[2] = x;
sort(ans,ans+3);
cout<<"Yes"<<endl;
printf("%.2lf %.2lf %.2lf\n",ans[0],ans[1],ans[2]);
}
else{
cout<<"wtnl"<<endl;
}
return 0;
}
投递科大讯飞等公司10个岗位 >