【题解】Codeforces前11场泛做

嗯,然后这些题就是从好久之前开始就一直在做的CF前11场的一些题目,都比较简单,但是决定记录一下补补基础qwq

$\rm {CF·1C}$

求包含给定三点的正多边形最小面积。


先考虑,对于给出的三个正多边形顶点,两两连边之后,中垂线交于正多边形所在圆的圆心——原因是这三个点最优情况下一定是在顶点上的。那么可以凭此求出圆心和半径。

之后对于该多边形,我们考虑,由于其让求的正多边形需要面积最小。并且对于给出的三个点,由于在正多边形上的原因,所以圆心与其连线的角都应该是该正多边形相邻两个顶点在外接圆上所对的圆心角的整数倍

那么我们就做一个double类型的$\gcd$就好了——因为在外接圆大小一定时(三点已确定一个圆),对于正$n$边形,其面积与$n$成正相关。所以取$\gcd$一定是个最好的选择。

最后的面积嘛…大概只需要余弦定理一下就好。此处借鉴的是第一篇题解里面求面积的方法。同时,第三个角必须用$2\pi$减去另外两个角得到,如果不这样误差会相当的大……尤其是乘上一堆之后,面积会很不精确$qaq$

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
const double Eps = 1e-4 ;
const double Pi = acos(-1.00000) ;
struct Node{
bool mark ; // 0 = exist, 1 = inexist ;
double x, y ;
}A, B, C, O, m1, m2, m3 ;
struct Line{
int mark ;//0 : // x-axis, 1: // y-axis, 2: // normal ;
double k, b ; double x, y ; // y = kx + b, x = k, y = k ;
}L[12] ; double Len[4], agl[4], R, angle ; int i ;

double get_x(Line A, Line B){ return A.mark == 0 ? A.x : B.x ; } //which is x = k ;
double get_y(Line A, Line B){ return A.mark == 1 ? A.y : B.y ; } //which is y = k ;
double dis(Node A, Node B){ return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ; }
inline Node get_Mid(Node A, Node B){ return (Node){0, (A.x + B.x) / 2, (A.y + B.y) / 2 } ; }
inline Line get_verti(Node n, Line a){
if (!a.mark) return (Line) {1, 0, 0, 0, n.y} ;
if (a.mark == 1) return (Line) {0, 0, 0, n.x, 0} ;
double kk = -1.0 / a.k, bb = n.y - n.x * kk ;
return (Line){2, kk, bb, 0, 0 } ;
}
inline Line get_Line(Node A, Node B){
if (A. y == B. y) return (Line){1, 0, 0, 0, B.y} ;
if (A. x == B. x) return (Line){0, 0, 0, A.x, 0} ;
double kk = (A.y - B.y) / (A.x - B.x), bb = A.y - A.x * kk ;
return (Line){2, kk, bb, 0, 0} ;
}
inline Node get_inter(Line A, Line B){
if (A.mark == B.mark && (A.mark == 1 || A.mark == 0) )
return (Node){1, 0, 0 } ;
if ((A.mark == 1 && B.mark == 0) || (A.mark == 0 && B.mark == 1))
return (Node){0, get_x(A, B), get_y(A, B)} ;
if (A.mark == 1 && B.mark == 2) return (Node){0, (A.y - B.b) / B.k, A.y} ;
if (A.mark == 2 && B.mark == 1) return (Node){0, (B.y - A.b) / A.k, B.y} ;
if (A.mark == 2 && B.mark == 0) return (Node){0, B.x, B.x * A.k + A.b} ;
if (A.mark == 0 && B.mark == 2) return (Node){0, A.x, A.x * B.k + B.b} ;
return (Node){0, (A.b - B.b) / (B.k - A.k), (A.b - B.b) / (B.k - A.k) * A.k + A.b} ;
}
inline double gcd(double a,double b) {
if (fabs(b) < Eps) return a ;
if (fabs(a) < Eps) return b ;
return gcd(b, fmod(a, b)) ;
}
int main(){
cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y ;
A.mark = B.mark = C.mark = 0 ;
L[1] = get_Line(A, B), L[2] = get_Line(B, C), L[3] = get_Line(A, C) ;
m1 = get_Mid(A, B), m2 = get_Mid(B, C), m3 = get_Mid(A, C) ;
L[4] = get_verti(m1, L[1]), L[5] = get_verti(m2, L[2]) ;
O = get_inter(L[4], L[5]), R = (dis(O, A) + dis(O, B) + dis(O, C)) / 3.0 ;
Len[1] = dis(A, B), Len[2] = dis(B, C), Len[3] = dis(A, C) ;
for (i = 1 ; i <= 3 ; ++ i) agl[i] = acos(1 - Len[i] * Len[i] / (2 * R * R) );
agl[3] = 2 * Pi - agl[1] - agl[2], angle = gcd(agl[3], gcd(agl[1], agl[2])) ; printf("%.6lf\n", (Pi * R * R * sin(angle)) / angle) ; return 0 ;
}

$\rm CF·2B$

给定由非负整数组成的$n \times n$的正方形矩阵,寻找一条路径,以左上角为起点, 每次只能向右或向下走

以右下角为终点。并且,如果我们把沿路遇到的数进行相乘,积应当以最小数目的$0$的结尾.

$n\leq 1,000$

