day4上午

清北学堂--刷题班

题解

t1

反向思考，倒过来做，从最终状态变到0，
0变少，不是0变小

实际操作：
用数组记录每个数有多少个，
第一步，(a[0]+1)/2,然后a[1]->a[0],a[2]->a[1]耗时，
所以让(a[0]+1)->a[1]，赋值给a[1];

难度 noip t1~t2

t2

让每一段都尽量的大，那么，加一条边时，判断是否联通，可以bfs，太慢
优化：对于加了一条边，判断是否联通时，只加了一条边，所以从这条边的两个点开始bfs将所到达的点标记为1

之前的版本：
给平面上的一堆点，分成尽量少的点编号连续的点集，使得点集内任意两个点的距离不超过一个给定值L，

因为分组内的点是连续，能多取就多取，二分下一个分割的位置，
当前的位置，start+delta
delta = 100 ? 200 ? 300...
当在1000时不可取时，答案介于900~1000
同样可以delta=1 ? 2 ? 4 ? 8?...
2^(p-1) <= delta <= 2^p
在2^(p-1)与2^(p)之间二分

补充：
二分与增量法，
增量法，一个一个的增加判断，判断可不可行
如果一个一个的判断时，太慢，而且满足答案的单调性，可以二分，二分复杂度log

t3

考虑最好的情况，1,2,3,4,5
所以55555
看成12345
垫刀

变形的背包。

解题报告及总结

预计100+0+

t1

又是写了一个半小时，，，。
首先推出了结论，然后不会写，写完暴力差不多40~50分钟，然后想正解怎么写，想到后，赶紧写，差不多1个小时左右，发现做了一个小时了，后面还有两个，但是，不忍心放弃，又写了接近到1个小时15~20分钟，然后写出了正解，发现和暴力不一样，是暴力的错误，调试暴力，没调出，于是当时大胆的删了暴力，全放在了正解上。

这个题做的时间很长了，导致后面没有时间了，只有1个小时。

当时推出的结论：
首先将原题转换一下，将一段序列，操作多少次，变成一个0；
结论：对于不是0的数，-1，0合并
证明：
对于任意的x,y只存在于3中情况，
1、x,y都是0，直接合并
2、x是0，y不是，那么如果先合并，操作次数y+1,想让y减到0,操作次数y+1
3、都是0，先合并，x+y+1，先减到0，max(x,y)+1.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int MAXN = 1000100;

int a[MAXN];
int num[MAXN];


inline int read() {
    int x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}

int main() {
    freopen("multiset.in","r",stdin);
    freopen("multiset.out","w",stdout);

    int cnt ,ans ,mx = -1;
    int n = read();
    for (int i=1; i<=n; ++i) {
        a[i] = read();mx = max(mx,a[i]);
        num[a[i]]++;
    }
/*  if (n<=1000) {
        ans = 0;
        cnt = num[0];
        for (int i=1; i<=n; ++i) if (a[i]==0) a[i] = -1;
        for (int i=1; ; ++i) {
            ans ++;
            if (cnt>=2) cnt = (cnt+1)/2;
            bool flag = true;
            for (int k=1; k<=n; ++k) {
                if (a[k] > 0) a[k]--,flag = false;
                else if (a[k]==0) cnt++,a[k]=-1,flag = false;
            }
            if (flag) break;
        }

        printf("%d",ans-1);
        return 0;
    }*/
    ans = 0;
    cnt = num[0];
    int tt = 0,tmp;
    for (int i=1; i<=mx; ++i) {
        if (!num[i]) continue;
        tmp = i-tt;
        if (tmp>0) {
            tt += tmp;
            ans += tmp;
            if (cnt>=2) {
                int k = log(cnt-1)/log(2);
                k++;
                if (tmp>=k) cnt = 1;
                else {
                    int ttt = tmp;
                    while (ttt) cnt = (cnt+1)/2,ttt--;
                }

            }
            cnt += num[i];
        }
    }
    if (cnt) {
        int k = log(cnt-1)/log(2);
        k++;
        ans += k;
    }

    printf("%d",ans);

    return 0;
}

写的时间太长了

t2

当时时间紧，直觉感觉t3代码量少，于是...

t3

贪心的思路，结果错了。
当时是这样想的，考虑最好的情况是12345...如果当前有为1的，那么打掉它不会差，于是打掉了它，然后如果没有，那么可以有一个空隙打后面的，那么打什么样的点呢，
当前血量a的有多个，然后血量为a-1的没有，那么，打掉a一个，变成a-1，于是成了错误的，简单的，模拟，+贪心思路，只对了一个点。