Spy97 - 个人主页动态

2019-10-25 09:35

已编辑

题解 对于     (    x   1    ,    y   1    )   ,   (    x   2    ,    y   2    )    (x_1,y_1),(x_2,y_2)   (x1,y1),(x2,y2)确定的抛物线       y   1    =    x   1   2    +   b   ×    x   1    +   c    y   2    =    x   2   2    +   b   ×    x   2    +   c    y_1=x_1^2+b\times x_1+c \\ y_2=x_2^2+b\times x_2+c ...

0 点赞评论收藏

2019-10-25 09:35

已编辑

中国人民解放军国防科技大学 C++

codeforces 1083E The Fair Nut and Rectangles 动态规划单调性优化

题意 给出n个长方形，每个长方形有一个权值，要求选其中一些长方形，使得面积并减去权值和最大化 题解 首先     d   p    dp   dp方程很好想      d   p   [   i   ]   =   m   a   x    {   d   p   [   j   ]   +    y   i    ∗   (    x   i    −    x   j    )   −    a   i    }     dp[i]=max{\{dp[j]+y_i*(x_i-x_j)-a_i\}}   dp[i]=max{dp[j]+yi∗(xi−xj)−ai} 由于是      ...

0 点赞评论收藏

2019-10-25 09:36

已编辑

中国人民解放军国防科技大学 C++

ZOJ 4102 浙江省第16届大学生程序设计竞赛 C题 Array in the Pocket

题意 给     n    n   n个数，重新排列，要求每一个位置，新序列和原序列不能相同，字典序最小 题解 要求字典序最小，所以肯定是从前向后去填数 对于每一个位置，一次从小到大枚举可以选择的数，如果填之后，后面的依旧有解，那么就确定这个位置要填的数，否则继续枚举 关键在于判断后面是否有解 假设原序列中从当前位置开始到结束的构成     a    a   a；还剩下的可选的数为序列     b    b   b 例如：      4   ,   1   ,   3   ,   2    4 ,1, 3, 2   4,1,3,2 确定了第一个位置选     1    1   1之后，对应的 ...

0 点赞评论收藏

2019-10-25 09:36

已编辑

中国人民解放军国防科技大学 C++

ZOJ 4100 浙江省第16届大学生程序设计竞赛 A题 Vertices in the Pocket

