刷题笔记


9.26日考试

T1:质因数分解+快速幂 将N!进行质因数分解 如果分解质数的个数为奇数就删掉一个如果为
    偶数则直接乘入答案
T2:树状数组求逆序对  如果[l,r]是合法的 那么对于[l,r]中的每一个数都减一个L则∑≥0
    并且如果都减一个R则∑≤0
    我们用A[i]表示前i个数的前缀和
    那么不合法状态就是对于区间[l,r]中的每一个数如果减一个L那么A[r]-A[l-1]<0则
    A[l-1]>A[r] 如果都用R减去这个数 那么A[l-1]>A[r]为不合法状态
    于是问题就转换为了一个求前缀和逆序对的问题
T3:搜索 对于k=1的数据可以直接求解  对于其他数据可以进行搜索 判断对于当前这个葱是和
    前面的放在一个栅栏里还是自己再用一个栅栏  最终去最优解  剪枝:最优化剪枝

9.25测试题

T1:题意 -> 一个字符串是否同时存在独立的AC串和CA串  做法 -> 记录下每一个AC出现的位置(只记录
    A的位置)和每一个CA出现的位置(只记录C的位置)记录下来 再扫一遍查看是否存在两个位置(一个A
    的位置一个C的位置)差距≥2 如果存在则输出YES 否则输出NO
T2:利用宽搜扩展状态每次用当前状态尝试几种操作然后判断这种状态是否出现过 如果没有出现过就放入
    队列否则跳过 注意边界T

洛谷2884 每月的费用

二分答案

判断答案是否可行时 必须判断单个的是否比二分的答案大 如果大 则直接返回0 (必须判断 否则会WA)


9.20日考试

T1:模拟  坑点:注意闰年二月的天数
T2:堆  用小根堆记录每一个位置被占用的时间  每次让第i个去被占用时间最小的位置 最后输出堆顶
T3:枚举+贪心 如果要放1*2的一定放价格最大的 1*3的同理
坑点:2*2的网格无法放1*3的物品  如果只放1*3最终会剩下2*2网格的只有2*i(i%3==2)的背包会
出现这种情况 所以枚举只能枚举1*3的放多少个 根据前面的坑点可以计算出1*3最多放多少个 剩余
的体积放1*2的物品即可 然后取最大值

洛谷2419 牛大赛

Floyd

用f[i][j] 表示i可以打败j
如果 对于i 可以确定它和其他点的关系 则这个点的排名就可以确定


洛谷1849 拖拉机

spfa

确定边界 跑spfa


洛谷1705 爱与愁的过火

DP

用f[i][j]表示选i种菜价格为j元的可能有几种

1
2
3
//核心代码
F(i, 1, m) R(j, r, 1) F(k, a[i], t)
f[j][k] += f[j-1][k-a[i]];

洛谷1638 逛画展

枚举

枚举以每一点为左端点的最小区间 更新答案


洛谷1022 计算器的改良

模拟

未知数的系数作为分母 常数项 作为分子

对于等号右边的在相加时乘-1


洛谷1037 产生数

通过Floyd 求出哪两个数之间可以转换 记录每一个数 可以有几种转换

枚举给的数中包含哪些数字 用乘法原理


洛谷1062 数列

模拟

找规律 k的i次幂的位置在2的i次幂

而从k^(i-1) ~ k^i 之间的数则是由k^(i-1)和前(2^(i-1))个数分别求和得到


洛谷1077 摆花

DP

用f[i]表示摆到第i盆的可能数

f[i] = ∑f[i-k] k∈[1,num[i]];


洛谷1209 修理牛棚

DP

用f[i]表示到达第i个牛棚需要的总长度是多少

f[i] = Min(当前这个牛棚从新用一个模板,与前一个牛棚用同一个木板)
f[i]=Min(f[j]+a[i]-a[i-1], f[j-1]+1);

注意:每一必须将f[0]赋一个极大值


洛谷1213 时钟

枚举

枚举九种操作各需要多少次 每一种操作最多只能用3次

对于每一时钟看看对于这个时钟有影响的有多少次操作 然后判断时钟最终是否变为12点


洛谷1214 等差数列

模拟

想给出的数列从大到小排序 然后确定前两项 往后推n项


洛谷1327 数列排序

对于给出的序列 进行排序

对于一个序列中的数a 如果a在原序列中的位置与排序后的位置不同 就将原序列中占据a排序后的位置的数与a交换
同时更新答案和调换的那个数的目前位置


洛谷1353 跑步

DP

用f[i][j]表示i分钟此时疲劳度为j时能跑的最远距离

1.如果疲劳度为0 那么枚举休息的时间的长短
f[i][0] = Max(f[i-j][j]) j∈[1, Min(i,m)]
2.当疲劳度为0时 还可以继续休息
f[i][0] = Max(f[i-1][0]);
3.可以选择在第i秒进行跑步
f[i][j] = Max(f[i-1][j-1]+d[i]);


洛谷1407 工资

使用低消法 如果当前这个位众数 那么 如果碰到一个和这个数不一样的就让计数器– 否则++
如果计数器变为0则证明这不是众数更新记录的众数 最终输出


vijos 1228拯救世界-星际大战

DP 思想

用f[i][j] 表示用i个导弹打掉状态为j的目标(二进制第i位表示第i个目标是否打掉)需要的最短距离


vijos 1250最勇敢的机器人

背包DP

用并查集分组 然后做一遍分组背包DP


cogs 2480筷子 :

一个数列其中存在一个数且仅存在一个数出现过奇数次 在1MB的内存下 找出这个数

位运算:如果一个数被异或偶数次则等于没有被异或


coge 1967相遇与问候

模拟:使用两个队列记录每一个时间两头奶牛的移动方向 然后开始模拟


streaming#5NOIP模拟赛T1 珠

记录每一个‘2’的位置 每次直接从当前位置开始顺时针和逆时针扫然后更新最长的长度


streaming#5NOIP模拟赛T2 兔农

手玩几个数据 就可以发现当k为偶数的时候不存在兔子死亡的时候 所以可以直接进行快速幂

而当k为奇数的时候存在一次兔子死亡的情况之后就不会再出现兔子死亡的情况 所以分别记录模k和模p的值当模k为1的时候让模p的值减1 然后再进行快速幂


streaming#5NOIP模拟赛T3 高维网络

dp + 组合数 + 容斥原理

我们用总的方案减去经过破坏点的方案数就是答案 用f[i]表示从A到i(i记录第i个破坏点)这个点的不经过破坏点的方案数 用g[i][j]表示从i到j可以经过破坏点的方案数

$$ g[i][j] = (各维度权值之和的阶乘) / (各维度阶乘之积) $$

例:二维情况

$$ (行数+列数)! / (行数! * 列数!) $$

$$ f[i] = g[A][x] - ∑f[y] * g[y][x] (y应该先被更新) $$


BZOJ 越狱

组合数

用总共的可能减去不重复的可能就是最终答案

如果要不保证当前这个与前一个不一样那么当前这个就有m-1中可能