「算法」拓展欧几里得算法--exgcd

算法

由Bézout定理有:

形如$ax+by$的最小正整数解为$gcd(a,b)$

则有线性方程定理:

设$a,b\in N^*,g=gcd(a,b)$,则方程:

$ax+by=g$,总有一个正整数解$(x_1,y_1)$,可以通过exgcd得到。

而其每一个解可由$(x_1+\frac{kb}{g},y_1-\frac{ka}{g}),k\in N$得到。

代码

1
2
3
4
5
6
int exgcd(int a,int b,int &x,int &y){
if(b == 0){x = 1,y = 0;return a;}
int d = exgcd(b,a % b,x,y);
int z = x;x = y;y = z - y * (a / b);
return d;
}
分享到

「工程」html表单传值给php

问题

我想弄个在线计算md5值的框框,这样就不需要他人或者用后端语言啦。

于是想到了php里面的函数md5(),就能满足我的需要了(虽然我之前没有搞过php)。

但是发现我不会把表单里的数据传到php,,,

解决

于是就要google,首先是html部分,表单都是一样的,区别只有nametype而已。

然后用get方法传值,其实post也可以的。

1
2
3
4
<form action="https://api.cinema000.xyz/md5.php" method="get">     	
<input name="q" type="text">
<input name="submit" type="submit" value="Make">
</form>

在php中可以通过$_GET得到传过来的值,但是直接echo就会发现输出Array,说明那玩意是个数组,下标就是前面的name

1
2
3
4
5
<?php
if ($_GET["submit"] == "Make") {
echo md5($_GET['q']);
}
?>
分享到

「题解」Luogu 4942「小凯的数字」

分析

有如下引理:

一个数取余9的值等于其各个数字取余9的值

显然易证,证毕。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<cstdio>
typedef long long int64;
typedef __int128 int128;
int main(){
int T;int64 l,r;int128 s;scanf("%d",&T);
while(T--){
scanf("%lld %lld",&l,&r);
s = (int128)(l + r) * (int128)(r - l + 1) / 2;
printf("%lld\n",int64(s % 9));
}

return 0;
}
分享到

「题解」Luogu 1038「神经网络」

分析

这题数据范围极小,直接暴力枚举出入度模拟拓扑排序。

代码

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
/*#include<cstdio>
#include<vector>
const int MAXN = 100 + 6;
enum DFSColor{WHITE,GRAY,BLACK};
struct Vertex{
int id,u,c,d,f;
DFSColor color;
Vertex(){
color = WHITE;
}
Vertex(int id,int c,int u){
this -> id = id;
this -> c = c;
this -> u = u;
d = f = 0;
color = WHITE;
}
};
struct Edge{
int v,d;
Edge(){}
Edge(int v,int d){
this -> v = v;
this -> d = d;
}
};
int time;
std::vector<Vertex> V;
std::vector<Edge> G[MAXN];
void dfsVisit(Vertex &u){
time++;
u.d = time;
u.color = GRAY;
for(int i = 0;i < G[u.id].size();i++){
Edge &e = G[u.id][i];
if(V[e.v].color == WHITE) dfsVisit(V[e.v]);
}
u.color = BLACK;
time++;
u.f = time;
}
void dfs(){
for(int i = 0;i < V.size();i++) V[i].color = WHITE;
time = 0;
for(int i = 0;i < V.size();i++) if(V[i].color == WHITE) dfsVisit(V[i]);
}
void addEdge(int u,int v,int d){
G[u].push_back(Edge(v,d));
}

int main(){
int n,p,c,u,v,d;scanf("%d %d",&n,&p);
for(int i = 0;i < n;i++){
scanf("%d %d",&c,&u);
V.push_back(Vertex(i,c,u));
}
while(p--){
scanf("%d %d %d",&u,&v,&d);
u--;v--;
addEdge(u,v,d);
}
dfs();
for(int i = 0;i < V.size();i++){
printf("%d ",V[i].id + 1);
}
puts("");
for(int i = 0;i < V.size();i++){
printf("%d ",V[i].f);
}

return 0;
}
*/
#include<cstdio>
#include<cstring>
const int INF = 0x3f3f3f3f,MAXN = 100 + 6;
int G[MAXN][MAXN],C[MAXN],U[MAXN];
bool out[MAXN],in[MAXN];
int main(){
int n,m,u,v,d,cnt1,cnt2;scanf("%d %d",&n,&m);
for(int i = 1;i <= n;i++) scanf("%d %d",&C[i],&U[i]);
memset(G,INF,sizeof(G));
for(int i = 1;i <= m;i++){
scanf("%d %d %d",&u,&v,&d);
G[u][v] = d;
out[u] = in[v] = true;
}
for(int i = 1;i <= n;i++) if(in[i]) C[i] -= U[i];
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(G[i][j] != INF && C[i] > 0) C[j] += G[i][j] * C[i];
for(int i = 1;i <= n;i++){
if(!out[i]) cnt1++;
if(!out[i] && C[i] <= 0) cnt2++;
}
if(cnt1 == cnt2){printf("NULL");return 0;}
for(int i = 1;i <= n;i++) if(!out[i] && C[i] > 0) printf("%d %d\n",i,C[i]);

return 0;
}
分享到

