您的位置: 首页  >  文章  >  牛客寒假算法基础集训营 题解

牛客寒假算法基础集训营 题解

分类: 文章 • 2023-10-15 20:41:35

 

A. 处女座与线性代数

题目描述 

牛客寒假算法基础集训营 题解

众所周知，处女座是数学大师。他定义了k维空间里的处女座点。

对于给出的k维度空间上N个点，处女座点满足：

对于这个点P和空间里任意其他两个点P1P1、P2P2，有dot(→PP1,→PP2)<0dot(PP1→,PP2→)<0。

现在给你一个k维空间和这N个点，请求出这里面所有的处女座点。

Hint: dot(→A,→B)dot(A→,B→)表示两个向量的点乘（内积）。两个向量→A={a1,a2,⋯,an}和→B={b1,b2,⋯,bn}A→={a1,a2,⋯,an}和B→={b1,b2,⋯,bn}的点乘（内积）定义为：dot(→A,→B)=a1∗b1+a2∗b2+⋯+an∗bndot(A→,B→)=a1∗b1+a2∗b2+⋯+an∗bn。

输入描述:

输入数据第一行包含一个整数T，表示用例组数。

对于每组用例，第一行两个整数 N,k。

接下来 N 行，每行k个整数，表示每个点的坐标。

输出描述:

对于每一组数据，先输出一个整数ans，表示处女座点的个数。

接下来ans行，每行k个数，表示每个处女座点的坐标。

如果有多个点满足条件，则按照输入数据中出现的顺序进行输出。

示例1

输入

复制

1
3 2
0 0
1 1
-1 -1

输出

复制

1
0 0

备注:

3≤N≤1043≤N≤104

1≤k≤101≤k≤10

T≤100T≤100

对于每一个点，保证每一维坐标的绝对值在109109以内

题目分析

数学分析题，下面给出官方题解

我们将列举出本题所使用到的结论：

1.处女座点的数量最多为 1

证明：
牛客寒假算法基础集训营 题解

2. 若K维空间一个点集{P1,P2,⋯,PnP1,P2,⋯,Pn}存在处女座点，则????≤????+????≤????????+????

严格的证明需要利用高等代数。但是利用数学归纳法或线性代数方法证明同条件下证明????≤2????+1是显然的。 （提示：将处女座点的定义弱化为向量夹角为钝角或直角后即可证明）

综上所述，若????>????+2则直接输出0，否则暴力检查即可。由于????≤10，用????>2????+1判断也是可以的。
时间复杂度????(????^3)。

官方代码：

#include <cstdio>
#include <vector>
 
using namespace std;
 
int pt[10005][15];
int n, k;
 
int dot(int p, int p1, int p2) {
    int ans = 0;
    for (int i = 0; i < k; ++i)
        ans += (pt[p1][i] - pt[p][i]) * (pt[p2][i] - pt[p][i]);
    return ans;
}
 
int main(int argc, char* argv[]) {
 
    int kase = 0;
    int T;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < k; ++j)
                scanf("%d", &pt[i][j]);
        }
 
        int ans = -1;
        if ((k > 1 && n <= 2 * k) || (k == 1 && n <= 3)) {
            for (int p1 = 0; p1 < n; ++p1) {
                bool flag = true;
                for (int p2 = 0; p2 < n; ++p2) {
                    for (int p3 = 0; p3 < n; ++p3) {
                        if (p1 == p2 || p1 == p3 || p2 == p3)
                            continue;
                        if (dot(p1, p2, p3) >= 0) {
                            flag = false;
                            break;
                        }
                    }
 
                    if (!flag)
                        break;
                }
 
                if (flag) {
                    ans = p1;
                    break;
                }
            }
        }
 
        if (ans == -1)
            puts("0");
        else {
            puts("1");
            for (int i = 0; i < k; ++i) {
                if (i > 0)
                    putchar(' ');
                printf("%d", pt[ans][i]);
            }
            putchar('\n');
        }
    }
    return 0;
}

B. 处女座的比赛资格

题目分析

待补。

