牛客2020跨年場

前言

CF的跨年場我也打了，
Good Bye 2020
題解在我的個人 b l o g blog blog，

傳送門

牛客跨年場打了一會兒，就和室友一起吃 k f c kfc kfc看晚會，后來切了個A題，哈哈，

題解

A.關于元旦的冷/熱知識

有趣的歷史題， w a wa wa了好多發才過，事實證明百度不可靠，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int main(){int s=0;
      printf("D\n");//1
            printf("ABCD\n"); //2
            printf("D\n");//3
            printf("A\n");//4
            printf("ABC\n");//5
            printf("C\n");//6
            printf("B\n");//7
            printf("C\n");//8
            printf("D\n");//9
            printf("D\n");//10
            printf("A\n");//11
            printf("C\n");//12
            printf("C\n");//13
            printf("D\n");//14
            printf("AD\n");//15
  
	return 0;
}

B.牛牛想起飛

經典 d p dp dp問題，比較水，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int dp[N][105],n,a[N],b[N];
int main(){
    int y;scanf("%d%d",&n,&y);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    //for(int i=0;i<y;i++) dp[0][i]=1;
    dp[1][a[1]%y]=dp[1][((a[1]-b[1])%y+y)%y]=dp[1][((a[1]+b[1])%y+y)%y]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<y;j++){
            dp[i][j]|=(dp[i-1][((j-a[i])%y+y)%y]);
            dp[i][j]|=(dp[i-1][((j-(a[i]+b[i]))%y+y)%y]);
            dp[i][j]|=(dp[i-1][((j-(a[i]-b[i]))%y+y)%y]);
        }
        
    }
    for(int i=y-1;~i;i--){
        if(dp[n][i]){
            printf("%d\n",i);
            return 0;
        }
    }
	return 0;
}

C.最小互質數

如果沒有1，直接輸出1，否則歐拉篩一波，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+100,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n;
unordered_map<int,int>mp;
map<int,int>b;
bool a[N];
int p[N],cnt;
void Ess(int n){
	 memset(a,true,sizeof(a));
	 for(int i=2;i<=n;i++)
	 {
	 	if(a[i]) p[cnt++]=i;
	 	for(int j=0;j<cnt&&i*p[j]<=n;j++)
	 	{
	 		a[i*p[j]]=false;
	 		if(i%p[j]==0) break; 
		}
	 } 
} 

int main(){
    cin>>n;
    Ess(N-5);
    for(int i=1,x;i<=n;i++){
        cin>>x,mp[x]=1;
        for(int j=2;j*j<=x;j++){
            while(x%j==0){
                b[j]=1,x/=j;
            }
        }
        if(x>1) b[x]=1;
    }
    if(!mp[1]){
        return puts("1"),0;
    }
    else {
        for(int i=0;i<cnt;i++){
            if(!mp[p[i]]&&!b[p[i]]){
                cout<<p[i]<<endl;
                return 0;
            }
        }
    }
	return 0;
}

H.牛清楚的裙子!!!

考試時不會，題解看懂了，

令 d p [ i ] dp[i] dp[i]表示已經穿過 i i i種裙子后，還需要穿多少次裙子才能到達穿 n n n種裙子，

有： d p [ i ] = i n d p [ i ] + n ? i n d p [ i + 1 ] + 1 dp[i]=\dfrac{i}{n}dp[i]+\dfrac{n-i}{n}dp[i+1]+1 dp[i]=ni?dp[i]+nn?i?dp[i+1]+1，

解釋一下： i n d p [ i ] \dfrac{i}{n}dp[i] ni?dp[i] 就是有 i n \dfrac{i}{n} ni?的概率這一次穿的是之前穿過的裙子，同理有 n ? i n \dfrac{n-i}{n} nn?i?的概率穿的是沒穿過的裙子， + 1 +1 +1是因為無論是穿沒穿過的，還是穿了出穿過的，穿的次數都加1了，

化簡： d p [ i ] = d p [ i + 1 ] + n n ? i dp[i]=dp[i+1]+\dfrac{n}{n-i} dp[i]=dp[i+1]+n?in?

d p [ 0 ] = ∑ i = 0 n ? 1 n n ? i dp[0]=\sum\limits_{i=0}^{n-1}\dfrac{n}{n-i} dp[0]=i=0∑n?1?n?in?，

又因為每條裙子沒有差異，所以對于每一條裙子的期望是： ∑ i = 0 n ? i 1 n ? i \sum\limits_{i=0}^{n-i}\dfrac{1}{n-i} i=0∑n?i?n?i1?，

然后就可以預處理調和級數，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int t;
double dp[N];
int main(){
    scanf("%d",&t);for(int i=1;i<=N-5;i++) dp[i]=dp[i-1]+(double)1.0/i;
    while(t--){int n;
        scanf("%d",&n);
       double ans=(n-1)*dp[n]+dp[n]*10000.0;
       printf("%.7f\n",ans);
    }
	return 0;
}

其他有時間待補 … … \dots\dots ……