首页 > 代码库 > 省赛训练赛(---)

省赛训练赛(---)

A.HDU4968

最大gpa为从最大区间开始,每次取区间最小分数。

最小gap为从最小区间开始,每次取区间最大分数。

技术分享
#include<bits/stdc++.h>
using namespace std;

int ave,n;
int x[10] = {0,85,80,75,70,60};
double xx[10] = {0,4,3.5,3,2.5,2};
int y[10] = {0,69,74,79,84,100};
double yy[10] = {0,2,2.5,3,3.5,4};

int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--)
    {
        cin >> ave >> n;
        double sum1 = 0,sum2 = 0;
        int total = ave*n,now = 1;
        for(int i = 1;i <= n;i++)
        {
            while(total-x[now] < 60*(n-i))  now++;
            total -= x[now];
            sum1 += xx[now];
        }
        total = ave*n,now = 1;
        for(int i = 1;i <= n;i++)
        {
            while(total-y[now] > 100*(n-i)) now++;
            total -= y[now];
            sum2 += yy[now];
        }
        cout << fixed << setprecision(4) << sum2/n << " " << fixed << setprecision(4) << sum1/n << endl;
    }
    return 0;
}
View Code

B.HDU4970

先求每点受的伤害,然后求后缀和。

技术分享
#include<bits/stdc++.h>
using namespace std;

int n,m,k;
long long a[100005],b[100005];

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n && n)
    {
        cin >> m;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i = 1;i <= m;i++)
        {
            int l,r,x;
            cin >> l >> r >> x;
            a[r] += x;
            a[l-1] -= x;
        }
        for(int i = n;i >= 1;i--)
        {
            a[i] += a[i+1];
            b[i] = a[i]+b[i+1];
        }
        cin >> k;
        int ans = 0;
        while(k--)
        {
            long long h,x;
            cin >> h >> x;
            if(h > b[x])    ans++;
        }
        cout << ans << endl;
    }
    return 0;
}
View Code

C.HDU4864

工作和机器都先按时间降序,再按难度降序。

因为时间是降序的,我们从头到尾处理工作,把大于工作时间的机器拿出来,则它们对之后工作的时间都是满足的,每个工作,我们优先处理时间大的工作,因为难度对money的影响可以忽略。

技术分享
#include<bits/stdc++.h>
using namespace std;

int n,m,c[105];
struct xx
{
    int x,y;
    friend bool operator <(xx a,xx b)
    {
        if(a.x != b.x)  return a.x > b.x;
        return a.y > b.y;
    }
}a[100005],b[100005];

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n >> m)
    {
        for(int i = 1;i <= n;i++)   cin >> a[i].x >> a[i].y;
        for(int i = 1;i <= m;i++)   cin >> b[i].x >> b[i].y;
        sort(a+1,a+1+n);
        sort(b+1,b+1+m);
        memset(c,0,sizeof(c));
        int now = 1;
        int cnt = 0;
        long long ans = 0;
        for(int i = 1;i <= m;i++)
        {
            while(now <= n && a[now].x >= b[i].x)
            {
                c[a[now].y]++;
                now++;
            }
            for(int j = b[i].y;j <= 100;j++)
            {
                if(c[j])
                {
                    c[j]--;
                    cnt++;
                    ans += 500*b[i].x+2*b[i].y;
                    break;
                }
            }
        }
        cout << cnt << " " << ans << endl;
    }
    return 0;
}
View Code

D.HDU4866


E.HDU4867


F.HDU4869

不管怎么变,最后0和1的个数奇偶性不变,我们计算出最少的1的个数和最多的1的个数,这个区间内,相隔2都是符合的,因为翻牌是任意的,所以m个数中选i个1是组合数,预处理一下阶乘。

技术分享
#include<bits/stdc++.h>
#define MOD 1000000009
using namespace std;

