做题思路记录

发表于 | 阅读次数:
字数统计: 1,294 字

JZYZOJ

Sep/17 P1219 一道图论的题， 可以DP拿来做， 大概就是维护一个在当前节点所遇到的最小值， 和总价值的最优值。LA 3882 一道递推题，voj的数据挂掉了，于是到Poj上过了一下。这道题是来求约瑟夫问题， 进行倒退，f[n] 中储存的值为如果0为幸存者的话， 第一个点的人的序号。大概就是下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
using namespace std;
long long n,m,k,f;
int main() {
	while(scanf("%lld%lld%lld", &n,&k,&m) == 3 &&n) {
		f = 0;
		for (long long i=2;i<=n;++i) f=(f+k)%i;
		f = (m-k+1+f)%n;
		if(f<=0)f+=n;
		printf("%lld\n",f);
	}
}

Sep/18 P1828 一道图论题， 大概就是求一个拓扑序， 在进行拓扑序的同时维护一个数组， 来保证是每个节点通过拓扑序中最大的消耗值， 然后维护答案即可。　P1843 一道差分， 区间的大量操作， 然后求区间的最后结果很多时候都可以用差分来做 P1888 一道二分题， 注意如果题中出现最大的最小值或者最小的最大值的时候就要往二分的方向进行考虑， 二分+判定的效率是很高的

Sep/19 P1822 一个很水的单调栈的题， 一共建6个栈然后进行模拟即可
P1895 一道可以用差分来做的题， 使a数组都变成一样的， 等同于将f数组除第一项以外都变成0。因为对a数组的区间加减1的效果相当于对f[i], f[j+1]两项进行操作， 其实就是f数组中正负两个全部的权值和中绝对值最大的那一种数会消耗更多的操作， 而第一个就是一个没用的可以当做f[i]前一项的量， 而且a数组最后的值取决于f[1]里的值， 由于f正负权值和的绝对值之差这么多种可能可以在f[1]上加减， 所以a的数列的可能出现的情况就为 abs(p-q)+1 种 P1835 一道贪心， 区间内操作， 直接按照右端点进行排序， 左端点作为次要特征，然后优先填满右端点的那几个， 这样就能保证贪心是正确的.

Sep/20 P1824 一道搜索题， 第一遍打TLE了， 很懵逼， 我从每一个老师开始BFS显然效率十分低， 最后还是看了下学弟的代码（丢人）。 我承认自己搜索不是很好， 所以以后要注意锻炼这种题， 大概就是把所有的1点入队 ， 然后维持一个时间变量， 这个量的维护很巧妙：

1
2
3
4
5
int flag = tail;
for (int i=head; i<=tail; ++i) {
		if (i > flag)  flag = tail,++ans;
    	. . . 
}

这样可以维护BFS的层次， ans里存的就是第几层拓展。P1813 这是一道数论题， 该来的总算是来了， 不过自己想是根本没有思路的。详情请参考题解。

Sep/21 今天键盘到了， 感觉还行， ikbc C104 红轴感觉就是轻， 而且真的会出现误触的情况。 以后还要好好练习打字， 不能辜负这个键盘。 加油吧， 为了自己的梦想努力一把！
今天一上午把treap树过了一下， 把之前的东西整理了一下， 学习了一下fread。下午计划打几道题
下午沉浸在机械键盘的舒适感中无法自拔， 于是乎又没刷多少题。过掉了一道这个题 P1871 一道迭代加深搜索， 然而并没有一眼看出来。 还是因为太菜了 . . .

Sep/22 上午做了一道 P1866 自己想出来的，等下再写下思路. 这其实是一道很水的一个模拟吧， 其实也不很好给这道题分一个类别。 思路大概就是先找到第一个满足情况的奶牛然后删除之后的所有的这个奶牛的周期， 直到全部删完为止。

Sep/25 三天假期结束， 时间越来越上。 这星期打算把往年的Noip题都再重新做一遍， 来大概熟悉一下题的难度。今天做了Noip2017的前2道题， 第一题就是那一道很弱智的小学奥数题。 第二题就是时间复杂度这一道十分恶心的一个大模拟。 然而这题真的很恶心， 会有很多的细节， 像这种题在今年的Noip上应该还会出现。要提高自己的代码能力了。 虽然这种题好像思维难度并不是很大， 但是仍然会占据很大一部分的分数。 晚上在裕神的指导下A掉了一道锣鼓月赛的水题 P4889 kls与flag 不得不说这次洛谷的月赛是真的比较水， 技术含量比较低. . . 这就是一个比较水的模拟题， 离散化一下就好啦，可能还会有一点斥容的思想。反正就是很水的一道题