写了个dfs，发现无法记忆化。然后就不知道了。后来想到其实最后肯定会找两个点来回走。显然来回走希望这段路是最短的，但是如果要走到这个点的话，距离又不能保证很短，所以就不会了。。 题目大意：给n个点在一维数轴上有不同的位置，现在给定一个初始点（不在n个点上），问访问m个点（可以重复访问）最少的路程。 思路：首先dfs肯定是可写的，但是复杂度太高了。应该可以想到比较理想的情况是在两个点之间走来走去。假设挑了两个点t和t+1,从p走到t的话这段距离并不一定是值得的（即可能走过来花的路程更长）。因此直接算是不可行的，不过我们采用枚举t和t+1（这里没想到。。）那么在到达t之前，我们一定是直接走的！乍一...

应该很容易看出是要用dp解决的，然后我开了个二维的dp[i][0/1]表示i号位置有没有火焰，结果好像发现情况分不太清楚。 题目大意：直接看题目吧。 思路：如果设置为dp[i][0/1]表示i号位置有无火焰的话，当前是1的时候，我们需要判断i+1位和i-1位的情况。但是由于dp从小到大，所以我无法判断i+1的情况了，于是我就做不下去了。后来看了题解，发现有人用这个二维dp做的。居然直接去判断后面i+1位的情况。。。居然还可以这样，哎，对dp的理解太浅了。 看了大部分的题解是，dp[i][0/1][0/1]表示第i个位置有无火焰并且第i+1个位置有无火焰的方案。这样子的话，从上一个位置转移过来的...

