REVIEW OF [PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing]

很早前看的paper,实现了一个非完整版的算法,只讲实现了的部分。
算法的目的我的理解是,对于一张图片,规定了某些像素集合A是不能变的,其他像素not A可以变,要把这个图片补全。
补全的素材来自图片,但是图片的某些部分不能作为素材。
经典的应用就是图片的障碍物去除。

大概的算法就是从图片能作为素材的部分提取出很多patch,比如以每个像素为左上角,大小是5*5的像素块,
用这些patch来填补空的地方。
对每个像素,会维护一个最优patch,表示和这个位置fit得最好的patch
恩 因为有些像素是不能变的 所以patch会受到不能变的像素的限制

一开始可以假设除了不能变的像素是原本的颜色,其他都是黑色啥的
每一次迭代都会根据最优patch生成新的图片,再根据新的图片计算新的最优patch blabla 但是不能变的像素的最优patch永远都是自己。

考虑怎么找最优patch
这篇paper的算法就是随机好几次,取最优
但是在算[i,j]位置的最优patch的时候,
假设[i,j]的当前最优patch是maps[i][j][2]
除了把好几个随机的patch作为决策,还会把[maps[i-1][j][0]+1, maps[i-1][j][1]]类似的四个方向的最优决策作为决策之一
这里就是这篇paper的重点,它认为如果某个点随机到了最优的patch,则可以传递到旁边,它旁边的点最优patch可能也就在这个点的最优patch的旁边。

为了优化结果,还使用了金字塔算法,先在低分辨率的图片中找到一些较优解,并把这个解传递到较高分辨率作为初始值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
//============================================================================
// Name        : main.cpp
// Author      : Steffen Bingel, Benjamin Welle
// Version     :
// Copyright   :
// Description : Reshuffling Implementation using PatchMatch
//============================================================================

// std lib includes
#include <iostream>
#include <cstdio>
#include <time.h>
using namespace std;

// opencv includes
#include <opencv2/core/core.hpp>
#include <opencv2/imgproc/imgproc.hpp>
#include <opencv2/highgui/highgui.hpp>
using namespace cv;
using namespace std;

// our includes
const int MAXPTR = 5;
const int PATCH_SIZE = 9;
const int inf = 0x3f3f3f3f;

Mat srcs[MAXPTR], tars[MAXPTR];
Mat maps[20];
Mat consts[20];

int dist(Mat m1, Mat m2)
{
    if (m1.size() != m2.size()) return inf;
    int ans = 0;
    for (int i = 0; i < m1.rows; ++i)
        for (int j = 0; j < m1.cols; ++j)
            for (int k = 0; k < 3; ++k)
                ans += (m1.at<Vec3b>(i, j)[k] - m2.at<Vec3b>(i, j)[k])*(m1.at<Vec3b>(i, j)[k] - m2.at<Vec3b>(i, j)[k]);
    return ans;
}

Mat getPatch(Mat src, int x, int y)
{
    return src(Range(x, min(src.rows - 1, x + PATCH_SIZE - 1)), Range(y, min(src.cols - 1, y + PATCH_SIZE - 1)));
}

void calc(Mat src, Mat tar, Mat consts, Mat maps, int rev)
{
    if (!rev)
    {
        for (int x = 0; x < consts.rows; ++x)
        {
            cout << x;
            for (int y = 0; y < consts.cols; ++y)
            {
                if (consts.at<Vec2i>(x, y)[0]) continue;
                Mat patchNow = getPatch(tar, x, y);
                int tx = maps.at<Vec2i>(x, y)[0], ty = maps.at<Vec2i>(x, y)[1];
                int nowDist = dist(patchNow, getPatch(src, tx, ty));
                if (x)
                {
                    int tx = min(src.rows, maps.at<Vec2i>(x - 1, y)[0] + 1), ty = maps.at<Vec2i>(x - 1, y)[1];
                    int td = dist(patchNow, getPatch(src, tx, ty));
                    if (td < nowDist)
                    {
                        nowDist = td;
                        maps.at<Vec2i>(x, y)[0] = tx;
                        maps.at<Vec2i>(x, y)[1] = ty;
                    }
                }
                if (y)
                {
                    int tx = maps.at<Vec2i>(x, y - 1)[0], ty = min(src.cols, maps.at<Vec2i>(x, y - 1)[1] + 1);
                    int td = dist(patchNow, getPatch(src, tx, ty));
                    if (td < nowDist)
                    {
                        nowDist = td;
                        maps.at<Vec2i>(x, y)[0] = tx;
                        maps.at<Vec2i>(x, y)[1] = ty;
                    }
                }
                int maxr = max(src.rows, src.cols);
                while (maxr)
                {
                    for (int k = 0; k < max(1, 5 - maxr); ++k)
                    {
                        int dx = rand() % maxr, dy = rand() % maxr;
                        if (rand() % 2) dx *= -1;
                        if (rand() % 2) dy *= -1;
                        int tx = maps.at<Vec2i>(x, y)[0] + dx, ty = maps.at<Vec2i>(x, y)[1] + dy;
                        if (tx >= 0 && tx < src.rows && ty >= 0 && ty < src.cols)
                        {
                            int td = dist(patchNow, getPatch(src, tx, ty));
                            if (td < nowDist)
                            {
                                nowDist = td;
                                maps.at<Vec2i>(x, y)[0] = tx;
                                maps.at<Vec2i>(x, y)[1] = ty;
                            }
                        }
                    }
                    maxr /= 2;
                }
            }
        }
    }
    else
    {
        for (int x = src.rows - 1; x >= 0; --x)
        {
            cout << x << endl;
            for (int y = src.cols - 1; y >= 0 ; --y)
            {
                if (consts.at<Vec2i>(x, y)[0]) continue;
                Mat patchNow = getPatch(tar, x, y);
                int tx = maps.at<Vec2i>(x, y)[0], ty = maps.at<Vec2i>(x, y)[1];
                int nowDist = dist(patchNow, getPatch(src, tx, ty));
                if (x < src.rows - 1)
                {
                    int tx = max(0, maps.at<Vec2i>(x + 1, y)[0] - 1), ty = maps.at<Vec2i>(x + 1, y)[1];
                    int td = dist(patchNow, getPatch(src, tx, ty));
                    if (td < nowDist)
                    {
                        nowDist = td;
                        maps.at<Vec2i>(x, y)[0] = tx;
                        maps.at<Vec2i>(x, y)[1] = ty;
                    }
                }
                if (y < src.cols - PATCH_SIZE)
                {
                    int tx = maps.at<Vec2i>(x, y + 1)[0], ty = max(0, maps.at<Vec2i>(x, y + 1)[1] - 1);
                    int td = dist(patchNow, getPatch(src, tx, ty));
                    if (td < nowDist)
                    {
                        nowDist = td;
                        maps.at<Vec2i>(x, y)[0] = tx;
                        maps.at<Vec2i>(x, y)[1] = ty;
                    }
                }
                int maxr = max(src.rows, src.cols);
                while (maxr)
                {
                    for (int k = 0; k < max(1, 5 - maxr); ++k)
                    {
                        int dx = rand() % maxr, dy = rand() % maxr;
                        if (rand() % 2) dx *= -1;
                        if (rand() % 2) dy *= -1;
                        int tx = maps.at<Vec2i>(x, y)[0] + dx, ty = maps.at<Vec2i>(x, y)[1] + dy;
                        if (tx >= 0 && tx <= src.rows - 1 && ty >= 0 && ty <= src.cols - 1)
                        {
                            int td = dist(patchNow, getPatch(src, tx, ty));
                            if (td < nowDist)
                            {
                                nowDist = td;
                                maps.at<Vec2i>(x, y)[0] = tx;
                                maps.at<Vec2i>(x, y)[1] = ty;
                            }
                        }
                    }
                    maxr /= 2;
                }
            }
        }
    }
}

