投稿
  1. 首页
  2. 随笔

2022牛客寒假算法基础集训营1

江阴一中 • 2022-12-17 • 随笔 • 阅读 28

2022牛客寒假算法基础集训营1,第1张

2022牛客寒假算法基础集训营1

寒假第一场比赛，检验自己，相比去年2021寒假集训营有了较大进步了,下面我按照自己的做题顺序做个记录

题目列表

L 牛牛学走路（签到）

代码 E 炸鸡块君的高中回忆

分析+代码 H 牛牛看云

分析+代码 J小朋友做游戏

分析+代码 F中位数切分A九小时九个人九扇门

分析加代码

L 牛牛学走路（签到）


这是一道签到题，我们直接上代码，注意输出格式小数点后的位数。

代码 
#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 2e5+10;
int t, n, m;
string str;
PII p;
double ans;
void solve(){
	cin>>t;
	while(t--){
		str = "", ans = 0;
		cin>>n>>str;
		p.first = 0, p.second = 0;
		for(int i = 0;i < n;i++){
			if(str[i] == 'U'){
				p.first += 1;
			}
			else if(str[i] == 'D'){
				p.first -= 1;
			}
			else if(str[i] == 'L'){
				p.second -= 1;
			}
			else{
				p.second += 1;
			}
			double len = sqrt(abs(p.first*p.first)+abs(p.second*p.second));
			ans = max(ans,len);
		}
		printf("%.12lfn",ans);
	}
}
int main(){
	solve();
	return 0;
}
E 炸鸡块君的高中回忆

分析+代码

这道题我们如果循环模拟的话肯定是会超时的，所以我们就可以尝试寻找他的规律，我们发现我们能够成功进入学校的时间一定是奇数，同时我们可以推出一个公式： n ≤ m ∗ c n t − c n t + 1 nleq m*cnt-cnt+1 n≤m∗cnt−cnt+1时，我们可以成功让所有人都进入校园，那么就有 c n t ≥ n − 1 m − 1 cntgeqfrac{n-1}{m-1} cnt≥m−1n−1​，最终我们得到的答案为 a n s = c n t × 2 − 1 ans=cnttimes2-1 ans=cnt×2−1。
那么我们就可以通过

cnt = ceil(1.0*(n-1)/(m-1));

求得 c n t cnt cnt的结果， c n t cnt cnt表示进入学校的次数。