这道题目一开始直接写了个O(n^3*m)的dp上去，居然过了。 题目大意：有N块木板，每块木板长度都为M，把每块木板分为M个格子，每个格子能涂红色或蓝色，每个格子只能涂一次。每次涂只能选一段连续的区域涂。现在已经给定了每块木板格子上想要的颜色，问给T次涂色机会，一共可以让多少个格子能够涂出想要的颜色。N，M < 50,T < 2500 思路：一开始想了个三维的dp，dp[i][j][k]表示前i块木板且当前木板前j个格子涂了k次的最大值。那么就有：dp[i][j][k]=dp[i][t][k-1]+max(sum[i][j]-sum[i][t],j-t-(sum[i][j]-sum...

prim和Kruskal太久不打，都忘光啦。 题目大意：给n个点和m条边，每个点有一个高度h[i]，给定的m条边都有三个参数u,v,k表示u和v点有一天长度为k的边。其中这条边只能从高度高的地方连向高度低的地方。（两个点高度相同时就是无向边，否则是有向边）现在你可以从点1开始，问最多可以访问到的点的数量，以及在访问尽量多的点的前提下，让总路程最短。他有一种特异功能，可以无消耗无限制的回到之前去过的点。n<=10^5,m<=10^6 思路：首先根据题意我们可以完成建图。然后判断最多的点数量，我们可以从1开始直接bfs或者dfs求连通块数量。接着考虑第二个问题，其实如果是无向图，就变成...

打了20分钟的时候突然被叫去干活了。。心急火燎的交了A题。然后在8.50的时候坐下来想B题，最后在回寝室的床上打完了。。 赛后补了C题。 这里只放了前三题的题解，第四题开始不会了。。  A CCA的词典 可以证明，对两个单词进行排序，如果排序以后相同，那么就可以认为两个原单词是一样的。注意到单词长度<=2。所以我们直接比较两个位置的字母排序，然后哈希就可以了。  代码： #include<bits/stdc++.h> using namespace std; int t[100000]; int main() { int n; string s; cin>>n; ...

一个比较裸的题目吧。 题目大意：给n个数m次询问。每次询问一个区间[l,r]和一个数k，问区间[l,r]中小于等于k的数字个数。n,m<=10^5，a[i]<=10^5 思路：直接暴力查找肯定是不可行的。直接开桶的话，空间上也不允许。但是我们可以分块。把n个数分成n/sqrt(n)个块，每个块里sqrt(n)个数。最后一个块可能不足sqrt(n)个。然后对每个块里的数字进行统计。由于n<=10^5，最多分出sqrt(10^5)=320个块左右。那么我们可以开一个数组c[320][100040]表示第i个块中数字j出现了多少次,从时间和空间上都是开的下的。统计完以后我们可以再f...

数学也太难了QWQ 题目大意：给一个n*n的矩阵，对于矩阵的每个元素a[i]∈{0,1,2}其中每行的a[i]的和为2，a[i][i]=0a[i][j]=a[j][i]问满足条件的矩阵有多少个。n<=10^5 思路：看题目感觉是个递推，但是完全不知道怎么做。参考了题解：本题给出的矩阵我们可以联想到图的邻接矩阵（太妙了）显然根据题目的限制，这是一个每个点最多有两条边的无向图（妙啊）并且图中没有自环（a[i][i]=0），由于每个点最多两条边，图中只有简单环（不会存在一个点是多个环的公共点）。我们要求的就是这样的图的数量。 假设我们已经知道f[n-1]表示n-1个点时候的方案数。那么我们现在...

这场的前三题都挺水的，第4题骗分也有80，挺良心的。。  A 小L的作文 算送分题，直接一个for循环计数一下就可以了。   B 小L的多项式 根据题意，f(x)可以O(n)计算得到，求f(x1)...f(xm)的话，再for循环一遍就可以了。复杂度O(n*m)。由于n,m<=1000，所以可以直接计算。 C 小L的编辑器 对于本题，我是这么考虑的。先输入第一个字母建立一个根节点，然后如果往左就在左子树上建一个新节点，如果往右就在右子树上新建点，然后转移到当前点继续相同的操作。那么会发现最后的结果是这棵树的中序遍历输出。  代码： #include<bits/stdc++.h&gt...

我好像忘记背包怎么写了。。写二维居然挂掉了。。改了一维才过。 题目大意：题目解释起来比较复杂，直接贴原文链接：https://ac.nowcoder.com/acm/problem/14704 思路：看题目就给人浓浓的背包的感觉。显然不可能直接背包。我们假设最后已经得到了答案，那么我们必然会选择其中的一些菜肴，而且这些菜肴一定有固定的顺序去烹饪来使得美味值最大。我们考虑最后答案是两种菜肴a1和a2。最终答案有两种：ans1=a1-t1b1+a2-(t1+t2)b2 和 ans2=a2-t2b2+a1-(t1+t2)b1要让选择顺序为a1,a2的话，我们需要令ans1>ans2化简以后就是...

憋了一天，终于把这题做出来了。 题目大意：给一个长度为n的序列，现在可以从中移除m个元素得到一个新序列，问一共可以得到多少个互不相同的新序列。n<=10^5，m<=10思路：dp还是比较容易想到的。令dp[i][j]表示前i个元素移除了j个以后的方案数。那么显然第i个元素可选可不选，我们可以得到转移方程:dp[i][j]=dp[i-1][j]+dp[i-1][j-1]。但是这样会出现重复，举个栗子：2 4 1 2 2 1如果移除3个数字，我们移除[3,5]的数字和移除[4,6]的数字得到的结果是一样的。其实就是如果有两个数字相同，那么中间的数字全部被移除的时候（如果可以被全部移除）...

我觉得我的数学需要回炉重造。。 题目大意：给一个n个元素构成序列，从中选取子序列使得选取的子序列能够满足i<j,a[i]^j<a[j]<i。问一共有多少种子序列选择方案。n<=100,a[i]<=100 思路：其实我一开始的就想当然的认为了如果i<j<k,若a[i]^j<a[j]^i，那么就会有a[i]^k<a[k]^i。这样的话就可以用dp解决。令dp[i]表示以i为起点往右的满足条件的子序列方案数。那么对于i来说，我们可以枚举i右边的j，若满足a[i]^j<a[j]^i，那么我们有f[i]=∑f[j] 关键是a[i]^j和a[j]...

这题对我来说有一点点点点点....难！看题解都理解了好久。 题目大意：给一个n个点m条边的无向图，有些边上已经标记了边权0或者1，现在要给剩下的边标记0或1，使得图中任意的环上的边异或和为0。问一共有几种标记方案。 思路：本题有一个很巧妙的转化，就是把边权转为点权。对于一条边w(u,v)，我们将边权转移到两个端点上，赋予u和v分别为各自点权au和av，那么我们令边权=au^av。显然，在环上每个点有2条边，那么求环上的边权异或就是求每个点异或2次的异或和。也就是，每个点权会参与2次异或。那么我们可以得到，环上的异或和一定为0。而不构成环的点随便选，因此每个点选0/1，一共n个点的连通块，一共会...

居然是二分，真的是没想到。。。 题目大意：给n个数字ai，从这n个数中取任意长度不小于k的区间，对每个区间都获得其中的第k大的数。将这些区间中获得的第k大的数都放入数组b中，问数组b中的第m大的数字是多少？n<=100000,0<=ai<=10^9 思路：枚举区间肯定不行。这里考虑二分答案。假设二分当前答案为x，那么我们如果我们可以找到超过m-1个区间，其中这些区间中的第k大数字大于x，就说明当前二分的答案太小了。二分策略是成立的。那么如何查找到底有多少个满足条件的区间呢？这里用尺取法，我们维护两个指针l,r，一开始l=r=1，接着我们往右移动r，同时统计大于x的数字个数t，...

这道题想了很久，但是自己思路局限性太大了。 题目大意：比较麻烦，就不解释了。原文贴一下：  从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。请在这里输入引用内容为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1.请在这里输入引用内容现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。  思路：这题主要难住我的在发功的地方。一开始想的是，假设不考虑发功，从前往后按照时间...