void genera(Mat src, Mat tar, Mat maps)
{
    Mat counter = cv::Mat(src.rows,src.cols,CV_32SC4,Scalar::all(1));
    for (int i = 0; i < src.rows; ++i)
        for (int j = 0; j < src.cols; ++j)
        {
            for (int k = 0; k < 3; ++k)
                counter.at<Vec4i>(i, j)[k] = tar.at<Vec3b>(i, j)[k];
            counter.at<Vec4i>(i, j)[3] = 1;
        }
    for (int i = 0; i < src.rows; ++i)
        for (int j = 0; j < src.cols; ++j)
            for (int dx = 0; dx < PATCH_SIZE; ++dx)
                for (int dy = 0; dy < PATCH_SIZE; ++dy)
                {
                    int x = i + dx, y = j + dy;
                    if (x >= src.rows || y >= src.cols) continue;
                    for (int k = 0; k < 3; ++k)
                        counter.at<Vec4i>(x, y)[k] += src.at<Vec3b>(maps.at<Vec2i>(i, j)[0] + dx, maps.at<Vec2i>(i, j)[1] + dy)[k];
                    counter.at<Vec4i>(x, y)[3] += 1;
                }
    for (int i = 0; i < src.rows; ++i)
        for (int j = 0; j < src.cols; ++j)
            for (int k = 0; k < 3; ++k)
                tar.at<Vec3b>(i, j)[k] = counter.at<Vec4i>(i, j)[k] / counter.at<Vec4i>(i, j)[3];
}

void deal(Mat src, Mat tar, Mat consts, Mat maps)
{
    for (int i = 0; i < 10; ++i)
    {
        calc(src, tar, consts, maps, i % 2);
        genera(src, tar, maps);
    }
}

void UpCM(Mat mapsLast, Mat maps, Mat consts)
{
    for (int i = 0; i < maps.rows; ++i)
    {
        for (int j = 0; j < maps.cols; ++j)
            if (!consts.at<Vec2i>(i, j)[0])
            {
                maps.at<Vec2i>(i, j)[0] = mapsLast.at<Vec2i>(min(mapsLast.rows - 1, i / 2), min(mapsLast.cols - 1, j / 2))[0] * 2 + i % 2;
                maps.at<Vec2i>(i, j)[1] = mapsLast.at<Vec2i>(min(mapsLast.rows - 1, i / 2), min(mapsLast.cols - 1, j / 2))[1] * 2 + j % 2;
            }
    }
}

