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

2022牛客寒假算法基础集训营1（A/C/F/H)

DEIJL传送门

A-九小时九个人九扇门 题意

给定 n n n 个数字，求取出若干个数字之和的数字根（各个位的数字相加直到小于 10 10 10 为止）等于 1 1 1~ 9 9 9 的组合方法数。

容易发现对于任一数字，其数字根与 + 9 的 倍 数 +9的倍数 +9的倍数 的数字根相同，即 5 = 14 = 23 5=14=23 5=14=23 ，由此可以反推任一数字的数字根即为对 9 9 9 取模（ 余数为 0 0 0 时数字根即为 9 9 9 ）。变形套入 d p dp dp 即可。

参考代码

#include 
#define int long long
using namespace std;
const int N=1e5+10;
const int mod=998244353;
int n,a[N];
int f[N][10];

int count(int x){
	x=x%9;
    if(x==0)
        x=9;
    return x;
}

int get(int x,int y){
	x=count(x);
	y-=x;
	if(y>10)
		y-=10;
	if(y<0)
		return y+=9;
	else 
		return y;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    f[0][0]=1;
    for(int i=1;i<=n;i++){
    	for(int j=0;j<=9;j++){
    		f[i][j]=(f[i][j]+f[i-1][j])%mod;
    		f[i][count(a[i]+j)]=(f[i][count(a[i]+j)]+f[i-1][j])%mod;
		}
	}
	for(int i=1;i<=9;i++)
		cout< 
C-Baby’s first attempt on CPU 
题意 
在若干条可能存在前后顺序的语句中需要插入空白语句，使得存在前后顺序的语句之间至少存在 
    
     
      
       
        3
       
      
      
       3
      
     
    3 条语句的间隔，求符合要求时需要插入的最少空白语句数目。
 
模拟，采用 
    
     
      
       
        f
       
       
        [
       
       
        写
       
       
        入
       
       
        ]
       
       
        [
       
       
        对
       
       
        应
       
       
        读
       
       
        出
       
       
        ]
       
      
      
       f[写入][对应读出]
      
     
    f[写入][对应读出] 数组使得顺序遍历时能够找到写入语句对应的读出语句的位置，并添加对应的空白语句，同时通过前缀和计算两条语句中间插入的空白语句数目。
 
参考代码 
#include 
#define int long long
using namespace std;

const int N = 110;
int a[N][3];
int f[N][N];
int d[N],s[N];
int n,res,len,id;
inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=3;j++){
            cin>>a[i][j];
            if(a[i][j])
                f[i-j][i]=1;
        }
        
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++)s[j]=0;
    	for(int j=1;j<=n;j++)s[j]=s[j-1]+d[j];//s为d的前缀和 
        id=0;
        for(int j=1;j<=3;j++)
            if(f[i][i+j]){
				id=i+j; 
				break;
			}
        if(id==0) continue;
        res=s[id]-s[i];
    	len=id-i-1;
    	len+=res;
        if(len>=3) continue;
        len=3-len;
        if(id==i+3) {
            if(f[i+1][i+2]&&d[i+2]<3) {
                int shiji=min(len,3-d[i+2]);
        		d[i+2]+=shiji;
        		d[i+3]+=len-shiji;
            }
			else
                d[i+3]+=len;
        }
		else
            d[id]+=len;
    }
    for(int i=1;i<=n;i++)d[i]+=d[i-1];
    cout< 
F-中位数切分 
题意 
给定一个数组，要求划分为若干段，且每段的中位数都大于等于 
    
     
      
       
        m
       
      
      
       m
      
     
    m ，求最多段数。
 
难以置信！是连数组都不需要的结论题。统计大于等于 
    
     
      
       
        m
       
      
      
       m
      
     
    m 及小于 
    
     
      
       
        m
       
      
      
       m
      
     
    m 的数字个数，进行比较即可。由于需要贪最多的划分段，因此在保证其他小元素均能满足中位数要求的情况下，大于等于 
    
     
      
       
        m
       
      
      
       m
      
     
    m 的都将被划分为单独的一段。
 
参考代码 
#include
#define int long long
using namespace std;
const int N=1e5+10;

inline void solve(){
	int n,m,x;
	int ans=0;
	int s1=0,s0=0;
	cin>>n>>m;
	for(int i=0;i>x;
		if(x>=m)
			s1++;
		else 
			s0++;
	}
	if(s0>=s1){
		cout<<"-1"<>t;
	while(t--){
		solve();
	}
	return 0;
}
 
H-牛牛看云 
题意 
给定 
    
     
      
       
        n
       
      
      
       n
      
     
    n 个元素，求元素间两两（包括和自身）相加后与 
    
     
      
       
        1000
       
      
      
       1000
      
     
    1000 的差值的绝对值的加和。
 
二分+前缀和的方法， 与 
    
     
      
       
        1000
       
      
      
       1000
      
     
    1000 的差值可以分摊到两个元素的加和中，因此可以在读入的时候将所有元素都进行 
    
     
      
       
        −
       
       
        500
       
      
      
       -500
      
     
    −500 处理，同时累计自身贡献。
 
排序后，任意两个不同元素的加和可能出现两种情况：大于等于 
    
     
      
       
        0
       
      
      
       0
      
     
    0，或小于 
    
     
      
       
        0
       
      
      
       0
      
     
    0。因此可通过二分其相反数的位置进行分类，并根据符号的不同对 
    
     
      
       
        a
       
       
        [
       
       
        i
       
       
        ]
       
      
      
       a[i]
      
     
    a[i] 和前缀和的贡献做相应处理。
 
参考代码 
#include
#define int long long
using namespace std;
const int N=1000005;
int n;
int a[N],ans[N];
int sum,tt;

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){//自身贡献
		cin>>a[i];
		a[i]-=500;
        tt+=abs(2*a[i]);
	}
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        ans[i]=ans[i-1]+a[i];
	for(int i=1;i<=n;i++){
		int lower=lower_bound(a+1,a+n+1,-a[i])-a;
		sum+=(n-lower+1)*a[i]+ans[n]-ans[lower-1]-(lower-1)*a[i]-ans[lower-1];
	}
	cout<<(sum+tt)/2<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5713639.html