哈理工网络赛

大神博客：http://m.blog.csdn.net/just_sort/article/details/78775866

题目描述

在acimo星球, tabris 是一名勇敢的屠龙勇士，在上绿岛屠龙前决定挑选N种装备武装自己，现在每种装备有两个，**但每种装备tabris必须选择拿一个**，**不能多也不能少**。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。

输入描述:

有多组测试样例，输入到文件结束。
每组测试数据的第一行包含一个正整数NN，表示装备的种类数。
接下来N行，每行两个正整数a_i、b_i，表示两个不同的第ii种装备的属性加成值。

N∈[1,10³]
a_i,b_i∈[1,10⁶]

输出描述:

对于每组测试数据输出一个整数,为了方便输出最终的结果先乘2

再对1e9+7取模后的值。

示例1

输入

输出

说明

3465 = (1*3*5*7) + (1*3*5*8) +(1*3*6*7) + (1*3*6*8) + (1*4*5*7) + (1*4*5*8) + (1*4*6*7) + (1*4*6*8) + (2*3*5*7) + (2*3*5*8) + (2*3*6*7) + (2*3*6*8) + (2*4*5*7) + (2*4*5*8) + (2*4*6*7) + (2*4*6*8) ;


题意 ： 每组数据选择一个，将每组数据中选出的数据相乘，求最后的和。
思路 ： 先考虑只有一组数据的情况，答案即为两个数相加的和，在考虑有两组数据的情况，在纸上写一下会发现规律，所有数据的和即为每组数据的和相乘

代码示例 ：

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n;
    int a, b;
    
    while(~scanf("%d", &n)){
        ll ans = 1;
        for(int i = 1; i <= n; i++){
            scanf("%d%d", &a, &b);
            ans *= 1ll*(a+b)%mod;
            ans %= mod;
        }
        printf("%lld
", ans%mod);
    }
    

    return 0;
}

c .

题目描述

小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：

1.乌鸦坐飞机释放时间：x 固定伤害值：a

2.蜘蛛吃耳屎释放时间：y 固定伤害值：b

3.饿狼前进释放时间：z 固定伤害值：c

他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i

这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。

小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。

输入描述:

本题包含多组数据。
输入格式为：
T
x a
y b
z c
L R temp A
数据范围：
1<=T<=1e5
1<=x,y,z,L,R<=T
L<=R
<=a,b,c,temp,A<=1e5

输出描述:

输出包含一行，输出能够打出的最高伤害值。

示例1

输入

输出

备注:

大招：蓄力时间最短L秒，最多R秒。无限次释放，释放之后照成的伤害是随着时间增加的
蓄力L秒释放能够造成Temp的伤害
蓄力L+1秒释放能够造成Temp+1*A的伤害
依次类推


题目分析 ： 如果没有大招，那这题就是一个简单的线性dp，扫一遍就过了，但是现在有大招，加了一位博友，第一次才知道，原来这种公式是可以推出来的，dp[i] = max(dp[i], dp[j]+temp+A*(i-l-j)),i-r <= j <= i-l ,维护当时间是 i 时，寻找此时的最大值并且继续更新。
　　但是你单纯按照着这个递推公式推，你会出错了，因为你只是确保是dp[]的最大，但是时间是不确定的，因为有可能同一个dp值，但是有两个时间都是等于这个，因此可以将公式进一步变形，dp[i] = max(dp[i], dp[j]-A*j + temp + A*(i-l)),这里可以用优先队列去维护，但是有
　　个点一定要知道，就是 你的时间是递推的，因此在区间内不符合范围的解，此不符合的区间的前端以后也是不会用到的，因此可以之间删除，但是后面的点以后可能会用到，要保存下来。

代码示例 ：

const int eps = 1e5+5;
const double pi = acos(-1.0);
const int inf = 1<<29;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define ll long long

ll dp[eps];

struct node
{
    ll w;
    int u;
    
