贪心练习题

最大积分

https://www.ybtoj.com.cn/contest/130/problem/6

这题想策略倒不难，价值高的后买，乘以的等级就更高收益更高

难在等级增加时的算法模拟

（PS：题面其实说的很模糊。。T[i]到底表示总购买数还是再购买数也没清楚，导致前半段一直出错）

#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
//
//
    FOR(i,1,n){
        tmp = cnt - t[lev-1];
        cnt = a[i].num+cnt;
        if(cnt < t[lev]){
            ans+=a[i].num*a[i].c*lev;
        }
        else while(1){
            if(cnt < t[lev]){
                ans+=(cnt-t[lev-1])*a[i].c*lev;break;
            }
            else{
                ans+=(t[lev]-t[lev-1]-tmp)*a[i].c*lev;
                lev++;
                tmp = 0;    
            }    
        }
    }

cnt一直表示总购买量，tmp在购买下种物品之前记录，用来补充升级前的那部分

一次升级之后tmp就归0了，等购买下一种再记录。

砍树问题

https://www.ybtoj.com.cn/contest/130/problem/7

这让我想起之前的雷达问题！

同样要找到一个排序方式并说明其依据，那么根据经验，应该按横坐标（x）排序

好处是，只需要依次对相邻两棵树比较，不需要比较不相邻的树

对于P，左边的树到他距离D1，右边D2，那么这棵树的最高允许高度就为h = min（d1,d2），至少要砍去的长度就为max（ai-h,0）。

出栈序列

https://www.ybtoj.com.cn/contest/130/problem/8

字典序对局部最优策略提示很明显了，每次都要尽量找到序列数值最大的数先输出，直到序列全部入栈，再从栈顶依次输出。

我们用O(n)做法，可以记一个数组来找数值最大的数：如果后面的数都比它小，那么他一定要立即输出。

因此建立后缀最大值数组Max[n]。

int main(){
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
    Max[n] = a[n];
    ROF(i,n-1,1) Max[i] = max(a[i],Max[i+1]);
    //FOR(i,1,n) printf("%d ",Max[i]); enter;
    //模拟 
    FOR(i,1,n){
        int x = a[i];
        z[++top] = x; //进栈 
        while(z[top] > Max[i+1]) { //如果已是从现在到结束为止最大的数，弹出 
            printf("%d ", z[top--]);
        }
    }
    while(top) printf("%d ",z[top--]); //退完 
}

矩阵问题

 

荷马史诗

https://www.ybtoj.com.cn/contest/130/problem/4

一道构建出模型才能化繁为简的问题。

题的含义是建立n个k进制数，使他们没有前缀包含另一个数。

建立k进制数好办，保证条件就有难度了。

题解给的算法中运用了树：

 

 发现，如果将根到某个叶子路径边权按顺序连就得到了一个Si，一个叶子对应一个Si，同时可以满足前面的前缀条件！

那么，问题就转化为建造一个k叉树。

再想想最优方案：给边加上边权（Si出现的次数为w[i]，对应叶子节点的深度为dep[i](也可以说单词i转化为的字符个数)，那么总长为

所有n个词的dep[i]*w[i]

那么，边权较小的叶子节点应该深度较浅，以达到整体总长更小。

比如上图，原来3位置没有节点，那么将2节点挪移过去，一定不会比挪移前更差。

但是要只比较边权较小的叶子节点也不行，建不起多层树，所以我们用a[i]表示i子树中边权和,按a[i]从小到大取。

在计算中，不能保证每个树都有k个节点，计算的时候各种空位麻烦，所以我们搬出优化策略：

优化策略：补充若干个w=0的节点，使(n-1)%(k-1)=0

这样可以每次取前k个，这个算法就完美了

