1.24总结

1.24总结

1.早上两个半小时。

做第二周测试的P7940这题，由于这个题目限制条件有点多，因此每次把这个思路用代码进行实现的时候，就会发现这个思路有漏洞，每次都会漏掉题目的条件，一上午都没有完成这个题目。

由于我的思维定式，认为一定是先把上面全改成一半赢，一半输，再把下面全改为赢，做这个题目的思维不清晰。

2.下午两个半小时。

P7938

P7938 [A] Beautiful Array - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

括号匹配，如果是括号的左半边，就入栈，如果是括号的右半边，那栈里面还有元素的话就把栈顶元素出栈，然后匹配的括号的对数就加一，然后如果匹配的括号的对数大于等于m，就可以分出这个序列

代码实现

#include
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,top=0,sum=0;
        scanf("%d %d",&n,&m);
        char s[10001],a[10001];
        scanf("%s",s);
        for(int i=0;i0)
                {
                    top--;
                    sum++;
                }
            }
        }
        if(sum>=m)//括号能匹配的对数大于等于m，则证明可以分出来
            printf("1n");
        else
            printf("0n");
    }
    return 0;
}

3.晚上三个小时。

上午做题目的时候，感觉对贪心算法不熟悉，所以晚上看了讲解贪心算法的视频，并对一些贪心算法的从易到难的实例的思路进行理解，还有笔记。

贪心算法

每次 *** 作都取得该次 *** 作的最优解，（局部最优解），从而使最后得到的结果是最优的，（全局最优解）。

最优装载问题（也可以用背包算法解答）

一块石头不管重量多少，数量都只是一块，所以要在重量有限制的条件下装有块数最多的石头，只要先往小的石头装。

合并果子（也可以用“堆”来解答）

每次都取最小的两堆进行合并，因为越早合并的堆需要重复去和别的堆去合并成更大的堆的次数就越多，所以越早合并的堆的果子数越少越好。

国王的游戏NOIP2012