有向无环图（DAG）上的最短路。
注意：负权值边的存在使得 Dijkstra 算法不适用，特殊 DAG 的性质使得 SPFA 算法无法在规定的时间限内求解出答案。 考虑到 DAG 的特殊性，按照原图节点的拓扑顺序依次递推距离即可求解。

令????????表示节点1到i的最短路，????????????????_????表示节点的先驱集合。则有：

di=min(dj+cost(j,i))????????=min⁡(????????+????????????????(????,????))其中????∈????????????????_????，其中????????????????(????,????)表示从节点j到节点i的有向边的边权。

按照节点拓扑顺序计算d即可。

时间复杂度：????(????+????)

 

C. 处女座点名

题目分析

签到题，没什么意思

题目已经保证了输入顺序，只需要判断读入的数是否比上一个数大1即可。如果都满足，就是最后一个数没有出现。

时间复杂度：????(????)

 

D. 处女座的训练

题目分析

贪心思想。按照牛客寒假算法基础集训营 题解 作为关键字进行排序，按顺序完成作业即可。

时间复杂度：????(???? log N)

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		node [] a=new node[200005];
		Long sum=(long) 0;
		for(int i=1;i<=n;i++)
		{
			a[i]=new node();
			a[i].x=in.nextInt();
			a[i].y=in.nextInt();
			sum+=a[i].y;
		}
		Arrays.sort(a,1,n+1,new My());
		Long ans=(long) 0;
		for(int i=1;i<=n;i++)
		{
			//System.out.println(a[i].y);
			sum-=a[i].y;
			ans+=(sum)*a[i].x;
		}
		System.out.println(ans);
	}
}
class My implements Comparator<node>
{
	 public int compare(node stu1, node stu2) {
         return stu2.y*stu1.x-stu1.y*stu2.x;
	 }
}
class node
{
	public int x,y;
}

E. 处女座和小姐姐

链接：https://ac.nowcoder.com/acm/contest/329/E
来源：牛客网
 

题目描述

牛客寒假算法基础集训营 题解

既然昨天晚上处女座已经训练了，明天才要交作业，那今天就是平淡无奇要上课的一天了。

然而处女座也想自己的小姐姐了，可是这节课是老师安排座位，处女座坐在(1,1)，而小姐姐坐在(n,m)。他们之间只能通过传纸条的方式来交流感情。对于处女座而言，他上课不想过度分心，因此并不想传纸条，只在那里趁机折千纸鹤。

老师上课喜欢用"开火车"的方式让大家轮流回答问题，显然处女座作为(1,1)位，会被第一个叫起来回答，之后老师将依次叫起(2,1),(3,1),….(n,1),(n,2),(n−1,2)⋯(1,2),⋯(2,1),(3,1),….(n,1),(n,2),(n−1,2)⋯(1,2),⋯的人起来回答问题，每个人回答问题需要1秒。处女座在自己回答完以后会以每秒1个千纸鹤的速度折叠，在小姐姐开始回答问题的时候停止折叠。

处女座想知道，他这节课一共要折多少个千纸鹤？

输入描述:

输入文件包含T+1行，第一行包含一个整数T，表示用例组数。

接下来T行，每行包含两个整数n,m表示小姐姐的位置和教室的大小。

输出描述:

对于每一组用例，用一行输出一个整数，表示处女座要折的千纸鹤的个数。

示例1

输入

复制

1
3 3

输出

复制

7

备注:

2≤n,m≤1,000

 

题目分析

本题相当于只要求按照开火车的顺序，从(1,1)到(????,????)一共有几个人。
答案和m的奇偶性有关，如果m是偶数，答案是nm-n-1；如果m是奇数，答案是nm-2。

时间复杂度：????(1)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&x,&y);
        int ans;
        if(y%2==1)
            ans=x*y-2;
        else
            ans=x*(y-1)-1;
        printf("%d\n",ans);
    }
}

F. 处女座和小姐姐（二）

题目分析

待补。

本题分为两个子问题。

1. 求一个数组连续p个数mod P的乘积