#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 2e5+10;
int t, n, m;
ll ans;
void solve(){
	cin>>t;
	while(t--){
		ans = 0;
		cin>>n>>m;
		if(m==1&&n > 1)cout<<-1<= n)cout<<1< 
H 牛牛看云 

 
分析+代码 

这道题有一看
    
     
      
       
        1
       
       
        e
       
       
        6
       
      
      
       1e6
      
     
    1e6的数据范围，那么肯定是不能暴力的，比赛结束以后我看了一下大众的做法和我的不一样，我在这就只给出我的方法的代码了。
 我们需要求得的是
    
     
      
       
        
         ∑
        
        
         
          i
         
         
          =
         
         
          1
         
        
        
         n
        
       
       
        
         ∑
        
        
         
          j
         
         
          =
         
         
          i
         
        
        
         n
        
       
       
        ∣
       
       
        
         a
        
        
         i
        
       
       
        +
       
       
        
         a
        
        
         j
        
       
       
        −
       
       
        1000
       
       
        ∣
       
      
      
       sum_{i=1}^{n} sum_{j=i}^{n}lvert a_i+a_j-1000 rvert
      
     
    ∑i=1n​∑j=in​∣ai​+aj​−1000∣的结果。
 我首先是打表发现，我们输入的数据排序后与排序前得出的结果是一样的，那么我们不妨将输入的数据从小到大排序。同时我用
    
     
      
       
        s
       
       
        u
       
       
        m
       
      
      
       sum
      
     
    sum数组作前缀和数组，记录前
    
     
      
       
        i
       
      
      
       i
      
     
    i个的和，注意这个记录的是排序以后的。接着我用
    
     
      
       
        v
       
       
        i
       
       
        m
       
      
      
       vim
      
     
    vim数组存储在我们输入的数据数组中第一个大于等于
    
     
      
       
        1000
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       1000-num[i]
      
     
    1000−num[i]的数的位置，那么在这个
    
     
      
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       vim[i]
      
     
    vim[i]以前的位置的数字加上
    
     
      
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       num[i]
      
     
    num[i]必然是小于
    
     
      
       
        1000
       
      
      
       1000
      
     
    1000的，那么我们前面从
    
     
      
       
        i
       
       
        ∼
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        1
       
      
      
       isim vim[i]-1
      
     
    i∼vim[i]−1的范围内的结果就是
    
     
      
       
        (
       
       
        1000
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        j
       
       
        ]
       
       
        )
       
      
      
       (1000-num[i]-num[j])
      
     
    (1000−num[i]−num[j])而在这之前总共会有
    
     
      
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        i
       
      
      
       vim[i]-i
      
     
    vim[i]−i个类似的结果，也就是
 
    
     
      
       
        
         ∑
        
        
         
          j
         
         
          =
         
         
          i
         
        
        
         
          v
         
         
          i
         
         
          m
         
         
          [
         
         
          i
         
         
          ]
         
        
       
       
        (
       
       
        1000
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        j
       
       
        ]
       
       
        )
       
      
      
       sum_{j=i}^{vim[i]}(1000-num[i]-num[j])
      
     
    ∑j=ivim[i]​(1000−num[i]−num[j])
 那么我可以将其转化为
 
    
     
      
       
        1000
       
       
        ×
       
       
        (
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        i
       
       
        )
       
       
        −
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        ∗
       
       
        (
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        i
       
       
        )
       
       
        −
       
       
        (
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        1
       
       
        ]
       
       
        −
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        −
       
       
        1
       
       
        ]
       
       
        )
       
      
      
       1000times(vim[i]-i)-num[i]*(vim[i]-i)-(sum[vim[i]-1]-sum[i-1])
      
     
    1000×(vim[i]−i)−num[i]∗(vim[i]−i)−(sum[vim[i]−1]−sum[i−1])
 而在
    
     
      
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       vim[i]
      
     
    vim[i]之后的即为
    
     
      
       
        
         ∑
        
        
         
          j
         
         
          =
         
         
          v
         
         
          i
         
         
          m
         
         
          [
         
         
          i
         
         
          ]
         
         
          +
         
         
          1
         
        
        
         n
        
       
       
        (
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        +
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        j
       
       
        ]
       
       
        −
       
       
        1000
       
       
        )
       
      
      
       sum_{j=vim[i]+1}^{n}(num[i]+num[j]-1000)
      
     
    ∑j=vim[i]+1n​(num[i]+num[j]−1000)。将其转化为
 
    
     
      
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        n
       
       
        ]
       
       
        −
       
       
        s
       
       
        u
       
       
        m
       
       
        [
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        −
       
       
        1
       
       
        ]
       
       
        +
       
       
        n
       
       
        u
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        ×
       
       
        (
       
       
        n
       
       
        −
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        +
       
       
        1
       
       
        )
       
       
        −
       
       
        1000
       
       
        ×
       
       
        (
       
       
        n
       
       
        −
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
       
        +
       
       
        1
       
       
        )
       
      
      
       sum[n]-sum[vim[i]-1]+num[i]times(n-vim[i]+1)-1000times(n-vim[i]+1)
      
     
    sum[n]−sum[vim[i]−1]+num[i]×(n−vim[i]+1)−1000×(n−vim[i]+1)。
 但是我们要算绝对值内的值小于0的前提还有就是要
    
     
      
       
        i
       
       
        ≥
       
       
        v
       
       
        i
       
       
        m
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       igeq vim[i]
      
     
    i≥vim[i]，所以我们就会有如下核心代码
 

int pos = vim[i];
		if(i < pos){
			ans += (1000*(pos-i)-num[i]*(pos-i)-(sum[pos-1]-sum[i-1]));
			ans += (sum[n]-sum[pos-1]+num[i]*(n-pos+1)-1000*(n-pos+1));
		}
		else 
			ans += (sum[n]-sum[i-1]+num[i]*(n-i+1)-1000*(n-i+1));

 

代码如下
 