考虑$0$是怎么来的,那显然是$\times\text{=10}=2\times 5$。所以就把$2,5$分开$dp$。方程也很简单,就从左边和上边填一下表就好了。然后如果原来矩阵里面有$0$并且最后答案$>1$,那么就应该走$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
inline int qwq(int &N, int fac){
if (!N) { zerox = i, zeroy = j ; return 1 ; }
int res = 0 ; while (!(N % fac)) ++ res, N /= fac ; return res ;
}
inline void Print(int x, int y, int mark, int kind){ //mark 1 : D, 2 : R ;
if (!x || !y) return ;
// cout << x << " " << y << endl ;
if (kind == 1){
if (x - 1 && dp2[x][y] == dp2[x - 1][y] + base[x][y][kind])
Print(x - 1, y, 1, kind) ;
else if (y - 1 && dp2[x][y] == dp2[x][y - 1] + base[x][y][kind])
Print(x, y - 1, 2, kind) ;
}
else{
// cout << dp5[x][y] << " " << dp5[x - 1][y] << " " << dp5[x][y - 1] << endl ;
if (x - 1 && dp5[x][y] == dp5[x - 1][y] + base[x][y][kind])
Print(x - 1, y, 1, kind) ;
else if (y - 1 && dp5[x][y] == dp5[x][y - 1] + base[x][y][kind])
Print(x, y - 1, 2, kind) ;
}
if (!mark) return ; if (mark == 1) printf("D") ; else printf("R") ;
}
int main(){
cin >> N ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j)
scanf("%d", &base[i][j][0]) ;
memset(dp2, 63, sizeof(dp2)), dp2[1][0] = dp2[0][1] = 0 ;
memset(dp5, 63, sizeof(dp5)), dp5[1][0] = dp5[0][1] = 0 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j)
dp2[i][j] = min(dp2[i - 1][j], dp2[i][j - 1])
+ (base[i][j][1] = qwq(base[i][j][0], 2)) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j)
dp5[i][j] = min(dp5[i - 1][j], dp5[i][j - 1])
+ (base[i][j][2] = qwq(base[i][j][0], 5)) ;
Ans = min(dp5[N][N], dp2[N][N]) ;
if (Ans > 1 && zerox && zeroy){
cout << 1 << endl ;
// cout << zerox << zeroy << endl ;
for (i = 1 ; i < zerox ; ++ i) printf("D") ;
for (i = 1 ; i < zeroy ; ++ i) printf("R") ;
for (i = zerox + 1 ; i <= N ; ++ i) printf("D") ;
for (i = zeroy + 1 ; i <= N ; ++ i) printf("R") ;
}
else {
cout << Ans << endl ;
dp5[N][N] > dp2[N][N] ? Print(N, N, 0, 1) : Print(N, N, 0, 2) ;
}
return 0 ;
}

$\rm CF ·2C$

给出三个互不相交的圆,求一个点使得到这三个圆的切线夹角相同。

咋又是计算几何啊

设这点为$T$, 三个圆心分别为$A, B,C$。而圆$A$的半径$r_A$与$dis(A,T)$的比值,就是$sin(\frac{1}{2}\angle A_1TA_2)$,其中$A_1$和$A_2$是过T的圆A的两条切线与圆的交点。

那么也就是说,我们如果有$\angle A_1TA_2 = \angle B_1TB_2= \angle C_1TC_2$,那么一定有

稍微移一下项,就会有

那么我们就可以发现,对于两个点而言,我们要找的目标点$T$满足到两个点的距离等于一个给定的比例($r_A$和$r_B$给定)。

事实上,这样的点的轨迹是可以刻画的。我们列一个方程即可:

设比例系数为$k(k \geq 1)$, 那么:

稍微移一下项就会得到

看起来有点儿长……

令$A = k^2-1, C = - 2(k^2x_B - x_A), D = -2(k^2y_B - y_A), E = k^2x_B^2 - x_A^2 + k^2y_B^2 - y_A^2$

那么就会变成

由于$A,C,D,E$都是常数,所以这是一个圆的一般方程。

我们其实也可以发现,当$k=1$时。此时为一条直线(即中垂线),换句话说当且仅当两个圆半径相等时,点$T$的轨迹是一条直线。其余的情况则是一个圆

我们不妨先记这种到两个圆的圆心的距离成定比例的轨迹为两个圆的生成曲线

那么之后呢,我们发现,圆$A$和圆$C$的生成曲线,与圆$A$和圆$B$的生成曲线,至多有两个交点。那么我们只需要:

  • $(1)~~$判断三组圆的生成曲线是否都相交且交于一点,不是则无解。
  • $(2)~~$对于其中两个圆的生成曲线的交点,判断是否满足条件,即是我们已经找到了符合的点,我们需要判断对于圆$C$是否也满足
  • $(3)~~$如果选取的生成曲线恰好有$2$个交点且两个交点$T’,T’’$都满足$(2)$中的条件,那么我们选$sin$值最大的(对于$\leq \frac{\pi}{2}$的角,$sin$值与角的大小成正相关)。

然后算法就结束了。中间还有好多好多好多问题,比如圆与圆的交点怎么求,直线与直线的交点怎么求,圆与直线的交点怎么求……果然是道体力题233

代码很繁琐233

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

#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std ;
const double Eps = 1e-3 ; int i ;//以下的mark都是记录状态
struct Node{ int mark ; double xa, ya, xb, yb ; } I[5] ;
// 0 = inexist, 1 = exist*1, 2 = exist*2 ;
//此处我的Node存的实际上是两个点,即一个一元二次方程的两个解。
struct Line{ int mark ; double k, b ; double x, y ; }L[12] ;
//0 : // x-axis, 1: // y-axis, 2: // normal ;
struct Circle{
int mark ; // 1 : circle ; 0 : Line ;
double x, y, r ;
double A, B, C, D, E ;
Circle friend operator -(const Circle &A, const Circle &B){
return (Circle){0, A.x - B.x, A.y - B.y, A.r - B.r, A.A - B.A, A.B - B.B, A.C - B.C, A.D - B.D, A.E - B.E} ;
}
}C[10] ;
double ansx, ansy ; bool check ;

