达成三个单周坚持写博客成就（555因为双周都没写orz）

进度依然慢…

cf-Card Game

题意：博弈问题 给个n即n张牌（由1到n）每个人分n/2张 从Alex开始出牌 后手一定要比先手出的牌大 接u着Boris出 到谁出不了了就输了 求Alex赢、Boris赢和平局的分牌方式

求解：从最大的四张开始分 A先手 所以A赢就有两种 要么最大的在A 如果最大在B 那剩下的n-1和n-2必须在A n-3在A A赢 n-3不在 这四张牌平局 因而递归下去

由此可得f[n]=C(n/2-1,n-1)+C(2/n-3,n-4)+f[n-4]的递归公式 四张四张求解即可

写这题的时候思维很凝固的感觉 感觉还是要从NP开始想 觉得我的思考很没有条理性

还要注意一点 有取模和减法一起出现的时候 为了防止出现负数 要+MOD再%MOD

贴一个求组合数的板子(n比较小的情况)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void C()
{
    c[0][0]=1;
    for(int i=0;i<=70;i++)
    {
        for(int j=0;j<=70;j++)
        {
            if(j==0||j==i) c[i][j]=1;
            else
            {
                c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
            }
        }
    }
}
cf-Reset K Edges

题意：给n个结点 以及他们的深度（1的深度是0）还可以进行k次操作 一次操作：删掉一条边 将剩下的连到1的下面去 问最多经过k操作后的最小的树的深度

求解：二分+贪心 从下向上遍历 到了高度为mid-1的那一层 如果是根节点 那么不用动 但如果不是 就把这棵子树接到1上 记录进行的操作次数与k对比 注意为了做到无后效性 要从下向上遍历

cf-1250J

题意：有一群人 要站队 给个n 给个k n表示有n个不同的身高 (全部的身高从1-n) k表示要站几排 然后会依次给出每个身高下有多少个人 站队要求：一排里面两人身高最多相差1cm 求最后的方针里最多有多少个人

求解：求最大最小值的问题自然想到二分 这题是一个二分+一点贪心 总体框架没什么问题 在站队的贪心上出了点问题 应该是从小到大依次看这个身高能组成多少队列 然后从后一个身高里取一部分人恰好凑成新的一列 这样的贪心才是最优的（搞不懂我怎么想的 就不写错误思路了）

arc146-B Plus and AND

题意：n m k n个数 能给他们加m个1 问选k个数 进行与运算(e.g 011 AND 101=001)的最大值

求解：位运算的问题 从高位到低位贪心 如果m能够使得 k个数字这一位都为1 就消耗掉 如果不能 就继续向下贪心（因为只要有1个0 与运算后就都为0了）从31跑到0 一位一位判断

其实感觉这题思路倒是很好理解 就是代码好难写哦(我太菜了)

贴个代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
for(int i=31;i>=0;i--)//从高位到低位贪心 
    {
        for(int j=0;j<n;j++)
        {
            b[j]=c[j];
            if((a[j]>>i)&1) continue;
            else b[j]+=(1ll<<i)-(a[j]%(1ll<<i));
        }
        sort(b,b+n);
        ll sum=0;
        for(int j=0;j<k;j++) sum+=b[j];
        if(sum<=m)
        {
            ans|=(1ll<<i);
            for(int j=0;j<n;j++)
            {
                if(a[j]>>i&1) continue;
                else
                {
                    c[j]+=(1ll<<i)-(a[j]%(1ll<<i));
                    a[j]=1ll<<i;
                }
            }
        }
    }

zls说位运算就要么从高位到低位想 要么从低位到高位想

牛客-跳石头

题意：给L N M 分别表示起点到终点的距离 起点和终点之间的岩石数 以及组委会至多移走的岩石数 求最短跳跃距离的最大值

求解：经典二分 通过mid看需要移走几块石头

贴个check代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int cnt=0;
int last=0;
for(int j=0;j<=n;j++)
{
    if(x[j]-last<w)
    cnt++;
    else
    {
        last=x[j]; 
    }
}
if (cnt<=m) return true;
else return false;
牛客-数字组合

题意：给四个数组 问每个数组取一个数字 四个数字和为0 有多少种取法

求解：一个时间复杂度上的优化 先两两加一下组成两个新的数组 然后二分查找一下

牛客-[CQOI2010]扑克牌

题意：有n种牌 每种牌张数不一样 还有m张joker n张不同的牌可以凑成一副牌 但是每副牌里不能出现相同的牌（即joker最多可以代替一张普通牌）问最多多少副牌

求解：还是二分 判断要补多少张joker（注意不能超过mid） 注意开long long

1
2
3
4
5
6
7
int s=0;
for(int i=0;i<n;i++)
{
    s+=max(mid-a[i],(long long)0);
 } 
 if(m>=s&&mid>=s) return true;
 else return false;false;
牛客-K-th Number

题意：A数组有n个数 给了个k 将所有大于等于k的区间中的第k大的数放入B数组中 然后问B中第m大的数是哪个

求解：这题很难想到是二分（如果没出现在题单里我肯定想不到）找出所有区间中包含大于等于k个大于等于mid的区间的数量 check函数不太好写 看到很牛的代码 用数组s去记录从1开始大于等于mid的数字数量 然后从第k个数开始遍历 如果（l-i）区间满足条件 那么l之前的更长的区间必定满足条件 所以sum+=l即是目前为止满足条件的区间数

整个思维的转换很有意思

1
2
3
4
5
6
7
8
9
10
11
12
int sum=0;
for(int i=1;i<=n;i++)
{
    if(a[i]>=mid) s[i]=s[i-1]+1;
    else s[i]=s[i-1];
}
int l=0;
for(int i=k;i<=n;i++)
{
    while(s[i]-s[l]>=k) l++;
    sum+=l;
}

总结

先写这么多 感觉最近整个思维出现很紊乱的状态 下周开始复习一些基础的东西+过一遍贪心