void DownCM(Mat mapsLast, Mat maps, Mat constsLast, Mat consts)
{
    for (int i = 0; i < maps.rows; ++i)
        for (int j = 0; j < maps.cols; ++j)
        {
            if (constsLast.at<Vec2i>(i * 2, j * 2)[0])
            {
                consts.at<Vec2i>(i, j)[0] = 1;
                maps.at<Vec2i>(i, j)[0] = min(maps.rows - 1, mapsLast.at<Vec2i>(i * 2, j * 2)[0] / 2);
                maps.at<Vec2i>(i, j)[1] = min(maps.cols - 1, mapsLast.at<Vec2i>(i * 2, j * 2)[1] / 2);
            }
            else
            if (i * 2 + 1 < constsLast.rows && j * 2 + 1 < constsLast.cols && constsLast.at<Vec2i>(i * 2 + 1, j * 2 + 1)[0])
            {
                consts.at<Vec2i>(i, j)[0] = 1;
                maps.at<Vec2i>(i, j)[0] = min(maps.rows - 1, mapsLast.at<Vec2i>(i * 2 + 1, j * 2 + 1)[0] / 2);
                maps.at<Vec2i>(i, j)[1] = min(maps.cols - 1, mapsLast.at<Vec2i>(i * 2 + 1, j * 2 + 1)[1] / 2);
            }
            else
            if (i * 2 + 1 < constsLast.rows && constsLast.at<Vec2i>(i * 2 + 1, j * 2)[0])
            {
                consts.at<Vec2i>(i, j)[0] = 1;
                maps.at<Vec2i>(i, j)[0] = min(maps.rows - 1, mapsLast.at<Vec2i>(i * 2 + 1, j * 2)[0] / 2);
                maps.at<Vec2i>(i, j)[1] = min(maps.cols - 1, mapsLast.at<Vec2i>(i * 2 + 1, j * 2)[1] / 2);
            }
            else
            if (j * 2 + 1 < constsLast.cols && constsLast.at<Vec2i>(i * 2, j * 2 + 1)[0])
            {
                consts.at<Vec2i>(i, j)[0] = 1;
                maps.at<Vec2i>(i, j)[0] = min(maps.rows - 1, mapsLast.at<Vec2i>(i * 2, j * 2 + 1)[0] / 2);
                maps.at<Vec2i>(i, j)[1] = min(maps.cols - 1, mapsLast.at<Vec2i>(i * 2, j * 2 + 1)[1] / 2);
            }
            else
            {
                consts.at<Vec2i>(i, j)[0] = 0;
                maps.at<Vec2i>(i, j)[0] = min(maps.rows - 1, mapsLast.at<Vec2i>(i * 2, j * 2)[0] / 2);
                maps.at<Vec2i>(i, j)[1] = min(maps.cols - 1, mapsLast.at<Vec2i>(i * 2, j * 2)[1] / 2);
            }
            if (maps.at<Vec2i>(i, j)[0] >= maps.rows || maps.at<Vec2i>(i, j)[1] > maps.cols)
            {
                consts.at<Vec2i>(i, j)[0] = 0;
                maps.at<Vec2i>(i, j)[0] = rand() % maps.rows;
                maps.at<Vec2i>(i, j)[1] = rand() % maps.cols;
            }
        }
}

void work(Mat src, int x1, int x2, int y1, int y2, int dx, int dy)
{
    Mat tar = src.clone();
    Mat temp = tar(Range(x1, x2), Range(y1, y2));
    Mat temp2 = tar(Range(x1 + dx, x2 + dx), Range(y1 + dy, y2 + dy));
    for (int i = 0; i < temp2.rows; ++i)
        for (int j = 0; j < temp2.cols; ++j)
        {
            temp2.at<Vec3b>(i, j)[0] = temp.at<Vec3b>(i, j)[0];
            temp2.at<Vec3b>(i, j)[1] = temp.at<Vec3b>(i, j)[1];
            temp2.at<Vec3b>(i, j)[2] = temp.at<Vec3b>(i, j)[2];
        }
    imshow("src", src);
    imshow("tarbef", tar);
    int sx = (x2 - x1) * 0.25, sy = (y2 - y1) * 0.25;
    int rows = src.rows, cols = src.cols;
    consts[0] = Mat(rows, cols, CV_32SC2, Scalar::all(1));
    consts[0](Range(1, rows - 1), Range(1, cols - 1)) = Scalar::all(0);
    consts[0](Range(x1 + dx + sx, min(rows - 1, x2 + dx - sx)), Range(y1 + dy + sy, min(cols - 1, y2 + dy - sy))) = Scalar::all(1);

    maps[0] = Mat(rows, cols, CV_32SC2, Scalar::all(0));

    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
        {
            maps[0].at<Vec2i>(i, j)[0] = i;
            maps[0].at<Vec2i>(i, j)[1] = j;
        }

    for (int i = x1 + dx + sx; i <= x2 + dx - sx; ++i)
        for (int j = y1 + dy + sy; j < y2 + dy - sy; ++j)
        {
            maps[0].at<Vec2i>(i, j)[0] = i - dx;
            maps[0].at<Vec2i>(i, j)[1] = j - dy;
        }
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            if (!consts[0].at<Vec2i>(i, j)[0])
            {
                maps[0].at<Vec2i>(i, j)[0] = rand() % rows;
                maps[0].at<Vec2i>(i, j)[1] = rand() % cols;
            }

    srcs[0] = src.clone();
    tars[0] = tar.clone();

   
    rows = src.rows, cols = src.cols;
    int i = 0;
    while (rows > 4 * PATCH_SIZE && cols > 4 * PATCH_SIZE)
    {
        pyrDown(srcs[i], srcs[i + 1]);
        pyrDown(tars[i], tars[i + 1]);
        maps[i + 1] = Mat(srcs[i + 1].rows, srcs[i + 1].cols, CV_32SC2, Scalar::all(0));
        consts[i + 1] = Mat(srcs[i + 1].rows, srcs[i + 1].cols, CV_32SC2, Scalar::all(0));
        DownCM(maps[i], maps[i + 1], consts[i], consts[i + 1]);
        ++i;
        rows = srcs[i].rows;
        cols = srcs[i].cols;
    }
    while (i > 0)
    {
        deal(srcs[i], tars[i], consts[i], maps[i]);
        UpCM(maps[i], maps[i - 1], consts[i - 1]);
        genera(srcs[i - 1], tars[i - 1], maps[i - 1]);
        imshow("taraft", tars[i - 1]);
        i--;
    }
        cvWaitKey();
    pyrDown(tar, tar);

}

int main(int argc, char** argv) {
    //srand( time(0) );
    Mat src = imread("test.jpg");
    namedWindow("src");
    namedWindow("tarbef");
    namedWindow("taraft");
    //work(src, 3, 125, 385, 440, 70,100);
    work(src, 70, 230, 210, 300, 0,270);


    cvWaitKey();
    return 0;
}

REVIEW OF [A Survey of Shape Feature Extraction Techniques]

