牛客網 OI 賽制測試賽

比賽連結：​​這裡寫連結内容​​​ A 斐波那契

連結：https://www.nowcoder.com/acm/contest/181/A

設f[i]表示斐波那契數論的第i項

f[1]=1,f[2] =1,f[i] = f[i - 1] + f[i - 2]

給定一個n

求

附題解

#include<iostream>
#include<cstdio>
using namespace std;
 
int main(){
    string str;
    cin>>str;
    int len=str.length();
    if((str[len-1]-'0')%2==0){
        printf("1\n");
    }
    else{
        printf("-1\n");
    }
}      

B 就不放了

C 序列

連結：https://www.nowcoder.com/acm/contest/181/C

小a有n個數，他想把他們劃分為連續的權值相等的k段，但他不知道這是否可行。

每個數都必須被劃分

這個問題對他來說太難了，于是他把這個問題丢給了你。

首先要滿足的要求肯定是總和sum%k是否等于0，然後暴力枚舉，有k個就行（在總和是k的倍數的情況下）

k = 0;
        for(int j = 1; j <= N; j++) {
            cur += a[j];
            if(cur == sum / i)  cur=0,k++;
        }
        ans[i] =  (k == i);      

但是二分的方法更有前途

這裡貼一位大佬（牛客網流木）的二分

#include<bits/stdc++.h>
const int M=1000005;
 
typedef long long ll;
using namespace std;
ll a[M];
int n,q;
 
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
    while(q--){
        ll x;
        scanf("%lld",&x);
        if(a[n]%x)puts("No");
        else{
            int f=1;
            for(int i=1;i<=x-1;i++){
                int w=lower_bound(a+1,a+n+1,i*a[n]/x)-a;
   
                if(a[w]!=i*a[n]/x){f=0;puts("No");break;}
            }
            if(f)puts("Yes");
        }
    }
    return 0;
}      

D 小葉的巡查

就是一道樹的直徑題，開始把樹的直徑看錯了，沒敢寫

樹的直徑就是雙重dfs ,這題小心資料int會爆掉

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100001;
struct node{
    int to,next,w;
     
}edge[MAXN];
int head[MAXN];
int num;
int n,m;
typedef long long ll;
void add_edge(int u,int v,int w){
    edge[++num].next=head[u];
    edge[num].to=v;
    edge[num].w=w;
    head[u]=num;
     
}
int dp[MAXN];
ll ans=0;
int ed=0;
void dfs(int u,int fa,ll now)
{
    if(now>ans)
    {
        ans=now;
        ed=u;
    }
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(edge[i].to!=fa)
            dfs(edge[i].to,u,now+edge[i].w);
    }
}
int main(){
     
     scanf("%d",&n);
     memset(head,-1,sizeof(head));
     for(int i=1;i<n;i++)
     {
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         add_edge(u,v,w);
         add_edge(v,u,w);
     }
     dfs(1,0,0);
     dfs(ed,0,0);
     printf("%lld",ans*10+(1+ans)*ans/2);
    return 0;
}      

E 旅行青蛙

最長不下降子序列的裸題

開始我寫的是最長上升子序列，沒看清題目，納尼。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=23333+10;
int dp[N],a[N];
 
int binarysearch(int k,int len){
    int l=0,r=len-1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(k<dp[mid]) {
            r=mid-1;
        } else {
            l=mid+1;
        }
    }
    return l;
}
int main() {
    int n,len;
    scanf("%d",&n);
     
    for(int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    len=0;
    for(int i=0;i<n;i++){
        int t=binarysearch(a[i],len);
        if(t>=len) len++;
        dp[t]=a[i];
    }
     printf("%d\n",len);
}      

測試賽果然良心，除了F題，其他的都一眼可以看出解法，嗯，（敲碼另說）嗚嗚嗚嗚

最後一題放一下題解，和大佬的代碼記錄一下吧，

貼的是牛客網applese大佬的代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int mod=1e9+7;
namespace {
    inline int Add(const int &x,const int &y,const int &p) {
        int res=x+y;
        if(res>=p)
            res-=p;
        return res;
    }
    inline int Sub(const int &x,const int &y,const int &p) {
        int res=x-y;
        if(res<0)
            res+=p;
        return res;
    }
    inline int Mul(const int &x,const int &y,const int &p) {
        return 1ll*x*y%p;
    }
    inline int Pow(int x,int y,const int &p) {
        int res=1;
        while(y) {
            if(y&1)
                res=1ll*res*x%p;
            x=1ll*x*x%p;
            y>>=1;
        }
        return res;
    }
}
int T,n,k,val[1005],C[1005][1005];
int main() {
    for(int i=0;i<=1000;++i) {
        C[i][0]=1;
        for(int j=1;j<=i;++j)
            C[i][j]=Add(C[i-1][j-1],C[i-1][j],mod-1);
    }
    read(T);
    while(T--) {
        read(n),read(k);
        for(int i=1;i<=n;++i)
            read(val[i]);
        if(k<=2) {
            puts("1");
            continue;
        }
        sort(val+1,val+n+1);
        int ans=1;
        for(int i=1;i<=n;++i)
            ans=Mul(ans,Pow(val[i],Sub(C[n-1][k-1],Add(C[i-1][k-1],C[n-i][k-1],mod-1),mod-1),mod),mod);
        printf("%d\n",ans);
    }
}