inline bool Comp(Node A, Node B){ return A.mark < B.mark ; }
inline double get_x(Line A, Line B){ return A.mark == 0 ? A.x : B.x ; } //which is (x = k) ;
inline double get_y(Line A, Line B){ return A.mark == 1 ? A.y : B.y ; } //which is (y = k) ;
inline bool equal(double x, double y){ return (x - y <= Eps) && (x - y >= -Eps) ; }
inline double disa(Node A, Node B){
return sqrt((A.xa - B.xa) * (A.xa - B.xa) + (A.ya - B.ya) * (A.ya - B.ya));
}//第一个点之间的距离
inline double disb(Node A, Node B){
return sqrt((A.xb - B.xb) * (A.xb - B.xb) + (A.yb - B.yb) * (A.yb - B.yb));
}//第二个点之间的距离
//呃……我承认两个dis写的很麻烦……但是好像也没什么很简单的法子
inline Node Line_inter(Line A, Line B){//斜截式直线求交点(之前写的直接copy过来的)
if (A.mark == B.mark && (A.mark == 1 || A.mark == 0) )
return (Node){0, 0, 0, 0, 0} ;
if ((A.mark == 1 && B.mark == 0) || (A.mark == 0 && B.mark == 1))
return (Node){1, get_x(A, B), get_y(A, B), 0, 0} ;
if (A.mark == 1 && B.mark == 2)
return (Node){1, (A.y - B.b) / B.k, A.y, 0, 0} ;
if (A.mark == 2 && B.mark == 1)
return (Node){1, (B.y - A.b) / A.k, B.y, 0, 0} ;
if (A.mark == 2 && B.mark == 0)
return (Node){1, B.x, B.x * A.k + A.b, 0, 0} ;
if (A.mark == 0 && B.mark == 2)
return (Node){1, A.x, A.x * B.k + B.b, 0, 0} ;
return (Node){1, (A.b - B.b) / (B.k - A.k), (A.b - B.b) / (B.k - A.k) * A.k + A.b, 0, 0} ;
}
inline Node get_inter (Circle A, Circle B){//“生成曲线”求交点
if ((A.mark == 0 && B.mark) || (A.mark && B.mark == 0)){//一条是直线,一个是圆
if (!A.mark) {Circle C ; C = A, A = B, B = C ;} // B is a line ;
double a = 1 + (B.C / B.D) * (B.C / B.D), del ;
double c = A.E - B.E * A.D / B.D + B.E * B.E /((B.D) * (B.D)) ;
double b = (A.C - B.C * A.D / B.D + 2 * B.C * B.E /((B.D) * (B.D)) ) ;
if ((del = (b * b - 4 * a * c)) < -Eps) return (Node){0, 0, 0, 0, 0} ;
// printf("%lf %lf %lf %lf\n", a, b, c, del) ;
double xa = (-b + sqrt(del)) / (2 * a), xb = (-b - sqrt(del)) / (2 * a) ;
double ya = -B.C / B.D * xa - B.E / B.D, yb = -B.C / B.D * xb - B.E / B.D ;
// cout << "-----------------" << xa << " " << ya << " " << xb << " " << yb << endl ;
return (Node){2, xa, ya, xb, yb} ;//此处由于误差等原因,不容易判断是否delta=0的情况,所如果delta=0直接记录两遍,不影响结果
}
if (!A.mark && !B.mark){
Line La, Lb ; //两条都是直线,那么就直接转化成斜截式求。
if (!A.C) La = (Line){1, 0, 0, 0, - A.E / A.D} ;
else if (!A.D) La = (Line){0, 0, 0, -A.E / A.C, 0} ; else La = (Line){2, -A.C / A.D, -A.E / A.D, 0, 0} ;
if (!B.C) Lb = (Line){1, 0, 0, 0, - B.E / B.D} ;
else if (!B.D) Lb = (Line){0, 0, 0, -B.E / B.C, 0} ; else Lb = (Line){2, -B.C / B.D, -B.E / B.D, 0, 0} ;
return Line_inter(La, Lb) ;
}
if (A.mark && B.mark){
Circle C = A - B ; return get_inter(C, A) ;
//此处需要用到一点小知识,就是两个圆的交点很难求,但是我们可以通过相减求出交线来(必修二知识点),那么就直接把这条线代回第一个if里就好。
}
}
inline Circle make_rat(Circle A, Circle B){//rat = ratio[n.]比例;比率,用来求生成曲线的函数
double _k2 = (A.r / B.r) * (A.r / B.r) ; Circle Ans ; double t ;
Ans.A = Ans.B = (_k2 - 1),
Ans.C = -2 * (_k2 * B.x - A.x),
Ans.D = -2 * (_k2 * B.y - A.y),
Ans.E = (_k2 * B.x * B.x - A.x * A.x) + (_k2 * B.y * B.y - A.y * A.y),
Ans.x = Ans.y = Ans.r = 0 ;
if (Ans.A != 0)
Ans.mark = 1, t = Ans.A, Ans.A /= t,
Ans.B /= t, Ans.C /= t, Ans.D /= t, Ans.E /= t ;
else Ans.mark = 0 ;
return Ans ;
}
inline void make_for_Ans(){//最后的结果,判断选哪个交点
sort(I + 1, I + 3, Comp) ;//我闲的,方便一点
if (I[1].mark <= 1) ansx = I[1].xa, ansy = I[1].ya ;
else {
double A1, A11, B1, B11 ;
I[1] = get_inter(C[4], C[5]) ;
A1 = disa(I[1], (Node){0, C[1].x, C[1].y, 0, 0}) / C[1].r ;
A11 = disa(I[1], (Node){0, C[3].x, C[3].y, 0, 0}) / C[3].r ;
B1 = disb(I[1], (Node){0, 0, 0, C[1].x, C[1].y}) / C[1].r ;
B11 = disb(I[1], (Node){0, 0, 0, C[3].x, C[3].y}) / C[3].r ;
if (equal(A1, A11) && !equal(B1, B11)) ansx = I[1].xa, ansy = I[1].ya ;
else if (!equal(A1, A11) && equal(B1, B11)) ansx = I[1].xb, ansy = I[1].yb ;
else if (!equal(A1, A11) && !equal(B1, B11))
check = 1 ;//如果在误差范围内都不相等就说明无解。
else {
double Ja = sin(1 / A1), Jb = sin(1 / B1) ;//比较角的大小,通过sin来搞
if (Ja > Jb) ansx = I[1].xa, ansy = I[1].ya ;
else ansx = I[1].xb, ansy = I[1].yb ;
}
}
}
int main(){
for (i = 1 ; i <= 3 ; ++ i)
cin >> C[i].x >> C[i].y >> C[i].r ;
C[4] = make_rat(C[1], C[2]),
C[5] = make_rat(C[2], C[3]),
C[6] = make_rat(C[3], C[1]),
I[1] = get_inter(C[4], C[5]),
I[2] = get_inter(C[5], C[6]),
I[3] = get_inter(C[4], C[6]) ;
/*cout << I[1].xa << " " << I[1].xb << " " << I[1].ya << " " << I[1].yb << " " << I[1].mark << endl ;
cout << I[2].xa << " " << I[2].xb << " " << I[2].ya << " " << I[2].yb << " " << I[2].mark << endl ;
cout << I[3].xa << " " << I[3].xb << " " << I[3].ya << " " << I[3].yb << " " << I[3].mark << endl ;*/
if (!I[1].mark || !I[2].mark || !I[3].mark) return putchar('\n'), 0 ;
make_for_Ans() ; (!check) ? printf("%.5lf %.5lf", ansx, ansy) : 1 ; return 0 ;
}

