WOJ题目分析|江阴雨辰互联

2023年7月30日发(作者：)

打*号的是unsolved problem，出于某些原因，所有的计算几何全打*了。。知道原因的轻喷>.<。

1001 a+b

1002 找每段的单词个数，仔细点模拟就可以了

1003 阅读理解题。。把关系找出来就行了

1004 把几个单位换算清楚就可以了，简单题

1005 裸地01背包，f[i]=max(f[i-w[j]]+v[j])。

1006 k的范围又没给啊！！对k个询问每个用spfa做一次就OK了，不给数据范围真心难受。可以默认认为k很小了。。

1007 对于每一维找8个数中的最大值，最后加起来，水题

1008 源点和每个人连一条流量为k的的边，人和动物连一条流量为1的边，动物和汇点连一条流量为1的边，若最大流等于动物数量，则yes，否则no。

1009 根据条件把能建的边建上，然后跑spfa即可。

1010 打表或者其他方式可得到规律，除了最大的数其他的数都会消去，最大的数出现次数为2^(n-1),这个乘积就是答案

1011 很巧妙的DP，f[n]表示n个人组成队伍的方案数，假设我们要求f[n+1]了，那么第n+1个人的位置一定在某只队的最后，我们枚举这只队包括前面有x只队，那么n+1前面一共有x*3-2个人，后面有n+1-x*3个人，有DP，f[n+1]=sum(f[x*3-2]*f[n+1-x*3]*c(n,x*3-2))。特别的当（n+1）%3！=1时，第n+1个人还可以作为最后一支队的最后一人，这时答案要再加一个f[n]。

1012 很不错的题目，首先与处理出每个格子往右边延伸最多能多长，然后从左到右一列列的扫，每一列用一个单调队列维护答案，如果当前加入的数比队尾大，就统计队尾的答案然后出队，最后把本数入队。复杂度O（n2）。

1013 如果数据范围到了10W的话就只能用字符串最小表示法或者倍增算法来做，这个题直接暴力出所有的字符串排序即可。

1014 求3阶行列式的值，沙路法什么的随便水就可以了。。

*1015 No such problem. 1016 把x离散，然后对每个x开个vector，把y放到各自x对应的vector里排序，最后看所有的vector的所有匹配的数的平均值是不是一样的。

*1017 计算几何。

1018 首先找出序列中所有的置换，然后对于每个置换有两种方法将其调成合法。1.每次用置换中最小的数去和其他数换，ans=sum+min*(num-2）。2.用全局最小的元素换所有元素，最后还要把这个元素换出去，ans=sum+allmin*(num+1)。对于每个置换两种方案取min值相加就可以了。

1019 代码题，按照题目做就可以了。

1020 跟着操作模拟即可

*1021 No such problem.

1022 把所有的题目按T排序，然后按顺序插入到集合中，如果集合中题目的数量比当前题目的T小，则直接插入，否则如果当前的数的C比集合中最小的数小，就不加入，计算代价，否则把集合中最小的数拿出来计算代价，把这个数插入集合中，最后的总代价就是答案。

1023 有一种方法可以很快的求出一列数每k个数的方差，就是求出最开始k个数的方差，假设mid为前k个数的平均值，suma为前k个数的和，方差=suma2-2*suma*mid+mid*mid*k，算2->k+1的时候只用根据第一个数和第k个数修改suma，mid就可以快速求出现在的方差。本题的做法是枚举k，用上面方法预处理出所有区间的方差，然后dp[i]表示以i为结尾的方差和最小多少，dp[i]=max(dp[j]+g[j][i-1]),最后dp[n]就是答案。

1024 枚举起点然后DP的话肯定会Tle，正解是把所有边乘2加起来然后减去一个树的直径

*1025 计算几何。

1026 很简单的DP，dp[i][j] = max(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])+value[i][j],最后dp[n]中取最大值。

*1027 很有意思的题目，求做法。

1028 两个点横纵坐标和奇偶不同肯定无解，其余有解，最优解是先把一个棋子移到另一个的同一行（或者列），然后交叉着走到那个点

1029 按照题意转换即可，简单题 *1030 计算几何。

1031 原问题：x1+x2+…+xm=N,(0<=x1<=k,xi<=xi+1<=xi+k),问方法总数。最开始写的是dp[i][j][k]表示到第i个人，总共取了j个，最后一个人取了k的方法总数，复杂度O（n4）可以优化成O（n3）但是常数比较大加上高精的复杂度会TLE，可以这样考虑，假设x1=a1,x2==a1+a2+…+am,易知a1-am均为0-k的数，所以有na1+(n-1)a2+…+an=N,(0<= an<=k),dp[i][j]表示到了第i个数，总共用了j个巧克力的方法总数，dp[i][j]=sum(dp[i-1][j-i*k])，复杂度O（n3）