一、 Introduction
这篇paper是关于图形形状的feature提取的方法介绍的。图形的feature可以代表图形的某些性质,可以利用feature检索出拥有相同性质的图形,我觉得更主要的目的是检索出相似的图形。
这章提到了几个作为形状feature所应该有的性质(之后会看到,并不是每个feature提取方法都满足全部性质,只是满足的越多越好):
1.可辨识性:拥有相同feature的图形看起来很像。
2.稳定性I:对某个shape的位移、旋转、缩放不会影响他的feature
3.稳定性II:对某个shape的仿射变换不会影响他的feature
4.抗噪性:feature应该尽量免疫噪声的影响
5.抗遮蔽性:shape被遮住后feature应该也尽量不变
6.统计学上的独立性?:不能有两个线性相关的feature?
7.可靠性:对同一个shape的两次计算feature的结果应该一样
一个科学的descriptor(feature的集合?)应该满足这些性质:
1. 应该尽量表达图片的信息
2. 不能太大,便于存储
3. 要易于计算两个descriptor之间的距离
Feature提取可以有以下应用:
1. 相似shape检索
2. Shape识别和分类
3. Shape对齐(alignment)
4. Shape简化
然后提feature的方法分了几个类 blabla

二、 shape的性质(parameters)
可以认为相似的shape的同一个性质值也是相似的,可以用这个特点对图像做预处理。
1. 重心
2. 最小惯性轴:一条直线,满足shape边界上的点到这条直线的距离平方和最小。
3. 平均弯曲能量
4. 偏心率:Elo=1-W/L,其中W和L是最小(应该是面积?)包含shape的长方形的长宽。
5. 圆率
6. 椭圆方差
7. 方率? Shape面积/最小长方形面积
8. 凸性:凸包周长/shape周长
9. 固体性:shape面积/凸包面积
10. 欧拉数:联通块数-洞数
11. 剖面?:Prox(i)表示在x=i的地方画一条竖线,shape覆盖这条线的长度,Proy同
12. 洞比:洞的面积/shape面积

三、 表示shape的一维函数
Shape的一维函数可以作为feature使用,也可以作为别的feature提取方法的预处理。
1. 复数函数
2. 离重心距离函数
3. 角度函数
4. 轮廓曲率函数
5. 面积函数:边界相邻两点和重心组成的三角形的面积形成的函数
6. 三角形面积函数?:第i个点和i+k、i-k组成的三角形的面积形成的函数?
7. 弦长函数

四、 多边形近似
多边形的近似算法的目的是避免一些对shape含义表达无意义的细节,总的可以分为合并算法和拆分算法。
合并:
1.距离阈值算法:把连续的一段,在合并后差别不超过某个阈值的边界点合并。
2.多边形进化算法:每次把某个能量比较小的节点删掉
拆分:对一条线,若边界超过阈值,则加点?

五、 空间相关性feature
这章的第一节介绍了一个normalization的方法,是比较通用的,具体是:先把shape的重心位移到原点,再按照最小长方形的短边长度W成比例缩小W倍,再把shape旋转到最小惯性轴平行于x轴,并且保证重心在惯性轴的下方。
在做完normalization后再计算feature,就可以让feature有稳定性I。
空间相关性feature有以下几种:
1. 自适应格子覆盖:就是用一个四分树表示这个shape
2. 切格子?:

看这个图能脑补出大概的算法步骤:
a把shape框起来
b随便切成几块
c对于一块,缩小框的范围
d对于一块中不连通的块分别框起来
e对于一块,再缩小框的范围
对于每一块,再从b开始循环。
然后因为这样生成的格子可能太多了,存全部格子的信息代价太大,就用了一种抽样存格子重心的方法

3. 凸包:

看这个图大概就能理解,先做凸包,再对凹进去的地方分别递归处理,生成类似树的形状。
4. 代码链:好像是利用数字表示方向,大概的描绘出边界?
5. 平滑曲线分解:好像是把边界分解成很多可以低次表示的曲线,分别存储?
6. 把边界点采样,投影在惯性轴的位置作为feature
7. 横梁角度统计:好像是统计每三个等差点夹角个数?
8. Shape矩阵:用矩阵描述shape的覆盖域
9. Shape内容:这个feature好像主要是针对点的feature

把c放在某个点上,统计落在每个格子里的点的个数,作为feature。
10. 弦分配:统计边界相邻两点距离,把每个距离的个数作为feature
11. 经络图?:


看这两张图大概可以脑补出一个dfs求经络图的算法2333

六、 从物理的角度搞出一些数字作为feature
七、 量化空间方法
好像是把shape逐渐简化的过程,简化的过程中,细节和噪声会逐渐消失,从而能更好的提feature
1.

2. 交点图

大概意思就是用原曲线和[原曲线高斯平滑后的曲线]的交点作为结果,具体是高斯的平滑参数为y轴交点在平滑后曲线的位置为x,就会画出来上面那个东西。

八、好像是一个可以全局表示shape的方法,并且可以很灵活的调整精确度和效率之间的平衡,具体方法没有看的很懂XD
九、

BZOJ 1854: [Scoi2010]游戏

一个武器可以看成连接对应两个属性值的一条边
可以证明如果一个联通块中出现一个环
则整个联通块都可以取
否则会有一个点不能取
显然这个不取的点是最大的那个点= =
然后扫一遍看能取到哪就行了
找环和维护最大可以用并查集做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 1000005;
 
int n, fa[maxn], is[maxn];
 
int getfa(int now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u = getfa(u), v = getfa(v);
        if (u == v) is[u] = is[v] = 1;
        else
        {
            if (u < v)swap(u, v);
            if (is[u] || is[v]) is[u] = is[v] = 1;
            fa[v] = u;
            is[v] = 1;
        }
    }
    for (int i = 1; i < maxn; ++i)
        if (!is[i])
        {
            cout << i - 1;
            break;
        }
}

BZOJ 1576: [Usaco2009 Jan]安全路经Travel