$\rm CF·3B$

有一辆载重量为$v$的货车, 准备运送两种物品。

物品$A$的重量为$1$, 物体$B$的重量为$2$, 每个物品都有一个价值。 求货车可以运送的物品的最大价值。

$n\leq 100,000\quad v\leq 1e9$

其实是一个非常简单的贪心思路,就是如果两件重量为1的商品合成一件的话,比重量为2的要优我们就选合起来的。

$\mathsf {Somebody}$谈过一个小Idea,就是看上去我们期望每次取偶数个。那么我们一开始如果$M$是奇数,就从重量为1的那一堆选一个最大的……(虽然我不知道这个到底有没有用但是听起来挺科学)

有些小细节需要注意。其中拿出来一个说一下:边界问题其实不需要考虑得太仔细,只要一开始memset整个数组为-INF,那么当一种重量的用完了,另一种重量的没用完时,取max之后不会出现越界的情况

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
struct Data{
int num ,val ;
} base1[MAXN], base2[MAXN] ; int N, M, p, v, v1, v2, c ;
long long Ans ; int tot1, tot2, t1, t2, i ; vector <int> ans ;

inline bool Comp(Data a, Data b){ return a.val > b.val ; }
int main(){
cin >> N >> M ;
memset(base1, -63, sizeof(base1)) ;
memset(base2, -63, sizeof(base2)) ;
for (i = 1 ; i <= N ; ++ i){
scanf("%d%d", &p, &v) ;
if (p > 1) base2[++ tot2].val = v, base2[tot2].num = i ;
else/*qwq*/base1[++ tot1].val = v, base1[tot1].num = i ;
}
sort(base1 + 1, base1 + tot1 + 1, Comp),
sort(base2 + 1, base2 + tot2 + 1, Comp) ;
// for (i = 1 ; i <= N ; ++ i) cout << base1[i].num << " " << base1[i].val << " qwwq " ;
// for (i = 1 ; i <= N ; ++ i) cout << base2[i].num << " " << base2[i].val << " qwwq " ;
if (M & 1) ans.pb(base1[1].num), Ans += base1[1].val, ++ t1, M -- ;
while (M > 1){//此处>1是选v=2时防止越界
v2 = base2[t2 + 1].val ;
if (t1 >= tot1 && t2 >= tot2) break ;
v1 = base1[t1 + 1].val + base1[t1 + 2].val ;
if (t1 + 2 > tot1) v1 = base1[t1 + 1].val, c = 1 ; else c = 2 ;
if (v1 >= v2){
Ans += v1 ; M -= c ;
rep(i, 1, c) ans.pb(base1[++ t1].num) ;
}
else Ans += v2, M -= 2, ans.pb(base2[++ t2].num) ;
}//因为while的条件是M>1,所以需要判断一下是不是还可以选。
if (M && t1 < tot1)
Ans += base1[++ t1].val, ans.pb(base1[t1].num) ;
if (Ans < 0) return puts("0\n"), 0 ; cout << Ans << endl ;
for (vector<int> :: iterator k = ans.begin() ; k != ans.end() ; ++ k) cout << *k << " " ;

$\rm{CF·4D}$

给出一个限制$(w,h)$和$n$个物品的二维信息$(w_i,h_i)$

求物品二维都满足$w_i>w,~h_i>h$的前提下的最长二维严格上升子序列以及其长度
$n \leq 5,000$

一个比较显然的想法是,由于可以随便安排顺序,所以可以直接按其中一维排一个序,把这个当做下标,然后找另一维的$\mathsf {LIS}$。 那么由于是严格升序,所以要判一下相等。路径就照例是找前驱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (i = 1 ; i <= N ; ++ i)	{ 
scanf("%d%d", &A, &B), f[i] = 1 ;
if (A <= W || B <= H) continue ;
E[++ tot].w = A, E[tot].h = B, E[tot].num = i ;
}
sort(E + 1, E + tot + 1, Comp) ;
for (i = 1 ; i <= tot ; ++ i)
for (j = 1 ; j < i ; ++ j)
if (E[j].w < E[i].w && E[j].h < E[i].h)
if (f[i] < f[j] + 1) {
f[i] = f[j] + 1, r[i] = j ;
}
for (i = 1 ; i <= tot ; ++ i)
if (f[i] > ans) ans = f[i], End = i ;
while(End) s.push(End), End = r[End] ; cout << ans << endl ;
while (!s.empty()) cout << E[s.top()].num << " ", s.pop() ; return 0 ;

$\rm CF·5C$

给出一个括号序列,求出最长合法子串和它的数量。 合法的定义:这个序列中左右括号匹配。

$n\leq 1,000,000$

好像是道$sb$题?考虑把所有可以匹配的位置置为$1$,否则为$0$,那么答案就是有最长连续的$1$的段。$dp$一下就好了吧…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
char In[MAXN] ; stack <int> s ; 
int N, dp[MAXN], f[MAXN], base[MAXN] ;

int main(){
scanf("%s", In + 1), N = strlen(In + 1) ;
for (i = 1 ; i <= N ; ++ i){
if (In[i] == '(') s.push(i)/*, cout << "qwq" << endl */;
else if (!s.empty()) base[s.top()] = base[i] = 1, s.pop() ;
} int ans = 0 ;
for (i = 1 ; i <= N ; ++ i)
if (base[i]) dp[i] = dp[i - 1] + 1 ; else dp[i] = 0 ;
for (i = 1 ; i <= N ; ++ i)
f[i] = max(f[i - 1], dp[i]) ; cout << f[N] << " " ;
int maxx = -1 ;
for (i = 1 ; i <= N ; ++ i)
if (dp[i] == f[N]) ++ ans ; cout << (f[N] ? ans : 1) << endl ;
return 0 ;
}

$\rm CF·5D$

有一个长度为$l$的道路,你的加速是$a$。

从$[0,d]$的限速是$w$,$[0,l]$的限速是$v$,问你最少花费多少时间从起点到终点。

$w$的限速范围是$[d,d]$,即是说保证在交通标志处的速度不超过$w$即为合法。

高中物理模拟题??

其实就是分类讨论一下就好。

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
bool mark ; 
const double eps = 1e-7 ;
double x_1, x_2, ans, x ;
double vnow, a, vmax, L, D, vmaxd ;

inline bool equal(double a, double b){
if (b > a) swap(a, b) ;
return ((a - b <= eps) && (b - a >= -eps)) ;
}
int main(){
cin >> a >> vmax >> L >> D >> vmaxd ;
vnow = sqrt(0.5 * (2 * a * D + vmaxd * vmaxd)) ;
if (vnow > vmax) vnow = vmax, mark = 1 ;
x_1 = vnow * vnow / 2 / a, x_2 = (vnow * vnow - vmaxd * vmaxd) / 2 / a ;
if (vnow > vmaxd || equal(vnow, vmaxd)){
// if (!mark){
ans += vnow / a + (vnow - vmaxd) / a ;
if (x_1 + x_2 < D) x = D - x_1 - x_2, ans += x / vnow ;
/*}
else {
ans += vnow / a + (vnow - vmaxd) / a ;
x = ans += x / vnow ;
}*/
}
else {
vnow = vmax, x = vnow * vnow / 2 / a ;
if (x < L || equal(x, L)){
ans = vnow / a, ans += (L - x) / vmax ;
printf("%.9lf", ans) ; return 0 ;
}
else {
vnow = sqrt(2 * a * L) ;
ans = vnow / a, printf("%.9lf", ans) ; return 0 ;
}
}
x = (vmax * vmax - vmaxd * vmaxd) / 2 / a ;
if (x < L - D || equal(x, L - D)){
ans += (vmax - vmaxd) / a, ans += (L - D - x) / vmax ;
printf("%.9lf", ans) ; return 0 ;
}
else {
vnow = vmaxd, x = sqrt(2 * a * (L - D) + vnow * vnow) ;
ans += (x - vnow) / a, printf("%.9lf", ans) ; return 0 ;
}
}

$\rm CF·5E$

有$\mathsf n$座山组成一个环,两座山互相能看到的要求是相连的圆弧上没有任何其他的山高度比它们高,求能看到的山的组数。

$n\leq 100,000$

一眼看上去就给人一股单调栈的味道……但是看上去要断环为链?但是如果断环为链的话,有些贡献会算重。但是考虑会算重的正好是算一遍只算一个序列的答案。但是这还不够,因为我们发现成链之后,最高值和次高值在$[1,n]$能互相看到,并且在$[1,n]$和$[n+1,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
inline void init(int L){
for (int i = 0 ; i <= L ; ++ i) stack[i] = Mp(0, 0) ;
}
inline int Solve(int M){
init(M), ans = 0 ;
register int i, tp = 0 ;
for (i = 1 ; i <= M ; ++ i) {
while (tp && stack[tp].first < base[i])
ans += stack[tp].second, -- tp ;
if (stack[tp].first != base[i])
ans += (tp > 0), stack[++ tp] = Mp(base[i], 1) ;
else ans += (tp > 1) + stack[tp].second, ++ stack[tp].second ;
}
return ans ;
}
signed main(){
cin >> N ; register int i ;
for (i = 1 ; i <= N ; ++ i)
base[i + N] = base[i] = qr() ;
pair<int, int> St, Ed ;
St = Mp(-1, 0), Ed = Mp(-1, 0) ;
for (i = 1 ; i <= N ; ++ i){
if (St.first < base[i])
Ed = St, St = Mp(base[i], 1) ;
else if (St.first == base[i]) ++ St.second ;
else if (Ed.first < base[i]) Ed = Mp(base[i], 1) ;
else if (Ed.first == base[i]) ++ Ed.second ;
}
Ans = Solve(2 * N) - Solve(N),
Ans -= (St.second * St.second + ((St.second == 1) ? Ed.second : 0)),
cout << Ans << endl ; return 0 ;
}

$\rm CF·6D$

有一队人,你可以用膜某个人,会对当前人造成$a$点伤害,对旁边的人造成$b$点伤害。血量没了就会伤透心。

不能膜$1$号和$n$号,求最少多少膜多少次让所有人伤透心。

$n\leq 10$

看数据范围觉得是状压。后来发现其实就跟$\rm CF1110$的那个麻将题差不多,只需要记录$i-1$和$i$的状态即可。于是$f_{i,j,k}$表示前$i$个人,在$i-1$这里还剩$j$血,在$i$这里还剩$k$血,且前$i$个人都伤透心$\min$。然后记录一下路径就完了。

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
int dp[MAXN][MAXN][MAXN] ;
int N, a, b, blood[MAXN], i, j, k, l ;
pair<int, int> From[MAXN][MAXN][MAXN] ;

void Print(int step, int jj, int kk){
if (step <= 1) return ;
Print(step - 1, From[step + 1][jj][kk].first, From[step + 1][jj][kk].second) ;
int tow = dp[step][From[step + 1][jj][kk].first][From[step + 1][jj][kk].second] ;
for (int qwq = 1 ; qwq <= dp[step + 1][jj][kk] - tow ; ++ qwq) printf("%d ", step) ;
}
int main(){
cin >> N >> a >> b ;
for (i = 1 ; i <= N ; ++ i) cin >> blood[i], ++ blood[i] ;
memset(dp, 63, sizeof(dp)), dp[2][blood[1]][blood[2]] = 0 ;
for (i = 2 ; i < N ; ++ i)
for (j = 0 ; j <= blood[i - 1] ; ++ j)
for (k = 0 ; k <= blood[i] ; ++ k){
int down_ = (j + b - 1) / b ;
if (dp[i][j][k] > INF) continue ;
int up_ = max(down_, max((blood [i + 1] + b - 1) / b, (k + a - 1) / a)) ;
for (l = down_ ; l <= up_ ; ++ l){
int now_j = max(0, k - a * l) ;
int now_k = max(0, blood[i + 1] - b * l) ;
if (dp[i + 1][now_j][now_k] > dp[i][j][k] + l)
dp[i + 1][now_j][now_k] = dp[i][j][k] + l,
From[i + 1][now_j][now_k] = Mp(j ,k) ;
}
}
cout << dp[N][0][0] << endl ; Print(N - 1, 0, 0) ; return 0 ;
}

$\rm CF ·6E$

给一个$n$个元素的序列,从中挑出最长的子序列,要求子序列中元素差的最大值不超过$k$。问有几个最长子序列,子序列长度,以及这几个子序起始、终止位置。

$n\leq 100,000$

憨批题。显然就是个单调队列,但是发现似乎并没有什么很诡异的限制,并且只要求一个最大值最小值。于是果断想到$st$表套二分,复杂度$n\log n-n\log^2 n$……被单调队列吊起来锤233

值得注意的一点是,$st$表回答询问的复杂度,大多数写法都是亚$\log $级别的,而不是传的神乎其神的$O(1)$。但其实只要预处理一下大于等于$x$的$2$的幂即可。

然后CSP前试机的时候顺便写出了单调队列的做法,代码大概长这样:

1
2
3
4
5
6
7
8
9
10
11
int q[MAXN], p[MAXN] ;
int l = 1, h1 = 1, t1 = 0, h2 = 1, t2 = 0 ;
for (i = 1 ; i <= N ; ++ i){
while (h1 <= t1 && base[q[t1]] < base[i]) t1 -- ;
while (h2 <= t2 && base[p[t2]] < base[i]) t2 -- ;
q[++ t1] = p[++ t2] = i ;
while (h1 <= t1 && h2 <= t2 && base[q[h1]] - base[p[h2]] > K){
l ++ ; while (q[h1] < l) ++ h1 ; while (p[h2] < l) ++ h2 ;
}
ans = max(ans, s[i] - s[l - 1]) ;
}

然后是二分$st$表

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
inline void build_ST(){
register int H = log(N) / log(2) + 1 ;
for (j = 1 ; j <= H ; ++ j)
for (i = 1 ; i + (1 << j) <= N + 1 ; ++ i)
dp1[i][j] = max(dp1[i][j - 1], dp1[i + (1 << j - 1)][j - 1]),
dp2[i][j] = min(dp2[i][j - 1], dp2[i + (1 << j - 1)][j - 1]) ;
}
inline int query_max(int l, int r){
register int k = 0 ;
if (l == r) return base[l] ;
while (l + (1 << k) <= r) ++ k ;
return max(dp1[l][k - 1], dp1[r - (1 << k - 1) + 1][k - 1]) ;
}
inline int query_min(int l, int r){
register int k = 0 ;
if (l == r) return base[l] ;
while (l + (1 << k) <= r) ++ k ;
return min(dp2[l][k - 1], dp2[r - (1 << k - 1) + 1][k - 1]) ;
}
int main(){
cin >> N >> K ;
for (i = 1 ; i <= N ; ++ i)
dp1[i][0] = dp2[i][0] = base[i] = qr() ;
build_ST(), ans = 0 ;
for (i = 1 ; i <= N ; ++ i){
L = i, R = N ;
while (L <= R){
Mid = (L + R) >> 1 ;
if (query_max(i, Mid) - query_min(i, Mid) <= K)
t = Mid, L = Mid + 1 ;
else R = Mid - 1 ;
}
L = t ;
if (L - i + 1 > ans) ans = L - i + 1, Ans[cnt = 1][0] = i, Ans[cnt][1] = L ;
else if (L - i + 1 == ans) Ans[++ cnt][0] = i, Ans[cnt][1] = L ;
}
cout << ans << " " << cnt << endl ;
for (i = 1 ; i <= cnt ; ++ i)
printf("%d %d\n", Ans[i][0], Ans[i][1]) ; return 0 ;
}

$\rm CF·7C$

给定一条直线:$Ax+By+C=0$($A,B$不同时为$0$),找到任意一个点(在$-5e18$~$5e18$之间)让它的横纵坐标均为整数,或者确定没有这样的点。

sb的exgcd。我当时为什么要做这种题?$\rm Cf$又为什么要出这种题?qwq

$\rm CF·7D$

一个长度为$n$字符串$\sf S$被叫做$k$阶回文串,当且仅当它本身是一个回文串,而且它长度为$\lfloor \frac{n}{2}\rfloor$的前缀和后缀都是$k-1$阶回文串。任何一个字符串(包括空字符串)都至少是$0$阶字符串。举例来说,abaaba是3阶字符串。

现在给定你一字符串,请你求出其所有前缀的的阶级之和。

$|\sf S|\leq 5,000,000$

似乎有时候哈希写的比较$6$这种题几乎是秒。考虑$f_i$表示以$i$为结尾的字符串的阶数,那么

答案就是$\sum f_i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const long long base = 131 ;bool mark[MAXN] ;
char S[MAXN] ; int N, Ans, i, j, h, ans[MAXN] ;
long long base1[MAXN], base2[MAXN], times[MAXN] ;

inline void init(){
times[0] = 1 ;
for (i = 1 ; i <= N ; ++ i)
base1[i] = (base1[i - 1] * base + S[i]) % Mod ;
for (i = 1 ; i <= N ; ++ i)
base2[i] = (base2[i - 1] * base + S[N - i + 1]) % Mod ;
for (i = 1 ; i <= N ; ++ i) times[i] = times[i - 1] * base % Mod ;
}
int main(){
scanf("%s", S + 1),
N = strlen(S + 1), init() ;
for (i = 1 ; i <= N ; ++ i){
h = i / 2 ;
long long t1 = base1[h] % Mod ;
long long t2 = (base2[N - i + h] - (base2[N - i] * times[h] % Mod) + Mod) % Mod ;
ans[i] = (t1 == t2) * (ans[h] + 1), Ans += ans[i] ;
}
cout << Ans << endl ; return 0 ;
}

$\rm CF·8C$

平面上有$n\leq 24$个物品,pks从原点出发,求全部拾起并且回到原点行走的最短总距离。注意,他不能同时拿$>2$件物品。

我寻思着这不就是个欧拉路……只不过加了个限制。那么还是$\sf f_S$表示拿完$\sf S$里的东西,所走的最小距离。每次枚举两个点转移即可。但是注意即使是$\rm Cf$的机子,$2^{24}\cdot 24^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
38
int dp[MAXN], Pre[MAXN], Max ;
int N, D[50][50], i, j, k, bit[50], tp ; pair<int, int> Obj[50] ;

int main(){
cin >> Obj[0].fr >> Obj[0].sc >> N ;
for (i = 1 ; i <= N ; ++ i) cin >> Obj[i].fr >> Obj[i].sc ;
for (i = 0 ; i <= N ; ++ i)
for (j = 0 ; j < i ; ++ j)
D[i][j] = D[j][i] = (Obj[i].fr - Obj[j].fr) * (Obj[i].fr - Obj[j].fr)
+ (Obj[i].sc - Obj[j].sc) * (Obj[i].sc - Obj[j].sc) ;
Max = (1 << N) - 1 ;
for (i = 1 ; i <= Max ; ++ i) dp[i] = Inf ;
for (i = 1 ; i <= Max ; ++ i){
memset(bit, 0, sizeof(bit)), tp = 0 ;
for (j = 0 ; j < N ; ++ j) if (1 << j & i) bit[++ tp] = j + 1 ;
for (j = 1 ; j <= tp ; ++ j)
for (k = 1 ; k <= tp ; ++ k){
if (j != k){
if (dp[i] > dp[i ^ (1 << bit[k] - 1) ^ (1 << bit[j] - 1)] + D[bit[k]][bit[j]] + D[0][bit[k]] + D[0][bit[j]])
dp[i] = dp[i ^ (1 << bit[k] - 1) ^ (1 << bit[j] - 1)] + D[bit[k]][bit[j]] + D[0][bit[k]] + D[0][bit[j]],
Pre[i] = i ^ (1 << bit[k] - 1) ^ (1 << bit[j] - 1) ;
}
else
if (dp[i] > dp[i ^ (1 << bit[k] - 1)] + D[0][bit[k]] + D[bit[k]][0])
dp[i] = dp[i ^ (1 << bit[k] - 1)] + D[0][bit[k]] + D[bit[k]][0],
Pre[i] = i ^ (1 << bit[k] - 1) ;
if (dp[i] < 1061109567) break ;
}
}
cout << dp[Max] << endl ;
while (Max){
cout << 0 << " " ;
int qaq = Max ^ Pre[Max] ;
for (i = 0 ; i < N ; ++ i) if (1 << i & qaq) cout << i + 1 << " " ;
Max = Pre[Max] ;
}
cout << 0 << endl ; return 0 ;
}

$\rm CF·9D$

用$n$个点组成二叉树,问高度大于等于$h$的有多少个。

$n\leq 35$

没有限制就是卡特兰数这不必说……但是如果跳出思维定式的话,考虑原来的$dp_i$表示前i个点组成二叉树的方案数,转移就是枚举两个子树——那么如果要考虑高度,只需要加一维高度$j$即可,正好是高度$+1-1$的关系。

1
2
3
4
5
6
7
8
9
int main(){
cin >> N >> H ; int i, j, k ;
for (i = 0 ; i <= N ; ++ i) dp[0][i] = 1 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= N ; ++ j)
for (k = 0 ; k < j ; ++ k)
dp[j][i] += dp[k][i - 1] * dp[j - k - 1][i - 1] ;
cout << dp[N][N] - dp[N][D - 1] ;
}

$\rm CF·10C$

定义函数$s(x)$,$s(x)$的值等于$x$各数位上的数值之和,定义函数$d(x)$,当$s(x)\leq 9$时$d(x)=s(x)$,否则$d(x)=d(s(x))$。举例来说,$d(6543)=d(6+5+4+3)=d(18)=9$

现在给定一上限$N$,求在$[1….N]$内任取$A$,$B$,$C$满足$A\cdot B\not =C$且$d(C)=d(d(A)⋅d(B))$的组数。

$N\leq 1000000$

考虑$d()$的本质:

那么其实$a\cdot b=c$就一定意味着$d(d(a)\cdot d(b))=d(c)$,所以启发我们可以先求出后一部分的,然后减去前一部分。那么前一半的就是$\leq n$所有数的约数个数和。而这东西有一个经典的$O(n)$做法,就是枚举每一个$i$对它的倍数产生贡献。

那么后一半就可以考虑按照余数分类做,然后乘法原理乘起来即可。

1
2
3
4
5
6
7
8
9
10
11
long long N, base[20], A, B, i, j ; 

int main(){
cin >> N ;
for (i = 1 ; i <= N ; ++ i)
base[i % 9] ++, B += N / i ;
for (i = 0 ; i <= 8 ; ++ i)
for (j = 0 ; j <= 8 ; ++ j)
A += base[i] * base[j] * base[i * j % 9] ;
cout << A - B << endl ; return 0 ;
}

$\rm CF·10D$

求两个串的最长公共上升子序列。

  • $n\leq 500$

  • $n\leq 5,000$

第一个$subtask$,考虑$\sf f_{i,j}$表示$A$到$i$,$B$到$j$的最长公共上升子序列。那么转移的时候考虑多枚举一维$k$,当$A_i=B_j$时,可以从$k$转移过来。于是复杂度为$n^3$。

1
2
3
4
5
6
7
8
9
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j){
dp[i][j] = dp[i - 1][j] ;
if (base1[i] != base2[j]) continue ;
dp[i][j] = 1 ;
for (k = 1 ; k < j ; ++ k)
if (base2[k] < base2[j] && dp[i][j] < dp[i - 1][k] + 1)
dp[i][j] = dp[i - 1][k] + 1, f[j] = k ;
}

