atcoder11-16日刷题总结_编程atcoder

1月11日atcoder总结
abc276-E 不能用二维char来存，用string数组。走过的不能再走了，走完后把位置标记为#(即在dfs开始时标记)。还需要一个cnt来计步数，当现在搜到的路径的长度<3时这个路径也不行。
abc274-A printf保留三位小数输出即可
abc274-B 直接枚举统计即可
abc274-C 暴力递归即可
abc274-D 可行性dp。但是如果把行和列放在一起处理会TLE考虑分靠搞两个dp(dpa,dpb)。dpa(i,j)表示第i个竖直移动操作是否能到达j，dpb(i,j)表示第i个水平移动操作是否能到达j。
abc273-A 循环求阶乘
abc273-B 关于四舍五入的问题，直接模拟
abc273-C 题目有点绕，开始根本没看懂。后来看懂后原来是就是一道简单的map统计题。
1月12日总结
abc273-D 首先想到的是暴力模拟，但是超时，考虑优化。现在需要的是要快速找到上下左右最近的障碍。想到可以用两套map<int,set >来存行和列的障碍，然后直接用set的二分找最近的即可，O(qlogn)解决。
abc278-E 暴力做法就是枚举覆盖的矩形(的左上角)，复杂度O(n^{4)，考虑优化。可以用二维前缀和用来算一个子矩阵中数出现的次数，这样可以压掉一层循环编程O(n}3)，可以过了。
1月13日atcoder总结
1.abc272-A 求和即可
2.abc272-B 用二维数组存储，然后后面枚举任意两个人然后判断关系即可
3.abc272-C 偶数=奇+奇 或 偶+偶，题目要求最大，所以计一下第一和第二大的偶数之和与第一和第二大的奇数之和取max。
4.abc272-D 一看就是bfs，每次往所有距离他距离为sqrt(m)的点bfs即可。
5.abc272-E 看了题解，看到是啥调和级数（雾），看了一些博客才弄懂。
6.abc271-A 原来是用printf(“%x”)搞得，但是忽略了前缀0的问题。后来用手动模拟ac了
7.abc271-B 用vector数组模拟n个数组即可
8.abc271-C 开个桶。从小到大找，如果这个值不存在最大值就会-1。注意：存的时候不能把>n的存了，否则会re。
9.abc271-D 典型的背包，只不过有个关联的条件就是同一张牌的正反面不能共存，在过程中把选择记录一下情况即可。
1月14日atcoder总结
1.abc270-A 这里面的分数二进制中的0/1就表示做题的情况，所以用位运算中的或运算即可。
2.abc270-B 按照题意模拟即可。
3.abc270-C 用vector来存储树，然后直接从x开始dfs，dfs到y时输出一路上的点即可。
4.abc270-D 设f_i表示剩下i颗石头时Takahashi可以获得的最大石子数，那么如果我们这次拿走了a_j颗石子，然后对方最多获得f_i-aj颗石子，剩下的i-f_(i-a_j)颗石子就是Takahashi的了。所以枚举这里的aj然后和自己的f_i取max，最后的答案就是f_n
5.abc270-E 二分。二分一个x，表示对于每一个篮子i，都拿出min(ai,x)个苹果的情况，显然我们需要的答案时最大的x。最后时就扫一遍所有的篮子，凑k苹果即可。
6.abc269-A 直接计算即可
7.abc269-B 左上角=i最小的#,右上角=i最大的#,左下角=j最小的#,右下角=j最大的#
8.abc269-C 题意开始有点难理解，最后需要反转答案。
9.abc269-D 开始用bfs，但是还是会tle。后来想到用并查集来合并，也可以用于最后的查询集合数
abc285
A 就是判断倍数(右节点=父节点*2)
B 完全按照题目的意思暴力的话i,l,k全都得枚举是O(n^{3)，看懂题意后可以缩到O(n}2)
C 按照位数统计即可，要开long long
D 开始有过O(n^2)的贪心(好像算是)的思路，但是会tle。后面将题目化为图上的判环问题。
E 想到过dp的思路，但是状态设计错了，设成一维了(雾)。然后想到了一维表示不了就用二维，结果在状态转移上不会了www，看了题解。
abc269
E 需要二分两次。第一次是二分目标点x的位置，对于中点mid，如果矩阵[(1,1),(mid,n)]的棋子数量等于mid，那么就是l移动，否则就是移动r。第二次二分y，也是同理。
abc268
A 偷懒用map统计
B 模拟一下是否为前缀即可
C 一个人在位置i，喜欢的菜在位置j，那么就移动j-i mod n格就可以完成。先预处理每一个人菜移到左、右、面前需要旋转的格数，然后枚举桌子旋转的格数去一下max即可。
D 读懂了题意，在dfs全排列的基础上，加入下划线数量的枚举即可。
abc267
abc267-A 用map记录每个星期所对应的答案
abc267-B 需要理解一会题意，看懂后就直接模拟。
abc267-C 将题目转换一下，可以用前缀和&差分优化。
abc267-D 01背包的变形，只不过第i个物品的价值变成了i * a[i]，还算挺明显的。
abc283
abc283-E 考虑dp。二维数组想了半天想不出来转移，搞三维。dp[N][2][2]，表示第i行的操作情况。转移的时候考虑第i行、i-1行、i-2行的操作情况即可。
abc281
abc281-E 想到一个算是滑动窗口的一个思路吧。i<m时，不需要删，需要插入。i=m时，计算前面k个数的总和。i>m时，需要滑动这个窗口，也就是添加新元素+删除旧元素。这一切都可以用vector暴力搞，不会超时。