「题解」Luogu 1311「选择客栈」

分析

模拟赛写了这题,然后只会暴力60分的解法,不会递推阿。

遍历1到n,每次都输入colorprice,用一个变量now记录离第二个客栈最近的咖啡厅的价钱合理的客栈位置。

然后用last[i]表示最后一个以i为颜色的客栈的位置;

cnt[i]为以i为颜色的客栈总数;

sum[i]表示当前的方案数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
const int MAXN = 200000 + 6;
int last[MAXN],sum[MAXN],cnt[MAXN];
int main(){
int n,k,p,color,price,now,ans = 0;scanf("%d %d %d",&n,&k,&p);
for(int i = 1;i <= n;i++){
scanf("%d %d",&color,&price);
if(price <= p) now = i;
if(now >= last[color]) sum[color] = cnt[color];
last[color] = i;
ans += sum[color];
cnt[color]++;
}
printf("%d",ans);

return 0;
}
分享到

「项目」Cinema-Random-Data-Generator

简介

这是个写了不久的随机数生成器,用Java写的,UI就当然是JavaFX啦。

顺便庆祝自己生日?

地址

URL
Githubhttps://github.com/CinemaMediaGroup/Cinema-Random-Data-Generator
Gogs(自建)https://git.cinema000.xyz/CinemaMediaGroup/Cinema-Random-Data-Generator
分享到

「题解」Luogu 2073「送花」

分析

在机房小伙伴的安利下写了这题,其实看题发现set就可以解决问题了,但是想想还是手写一个红黑树好一点嘻嘻。(其实rank1的代码还真是set,,,开了-o2的set就是挂,真心跑不过阿(36ms),本人才74ms)。

差不多是平衡树版题,对于像我这样写成一个template的,可以创建花类(class Flower,或者你们的struct),然后重载小于号和等于号,这样都不用动树本身的。

代码