但是考虑其实$j$每次向右只加了$1$,所以对于同一个$i$,有很多决策都是重复的。换句话说就是这个决策($k$)是否应该选,在$j=k$时就可以求出来,而不用再向前扫一遍,因为在$A_i$定住的时候是没区别的。

于是最后:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int x){
if (!x) return ;
dfs(pre[x]), printf("%d ", B[x]) ;
}
int main(){
int i, j, k, n = 0 ;
for (N = qr(), i = 1 ; i <= N ; ++ i) A[i] = qr() ;
for (M = qr(), i = 1 ; i <= M ; ++ i) B[i] = qr() ;
for (i = 1 ; i <= N ; ++ i){
int res = 0, befo = 0 ;
for (j = 1 ; j <= M ; ++ j){
if (A[i] != B[j]) f[i][j] = f[i - 1][j] ;
else f[i][j] = res + 1, pre[j] = befo ;
if (B[j] < A[i])
if (res < f[i - 1][j])
res = f[i - 1][j], befo = j ;
}
}
for (i = 1 ; i <= M ; ++ i) if (ans < f[N][i]) ans = f[N][i], n = i ;
cout << ans << endl ; dfs(n) ; return 0 ;
}

$\rm CF·11C$

你有一个$01$矩阵。里面有多少个正方形?