先构出最短路径树(题目说唯一)
对于一个非树边(u,v) 一定使树构成一个环
并且使环上的点(除了lca(u,v))都有了一个次短路
对于点i 这个所谓次短路的长度就是dist[u]+dist[v]+value[u,v]-dist[i]
可以发现次短路大小长度跟u,v有关 跟i无关
所以对于一个非树边(u,v)设它的权值为dist[u]+dist[v]+value[u,v]
把这个权值按从小到大排序 每次把环上没被赋值过的点赋上值
快速实现上面那个 可以用并查集(不用多说了吧=v=)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 100005;
 
struct line
{
    int to, next, v;
}li[maxn * 10];
 
struct wtf
{
    int v, cost;
    wtf(int a, int b) : v(a), cost(b) {}
};
 
struct hh
{
    int u, v, va;
}t[maxn * 5];
 
int be[maxn], dist[maxn], fa[maxn], f[maxn], d[maxn], tot, ans[maxn], l, n, m, b[maxn];
priority_queue<wtf> q;
 
bool operator<(wtf a, wtf b)
{
    return a.cost > b.cost;
}
 
bool cmp(hh a, hh b)
{
    return a.va < b.va;
}
 
void makeline(int fr, int to, int v)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
}
 
int getfa(int now)
{
    return (!f[now]) ? now : f[now] = getfa(f[now]);
}
 
void re_ans(int u, int v, int va)
{
    int lastu = -1, lastv = -1;
    while (getfa(u) != getfa(v))
    {
        if (d[getfa(u)] < d[getfa(v)]) swap(u, v), swap(lastu, lastv);
        if (ans[u] == -1)
        {
            ans[u] = va - dist[u];
            if (lastu != -1)
                f[lastu] = u;
        }
        else
            if (lastu != -1)
                f[lastu] = getfa(u);
        lastu = getfa(u);
        u = fa[lastu];
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i)
    {
        int fr, to, v;
        scanf("%d%d%d", &fr, &to, &v);
        makeline(fr, to, v);
        makeline(to, fr, v);
    }
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    d[1] = 1;
    q.push(wtf(1, 0));
    while (!q.empty())
    {
        while (!q.empty() && b[q.top().v]) q.pop();
        if (q.empty()) break;
        int now = q.top().v;
        b[now] = 1;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (b[to] || dist[to] <= dist[now] + li[i].v) continue;
            fa[to] = now;
            d[to] = d[now] + 1;
            dist[to] = dist[now] + li[i].v;
            q.push(wtf(to, dist[to]));
        }
    }/*
    for (int i = 1; i <= n; ++i)
        printf("%d\n", dist[i]);
    printf("\n\n");*/

    for (int i = 1; i <= n; ++i)
        for (int j = be[i]; j; j = li[j].next)
        {
            int to = li[j].to;
            if (to >= i || fa[to] == i || fa[i] == to) continue;
            t[tot].u = i, t[tot].v = to, t[tot].va = dist[i] + dist[to] + li[j].v;
            ++tot;
        }
    memset(ans, -1, sizeof(ans));
    sort(t, t + tot, cmp);
    for (int i = 0; i < tot; ++i)
        re_ans(t[i].u, t[i].v, t[i].va);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", ans[i]);
}

BZOJ 1016: [JSOI2008]最小生成树计数

求一个无向图(n,m)的生成树数可以构造下面一个矩阵
矩阵大小:(n * n)
对于一个位置(i,j)
如果i==j则上面的数为点i的度数
否则为i到j的边数的相反数
如一个图1<->2,2<->3点数为3
则矩阵为
1 -1 0
-1 2 -1
0 -1 1
吧这个矩阵的第i行和第i列去掉(1<=i<=n i取任意值都可) 然后叫这个剩下来的矩阵n-1阶余子式 求这个矩阵的行列式的绝对值即为该图的生成树数 (我不知道行列式是什么啊QAQ 我就只知道能这么用QvQ 虽然听起来不像是一个值 但是就这么用吧QvQ) 求一个矩阵的行列式就是先用高斯消元把这个矩阵消成上三角矩阵 然后ans=π(f[i][i]) 对于求生成树数这个矩阵 ans最后会是一个整数 但是中间步骤可能是小数 最小生成树计数怎么做呢=、= 先把边按权值从小到大排序 从小到大遍历 对于边权相同的一些边取出来 对于这些边的每个联通子图求生成树数(自环要无视) ans=π每个联通子图求生成树数 最后把每个联通块用并查集分别并为一个点 然后再做下一个边权的边集即可 这题的ans可能很大 如果直接开double或long double都可能爆(其实long double不会=-=) 这题有mod一个数 如果可以让ans中间过程也是整数就非常好 考虑对一个矩阵的某行减掉某行的某倍 这个矩阵的行列式是不会变的 则我们可以用一个类似辗转相除的方法 让这个矩阵在保证每个元素仍是整数的情况下变为上三角矩阵(详见代码) 【周冬《生成树的计数及其应用》】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll inf = 31011;
const ll maxn = 105;

struct lin
{
    ll fr, to, v;
}p[10005];

struct line
{
    ll next, to;
}li[10005];

ll be[maxn], fa[maxn], l, to[maxn], tot, ans, n, m;
ll v[maxn][maxn];
queue<ll> q;

bool cmp(lin a, lin b)
{
    return a.v < b.v;
}