把序列按照长度m分成若干段，计算每段内的前缀和后缀乘积。
这样任意划窗位置的答案可以看成前一段的后缀和后一段的乘积拼出。
时间复杂度????(????∗????+????−1)

2. 找出长度为k的符合条件的链的个数

使用dfs进行搜索，复杂度〖400∗3〗^20显然会超时，因此使用枚举起点然后双向dfs的方法，一次往两边进行搜索，从而把复杂度降低到400∗〖2∗3〗^10，可以使用状压等方式记录状态。

G. 处女座和小姐姐（三）

链接：https://ac.nowcoder.com/acm/contest/329/G
来源：牛客网
 

牛客寒假算法基础集训营 题解

经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！

处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。

现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。

输入描述:

一行包括两个数字l,r，表示你给处女座展示的数字范围为[l,r]。

输出描述:

一行一个整数，表示处女座内心激动的次数。

示例1

输入

复制

10 20

输出

复制

1

备注:

0≤l≤r≤1018

题目分析

状压DP，基本题

 

///求前n个数的二进制形式含有11个数的和
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=40;
typedef long long ll;
int n;
int dig[maxn];
ll dp[maxn][maxn];

ll dfs(int pos,int sta,int limit)
{
    if(pos<0) return sta;
    if(!limit&&dp[pos][sta]!=-1)
    	 return dp[pos][sta];
    ll ans=0;
    int up=(limit?dig[pos]:9);  
    for(int i=0;i<=up;i++)
    {
		ans+=dfs(pos-1,sta||i==6,limit&&i==up);
        
    }
    if(!limit) dp[pos][sta]=ans;
    return ans;
}
ll solve(ll n)
{
    int len=0;
    memset(dp,-1,sizeof(dp));
    while(n)
    {
        dig[len++]=n%10; ///转化为二进制
        n/=10;
    }
    return dfs(len-1,0,1);
}
int main()
{
    int T,cas=1;
            ll a,b;
         cin>>a>>b;
         //cout<<solve(a)<<endl;
        printf("%lld",solve(b)-solve(a-1));
   
    return 0;
}

H.处女座的百日理财计划

题目分析

首先题目要求按照期望估算收益，则借钱的收益是(1+Mi%)∗(1−Pi%)(1+????????%)∗(1−????????%)，*的收益是2∗Qi%2∗????????%。
显然如果*概率>50%一定会去玩。对于借钱直接进行dp即可。由于收益固定，每次一定是全部都进行投入的。
注意由于题目里要取max，且涉及到乘法操作，只能全程用高精度计算最后进行取模。

时间复杂度：????(200????)

I.处女座的约会

题目分析

很坑的一道题

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		while(n-->0)
		{
			String s=in.next();
				
			System.out.println("cnznb");
			
		}
		
	}
}

显然处女座十分牛逼，因此输出“cnznb”即可
咳咳……至于正确的做法。首先因为每次在右边砍掉一个头就相当于在左边会多出来一个头，所以可以把每????次操作看作一轮，每轮的操作都是从01串右边向左边对每个位置在原位依次进行操作。我们考虑这种做法，从右到左我们首先看到1就把他变成0，0的话让他随机，直到第一次出现有0变成了1的情况。如果没有出现这种情况那么这个串已经符合了要求，如果有0变成1发生，那么在这之后的1我们都继续变成1。这样一轮结束之后，这个01串所表示的二进制数的的大小一定是严格增加了的（因为虽然你可能把一些1变成了0但是有一个高位的0变成了1）而这个二进制数的大小是有限的，因此在有限步内一定可以把这串数变成全0串。

时间复杂度：????(1)

 

J. 处女座的比赛

题目分析

题目要求找出在给定的hash函数下hash值相同的答案。
注意到对于长度是1-4的小写字母的字符串一共共475254个，已经可以包含[0,9983)的范围，因此暴力对每个hash值记录两个字符串输出即可。记两个是防止输出和输入串相同判错，从而使用另一种替换。

时间复杂度：????(26+262+263+26426+262+263+264)

相关推荐