A循环
题目大意
给一个循环语句
for (i = a; i op b; i += c)
op为<=, >=或!=
求i += c执行的次数 或 判断死循环
for (i = a; i op b; i += c)
op为<=, >=或!=
求i += c执行的次数 或 判断死循环
做法
分类讨论
1、判断掉死循环的情况（既一开始条件为假，之后也不会为真）
2、判断掉一开始就为真的情况
3、除法计算答案
这题很简单，主要是要细心
1、判断掉死循环的情况（既一开始条件为假，之后也不会为真）
2、判断掉一开始就为真的情况
3、除法计算答案
这题很简单，主要是要细心
B供给和需求
题目大意
给定若干个供给关系: 供给 = 价格 * c[i]
若干个需求关系: 需求 = max(0, a[i] – 价格 * b[i])
价格是整数，求最小的 |总供给 – 总需求|
若干个需求关系: 需求 = max(0, a[i] – 价格 * b[i])
价格是整数，求最小的 |总供给 – 总需求|
做法
1、常见的错误思路: 用 sum(b) / (sum(a) + sum(c))来确定价格
错误原因：需求不能小于0
2、暴力思路：枚举价格，找出最小值
错误原因：需求不能小于0
2、暴力思路：枚举价格，找出最小值
正解：二分
考虑v = 总需求 – 总供给
那么随着价格上升，v一定是下降的（价格上升，需求减少，供给增加）
因此可以二分价格，找到最小的非负v，和最大的负v，比较得出答案
C读心术
那么随着价格上升，v一定是下降的（价格上升，需求减少，供给增加）
因此可以二分价格，找到最小的非负v，和最大的负v，比较得出答案
C读心术
题目大意
给定一系列操作，每个操作为:
a = a + x
a = a * x
a = a % x
问是否无论初始的a是多少，最终的结果都是固定的
模运算规律
给定一系列操作，每个操作为:
a = a + x
a = a * x
a = a % x
问是否无论初始的a是多少，最终的结果都是固定的
模运算规律
模运算的计算中
(a + x1) % x2 = (a % x2 + x1) % x2
(a * x1) % x2 = (a % x2 * x1) % x2
两条推论:
1、计算过程中，对于每一步计算找到它之后的第一次%运算，每一步运算结束后
都可以先做一次取模
2、假设第一次%运算的操作数为x，那么如果有a % x = b % x，那么以a开始和
以b开始最终结果肯定是一样的
因此我们只需要枚举0到10000并计算结果即可
特殊情况：如果一个操作之后没有%运算了，那么考虑有没有*0操作，如果没有的
话到这一步时不同的结果到最后也会不同
(a + x1) % x2 = (a % x2 + x1) % x2
(a * x1) % x2 = (a % x2 * x1) % x2
两条推论:
1、计算过程中，对于每一步计算找到它之后的第一次%运算，每一步运算结束后
都可以先做一次取模
2、假设第一次%运算的操作数为x，那么如果有a % x = b % x，那么以a开始和
以b开始最终结果肯定是一样的
因此我们只需要枚举0到10000并计算结果即可
特殊情况：如果一个操作之后没有%运算了，那么考虑有没有*0操作，如果没有的
话到这一步时不同的结果到最后也会不同
D中国式家长1
题目大意
给定M个事件，每个事件有三个属性:
iqNeed, iqAdd, face
代表iq >= iqNeed时才可以安排，安排完之后iq会增加iqAdd点，面子会增加face点，
但iqAdd和face每次会减少1
一共安排N个事件，问最终face最大是多少
iqNeed, iqAdd, face
代表iq >= iqNeed时才可以安排，安排完之后iq会增加iqAdd点，面子会增加face点，
但iqAdd和face每次会减少1
一共安排N个事件，问最终face最大是多少
观察规律
对于任意的事件执行顺序，必然可以调整成按iqNeed升序执行
证明：
如果对于连续执行的两个时间task1和task2，task1.iqNeed > task2.iqNeed
那么交换他们的执行顺序也是可行的
对于task1: 因为执行过task2之后，iq不会减少，因此task1必然可以执行
对于task2: 因为task1.iqNeed > task2.iqNeed, 执行task1时iq > task1.iqNeed > task2.iqNeed，
所以先执行task2也是满足条件的
证明：
如果对于连续执行的两个时间task1和task2，task1.iqNeed > task2.iqNeed
那么交换他们的执行顺序也是可行的
对于task1: 因为执行过task2之后，iq不会减少，因此task1必然可以执行
对于task2: 因为task1.iqNeed > task2.iqNeed, 执行task1时iq > task1.iqNeed > task2.iqNeed，
所以先执行task2也是满足条件的
动态规划
因此可以考虑按iqNeed升序排列之后动态规划
一种动归状态:
f[i][j][k]代表前i个事件一共安排了j天，执行完成后iq为k的情况下face最大值为多少
转移时考虑枚举当前事件的执行天数（枚举到iqAdd, face都为0既可）
一种动归状态:
f[i][j][k]代表前i个事件一共安排了j天，执行完成后iq为k的情况下face最大值为多少
转移时考虑枚举当前事件的执行天数（枚举到iqAdd, face都为0既可）
std
全部评论
(0) 回帖