#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 1e6+10;
int t, n, m;
int num[N];
int sum[N];
int vim[N];
ll ans;
void solve(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)scanf("%d",&num[i]);
	sort(num+1,num+n+1);
	for(int i = 1;i <= n;i++){
		sum[i] = sum[i-1]+num[i];
		vim[i] = lower_bound(num+1,num+n+1,1000-num[i])-(num);
		// cout< 
J小朋友做游戏 

 
分析+代码 

根据出题人的做法：先将两种小朋友的幸福度分别按从大到小排序，记为
    
     
      
       
        A
       
      
      
       A
      
     
    A和
    
     
      
       
        B
       
      
      
       B
      
     
    B数组，那么最优的方案一定是从
    
     
      
       
        A
       
      
      
       A
      
     
    A和
    
     
      
       
        B
       
      
      
       B
      
     
    B中各选一个前缀，因此可以求出两个数组的前缀和，然后枚举从
    
     
      
       
        A
       
      
      
       A
      
     
    A中选了多少人（从
    
     
      
       
        B
       
      
      
       B
      
     
    B中选的人数等于总人数减去
    
     
      
       
        A
       
      
      
       A
      
     
    A中的），利用前缀和
    
     
      
       
        푂
       
       
        (
       
       
        1
       
       
        )
       
      
      
       푂(1)
      
     
    O(1)的获得此时的总幸福度，对于圆圈紧挨着的限制，其实就相当于限制闹腾小朋友最多选
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       frac{n}{2}
      
     
    2n​个，在上面枚举的时候加入该限制即可；
 我的做法略显复杂，不过也是类似于如此。
 直接上代码了。
 

#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 1e4+10;
int t, a, b, n, m;
int ans;
int va[N], vb[N];
bool cmp(int x, int y){
	return x > y;
}
void solve(){
	cin>>t;
	while(t--){
		memset(va,0,sizeof(va));
		memset(vb,0,sizeof(vb));
		ans = 0;
		cin>>a>>b>>n;
		for(int i = 1;i <= a;i++)cin>>va[i];
		for(int i = 1;i <= b;i++)cin>>vb[i];
		sort(va+1,va+a+1,cmp);sort(vb+1,vb+b+1,cmp);
		if((n%2==1&&a<=n/2)||(n%2==0&&a n/2){
				ans += va[ta++];
			}
			else{
				if(va[ta] 

出题人做法
 

#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define mem(s,i) memset(s,i,sizeof(s))
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 1e4+10;
const int mod = 1e9+7;
int t, n, m, ans;
int A[N], B[N];
bool cmp(int x, int y){
	return x > y;
}
void solve(){
	cin>>t;
	while(t--){
		mem(A,0), mem(B,0);
		int a, b, x;
		cin>>a>>b>>x;
		for(int i = 1;i <= a;i++)cin>>A[i];
		for(int i = 1;i <= b;i++)cin>>B[i];
		sort(A+1,A+a+1,cmp);sort(B+1,B+b+1,cmp);
		for(int i = 1;i <= a;i++)A[i] += A[i-1];
		for(int i = 1;i <= b;i++)B[i] += B[i-1];
		ans = -1;
		for(int i = 1;i <= x;i++){
			int ta = i, tb = x-i;
			if(ta<=a&&tb<=b&&tb<=x/2)
				ans = max(ans,A[ta]+B[tb]);
		}cout<
 
F中位数切分 


 这个题有两种方法，一个是找规律简单做法，一个是用树状数组+离散化+DP的做法，我只会简单的，所以就用简单做法了。
 简单做法就是找规律，规律每个人找的可能不一样。就不多说了，直接上代码了。
 

#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 1e5+10;
int t, n, m;
int num[N];
void solve(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i = 1;i <= n;i++)scanf("%d",&num[i]);
		sort(num+1,num+n+1);
		int pos = lower_bound(num+1,num+n+1,m)-num;
		// cout< (n/2+n%2)){
			printf("-1n");
		}
		else{
			printf("%dn",n-pos*2+2);
		}
	}
}
int main(){
	solve();
	return 0;
}

 
A九小时九个人九扇门 

 
分析加代码 


     
      
       
        
         D
        
        
         P
        
       
       
        DP
       
      
     DP的一道题，当时没写起，赛后补上的。
 我们需要知道，一个数的数字根等于这个数对
     
      
       
        
         9
        
       
       
        9
       
      
     9取模的结果，特别的。取模为
     
      
       
        
         0
        
       
       
        0
       
      
     0那么数字根为
     
      
       
        
         9
        
       
       
        9
       
      
     9。
 我们就可以将问题转化为从
     
      
       
        
         n
        
       
       
        n
       
      
     n个数中取出一些数字，让这些数字的和对
     
      
       
        
         9
        
       
       
        9
       
      
     9取模得
     
      
       
        
         0
        
        
         ,
        
        
         1
        
        
         ,
        
        
         2
        
        
         ,
        
        
         3
        
        
         ,
        
        
         4
        
        
         ,
        
        
         5
        
        
         ,
        
        
         6
        
        
         ,
        
        
         7
        
        
         ,
        
        
         8
        
       
       
        0,1,2,3,4,5,6,7,8
       
      
     0,1,2,3,4,5,6,7,8有多少种选法。这个时候我们就想到
     
      
       
        
         01
        
        
         背
        
        
         包
        
       
       
        01背包
       
      
     01背包类型的
     
      
       
        
         D
        
        
         P
        
       
       
        DP
       
      
     DP问题了，我们定义一个
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         j
        
        
         ]
        
       
       
        dp[i][j]
       
      
     dp[i][j]表示在我们考虑了前
     
      
       
        
         i
        
       
       
        i
       
      
     i个数，选择一些数使得求和对
     
      
       
        
         9
        
       
       
        9
       
      
     9取模的
     
      
       
        
         j
        
       
       
        j
       
      
     j的方案数。
 重点是状态转移方程，如下所示。 

			m = (j+num[i])%9;
			ans[i][m] = ans[i-1][m];
			ans[i][m] += ans[i-1][j];
			ans[i][m] %= mod;

 

代码
 

#include
#include
#include
#include
#include
#include
#define ll long long
#define PII pair
#define INF 0x7fffffff
using namespace std;
const int N = 1e5+10;
const int mod = 998244353;
int t, n, m;
int num[N];
int ans[N][15];
void solve(){
	cin>>n;
	for(int i = 1;i <= n;i++)cin>>num[i], num[i]%=9;
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < 9;j++){
			m = (j+num[i])%9;
			ans[i][m] = ans[i-1][m];
			ans[i][m] += ans[i-1][j];
			ans[i][m] %= mod;
		}
		ans[i][num[i]]++;
	}
	for(int i = 1;i <= 9;i++)cout<
 

暂时补题到这，后续会继续更新。
 希望下次再接再厉！
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714594.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
江阴一中 江阴一中 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-18

发表评论

登录后才能评论

评论列表（0条）

保存