6.32kb的码量,,,这大概就是考场不常见的原因吧

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
#include<cstdio>
int ansW,ansC;
enum RBColor{RED,BLACK};
template<class T>
class RBTNode{
public:
T key;
RBColor color;
int size,cnt;
RBTNode *p,*ch[2];
RBTNode(){}
RBTNode(T key){
this -> key = key;
size = cnt = 1;
color = RED;
}
};
template<class T>
class RBT{
public:
RBTNode<T> *root,*nil;
RBT<T>(){
nil = new RBTNode<T>();
nil -> color = BLACK;
nil -> size = nil -> cnt = 0;
root = new RBTNode<T>();
root = nil;
root -> p = nil;
}
inline void inOrder(RBTNode<T> *x){
if(x != nil){
inOrder(x -> ch[0]);
ansC += x -> key.c,ansW += x -> key.w;
inOrder(x -> ch[1]);
}
}
inline void rotate(RBTNode<T> *x,bool isRight){
RBTNode<T> *y = x -> ch[!isRight];
x -> ch[!isRight] = y -> ch[isRight];
if(y -> ch[isRight] != nil) y -> ch[isRight] -> p = x;
y -> p = x -> p;
if(x -> p == nil) root = y;
else x -> p -> ch[x == x -> p -> ch[1]] = y;
y -> ch[isRight] = x;
x -> p = y;
y -> size = x -> size;
x -> size = x -> ch[0] -> size + x -> ch[1] -> size + x -> cnt;
}
inline RBTNode<T>* minimum(RBTNode<T> *x){
if(x == nil) return nil;
while(x -> ch[0] != nil) x = x -> ch[0];
return x;
}
inline RBTNode<T>* maximum(RBTNode<T> *x){
if(x == nil) return nil;
while(x -> ch[1] != nil) x = x -> ch[1];
return x;
}
inline RBTNode<T>* find(T k){
RBTNode<T> *x = root;
while(x != nil){
if(x -> key == k) return x;
x = x -> ch[x -> key < k];
}
return nil;
}
inline void insert(T k){
RBTNode<T> *x = root,*y = nil,*z = new RBTNode<T>(k);
while(x != nil){
y = x;
y -> size++;
if(x -> key == k){x -> cnt++;return;}
x = x -> ch[x -> key < k];
}
z -> p = y;
z -> ch[0] = z -> ch[1] = nil;
if(y == nil) root = z;
else y -> ch[y -> key < k] = z;
insertFixup(z);
}
inline void insertFixup(RBTNode<T> *z){
RBTNode<T> *fa,*ga,*y;
bool isLeft;
while(z -> p -> color == RED){
fa = z -> p,ga = fa -> p;
isLeft = fa == ga -> ch[0];
y = ga -> ch[isLeft];
if(y -> color == RED){
y -> color = fa -> color = BLACK;
ga -> color = RED;
z = ga;
}else{
if(z == fa -> ch[isLeft]){z = fa;rotate(z,!isLeft);}
z -> p -> color = BLACK;
z -> p -> p -> color = RED;
rotate(ga,isLeft);
}
}
root -> color = BLACK;
}
inline void transplant(RBTNode<T> *u,RBTNode<T> *v){
v -> p = u -> p;
if(u -> p == nil) root = v;
else u -> p -> ch[u == u -> p -> ch[1]] = v;
}
inline void remove(T k){
RBTNode<T> *z = root,*w = nil,*y,*x,*delta;
RBColor oldColor;
while(z != nil){
w = z;
w -> size--;
if(k == z -> key) break;
z = z -> ch[z -> key < k];
}
if(z != nil){
if(z -> cnt > 1){z -> cnt--;return;}
y = z;
oldColor = y -> color;
if(z -> ch[0] == nil){x = z -> ch[1];transplant(z,z -> ch[1]);}
else if(z -> ch[1] == nil){x = z -> ch[0];transplant(z,z -> ch[0]);}
else{
y = minimum(z -> ch[1]);
oldColor = y -> color;
x = y -> ch[1];
if(y -> p == z) x -> p = y;
else{
delta = y;
while(delta != z){
delta -> size -= y -> cnt;
delta = delta -> p;
}
transplant(y,y -> ch[1]);
y -> ch[1] = z -> ch[1];
y -> ch[1] -> p = y;
}
transplant(z,y);
y -> ch[0] = z -> ch[0];
y -> ch[0] -> p = y;
y -> color = z -> color;
y -> size = y -> ch[0] -> size + y -> ch[1] -> size + y -> cnt;
}
if(oldColor == BLACK) removeFixup(x);
}else{
while(w != nil){w -> size++;w = w -> p;}
}
delete z;
}
inline void removeFixup(RBTNode<T> *x){
RBTNode<T> *fa,*w;
bool isLeft;
while(x != root && x -> color == BLACK){
fa = x -> p;
isLeft = x == x -> p -> ch[0];
w = fa -> ch[isLeft];
if(w -> color == RED){
fa -> color = RED;
w -> color = BLACK;
rotate(fa,!isLeft);
w = fa -> ch[isLeft];
}
if(w -> ch[0] -> color == BLACK && w -> ch[1] -> color == BLACK){w -> color = RED;x = x -> p;}
else{
if(w -> ch[isLeft] -> color == BLACK){
w -> color = RED;
w -> ch[!isLeft] -> color = BLACK;
rotate(w,isLeft);
w = fa -> ch[isLeft];
}
w -> color = fa -> color;
fa -> color = BLACK;
w -> ch[isLeft] -> color = BLACK;
rotate(w -> p,!isLeft);
x = root;
}
}
x -> color = BLACK;
}
};
class Flower{
public:
int w,c;
Flower(){}
Flower(int w,int c){
this -> w = w;
this -> c = c;
}
bool operator == (const Flower &rhs) const{
return c == rhs.c;
}
bool operator < (const Flower &rhs) const{
return c < rhs.c;
}
};
RBT<Flower> T;
int main(){
int op,w,c;
Flower e;
RBTNode<Flower> *d;
while(scanf("%d",&op) == 1 && op != -1){
if(op == 1){
scanf("%d %d",&w,&c);
e = Flower(w,c);
if(T.find(e) == T.nil) T.insert(e);
}else if(op == 2){
d = T.maximum(T.root);
if(d != T.nil) T.remove(d -> key);
}else if(op == 3){
d = T.minimum(T.root);
if(d != T.nil) T.remove(d -> key);
}
}
T.inOrder(T.root);
printf("%d %d",ansW,ansC);

return 0;
}
分享到

