1.今天考了一个考试。

分数235/300分。

A[暴力]

题意:队伍两两之间互相比赛,赢3分,平1分,负0分 问有多少种可能

观察数据范围n<=5

所以最多进行5*(5-1)/2=10场比赛

最多只有3^10种可能

直接暴力即可

#include<cstdio>

int p3[10][10][10],p4[10][10][10][10],p5[20][20][20][20][20];
int n,a,b,c,d,e;

inline void dfs3(int k,int n,int a,int b,int c){
    if (k==n){
        p3[a][b][c]++;
        return;
    }
    if (k==0){
        dfs3(1,n,a+3,b,c);
        dfs3(1,n,a+1,b+1,c);
        dfs3(1,n,a,b+3,c);
    }
    if (k==1){
        dfs3(2,n,a,b+3,c);
        dfs3(2,n,a,b+1,c+1);
        dfs3(2,n,a,b,c+3);
    }
    if (k==2){
        dfs3(3,n,a,b,c+3);
        dfs3(3,n,a+1,b,c+1);
        dfs3(3,n,a+3,b,c);
    }
}

inline void dfs4(int k,int n,int a,int b,int c,int d){
    if (k==n){
        p4[a][b][c][d]++;
        return;
    }
    else if (k==0){
        dfs4(k+1,n,a+3,b,c,d);
        dfs4(k+1,n,a+1,b+1,c,d);
        dfs4(k+1,n,a,b+3,c,d);
    }
    else if (k==1){
        dfs4(k+1,n,a+3,b,c,d);
        dfs4(k+1,n,a+1,b,c+1,d);
        dfs4(k+1,n,a,b,c+3,d);
    }
    else if (k==2){
        dfs4(k+1,n,a,b+3,c,d);
        dfs4(k+1,n,a,b+1,c+1,d);
        dfs4(k+1,n,a,b,c+3,d);
    }
    else if (k==3){
        dfs4(k+1,n,a+3,b,c,d);
        dfs4(k+1,n,a+1,b,c,d+1);
        dfs4(k+1,n,a,b,c,d+3);
    }
    else if (k==4){
        dfs4(k+1,n,a,b+3,c,d);
        dfs4(k+1,n,a,b+1,c,d+1);
        dfs4(k+1,n,a,b,c,d+3);
    }
    else if (k==5){
        dfs4(k+1,n,a,b,c+3,d);
        dfs4(k+1,n,a,b,c+1,d+1);
        dfs4(k+1,n,a,b,c,d+3);
    }
}

inline void dfs5(int k,int n,int a,int b,int c,int d,int e){
    if (k==n){
        p5[a][b][c][d][e]++;
        //printf("%d %d %d %d %d\n",a,b,c,d,e);
        return;
    }
    else if (k==0){
        dfs5(k+1,n,a+3,b,c,d,e);
        dfs5(k+1,n,a+1,b+1,c,d,e);
        dfs5(k+1,n,a,b+3,c,d,e);
    }
    else if (k==1){
        dfs5(k+1,n,a+3,b,c,d,e);
        dfs5(k+1,n,a+1,b,c+1,d,e);
        dfs5(k+1,n,a,b,c+3,d,e);
    }
    else if (k==2){
        dfs5(k+1,n,a,b+3,c,d,e);
        dfs5(k+1,n,a,b+1,c+1,d,e);
        dfs5(k+1,n,a,b,c+3,d,e);
    }
    else if (k==3){
        dfs5(k+1,n,a+3,b,c,d,e);
        dfs5(k+1,n,a+1,b,c,d+1,e);
        dfs5(k+1,n,a,b,c,d+3,e);
    }
    else if (k==4){
        dfs5(k+1,n,a,b+3,c,d,e);
        dfs5(k+1,n,a,b+1,c,d+1,e);
        dfs5(k+1,n,a,b,c,d+3,e);
    }
    else if (k==5){
        dfs5(k+1,n,a,b,c+3,d,e);
        dfs5(k+1,n,a,b,c+1,d+1,e);
        dfs5(k+1,n,a,b,c,d+3,e);
    }
    else if (k==6){
        dfs5(k+1,n,a+3,b,c,d,e);
        dfs5(k+1,n,a+1,b,c,d,e+1);
        dfs5(k+1,n,a,b,c,d,e+3);
    }
    else if (k==7){
        dfs5(k+1,n,a,b+3,c,d,e);
        dfs5(k+1,n,a,b+1,c,d,e+1);
        dfs5(k+1,n,a,b,c,d,e+3);
    }
    else if (k==8){
        dfs5(k+1,n,a,b,c+3,d,e);
        dfs5(k+1,n,a,b,c+1,d,e+1);
        dfs5(k+1,n,a,b,c,d,e+3);
    }
    else if (k==9){
        dfs5(k+1,n,a,b,c,d+3,e);
        dfs5(k+1,n,a,b,c,d+1,e+1);
        dfs5(k+1,n,a,b,c,d,e+3);
    }
}