    bool operator< (const node &c)const{
        return w < c.w;
    }
    node(ll _w, int _u):w(_w), u(_u){}
};

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t;
    
    int x, a, y, b, z, c;
    int l, r, tem, A;
    priority_queue<node>que;
    stack<node>s;
    //node v(0, 0);
    
    while(~scanf("%d", &t)){
        scanf("%d%d", &x, &a);
        scanf("%d%d", &y, &b);
        scanf("%d%d", &z, &c);
        scanf("%d%d%d%d", &l, &r, &tem, &A);
        
        while(!que.empty()) que.pop();
        while(!s.empty()) s.pop();
        memset(dp, 0, sizeof(dp));
        
        ll ans = 0;
        for(int i = 1; i <= t; i++){
            if (i >= x) dp[i] = max(dp[i], dp[i-x]+a);
            if (i >= y) dp[i] = max(dp[i], dp[i-y]+b);
            if (i >= z) dp[i] = max(dp[i], dp[i-z]+c);
             
            que.push(node(0, 0));
            if (i >= l){
                while(!que.empty()){
                    node v = que.top();
                    if (v.u < i-r || v.u > i-l) que.pop();
                    else break;
                    if (v.u > i-l) s.push(v);
                }
                node v = que.top();
                dp[i] = max(dp[i], v.w+1ll*tem+1ll*A*(i-l));
                //if (i == 2) printf("@@%lld %d %d %d", v.w, tem, A, i-l);
            }
            que.push(node(dp[i]-1ll*A*i, i));
            while(!s.empty()) {
                que.push(s.top());
                s.pop();
            } 
            ans = max(ans, dp[i]);
            //printf("**%lld
", dp[i]);   
        }
        printf("%lld
", ans);
    }

    return 0;
}

另一种写法：要好好理解一下为什么 ret 要初始化为 long long 的负无穷

const int eps = 1e5+5;
const double pi = acos(-1.0);
const int inf = 1<<29;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define ll long long

ll dp[eps];
struct node
{
    int l, r, k;
    ll w;
}tree[eps<<2];
ll maxx;

void build(int l, int r, int k){
    tree[k].l = l, tree[k].r = r;
    if (l == r){
        tree[k].w = 0;
        return;
    }
    int m = (l + r)>>1;
    build(l, m, k<<1);
    build(m+1, r, k<<1|1);
    tree[k].w = max(tree[k<<1].w,tree[k<<1|1].w);
}

ll query(int L, int R, int k){
    if (L <= tree[k].l && tree[k].r <= R){
        return tree[k].w;
    }
    int m = (tree[k].l + tree[k].r) >> 1;
    ll ret = -__LONG_LONG_MAX__; // 初始化为long long 的负无穷
    if (L <= m) ret = max(ret, query(L, R, k<<1));
    if (R > m) ret = max(ret, query(L, R, k<<1|1));
    return ret;
}

void update(int pos, ll val, int k){
    if (tree[k].l == tree[k].r){
        tree[k].w = val;
        return;
    }
    int m = (tree[k].l + tree[k].r) >> 1;
    if (pos <= m) update(pos, val, k<<1);
    else update(pos, val, k<<1|1);
    tree[k].w = max(tree[k<<1].w,tree[k<<1|1].w);
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int t;
    int x, a, y, b, z, c;
    int l, r, tem, A;
    
    while(~scanf("%d", &t)){
        scanf("%d%d", &x, &a);
        scanf("%d%d", &y, &b);
        scanf("%d%d", &z, &c);
        scanf("%d%d%d%d", &l, &r, &tem, &A);
        
        memset(dp, 0, sizeof(dp));
        build(0, t, 1);
        ll ans = 0;
        for(int i = 1; i <= t; i++){
            if (i >= x) dp[i] = max(dp[i], dp[i-x]+a);
            if (i >= y) dp[i] = max(dp[i], dp[i-y]+b);
            if (i >= z) dp[i] = max(dp[i], dp[i-z]+c);
            if (i >= l) {
                int L = i - r, R = i - l;
                if (L < 0) L = 0; 
                dp[i] = max(dp[i], query(L, R, 1)+1ll*tem+1ll*A*(i-l));
            }
            update(i, dp[i]-1ll*A*i, 1);  
            ans = max(ans, dp[i]); 
        }
        printf("%lld
", ans);
    }
    return 0;
}

东北日出西边雨道是无情却有情