「随笔」Emacs--神的编辑器

简介

Emacs与Vim并称神的编辑器和编辑器之神。

而我为了NOIP考场上能用括号补全,入坑了Emacs。

其实一开始会有点不习惯,因为快捷键和一般软件大多不同,不过习惯了(大概模了半个小时)就发现这个货手感巨JB好的。

个人的开发兴趣也许会降低,公司会倒闭,但是自由软件基金会永垂不朽!

界面

直接看界面就好了:

不做特别评价。

快捷键

约定:

C表示Ctrl

M表示Alt

S表示Shift

<ret>表示回车

-表示一起按下

毕竟我也是刚入坑,所以就只有几个常用的:

  1. 复制 M-w
  2. 剪切 C-w
  3. 粘贴 C-y
  4. 选择 [email protected](就是C-S-2,之后松开2,但是不要松开C和S,然后用方向键之类的)
  5. 撤销 C-x u
  6. 保存(续命) C-x C-s

配置文件

提配置文件是因为要括号补全嘛,顺便把行号和tab也搞定了,我先说怎样加载配置文件:

配置文件位置:~/.emacs.d/init.el,不存在就新建,这是Linux的路径,Windows的自己找找吧233

加载配置文件方法:M-x <ret> ~/.emacs.d/init.el,就是M-x后再来个回车然后再输入路径。