附代码

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
#define int long long
#define il inline 
typedef long long ll;
using namespace std;
const int M = 110086;
int n,k,cnt,ans,w[M];
struct tle{
    int v; //该点权值 
    int h; //该点子树高度 
};
il bool operator < (const tle &a,const tle &b){
    if(a.v!=b.v) return a.v > b.v; 
    else return a.h > b.h;
}
priority_queue <tle>q;
signed main(){
    cin>>n>>k;
    FOR(i,1,n) {
        scanf("%lld",&w[i]);
        tle tmp;
        tmp.v = (ll)w[i];
        tmp.h = 0;
        q.push(tmp);
    } //初始化：全是叶子，深度为0，权值w[i]
    cnt = n;
    if((n-1)%(k-1)!=0){
        cnt+=k-1-(n-1)%(k-1);
    } 
    FOR(i,1,cnt-n) {
        tle tmp;
        tmp.v = 0ll;
        tmp.h = 0;
        q.push(tmp);
    } //n-1不是k-1整数倍时，用权值为0的点补全
    while(cnt != 1) {
        ll val = 0ll;
        int dep = 0;
        FOR(i,1,k){ //step1:取出前k小 
            tle tot = q.top();
            val += (ll) tot.v;
            dep = max(dep,tot.h);
            q.pop();
        }
        cnt = cnt - k + 1; //step2:cnt减值
        ans += val;//step3:加上权值之和 
        tle tmp;
        tmp.v = val;
        tmp.h = dep+1; //+1是因为要变父亲了，加辈
        q.push(tmp);  //step4:把父亲压进去，合并完成，一次循环结束 
    }
    cout << ans << endl << q.top().h << endl;
    return 0;
}

---

二分练习题

 

 二分的适用范围：最优解具有单调性

合法|不合法：把最优化问题转化为判定问题

数列分段

https://www.ybtoj.com.cn/contest/131/problem/1

经典的二分转化--找到合适的L与R（此题是数列max到数列sum）--二分判断mid是否满足--满足则大于mid部分丢掉，不满足则小于mid部分丢掉

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
#define mid ((l+r)>>1)
using namespace std;
int n,m,a[100005],max_of_ai,sum_of_ai;
int ck(int limit){
    int cnt = 1,sum = 0;
    FOR(i,1,n) {
        if(sum + a[i] <= limit) sum+=a[i];
        else cnt++,sum = a[i];
    }//单调选择，看作找不大于limit的最少连续段的问题 
    return cnt <= m;
}
int main(){
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d",&a[i]),max_of_ai = max(max_of_ai,a[i]),sum_of_ai += a[i];
    int l = max_of_ai,r = sum_of_ai;
    while(l < r){
        //printf("%d %d\n",l,r);
        if(ck(mid)) r = mid;
        else l = mid+1;
    }
    cout<<l<<endl;
}

攻击法坛

https://www.ybtoj.com.cn/contest/131/problem/6

二分的题各不相同，但是能推出二分的模型，按照题本身特点来做

这个题特点是融合DP

#include<bits/stdc++.h>
#define define define 
#define enter puts("\n")
#define FOR(i,a,b) for(int i = (a);i <= (b);i++)
#define mid (l+r)/2
using namespace std;
const int MAXN = 2005;
int n, R, G, a[MAXN], l = 1, r = 0,ans = 0,cnt;
int dp[MAXN][MAXN],p[MAXN],q[MAXN];
bool ck (int L){
    memset(dp,0,sizeof(dp));
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    FOR(i,1,n) FOR(j,i,n){
        if(a[j]-a[i]+1<=L) p[i] = j;if(a[j]-a[i]+1<=2*L) q[i] = j;
    }
    p[n+1] = q[n+1] = n;
    FOR(i,0,R) FOR(j,0,G){
        cnt++;
        if(i>0) dp[i][j]=max(dp[i][j],p[dp[i-1][j]+1]);
        if(j>0) dp[i][j]=max(dp[i][j],q[dp[i][j-1]+1]);
    }//枚举 
    return dp[R][G]==n;
}
int main(){
    scanf("%d%d%d",&n,&R,&G);
    FOR(i,1,n) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int l = 1,r = a[n] - a[1] + 1;a[0] = 0;
    if(R+G >= n) return printf("1\n"),0;
    while(l <= r){
        if(ck(mid)) ans = mid,r = mid-1;else l = mid+1;
    }
    cout<<ans<<endl;
}