void makeline(ll fr, ll to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

ll bfs(ll now)
{
    for (to[now] = tot = 1, v[1][1] = 0, q.push(now); !q.empty(); )
    {
        ll now = q.front();
        q.pop();
        for (ll i = be[now]; i; i = li[i].next)
        {
            ll _to = li[i].to;
            if (_to == now) continue;
            if (!to[_to])
            {
                to[_to] = ++tot;
                for (ll j = 1; j <= tot; ++j)
                    v[j][tot] = v[tot][j] = 0;
                q.push(_to);
            }
            v[to[now]][to[now]] += 1;
            v[to[now]][to[_to]] -= 1;
        }
    }
    if (tot == 1) return 1;
    ll ans = 1;
    for (ll i = 1; i < tot; ++i)
    {
        if (!v[i][i])
        {
            ll ans = -1;
            for (ll j = i + 1; j < tot; ++j)
                if (ans == -1 || abs(v[j][i]) > abs(v[ans][i]))
                    ans = j;
            for (ll j = i; j < tot; ++j)
                swap(v[i][j], v[ans][j]);
        }
        for (ll j = i + 1; j < tot; ++j)
            while (v[j][i])
            {
                ll t = v[i][i] / v[j][i];
                for (ll k = i; k < tot; ++k)
                    v[i][k] -= t * v[j][k],
                    swap(v[j][k], v[i][k]);
            }
        ans = (ans * v[i][i]) % inf;
    }
    return ans % inf;
}

ll getfa(ll now)
{
    return (!fa[now]) ? now : fa[now] = getfa(fa[now]);
}

int main()
{
    ans = 1;
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; ++i)
        scanf("%lld%lld%lld", &p[i].fr, &p[i].to, &p[i].v);
    sort(p, p + m, cmp);
    ans = 1;
    for (ll i = 0; i < m;)
    {
        l = 0;
        memset(be, 0, sizeof(be));
        memset(to, 0, sizeof(to));
        ll j;
        for (j = i; j < m && p[i].v == p[j].v; ++j)
            makeline(getfa(p[j].fr), getfa(p[j].to)),
            makeline(getfa(p[j].to), getfa(p[j].fr));
        ll t = j;
        for (ll j = 1; j <= n; ++j)
            if (!to[getfa(j)])
                ans = (ans * bfs(getfa(j))) % inf;
        for (ll j = i; j < t; ++j)
            if (getfa(p[j].fr) != getfa(p[j].to))
                fa[getfa(p[j].fr)] = getfa(p[j].to);
        i = t;
    }
    for (int i = 1; i <= n; ++i)
        if (getfa(i) != getfa(1))
        {
            cout << 0;
            return 0;
        }
    cout << abs(ans);
}

博物馆(museum)

这题求的是到某个点为终点的概率
以某个点为终点的概率可以是这个状态被进入的期望次数
即f[i][j]表示第一个人到i点 第二个人到j点的进入这个状态的期望次数
12
p是停留在某个点的概率 d是某个点的度数 S1 S2是初始状态
这个方程有环
所以用高斯消元做
把每个fij看成一个元 拿去解方程 即可出解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

struct line
{
    int to, next;
}li[1005];

int n, m, a, b, be[25], d[25], to[1005][2], fr[25][25], tot, l;
double p[25], v[405][405], ans[405];

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d%d%d%d", &n, &m, &a, &b);
    for (int i = 0; i < m; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
        ++d[fr], ++d[to];
    }
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            fr[i][j] = tot;
            to[tot][0] = i, to[tot][1] = j;
            ++tot;
        }
    for (int i = 0; i < tot; ++i)
    {
        int u1 = to[i][0], u2 = to[i][1];
        v[i][i] = -1 ;
        if (u1 == u2) continue;
        v[i][i] += p[u1] * p[u2];
        double va1 = p[u1] * (1 - p[u2]) / d[u2],
                     va2 = (1 - p[u1]) * p[u2] / d[u1],
                     va = (1 - p[u1]) * (1 - p[u2]) / d[u1] / d[u2];

        for (int j1 = be[u2]; j1; j1 = li[j1].next)
            v[fr[u1][li[j1].to]][i] = va1;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            v[fr[li[j1].to][u2]][i] = va2;

        for (int j1 = be[u1]; j1; j1 = li[j1].next)
            for (int j2 = be[u2]; j2; j2 = li[j2].next)
                v[fr[li[j1].to][li[j2].to]][i] = va;
    }
    v[fr[a][b]][tot] = -1;/*
    for (int i = 0; i < tot; ++i)
    {
        for (int j = 0; j <= tot; ++j) printf("%.2f ", v[i][j]);
        printf("\n");
    }*/

    for (int i = 0; i < tot; ++i)
    {
        int t = -1;
        for (int j = i; j < tot; ++j)
            if (t == -1 || abs(v[j][i]) > abs(v[t][i]))
                t = j;
        for (int j = 0; j <= tot; ++j)
            swap(v[i][j], v[t][j]);
        for (int j = i + 1; j < tot; ++j)
        {
            double va = v[j][i] / v[i][i];
            for (int k = i; k <= tot; ++k)
                v[j][k] -= va * v[i][k];
        }
    }
    for (int i = tot - 1; i >= 0; --i)
    {
        for (int j = i + 1; j < tot; ++j)
            v[i][tot] -= ans[j] * v[i][j];
        ans[i] = v[i][tot] / v[i][i];
    }/*
    for (int i = 0; i < tot; ++i)
        printf("%.6f ", ans[i]);
        printf("\n");*/

    for (int i = 1; i <= n; ++i)
        printf("%.6f ", ans[fr[i][i]] + 1e-8);
    fclose(stdin);fclose(stdout);
}

BZOJ 3451: Tyvj1953 Normal

考虑两个点a,b
a对b的删除时间有1的贡献当且仅当
在a到b的路径上的所有点中a是第一个删除的
这个有1/dist(a,b)的概率 对答案的贡献是1
所以这题就是求Σ1/(u,v)
这个可以用树分治做(233)
然后树分治合并两棵子树的f的时候要n^2的时间
这个可以fft优化到nlogn
总复杂度nlog^2n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 300005;
const int P = (1 << 21) * 479 + 1;
const int G = 3;

struct line
{
    int to, next;
}li[maxn * 2];

int be[maxn], mx[maxn], f[maxn], b[maxn], fa[maxn], is[maxn], g[maxn][2], gt[maxn][2], d[maxn], br[maxn];
ll t1[maxn], t2[maxn], tt1[maxn], tt2[maxn];
int l, n, tot, tot1;
ld ans;
queue<int> q;
stack<int> s;
vector<int> v;

