3.4

A

A
只能购买2的次方数的纸张，而他最大可以购买n大小的纸张
也就是求小于n的最大二次方数

#include<bits/stdc++.h>
using namespace std;

int main(){
    int x;
    cin>>x;
    int d=(int)log2(x);
    cout<<pow(2,d);
    return 0;
}

B

B
已知她最多可以吃多少糖，再给出每一个巧克力的含糖量，求她最多可以吃多少巧克力
直接排序即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110],b[1010],c[1010];

int32_t main(){
    int n,s,d,sum=0;
    cin>>n;
    cin>>s;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum>s) {
            d=i;
            break;
        }
    }
    cout<<d-1<<endl;
    return 0;
}

C

C
已知圆心坐标和半径，再给n个点的坐标，求有多少个点在圆内
使用\(x^2\)+\(y^2\)<=\(r^2\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110],b[1010],c[1010];

int32_t main(){
    int n,cx,cy,r,x,y,ans=0;
    cin>>n>>cx>>cy>>r;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&x,&y);
        if((x-cx)*(x-cx)+(y-cy)*(y-cy)<=r*r)
            ans++;

    }
    cout<<ans<<endl;
    return 0;
}

D

D
这道题赛时没做出来，以为是个思维题，一直在找规律，补题发现是dp。题意是给你一串只由T和C组成的字符串，将它分成T，C，TC，CC的小段，有多少种分法。其实这个题可以发现他只分成长度为一的和长度为二的字符串，那么其中一位下标就可以存为当前这一位前面还有几个字母没有组合，只能为0和1，另一位下标存当前在哪一位，然后分情况讨论，如果当前这一位是T,那无论前一位有没有字母没有组合，它都不能和之前组，只能自己一组，或者自己和后面组,dp[x][1]=0;如果是C，无论前面是哪个字母都可以组，所以只要前一位是被单独留下的即可，想要被单独留下，那前一位的前面不能留下字母，dp[x][i]=dp[i-1][0],而他俩前面不留字母的情况是完全一样的，任何情况都可以，不论前面留不留字母，他都可以单独dp[x][0]=d[x-1[0]+dp[x-1][1]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[1000010][2];
int32_t main(){
    int mod=1e9+7;
    string s;
    cin>>s;
    int n=s.length();
    f[0][0]=1;
    f[0][1]=0;
    for(int i=1;i<s.length();i++){
        if(s[i]=='T'){
            f[i][0]=(f[i-1][0]+f[i-1][1])%mod;
            f[i][1]=0;
        }
        else{
            f[i][0]=(f[i-1][0]+f[i-1][1])%mod;
            f[i][1]=f[i-1][0];
        }
    }
    cout<<(f[n-1][0]+f[n-1][1])%mod<<endl;
    return 0;
}

E

E
这一天共召开n场会议，每一次会议都会提供a,b,c个idea，他不能连着开两场会议，怎么安排会议可以解决最多的idea，首先每一次开会处理的idea一定是三个数中的最大值。在选择的时候可以选他的x+2或x+3场，当选择x+4时，可以选完x+2再选是更优的情况。递推表达式就是dp[i]=max(dp[i-2],dp[i-3])+a[i];这里注意最后一场会议有可能是倒数第二场，输出结果应该是max(dp[n],dp[n-1]

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1010],b[1010],c[1010],d[1010],s1[1010],s2[1010],dp[1010];

int32_t main(){
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&c[i]);
        d[i]=max(max(a[i],b[i]),c[i]);
        //cout<<i<<" "<<d[i]<<endl;
    }
    if(n==1){
        cout<<d[1]<<endl;
        return 0;
    }
    else if(n==2){
        cout<<max(d[1],d[2])<<endl;
        return 0;
    }
    dp[1]=d[1];
    dp[2]=d[2];
    for(int i=3;i<=n;i++){
        dp[i]=max(dp[i-2]+d[i],dp[i-3]+d[i]);
    }
    cout<<max(dp[n],dp[n-1])<<endl;
    return 0;
}

F

F
这道题为多组数据，每组提供b,l，求这两个数的gcd并把它分解质因数，注意每一组数据输出后面都有一行0

#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
    int T,b,l;
    cin>>T;
    while(T--){
        cin>>b>>l;
        int x=__gcd(b,l);
        int y=sqrt(x);
        for(int i=2;i<=y;i++){
            int ans=0;
            while(1){
                if(x%i!=0)
                    break;
                else
                    x/=i,ans++;
                //cout<<x<<" "<<i<<" "<<ans<<endl;
            }
            if(ans!=0)
            cout<<i<<" "<<ans<<"\n";
        }
        if(x>1)
            cout<<x<<" 1\n";
        cout<<0<<"\n";
    }
    return 0;
}