看下我的配置文件(有注释版(应该使用无注释版,后面有)):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(global-linum-mode 1)#开启行号
(electric-pair-mode 1)#开启括号匹配
(setq electric-pair-pairs '(#自定义括号匹配,没有匹配小于号,因为,,,
(?\' . ?\')
(?\" . ?\")
(?\{ . ?\})
(?\[ . ?\])
(?\( . ?\))
))
(show-paren-mode 1)#开启括号高亮
(setq show-paren-style 'parenthesis)#自定义括号匹配样式
(setq-default indent-tabs-mode nil)#将tab替换为空格
(setq c-basic-offset 4)#c/c++ tab宽
(setq c-default-style "linux")#避免大括号匹配出锅
(setq default-tab-width 4)#tab宽

无注释版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(global-linum-mode 1)
(electric-pair-mode 1)
(setq electric-pair-pairs '(
(?\' . ?\')
(?\" . ?\")
(?\{ . ?\})
(?\[ . ?\])
(?\( . ?\))
))
(show-paren-mode 1)
(setq show-paren-style 'parenthesis)
(setq-default indent-tabs-mode nil)
(setq c-basic-offset 4)
(setq c-default-style "linux")
(setq default-tab-width 4)
分享到

「题解」UVa 12174「Shuffle」

分析

用滑动窗口来思考即可。

代码

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
#include<cstdio>
#include<algorithm>
const int MAXN = 100000 + 6;
int X[MAXN * 3],cnt[MAXN];
bool hash[MAXN * 2];

int main(){
int T,s,n,tot,ans;scanf("%d",&T);
bool running;
while(T--){
scanf("%d %d",&s,&n);
std::fill(X,X + n + 2 * s,-1);
for(int i = 0;i < n;i++) scanf("%d",&X[i + s]);
tot = ans = 0;
std::fill(cnt + 1,cnt + s + 1,0);
std::fill(hash,hash + n + s + 1,false);
for(int i = 0,len = n + s + 1;i < len;i++){
if(tot == s || (i < s && tot == i) || (i > n && tot == n + s - i)) hash[i] = true;
if(i == n + s) break;
if(X[i] != -1 && --cnt[X[i]] == 0) tot--;
if(X[i + s] != -1 && cnt[X[i + s]]++ == 0) tot++;
}
for(int i = 0;i < s;i++){
running = true;
for(int j = i,len = n + s + 1;j < len;j += s) if(!hash[j]) running = false;
if(running) ans++;
}
printf("%d\n",ans == n + 1 ? s : ans);
}

return 0;
}
分享到

「题解」UVa 1607「Gates」

分析

二分尝试即可。

代码

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
#include<cstdio>
#include<algorithm>
const int MAXM = 200000 + 6;
int n,m;
struct Gate{
int a,b,o;
};Gate G[MAXM];
int output(int k){
int a,b,va,vb;
for(int i = 1;i <= m;i++){
a = G[i].a,b = G[i].b;
va = a < 0 ? -a > k : G[a].o;
vb = b < 0 ? -b > k : G[b].o;
G[i].o = !(va && vb);
}
return G[m].o;
}
int solve(int vn){
int L = 1,R = n,mid;
while(L < R){
mid = L + (R - L) / 2;
if(output(mid) == vn) R = mid;
else L = mid + 1;
}
return L;
}
int main(){
int T,v0,vn,x;scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;i++) scanf("%d %d",&G[i].a,&G[i].b);
v0 = output(0),vn = output(n);
if(v0 == vn) for(int i = 1;i <= n;i++) printf("0");
else{
x = solve(vn);
for(int i = 1;i < x;i++) printf("0");
printf("x");
for(int i = x + 1;i <= n;i++) printf("1");
}
puts("");
}
}
分享到

「题解」UVa 690「Pipeline Scheduling」

分析

见标签

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN = 5,MAXM = 100 + 6;
int n,c,ans,W[MAXN],jump[MAXM];
bool check(int s[],int k){
for(int i = 0;i < MAXN;i++) if((s[i] >> k) & W[i]) return false;
return true;
}
void init(){
char s[MAXM];
ans = n * 10;
memset(W,0,sizeof(W));
for(int i = 0;i < MAXN;i++){
scanf("%s",s);
for(int j = 0;j < n;j++) if(s[j] == 'X') W[i] |= (1 << j);
}
for(int i = 0;i <= n;i++) if(check(W,i)) jump[c++] = i;
}
void dfs(int s[],int d,int sum){
if(sum + jump[0] * (10 - d) > ans) return;
if(d == 10){ans = std::min(ans,sum);return;}
int P[MAXN];
for(int i = 0;i < c;i++)
if(check(s,jump[i])){
for(int j = 0;j < MAXN;j++) P[j] = (s[j] >> jump[i]) ^ W[j];
dfs(P,d + 1,sum + jump[i]);
}
}
int main(){
while(scanf("%d",&n) == 1 && n){
init();
dfs(W,1,n);
printf("%d\n",ans);
}

return 0;
}
分享到

「题解」Luogu 4932「浏览器」

分析

首先利用了g++内置函数__builtin_parity(x),用于返回x的二进制表示下1个数的奇偶。

内置函数很快,可以近似为$O(1)$。

然后再利用xor运算的性质,统计每个点权值的parity,然后用奇数的个数乘上偶数的个数就是答案。

Hints

注意中间结果不要溢出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<cstdio>
typedef long long int64;
const int MAXN = 1e7 + 6;
int64 X[MAXN];
int cnt[MAXN];

int main(){
int n,a,b,c,d;scanf("%d %d %d %d %d %lld",&n,&a,&b,&c,&d,&X[0]);
register int i;register int64 ans1 = 0,ans2 = 0;
for(i = 1;i <= n;i++){
X[i] = ((a * X[i - 1] % d * X[i - 1] % d + b * X[i - 1] + c) % d + d) % d;
cnt[i] = __builtin_parity(X[i]);
if(cnt[i]) ans1++;
else ans2++;
}
printf("%lld",ans1 * ans2);
return 0;
}
分享到

「题解」Luogu 1034「矩形覆盖」

分析

DFS,枚举每个点属于的不同矩形,如果它本身被包含在矩阵里,就直接搜下一个点,否则就根据当前点扩大矩阵。

代码

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
#include<cstdio>
const int MAXN = 50 + 6,INF = 0x3f3f3f3f;
int n,k,ans = INF;
struct Point{
int x,y;
Point(){}
Point(int x,int y){
this -> x = x;
this -> y = y;
}
};Point P[MAXN];
struct Square{
Point l,r;
Square(){}
Square(Point l,Point r){
this -> l = l;
this -> r = r;
}
};Square S[MAXN];

inline bool fuck(int i,int j){
if(S[i].l.x == INF || S[i].l.y == INF || S[i].r.x == -INF || S[i].r.y == -INF ||
S[j].l.x == INF || S[j].l.y == INF || S[j].r.x == -INF || S[j].r.y == -INF ||
S[i].l.x > S[j].r.x || S[i].l.y > S[j].r.y || S[j].l.x > S[i].r.x || S[j].l.y > S[i].r.y) return false;
return true;
}

bool check(){
for(int i = 1;i <= k;i++) for(int j = i + 1;j <= k;j++) if(fuck(i,j)) return false;
return true;
}

int getS(){
int s = 0;
for(int i = 1;i <= k;i++) if(S[i].l.x != INF) s += (S[i].r.x - S[i].l.x) * (S[i].r.y - S[i].l.y);
return s;
}

void dfs(int cur){
if(cur == n + 1){ans = getS();return;}
Square delta;
for(int i = 1;i <= k;i++){
delta = S[i];
if(S[i].l.x > P[cur].x) S[i].l.x = P[cur].x;
if(S[i].l.y > P[cur].y) S[i].l.y = P[cur].y;
if(S[i].r.x < P[cur].x) S[i].r.x = P[cur].x;
if(S[i].r.y < P[cur].y) S[i].r.y = P[cur].y;
if(check() && getS() < ans) dfs(cur + 1);
S[i] = delta;
}
}

int main(){
scanf("%d %d",&n,&k);
for(int i = 1;i <= n;i++) scanf("%d %d",&P[i].x,&P[i].y);
for(int i = 1;i <= k;i++) S[i].l.x = S[i].l.y = INF,S[i].r.x = S[i].r.y = -INF;
dfs(1);
printf("%d",ans);

return 0;
}
分享到

「题解」Luogu 1033「自由落体」

分析

物理题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<cmath>
const double eps = 1e-4,G = 10;
double v;
inline double f(double x){return sqrt(G / (2.00 * x));}
int main(){
int n,ans = 0;
double h,s1,l,k;scanf("%lf %lf %lf %lf %lf %d",&h,&s1,&v,&l,&k,&n);
for(int i = 0;i < n && i <= s1;i++){
if(f(h) * (s1 - i) - v < eps && f(h - k) * (s1 + l - i) - v > -eps) ans++;
}
printf("%d",ans);

return 0;
}
分享到

「题解」Luogu 1032「字串变换」

分析

隐式图BFS

代码

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
#include<iostream>
#include<string>
#include<map>
#include<queue>
const int MAXN = 666;
int cnt;
bool running;
std::multimap<std::string,std::string> map;
std::multimap<std::string,std::string>::iterator it;

void bfs(std::string s,std::string t){
int pos;
std::queue<std::string> Q;
std::map<std::string,int> hash;
std::string cur,delta;
Q.push(s);
hash[s] = cnt;
while(Q.size()){
cur = Q.front();Q.pop();
cnt = hash[cur];
if(cnt > 10) break;
if(cur == t){running = true;break;}
for(it = map.begin();it != map.end();it++){
delta = cur;
pos = 0;
while((pos = delta.find(it -> first,pos)) != std::string::npos){
cur.replace(pos,it -> first.size(),it -> second);
if(!hash.count(cur)){
hash[cur] = cnt + 1;
Q.push(cur);
}
cur = delta;
pos++;
}
}
}
}
int main(){
running = false;
std::string A,B,delta1,delta2;
std::cin >> A >> B;
while(std::cin >> delta1 >> delta2) map.insert({delta1,delta2});
bfs(A,B);
A = cnt > 10 ? "NO ANSWER!" : std::to_string(cnt);
if(!running){std::cout << "NO ANSWER!";return 0;}
std::cout << A;

return 0;
}
分享到

「题解」Luogu 2347「砝码称重」

分析

直接$O(n^6)$暴力枚举,开启优化开关,即可通过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<unordered_set>
const int MAXN = 6 + 6;
int A[MAXN],B[10086];
int main(){
int ans = 0;
for(int i = 1;i <= 6;i++) scanf("%d",&A[i]);
for(int i = 0;i <= A[1];i++)
for(int j = 0;j <= A[2];j++)
for(int k = 0;k <= A[3];k++)
for(int l = 0;l <= A[4];l++)
for(int m = 0;m <= A[5];m++)
for(int n = 0;n <= A[6];n++)
B[i * 1 + j * 2 + k * 3 + l * 5 + m * 10 + n * 20]++;;
for(int i = 0;i < 1001;i++) if(B[i]) ans++;
printf("Total=%d",ans - 1);

return 0;
}
分享到