其中正方形的边用$1$表示。我们现在只对这些正方形感兴趣:

第一种:每条边与矩阵的边平行的正方形;

第二种:每条边与矩阵的对角线平行的正方形。

$t\leq 10,000\quad 2\leq n,m\leq 250$

然后就是个搜索,用来练程序实现的。大概就是考虑八连通地去$\sf dfs$ ,然后只搜$1$不搜$0$,记录一下搜过的周长,然后去$check$ 。$check$主要就是分类讨论是平行对角线还是平行边长。

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
void dfs(int x, int y, int &step){
if (base[x][y] != 1) return void() ;
base[x][y] = -1, ++ step ;
for (int i = 0 ; i < 8 ; ++ i){
int kx = x + dx[i], ky = y + dy[i] ;
if (kx >= 1 && kx <= N && ky >= 1 && ky <= M) dfs(kx, ky, step) ;
}
return void() ;
}
int chk1(int step, int x, int y){
if (x + step > N || y + step > M) return 0 ;
for (int i = 1, j ; i <= step ; ++ i){
j = (base[x + i][y] != -1) | (base[x][y + i] != -1)
| (base[x + step][y + i] != -1) | (base[x + i][y + step] != -1) ;
if (j) return 0 ;
}
return 1 ;
}
int chk2(int step, int x, int y){
int lx = step << 1 ;
if (x + lx > N || y + step > M) return 0 ;
if (base[x + lx][y] != -1 || y < step) return 0 ;
for (int i = 1, j ; i <= step ; ++ i){
j = (base[x + lx - i][y - i] != -1) | (base[x + lx - i][y + i] != -1)
| (base[x + i][y - i] != -1) | (base[x + i][y + i] != -1) ;
if (j) return 0 ;
}
return 1 ;
}
int main(){
cin >> T ; int i, j ;
while (T --){
cin >> N >> M, ans = 0 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
scanf("%1d", &base[i][j]) ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j){
if (base[i][j] != 1) continue ;
res = 0, dfs(i, j, res) ;
if (res % 4 == 0 && res / 4 <= min(N, M))
ans += chk1(res / 4, i, j) + chk2(res / 4, i, j) ;
}
cout << ans << endl ;
}
return 0 ;
}