int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    scanf("%d",&n);
    if (n==2){
        scanf("%d%d",&a,&b);
        if (a==3&&b==0||a==1&&b==1||a==0&&b==3) printf("1\n");
        else printf("0\n");
        return 0;
    }
    else{
        if (n==3) dfs3(0,3,0,0,0);
        if (n==4) dfs4(0,6,0,0,0,0);
        if (n==5) dfs5(0,10,0,0,0,0,0);
        scanf("%d%d%d",&a,&b,&c);
        if (n>=4) scanf("%d",&d);
        if (n==5) scanf("%d",&e);
        if (n==3){
            if (a>6||b>6||c>6) printf("0\n");
            else printf("%d\n",p3[a][b][c]);
            return 0;
        }
        else if (n==4){
            if (a>9||b>9||c>9||d>9) printf("0\n");
            else printf("%d\n",p4[a][b][c][d]);
            return 0;
        }
        else{
            if (a>12||b>12||c>12||d>12||e>12) printf("0\n");
            else printf("%d\n",p5[a][b][c][d][e]);
            return 0;
        }
    }
    return 0;
}

这个题非常水,所以我就拿了全分。然后非常皮的写了150行

B[贪心]

题意:给你一个01数组初始状态,问能否在10步内求得目标状态

我们从0的角度出发

因为0只有一种移动方式

就是在旁边有1的情况才能移动,并且只能与这个1相连的1交换。

所以0的顺序并不会调换

这样我们就可以对每个0最终处于哪个位置进行标记

首先我们知道总有一个0通过一步是可以直接到目标点的

然后这个到达目标点后,一定会有更多的能够到达位置

所以每个0到达目标位置总需要1或0步

这时我们再判断那些点的位置等于他本身就行了。

#include<cstdio>
int n,a,b,num0,num[30],ans;
int main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a);
        if (a==0) num[++num0]=i;
    }
    ans=num0; num0=0;
    for (int i=1;i<=n;i++){
        scanf("%d",&b);
        if (b==0)
            if (num[++num0]==i) ans--;
    }
    if (ans<=10) printf("%d\n",ans);
    else puts("QAQ");
    return 0;
}

这个题虽然有点考思维,但也很水,所以也拿了全分。

C[二分答案+贪心]

题意:给你n个数,让你每次从中选出m个数组成一个序列,且其中后一项永远大于等于前一项的2倍,每个数只能选一次,问最多可以抠出几个序列

这个题发现答案可以二分

然后贪心

每次找出最小的序列取出

贪心是一定可行的

最后输出可行结果即可

#include<cstdio>
#include<algorithm>
using namespace std;

long long n,m,a[100010],b[100010],ans;

inline long long v_in(){
    char ch=getchar();
    long long sum=0;
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9'){
        sum=(sum<<3)+(sum<<1)+(ch^48);
        ch=getchar();
    }
    return sum;
}

inline bool judge(long long k){
    for (long long i=0;i<k;i++) b[i]=0;
    long long i=0,j=0,t=0;
    while (i<k*m){
        t++;
        while (t<=n&&a[t]<2*b[j]) t++;
        if (t>n) return false;
        b[j]=a[t];
        i++;
        if (j==k-1) j=0;
        else j++;
    }
    return true;
}

int main(){
    freopen("C.in","r",stdin);
    freopen("C.out","w",stdout);
    n=v_in();
    m=v_in();
    for (register long long i=1;i<=n;i++) a[i]=v_in();
    sort(a+1,a+n+1);
    long long l=0,r=n/m;
    while (l<=r){
        long long mid=(l+r)>>1;
        if (judge(mid)){
            ans=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    printf("%lld\n",ans);
    return 0;
}

这个题本身我只想骗个n/m的分,结果骗到了35分。

总的来说,自己其实并不是很满意,最后一题该想的没有想到。

2.月考是真的爆炸

我都有种想冲国家队逃避高考的冲动了。

3.今天是平安夜

希望自己的愿望能够实现吧。

4.月考结束了。

我也要开始看内容了。

首先把上个星期的暴搜看完

然后:

1.CDQ分治

2.SG函数

3.Link-Cut Tree

4.搜索剪枝(A-star,IDA-star等)

5.数论知识