int getz(int now)
{
    int tot = 0, as = -1;
    for (q.push(now), b[now] = 1, fa[now] = -1; !q.empty(); )
    {
        int now = q.front();
        ++tot;
        q.pop();
        s.push(now);
        f[now] = mx[now] = 0;
        for (int i = be[now]; i; i = li[i].next)
        {
            int to = li[i].to;
            if (is[to] || b[to]) continue;
            fa[to] = now;
            b[to] = 1;
            q.push(to);
        }
    }
    for (; !s.empty(); )
    {
        int now = s.top();
        s.pop();
        b[now] = 0;
        ++f[now];
        if (fa[now] != -1)
            f[fa[now]] += f[now],
            mx[fa[now]] = max(mx[fa[now]], f[now]);
        mx[now] = max(mx[now], tot - f[now]);
        if (as == -1 || mx[as] > mx[now])
            as = now;
    }
    return as;
}

bool cmp(int a, int b)
{
    return f[a] < f[b];
}

int bitre(int a, int n)
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
        ans += (1 << i) * ((a & (1 << (n - i - 1))) ? 1 : 0);
    return ans;
}

ll power(ll a, ll n)
{
    ll ans = 1;
    while (n)
    {
        if (n & 1) ans = (ans * a) % P;
        a = (a * a) % P;
        n >>= 1;
    }
    return ans;
}

void fnt(ll y[], const ll b[], ll n, ll rev = 1)
{
    ll len = 1 << n;
  for (ll i = 0; i < len; ++i)
    y[i] = b[bitre(i, n)];
    for (int i = 1; i <= n; ++i)
    {
        ll m = 1 << i;
        ll wn = power(G, (P - 1) / m);
        for (int j = 0; j < len; j += m)
        {
            ll w = 1;
            for (int k = j; k < j + m / 2; ++k)
            {
                ll u = y[k], v = (w * y[k + m / 2]) % P;
                y[k] = (u + v) % P, y[k + m / 2] = (u - v) % P;
                w = (w * wn) % P;
            }
        }
    }
    if (rev == 1) return;
    ll re = power(len, P - 2);
    for (int i = 0; i < len; ++i)
        y[i] = (y[i] * re % P + P) % P;
    reverse(y + 1, y + len);
}

void calc2(int v)
{
    int n, len;
    for (n = 0; (1 << n) < (v + 1) * 2; ++n);
    len = 1 << n;
    for (int i = 0; i < len; ++i)
        t1[i] = g[i][0] != tot1 ? 0 : g[i][1],
        t2[i] = gt[i][0] != tot ? 0 : gt[i][1];
    fnt(tt1, t1, n);
    fnt(tt2, t2, n);
    for (int i = 0; i < len; ++i) tt1[i] = (tt1[i] * tt2[i]) % P;
    fnt(t1, tt1, n, -1);
    for (int i = 2; i < len; ++i)
        ans += 1.0 / i * t1[i];
}

void calc(int now)
{
    getz(now);
    while (!v.empty()) v.pop_back();
    for (int i = be[now]; i; i = li[i].next)
        if (!is[li[i].to])
            v.push_back(li[i].to);
    sort(v.begin(), v.end(), cmp);
    ++tot1;
    for (int k = 0; k < v.size(); ++k)
    {
        int to = v[k];
        ++tot;
        for (q.push(to), br[to] = tot, d[to] = 1; !q.empty();)
        {
            int now = q.front();
            q.pop();
            if (gt[d[now]][0] != tot)
                gt[d[now]][0] = tot,
                gt[d[now]][1] = 0;
            ++gt[d[now]][1];
            for (int i = be[now]; i; i = li[i].next)
            {
                int to = li[i].to;
                if (br[to] == tot || is[to]) continue;
                br[to] = tot;
                d[to] = d[now] + 1;
                q.push(to);
            }
        }
        for (int i = 1; i <= f[to]; ++i)
        {
            if (gt[i][0] != tot) break;
            ans += 1.0 / (i + 1) * gt[i][1];
        }
        calc2(f[to] + 1);
        for (int i = 1; i <= f[to]; ++i)
        {
            if (g[i + 1][0] != tot1)
                g[i + 1][0] = tot1,
                g[i + 1][1] = 0;
            if (gt[i][0] != tot) break;
            g[i + 1][1] += gt[i][1];
        }
    }
}

void solve(int now)
{
    int z = getz(now);
    is[z] = 1;
    calc(z);
    for (int i = be[z]; i; i = li[i].next)
        if (!is[li[i].to])
            solve(li[i].to);
}

void makeline(int fr, int to)
{
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; ++i)
    {
        int fr, to;
        scanf("%d%d", &fr, &to);
        makeline(fr, to);
        makeline(to, fr);
    }
    solve(0);
    printf("%.4f", n + (double)ans * 2);
    fclose(stdin);fclose(stdout);
}

BZOJ 3450: Tyvj1952 Easy

对于连续的一段o
考虑第i个o
贡献的权值是2i-1
这样Σvi=n^2(1<= i <= n) 对所有n都有效 f[i]表示考虑前i个按键 期望收益是多少 问题是怎么转移呢0.0 显然f[i] = f[i - 1] + (i的期望收益) (根据期望可加) i的期望收益 枚举所有?的选择 设第j种选择最后有连续len[j]个o 一共m种选择 则i的期望收益为: ----------------------------- Σ(len[j] * 2 - 1) / m = (Σ(len[j]) / m) * 2 - 1 ----------------------------- Σ(len[j]) / m其实考虑前i位 最后连续的o的期望长度 这样就很简单了 g[i]表示前i为最后连续o的期望长度 然后就可以推了 但是如果长度为0 则按那个公式期望收益为0*2-1 = -1 显然是错的 要特判掉 怎么弄呢= = 可以从g[i - 1]转移 如果s[i] == 'x'就不管了 f[i] = f[i - 1] 如果s[i] == 'o'也不会有0的情况 直接转移即可 f[i] = f[i - 1] + g[i] * 2 - 1 如果s[i] == '?'那么有1/2的概率会长度为0则 f[i] = f[i - 1] + (g[i - 1] * 2 + 1) / 2即可(有1/2概率没收益)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const int maxn = 300005;
 