$\rm CF·11D$

求简单无向图的环数。

$n\leq 19$

一开始想状压边,但是发现转移比较难转移并且状态数太多。于是就考虑定$\sf f_{s,u,v}$表示走过了集合$\sf s$中的点,起点为$u$终点为$v$的方案数。枚举转移的时候考虑刷表,枚举不在集合$\sf s$中的一个新点转移。

观察到其实转移时并不需要知道是从哪个点转移过来的,这东西也不影响方案数,所以直接默认是从lowbit转移过来的,这样每次需要判一下新的点会不会破坏这个状态的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
cin >> N >> M, Mx = (1 << N) - 1 ;
for (i = 1, j = 0 ; j < N ; ++ j, i <<= 1) f[i][j] = 1 ;
for (i = 1 ; i <= M ; ++ i) cin >> u >> v, u --, v --, A[u][v] = A[v][u] = 1 ;
for (s = 1 ; s <= Mx ; ++ s){
for (i = 0 ; i < N ; ++ i){
if (!((1 << i) & s) || !f[s][i]) continue ;
for (j = 0 ; j < N ; ++ j){
if (!A[i][j] || low(s) > (1 << j)) continue ;
if ((1 << j) == low(s) && (1 << j & s)) ans += f[s][i] ;
else if (!(1 << j & s)) f[s | (1 << j)][j] += f[s][i] ;
}
}
}
cout << ((ans - M) >> 1) << endl ;