百度之星

HDU4823

代码：

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

#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
const int N=100010;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,int b){ll ans=1;while(b){if(b&1) ans=ans*a;a*=a;b>>=1;}return ans;}

ll n,m,v,k; 

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>n>>m>>v>>k;
        int ans=0;
        if(m>=n){
            cout<<0<<endl;
            continue;
        }
        else{
            while(m<n){
                ll tmp=(m-v)*k;
                if(tmp>m){
                    ans++;
                    m=tmp;
                }
                else{
                    ans=-1;
                    break;
                }
            }
            cout<<ans<<endl;
        }
    }
}

HDU6743

#include<bits/stdc++.h>
using namespace std;
const int N=100010;

struct node{
    int x,y;
    int ans;
}a[N];

bool cmp(node a,node b){
    return a.ans<b.ans;
} 
int main(){
    int n,m;
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<n;i++) {
            cin>>a[i].x>>a[i].y;
            int tt=m/a[i].x;
            if(tt*a[i].x!=m) ++tt;//要避免除0，RE
            a[i].ans=tt*a[i].y;
        }
        sort(a,a+n,cmp);
        cout<<a[0].ans<<endl;
    }
}

HDU6744

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

int score[] {95, 90, 85, 80, 75, 70, 67, 65, 62, 60, 0};
double point[] {4.3, 4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7, 1.0, 0};

int main()
{
    int test;
    cin>>test;
    while(test--){
        int x; cin>>x; double ans=0;
        for(int i=0; i<11; i++)
            for(int j=0; j<11; j++)
                for(int k=0; k<11; k++)
                    for(int t=0; t<11; t++)
                        if(score[i]+score[j]+score[k]+score[t]<=x)
                            ans=max(ans, point[i]+point[j]+point[k]+point[t]);

        printf("%.1lf\n", ans);
    }

    return 0;
}

HDU6745

题目描述：

一开始没看出来是DP，一脸懵逼,如果知道是DP的话就好做了，只需要判断当前的状态两个是否是互质，是的话就+1，不是的话就取前一状态的最大值。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a,b,dp[N][N];
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    //ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=1000;j++){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+(gcd(i,j)==1);
        }
    }
    int n,m;
    int t;
    scanf("%d",&t);//要用更快的输入输出方式，用cin关同步都会超时。
    while(t--){
        scanf("%d%d",&a,&b);
        printf("%d\n",dp[a][b]);
    }
}