int n,m;
long long f[100005];
long long qpower(long long a,long long b,long long c)
{
    long long ans = 1;
    a = a%c;
    while(b)
    {
        if(b%2) ans = ans*a%c;
        a = a*a%c;
        b /= 2;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    f[0] = 1;
    for(int i = 1;i <= 100000;i++)  f[i] = f[i-1]*i%MOD;
    while(cin >> n >> m)
    {
        int l = 0,r = 0;
        for(int i = 1;i <= n;i++)
        {
            int x;
            cin >> x;
            int ll = l,rr = r;
            if(x < ll)  l = ll-x;
            else if(x < rr) l = ll%2 == x%2?0:1;
            else    l = x-rr;
            if(x < m-rr)   r = rr+x;
            else if(x < m-ll)  r = (m-rr)%2 == x%2?m:m-1;
            else    r = 2*m-ll-x;
        }
        long long ans = 0;
        for(int i = l;i <= r;i += 2)
        {
            ans = (ans+f[m]*qpower(f[i]*f[m-i],MOD-2,MOD)%MOD)%MOD;
        }
        cout << ans << endl;
    }
    return 0;
}
View Code

G.HDU4960

dp[i][j]代表将区间i-j合并乘回文串的最小花费,递归处理,过程中记忆化一下。

技术分享
#include<bits/stdc++.h>
#define MOD 1000000009
using namespace std;

int n,a[5005],cost[5005],dp[5005][5005];
long long sum[5005];

int dfs(int l,int r)
{
    if(l >= r)  return 0;
    if(dp[l][r] != -1)  return dp[l][r];
    dp[l][r] = cost[r-l+1];
    int ll = l,rr = r;
    while(ll < rr)
    {
        while(ll < rr && sum[ll]-sum[l-1] < sum[r]-sum[rr-1])  ll++;
        while(ll < rr && sum[ll]-sum[l-1] > sum[r]-sum[rr-1])  rr--;
        if(ll < rr && sum[ll]-sum[l-1] == sum[r]-sum[rr-1])
        {
            dp[l][r] = min(dp[l][r],dfs(ll+1,rr-1)+cost[ll-l+1]+cost[r-rr+1]);
            ll++;
        }
    }
    return dp[l][r];
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n && n)
    {
        memset(sum,0,sizeof(sum));
        memset(dp,-1,sizeof(dp));
        for(int i = 1;i <= n;i++)   cin >> a[i];
        for(int i = 1;i <= n;i++)   cin >> cost[i];
        for(int i = 1;i <= n;i++)   sum[i] = sum[i-1]+a[i];
        cout << dfs(1,n) << endl;
    }
    return 0;
}
View Code

H.HDU4961

从左往右扫一遍,更新当前可行约数的最新值,这样b肯定为最接近的。

从右往左扫一遍,同上。

技术分享
#include<bits/stdc++.h>
#define MOD 1000000009
using namespace std;

int n,a[100005],b[100005],c[100005],vis[100005];

int main()
{
    ios::sync_with_stdio(false);
    while(cin >> n && n)
    {
        for(int i = 1;i <= n;i++)   cin >> a[i];
        memset(vis,0,sizeof(vis));
        for(int i = 1;i <= n;i++)
        {
            if(vis[a[i]])   b[i] = a[vis[a[i]]];
            else    b[i] = a[i];
            for(int j = 1;j <= sqrt(a[i]+0.5);j++)
            {
                if(a[i]%j == 0)
                {
                    vis[j] = i;
                    vis[a[i]/j] = i;
                }
            }
        }
        memset(vis,0,sizeof(vis));
        for(int i = n;i >= 1;i--)
        {
            if(vis[a[i]])   c[i] = a[vis[a[i]]];
            else    c[i] = a[i];
            for(int j = 1;j <= sqrt(a[i]+0.5);j++)
            {
                if(a[i]%j == 0)
                {
                    vis[j] = i;
                    vis[a[i]/j] = i;
                }
            }
        }
        long long ans = 0;
        for(int i = 1;i <= n;i++)   ans += (long long)b[i]*c[i];
        cout << ans << endl;
    }
    return 0;
}
View Code

I.HDU4963


J.HDU4966

 

省赛训练赛(---)