题意      n    n   n个点，一开始没有边，有两种操作 一是连接点     (   x   ,   y   )    (x,y)   (x,y) 二是假如向图中加入     k    k   k条边，问最小、最大的联通块个数分别是多少 题解 最少联通块个数，就是加入的边都连接两个不同的联通块 最多联通块个数，首先要把各个联通块补成完全图，如果还有剩的边，则按照联通块的大小从大到小排序，每次合并最大的两个联通块，直到没有边剩下 问题的关键是如何求解最多联通块个数，暴力排序是肯定不行的 线段树+二分      S   e   g   [   l   ,   r   ]    Seg[l...

0 点赞评论收藏

2019-10-25 09:37

已编辑

中国人民解放军国防科技大学 C++

ZOJ 4097 Rescue the Princess

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5986 题意      n    n   n个点，     m    m   m条边的图，询问     z   ,   x   ,   y    z,x,y   z,x,y，是否能找到     x    x   x到     z    z   z，     y    y   y到     z    z   z没有重复经过路的方案。 题解 边双联通，进行缩点，然后用LCA判断。 代码 #include<bits/stdc++.h> #define N 3...

0 点赞评论收藏

2019-10-25 09:37

已编辑

中国人民解放军国防科技大学 C++

华中科技大学程序设计邀请赛网络赛 F War

题意 给出一个n个点的树，询问编号在一个区间内的点到给定点的最近距离。 题解 分块暴力求解，整块中用SPFA预处理，零散的用LCA求解。 首先根据内存限制，计算出打开能开     200   ∗   N    200*N   200∗N的数组，所以，每     500    500   500个点为一块，在块内跑一边SPFA，求出块内的点到其他点的最短路。 询问区间     [   l   ,   r   ]    [l,r]   [l,r],分为多个整块的和多个零散的在块以外的，整块的就用之前SPFA处理的求解，零散的就分别于目标点做LCA，求最小值即可。 需要注意的是，因为要大量求解LCA...

0 点赞评论收藏

2019-10-25 09:37

已编辑

中国人民解放军国防科技大学 C++

codeforces 1140E Palindrome-less Arrays

题意 给出n个数，其中值为-1的需要从[1,m]中选一个数替代。要求替代后，不能出现某个子序列是回文的，求方案数。 题解 题目要求不能是回文，这就等价于不能出现     a   [   i   ]   =   =   a   [   i   +   2   ]    a[i]==a[i+2]   a[i]==a[i+2]的情况,这个转换很重要。 那么我们就可以根据奇偶分开来处理，答案就是两者的乘积。 接下来是具体求方案数 设序列      A   ,   −   1   ,   −   1   ,   .   .   .   ,   −   1   ,   −   1   ,   B    A...

0 点赞评论收藏

2019-10-25 09:38

已编辑

中国人民解放军国防科技大学 C++

codeforces 1140F Extending Set of Points

题解 将     x    x   x坐标相同的点连接到一起，将     y    y   y坐标相同的点连接到一起，每个联通块的     x   、   y    x、y   x、y坐标的种类的乘积的和就是答案。 对于第     i    i   i个联通块（集合），用     n   x   [   i   ]    nx[i]   nx[i]表示其中     x    x   x坐标的种类数，     n   y   [   i   ]    ny[i]   ny[i]表示其中     y    y   y坐标的种类数，     n   x   [   i   ]   ∗   n   y...

0 点赞评论收藏

2019-10-25 09:38

已编辑

中国人民解放军国防科技大学 C++

Codeforces 548 E Maximize Mex

题意 有     n    n   n个人，每个人有一个属性值      c   i     c_i   ci，并属于唯一的一个俱乐部      b   i     b_i   bi，有     d    d   d天，每天指定一个人离开他所属的俱乐部（以后不再回来），离开后，每一个俱乐部每天要推举一个人，每天被推举上来的人的属性值构成序列     S    S   S，要使     S    S   S的     m   e   x    mex   mex值最大，输出每天的     m   e   x    mex   mex最大值。 mex是指在一个序列中没有出现的最小自然数，在博弈...

0 点赞评论收藏

2019-10-25 09:38

已编辑

中国人民解放军国防科技大学 C++

牛客练习赛42 出题的诀窍

题解 对于每一个数，算贡献，对于有相同的数，我们只计算先出现的数的贡献。 对于第     i    i   i行的数     x    x   x,设前     i    i   i行中与     x    x   x重复的个数分别为      a   1    ,    a   2    ,   .   .   .   .   .   .   ,    a    i   −   1     ,    a   i     a_1,a_2,......,a_{i-1},a_{i}   a1,a2,......,ai−1,ai,那么这一行这个数的贡献为       a   i    ∗  ...

0 点赞评论收藏

2019-10-25 09:39

已编辑

中国人民解放军国防科技大学 C++

CSP2018年12月 CIDR合并

#include<bits/stdc++.h> #define N 100010 #define LL unsigned int using namespace std; int n,m=0; char x[30]; vector<int> th; bool f[N]; struct node { LL a;int b,c; bool operator < (const node z) const { return a==z.a?b<z.b:a<z.a; } }c[N]; int pp(char *s) { th.clear(); int t=-1; ...

0 点赞评论收藏

2019-10-25 09:39

已编辑

中国人民解放军国防科技大学 C++

ICPC 2018 焦作 C题 Supreme Command

   题意 给出一个     n   ×   n    n×n   n×n的棋盘，保证每行每列只有一个棋子，给出多种操作，将所有棋子先上/下/左/右移动     k    k   k步（遇到边界则停止移动），提问某一个棋子的现在的位置或问当前有多少对棋子是在一个格子里的。 题解 棋盘的两个方向可以分别考虑，我们现在只考虑水平方向 用区间     [   l   ,   r   ]    [l,r]   [l,r]表示对于初始棋盘来说，水平坐标在     [   l   ,   r   ]    [l,r]   [l,r]范围内的棋子是没有触碰到边界的 比如样例中的棋盘，向左移动2格后，只有...

0 点赞评论收藏

2019-10-25 09:39

已编辑

中国人民解放军国防科技大学 C++

2018 ICPC 焦作 H题 Can You Solve the Harder Problem?

  题意： 给出n个数，定义 f [ l, r ]表示 区间 [ l , r ]的最大值，求所有 子区间的最大值的和，要求相同的子区间只能算一次 比如 数列 5  6 5 6 ， 区间 [ 1, 2 ] 和 [ 3, 4]是一模一样的，所以只能算一次。   题解： 假如抛开限制，那就是一个经典的算贡献的题目。 要求重复的区间只能算一次，很容易想到 相同的子串，又联想到后缀数组。 后缀数组中height数组表示字典序相邻的两个后缀的LCP，那么显然LCP就是重复的，我们不能算，如图  对于字典序排第K的后缀，其LCP的部分已经在K-1中计算了，所以我们要新算的区间是右端点在红色圈内的区间 这样就...

0 点赞评论收藏

2019-10-25 09:40

已编辑

中国人民解放军国防科技大学 C++

2018 ICPC 徐州区域赛 H Rikka with A Long Colour Palette

  题意： 给出n个数轴上的线段，进行每个线段染一种颜色，求混合有k种颜色的距离的和。 题解： 如果某一段被k条及以上线段覆盖，那么这一段一定是满足条件的，问题是如何求解方案数。 确定一条线段染什么颜色一定是根据左右端点判断得到的，所以我们只关心端点。 将左端点记为1，右端点记为-1，排序，相同的位置，右端点更靠前。 用一个队列保存没有染色的点，一开始所有颜色都在队列。 从小到大枚举位置 如果是左端点，并且队列不为空，我们就将这个线段染成队首的颜色 如果是右端点，如果这条线段染过色，就将该颜色放入队尾，进行回收 但是有几个细节要考虑 左端点时，如果所有颜色都染了，该染什么颜色？随便染吗？不是的...

0 点赞评论收藏

2019-10-25 09:40

已编辑

中国人民解放军国防科技大学 C++

ICPC 2018 南京 Mediocre String Problem

题解：  题目的意思就是在第一个串里找“s1s2s3”，第二个串里找“s4”，如上拼接后，是一个回文串，求方案数 可以发现，s1与s4是回文的，s2和s3是回文的，我们枚举s1的右端点，s1的长度乘以s2起始点为左边界的回文串的数量，累加就是答案。 现在分两部分，一是求s1，二是求以每个点为左边界的回文串的数量 一的话，就是求每个后缀匹配第二个串的LCP，可以用扩展kmp求得，也可以用hash加二分求得，二的话，用马拉车算法+前缀和就可以解决。 代码：  #include<bits/stdc++.h> #define N 1000010 #define INF 0x3f3f3f3f...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：