1032 暴力小的一维的取法对于每种取法在大的一维取最优值

1033 大于（a-1)*(b-1)的数一定可以用a,b的线性组合来表示。证明：因为a和b互斥，所以a*0,a*1…a*(b-1)一定是0->b-1的一个排列，对于任何大于(a-1)*（b-1)的数c，一定存在一个k(0<=k

1034 N个平面可以把空间分成(n*n*n+5*n+6)/6份，证明不会=

=。。。

1035 问一个数除2向上取整是多少，可以用ceil，有个简单的方法就是把n加1直接除2

1036 很简单的DP dp[i] = dp[i-1] + dp[i-2] +dp[i-3] , 要写高精

1037 把区间复制一遍，从左到右如果油够就带着，不够就清零，算出到每个点的油量，最后看油量是否有一段长至少为n的序列，有就yes，否则no

1038 把两两间距离算出来就是裸地最小生成树了。

1039 维护一颗线段树，记录L之后的最近的空格的位置，查询和插入均为nlogn

1040 找出现数最多的数 map水水就能过了

1041 dp[x][y][f]表示走到(x,y)，被咬了f口，记忆化搜索看是否能走到终点即可。

*1042 计算几何。

1043 是数据范围太小了了还是数据太弱了，这个题提交的都是暴力的做法，而且居然还能A= =。正解是类似后缀数组的处理，先把所有字符串排序，然后每相邻两个字符串暴力求一个lcp，得到一个lcp数组，然后对于每个查询都在对应的lcp区间里取最小值，线段树rmq均可。复杂度排序O(N*L*LOG(N))+询问O（m*q*logn）。

*1044 计算几何。

1045 简单的模拟题

1046 冒泡排序的交换次数就是逆序对的个数，找数列有多少逆序对即可。

1047 n2递推一下就可以了，水题

*1048 计算几何。

1049 dp[i]表示以i结尾最少可以由多少个单词构成，如果单词j是i的后缀，那么dp[i]=min(dp[i],dp[i-length(word[j])]+1);

1050 裸的最小生成树，prim和kruscal均可。

*1051 好像写起来很麻烦的样子。。没什么好的想法。。

*1052 No such problem.

1053 也是一道很恶心的题目。。可以把两个可以消去的单元结合起来看成一个元素，元素值为其字典序的大小，然后就可以用一个集合来维护了，首先把所有边缘的可以消去的组放到集合里，每次从集合中取出最小的组，消去，然后把因为这个消去而变得有效的组加到集合中，直到集合为空，如果还有没有消去的元素，那么就error。

1054 题意：给一个大串和一个小串，小串可以从任一位开始，然后无限循环，构成新的串，问两串之间最长公共子序列。最朴素的想法就是枚举从哪一位开始，然后模拟匹配，答案取max，复杂度O(N*M*M)肯定会TLE。我们可以把小串自我复制多次(不小于大串长度）然后求两个新串的最长公共子序列，利用后缀数组的倍增算法可以把复杂度降低到O(n*logn),但就本题而言，后缀数组的大常数仍然会导致超时。可以利用扩展KMP把字符串正着做一次，倒着做一次，然后枚举每一位算出该位从子串第一位向后匹配，前一位从子串最后一位向前匹配的和，更新答案，复杂度O(N)。常数还是略大。。擦着时限的边过了，rank1只跑了400MS，理论上小串这种形式应该还是有性质可以挖掘的，求正解。

1055 找出关系替换字符串，新手题

1056 2-sat入门，如果i和j冲突，那么i->j',j'->i,i'->j,j->i'。最后答案是2^scnt数量的一半，如果某个i和i'在一个scnt里，那么就无解。 *1057 计算几何。

1058 实在不知道怎么做。。打表找了个规律，规律还是挺好看的，求证明。。。

*1059 个人感觉题目有问题啊，或者谁来跟我说下为什么2 3 4 1 2 1 的结果跑出来是2 2

2 3 ？

1060 简单的数位DP，从高位往地位做，如果当前部分比以前小那么当前位选K最优，如果相等的话就看能否选K了，不能就选0，K=0的情况比较麻烦，可以单独写个特判。

1061 后缀数组，首先二分最长的公共前缀长度，然后对于长度将h数组分组，对每组的所有串用区间的贪心求出最多的互不重合的区间个数，返回即可，如果没有可行的分组就调整上界，反之调整下界。

*1062 计算几何。

1063 数据强了一点的k短路，这个题有个问题就是中间跑的时候会超内存，原因就在于每个点虽然只能出队k次，但是进队的次数绝对不止k次，只是说队列中最多只有k个这个点，这样导致队列中有很多不必要的点，最好的做法是应该是这个点进来以后发现队列中这个点的数量多于k，那么就删除最大的那个，因为这个点根本不会出队，但问题是因为k短路的队列是个优先队列，不容易找到每个点最大的点的位置，我的做法是直接卡每个点最多进队500次，不知道前面那种方法怎么做。

1064 和1040很像，map水之

*1065 计算几何。

1066 dp[i][j]表示上个动作是i，现在的困难度为j，转移是dp[i][j]->dp[k][j+diff[i][k]],最后在所有的dp[i][j]中取max。

1067 很经典的题目，因为n很小，所以把物品分成两半，每一半搜出所有的结果排序，然后一半在另外一半里面二分查找，复杂度O（2^(n/2)*log(2^(n/2))

*1068 插头DP还是很好看出来的。。问题是转移太麻烦了点了吧。。写了2次都写到一半写不下去了。。

1069 最长公共子串问题，后缀数组模板题，解法见09年国家集训队罗穗骞论文。

1070 暴搜，有点难写。 1071 维护一颗长度为n的线段树，记录每个人是否死掉了，然后每次循环的时候都先用公式找到当前要死的人是活着的人中的第几个，然后在线段树中找到这个人的标号，输出，然后删掉这个人。设上次死的人编号为x，现在有y个人活着，那么下一个人是活着的人中的第(x-1+m)%y个。题目描述有问题，最后还要输出一个空格。

1072 注意到数的范围很小，可以用DP来做，如果i是一个区间的终点，那么dp[i] =

max( dp[begin[k]-1] + length[k] ) , 最后dp[i] = max(dp[i-1],dp[i]) , dp[300000]就是答案。

1073 No such problem.

1074 用map存每个数存不存在，然后n2暴力，复杂度n2logn，强烈怀疑这个题的数据范围，n的真实范围其实只有100?那些500ms过的莫非是n3的算法=

=？！

1075 除了第四个人，其余人的转移方程为dp[k][j] = dp[k-1][j-1] + dp[k-1][j+1] , 关于4的处理可以先全部不算，如果询问是4的话就输出dp[k-1][3]+dp[k-1][5]。

1076 按照克鲁斯卡尔算法来做，每次合并一定会导致森林中树的数量减少1，一旦树的数量少于K的时候直接返回当前的答案就可以了。PS:不知道为什么这样是最优的，如果有可以cha的情况请联系我。

1077 两次DP，第一次f[i][j]表示把i到j变成一段合法序列需要的最少操作f[i][j]=min(min(f[i][j-1],f[i+1][j])+1,(如果i和j配套）f[i+1][j-1]）;第二次dp[i]表示以i为结尾的序列变成合法的最小操作数dp[i]=min(dp[j]+f[j+1][i])。

1078 裸的spfa，松弛条件按照题目说的改下就行。

1079 法雷序列，最坏的可能性虽然还是10^7,但是一般情况就是log(n)了，还是很好的方法。话说whu每年E鸣或者校赛总有一道法雷序列的题目。。。

1080 选的数为14的倍数后手赢，其余先手赢，证明比较简单，略去。

1081 裸的二分图匹配，如果某行列为1，就把这行和这列连条边，最后问的就是最少点覆盖，即最大匹配。

1082 把每个点拆成i和i’，连边i->i'，权值为1，如果i和j有边，就连边i'->j,j'->i，权值为无穷，特别的s->s',t->t'也为无穷，最后求s->t'的最大流即可。 1083 拓扑排序稍微改了一下，拓扑排序是把所有度为0的点入队，然后依次出队调整其他点，这个题就用个优先队列就可以了，其他不变，每次把队列中编号最小的点出队。

1084 有没有发现样例很熟悉呢= = 是的！去看1061吧。。。

1085 k短路问题，具体方法网上有好多，不说了。

*1086 不知道怎么做，某人跟我说去跑二分图匹配，10W个点的匹配。。匹。。配。。

1087 暴力枚举两个星星，看其他哪些星星在线上就行了，复杂度n3

*1088 找不到公式怎么破。。

1089 裸的spfa，水题。

1090 把所有的速度离散以后建线段树，把所有的蛇按照位置从大到小排序，然后对于每条蛇，查线段树中速度比他小的个数，统计到答案里，然后把当前速度插入到线段树中。

*1091 好像是个神题，没大看懂题意。。

1092 暴力跑出500W以内的质数和质数方幂的表，排序后查表即可。

1093 左偏树，算是入门的题目了吧。。不知道左偏树的可以去看国家集训队论文。

*1094 转移方程f[n]=f[n-1]*2+f[n-2]*2应该还是很好看出来的。。问答案有多少位。。这个也太无聊了点了吧。。

1095 暴力跑出所有的子局面然后构成一个DAG图，求该图上的最小路径覆盖即可。题目中会出现一开始就3个一行一列等情况，这种情况只要下本局就可以了。