偶尔刷刷题

分类

题解(32)

/ 注册

全部文章（共32篇）

牛客NOIP暑期七天营-普及组2-D线段

题目大意：已知n条线段的左右端点与颜色，现有m个循环，问区间中被完全包含的线段有多少种颜色？ 36分，普及组该拿的分数：对于每个区间，暴力枚举每条线段，统计颜色数——只有颜色恰好加到1，才算增加一种颜色的线段。 for(i=1; i<=m; i++){ ans = 0;...

树状数组区间贪心思维统计数据结构

2019-08-20

1 816

牛客NOIP暑期七天营-普及组2-C硬币

题目大意：有n枚硬币，a枚正面朝上，b枚反面朝上，每次操作随机抽取一枚翻过来，m次操作正面朝上的数量的数学期望是多少？如果只有1枚硬币，每次翻转的都是同一枚，最终要么是正面朝上，要么是反面朝上，数学期望是0或者1。对于n枚硬币，a枚正面朝上，b枚反面朝上，下一次有两种状态： 1、随机抽到正面朝上...

期望滚动数组递推概率 DP

2019-08-20

1 736

牛客NOIP暑期七天营-普及组2-B括号

题目大意：一个只有()的字符串，匹配的1对括号可以花1次操作消去，不匹配的可以花1次操作对字符进行括号取反。保证长度是偶数，至少多少次操作才能消去所有括号？能匹配的用1次操作进行消去（至少1次，已是最优）不能匹配的括号：入栈，等待匹配；显然右括号入栈无法消去，必须使用1次操作转成左括号。如果左...

括号匹配字符串栈贪心

2019-08-20

1 688

牛客NOIP暑期七天营-普及组2-A采蘑菇

题目大意：已知n个点的蘑菇数量，采到的蘑菇只能是偶数，你可以将某个点的蘑菇数量加1，请问最多采多少蘑菇？显然，偶数的全部都可以采；对于奇数的，至多使用1次魔法增加1后进行采摘，贪心选择最大的奇数。如果没有奇数，魔法就不用了，用了会导致偶数少采一个。 #include <bits/stdc++...

细节贪心循环

2019-08-20

1 863

牛客NOIP暑期七天营-普及组1-D矩阵

题目大意：给定一个n*m的矩阵，输出最大子矩阵（元素之和最大值）。对于每一个子矩阵，如果左上角是(x, y)，右下角是(p, q)，那么他每一行的元素之和是：用乘法分配率合并后即：这样，问题就转化为求数组a中的最大子段和以及数组b中的最大子段和问题了。当然，还需要注意细节： 1、对...

分配律数学分类讨论思维前缀和

2019-08-19

0 762

牛客NOIP暑期七天营-普及组1-C丢失的题面

题目大意：阅读程序，优化时间复杂度，过掉所有数据。 # 原代码 int mod = 1e9 + 7; cin >> n >> m; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int j = 1; j <=...

堆阅读程序写结果数据结构优先队列

2019-08-19

1 927

牛客NOIP暑期七天营-普及组1-B相似度查询

题目大意：给定一个母串，问从母串中最多依次抽出多少个字符恰好是另一个字符串的前缀？（m个匹配串）对于每个要匹配的字符串，逐个字符查找，只有先找到前面的字符，后面的字符才能够匹配，因为要按照原来的顺序。对于匹配成功的，母串前面那些字符就不能再用来匹配了，因为要按照原来顺序。（贪心：越先找到越好） ...

模拟字符串查找

2019-08-19

0 733

牛客NOIP暑期七天营-普及组1-A统计

题目大意：统计小写字母出现次数。开一个数组，存储每个字符出现次数，最后输出小写字母的次数即可。字符ascii不超过128，数组开130就够了。 #include <stdio.h> int n, m, i, j, k, c[130]; char s[100005]; int main(...

字符语法统计

2019-08-19

0 775

计蒜客信息学8月普及组模拟赛D-DD摆磁铁

题目大意：n个点的树，有m*2个点有磁铁，如果配对使得m对磁铁之间的距离之和最大？对于每一条边，左边有x个磁铁，右边有y个磁铁，要想距离大，那么尽量左右两边互相配对，最多可以配min(x, y)对。每条边都是如此。 #include <bits/stdc++.h> #define N ...

树贪心思维

2019-08-18

0 733

计蒜客信息学8月普及组模拟赛C-DD去旅行

题目大意：n个点m条边，从1走到n需要多少代价？（边的代价为点数*距离）最短路问题，只是需要记录每个点的深度，更新距离是需要用到。每个点都有n种深度，很难确定SPFA的队列开多大，故用优先队列，当点n出队时，最小代价就出来了，因为后面的代价只会越来越大。 #include <bits/st...

最短路 SPFA

2019-08-18

0 944