HL DAY6

· · 个人记录

今天 T3SB了

感觉自己考试特别不会分配时间

总是在最后不知道要打那一道题

T210分钟50分可还行

T1：

这题一开始乱搞 莫名其妙过了样例

一开始想排序乱搞 结果一直被自己hack

后来发现正解其实就是枚举公约数

再枚举倍数用桶计数

这样算法复杂度整体是O（Nlogn）级别的

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
inline int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch =getchar();
    }
    return x*f;
} 
int n,k,a[N],buc[N],maxx=0,tot;
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        buc[a[i]]++;
        maxx=max(a[i],maxx);
    }   
//  if(k==1){
//      printf("%d",maxx);
//      return 0;
//  }
    for(int i=maxx;i>=1;i--){
        int cnt=0;
        for(int j=i;j<=maxx;j+=i){
            cnt+=buc[j];
            if(cnt>=k){
                printf("%d",i);
                return 0;
            }
        }
    }
    return 0;
}

T2：

第一眼？

卡特兰数？

？

然后我发现其实50分数据特别小

直接两重DFS

暴力判断

后来想了想正解 没什么大思路

（其实应该往组合数学方面想但是数论没学好）

于是先咕着 去看T3

后来T3过了小样例没过大样例就炸掉了 赶紧刚T2 直接10分钟打完

中间还打错了一步直接无限递归爆栈把exe给炸掉了

后来调了调直接秒掉大（一点）样例

而且也没超时 0.000s

50分到手

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
int m[2001][2001],a,b,c,d;
int dx[2],dy[2],ans;
const int mod=100000007;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
} 
inline void dfs2(int x,int y){
    for(int i=0;i<=1;i++){
        int fx=x+dx[i];
        int fy=y+dy[i];
        if(fx<=a&&fy<=d){
            if(m[fx][fy]==0){
                if(fx==a&&fy==d) {
                ans=(ans+mod+1)%mod;
                }
                else dfs2(fx,fy);
            }
        }
    }   
}
inline void dfs1(int x,int y){
    for(int i=0;i<=1;i++){
        int fx=x+dx[i];
        int fy=y+dy[i];
        if(fx<=a&&fy<=b){
            if((!(fx==c&&fy==0))&&(!(fy==d&&fx==a))){
                m[fx][fy]=1;
                if(fx==a&&fy==b) dfs2(c,0);
                else {
                dfs1(fx,fy);
                m[fx][fy]=0;
                }
            }
        }
    }
}
int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    a=read(),b=read(),c=read(),d=read();
    dx[0]=1;
    dx[1]=0;
    dy[0]=0;
    dy[1]=1;
    dfs1(0,0);
    printf("%d",ans%mod);   
    return 0;
}

正解其实特别SB

就是个组合数学的式子

没办法 组合数学没学好

注意下求阶乘逆元

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e8+7;
const int N=2e5 + 5;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch =getchar();
    }
    return x*f;
} 
int a,b,c,d,f[N],inv[N],ans1,ans2,ans;//f数组表示阶乘 inv数组表示逆元 
inline int pow(int x, int n) {
    if (!n) return 1;

    int  res = pow(x, n >> 1);
    res = res * res % mod;
    if (n & 1) res = res * x % mod;
    return res;
}

signed main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    a=read(),b=read(),c=read(),d=read();
    f[0]=1;
    for(int i=1;i<N;i++){
        f[i]=f[i-1]*i%mod;
    } 
    inv[N-1]=pow(f[N-1],mod-2);
    for(int i=N-1;i>=1;i--){
        inv[i-1]=inv[i]*i%mod;
    }
    ans1=(f[a+b]*inv[a]%mod*inv[b]%mod)*(f[a-c+d]*inv[a-c]%mod*inv[d]%mod)%mod;
     ans2=(f[a+d]*inv[d]%mod*inv[a]%mod)*(f[a-c+b]*inv[a-c]%mod*inv[b]%mod)%mod; 
     ans=ans1-ans2;
    ans=(ans+mod)%mod;
    printf("%lld",ans);
    return 0;

}

T3:

这道题当时考场上直接暴力...

没想到会得到10分

因为只过了小数据

另一个数据 2 1 2 1 2 1 2 1

就被卡了..

但是还是交上去了