ld f[maxn], g[maxn];
int n;
 
int main()
{
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++i)
    {
        char c = getchar();
        if (c == 'x') f[i] = f[i - 1], g[i] = 0;
        if (c == 'o') g[i] =  g[i - 1] + 1, f[i] = f[i - 1] + g[i - 1] * 2 + 1;
        if (c == '?') g[i] = (g[i - 1] + 1) / 2, f[i] = f[i - 1] + g[i - 1] + 0.5;
    }
    printf("%.4f", (double)f[n]);
}

BZOJ 3437: 小P的牧场

这题一看就是奇怪的dp啊╮(╯_╰)╭
f[i]表示考虑前i个牧场 且第i个有取的最小代价
但是把这个方程列出来 会发现这个方程有一部分的系数是一个公差为1的等差数列
这就很蛋疼
不能以一个项数为O(1)级的多项式表示i取j决策的代价

怎么办呢
所谓正难则反
首先设答案为类似只在n+1号位置取一个观察站 的代价
如果这时候在i位置取一个观察站 则答案会减少(sum[i] * (n – i) – a[i])
f[i]表示考虑i~n的牧场 最多可以扣掉多少代价 且i有取
方程为
f[i] = max(a[i] + f[j] + sum[i] * (j – i))
sum[i]表示Σ(b[j])(1 <= j <= i) 这个方程拿去斜率优化一下即可 另外这个系列的数据范围巨坑无比 n的范围是100w 他写变成n <= 1000000,0 后面加了个,0不知道作何心态=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
 
const ll maxn = 1000 * 1000 + 5;
 
struct poll
{
    ll x, y;
    poll(ll a = 0, ll b = 0) : x(a), y(b) {}
};
 
poll q[maxn];
ll f[maxn], n, a[maxn], b[maxn], sum[maxn], h, t;
ll ans;
 
ll xj(poll a, poll b, poll c)
{
    return ((ll)b.x - a.x) * (c.y - a.y) - ((ll)b.y - a.y) * (c.x - a.x);
}
 
ll calc(ll i, poll j)
{
    return -a[i] + j.y + sum[i] * (j.x - i);
}
 
int main()
{
    scanf("%lld", &n);
    for (ll i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < n; ++i)
    {
        scanf("%lld", &b[i]);
        ans += ((ll)n - i) * b[i];
        if (!i) sum[i] = b[i];
        else sum[i] = sum[i - 1] + b[i];
    }
    f[n - 1] = sum[n - 1] - a[n - 1];
    h = t = 0;
    q[0] = poll(n - 1, f[n - 1]);
    ll as = f[n - 1];
    for (ll i = n - 2; i >= 0; --i)
    {
        while (h < t && calc(i, q[h]) <= calc(i, q[h + 1])) ++h;
        f[i] = calc(i, q[h]);
        while (h < t && xj(q[t - 1], q[t], poll(i, f[i])) <= 0) --t;
        q[++t] = poll(i, f[i]);
        as = max(as, f[i]);
    }
    printf("%lld", ans - as);
}

BZOJ 3439: Kpm的MC密码【论splay的正确姿势】

这题本身很简单
就是把串反过来做trie+区间k大即可
但是这题主席树做空间不够(应该是不够吧0.0)
于是就按拓扑序做启发式合并平衡树
刚好早上被黄神神d模板过长 于是orz了贵校的模板 学习了下
这是spaly的一些函数的科学写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

然后这题的全题代码0 0
我只能说要是用我原来的模板得多100行=-=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct node
{
    int ch[26], sum, fa;
    vector<int> to;
}tr[maxn];

struct nodes
{
    int c[2], fa, sum;
}t[maxn];

int n, d[maxn], totr, root[maxn], ans[maxn], k[maxn];
string s;
queue<int> q;

void inss(int no)
{
    for (int i = s.length() - 1, now = 1; i >= 0; --i)
    {
        int to = tr[now].ch[s[i] - 'a'];
        ++tr[now].sum;
        if (!to)
        {
            to = tr[now].ch[s[i] - 'a'] = ++totr;
            tr[to].fa = now;
            ++d[now];
        }
        if (!i) tr[to].to.push_back(no), ++tr[to].sum;
        now = to;
    }
}

void up(int now)
{
    t[now].sum = t[t[now].c[0]].sum + t[t[now].c[1]].sum + 1;
}

void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

int dfs(int now, int root)
{
    if (!now) return root;
    root = dfs(t[now].c[0], root);
    root = dfs(t[now].c[1], root);
    root = ins(root, now);
    return root;
}

int merge(int u, int v)
{
    if (!u) return v;
    if (!v) return u;
    if (t[u].sum < t[v].sum) swap(u, v);
    return dfs(v, u);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    totr = 1;
    for (int i = 1; i <= n; ++i)
    {
        s = "";
        char c = getchar();
        while (!(c >= 'a' && c <= 'z')) c = getchar();
        while (c >= 'a' && c <= 'z')
        {
            s += c;
            c = getchar();
        }
        inss(i);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d", &k[i]);

    for (int i = 1; i <= totr; ++i)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int to = tr[now].ch[i];
            if (!to) continue;
            root[now] = merge(root[now], root[to]);
        }
        for (int i = 0; i < tr[now].to.size(); ++i)
            root[now] = ins(root[now], tr[now].to[i]);
        for (int i = 0; i < tr[now].to.size(); ++i)
        {
            int to = tr[now].to[i];
            if (k[to] > tr[now].sum) ans[to] = -1;
            else root[now] = ans[to] = query(root[now], k[to]);
        }
        if (!--d[tr[now].fa]) q.push(tr[now].fa);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    fclose(stdin);fclose(stdout);
}