4c题目的小积累

记录一些忽视的小细节

最短路维护多个属性的问题

题目

L2-001. 紧急救援

AC代码

注意最短路径的条数的维护,一开始我想错了.way[]

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2+10;
const int INF = 1e9+10;
vector<int> G[maxn];
int n, m, s, t;
int pre[maxn];
int weight[maxn];
int way[maxn];
int dis[maxn];
bool vis[maxn];
int w[maxn][maxn];
int max_weight[maxn];
void dfs(int s){
for(int i=0; i<maxn; i++) dis[i] = INF;
memset(vis, 0, sizeof(vis));
for(int i=0; i<n; i++) max_weight[i] = 0;
dis[s] = 0;
max_weight[s] = weight[s];
way[s] = 1;
for(int i=0; i<n; i++){
int min_dis = INF;
int u = -1;
for(int j=0; j<n; j++){
if(!vis[j]&&dis[j]<min_dis){
u = j;
min_dis = dis[j];
}
}
vis[u] = true;
if(u == -1) return;
for(int j=0; j<G[u].size(); j++){
int v = G[u][j];
if(!vis[v]){
if(dis[v]>dis[u]+w[u][v]){
dis[v] = dis[u]+w[u][v];
way[v] = way[u];//这里需要注意一下
pre[v] = u;
max_weight[v] = max_weight[u]+weight[v];
}
else if(dis[v] == dis[u]+w[u][v]){
way[v] += way[u];//这里更新的时候需要注意一下
if(max_weight[v]<max_weight[u]+weight[v]){
pre[v] = u;
max_weight[v] = max_weight[u]+weight[v];
}
}
}
}
}
}
int main()
{
while(~scanf("%d%d%d%d", &n, &m, &s, &t)){
for(int i=0; i<n; i++) G[i].clear();
memset(way, 0, sizeof(way));
for(int i=0; i<n; i++) pre[i] = i;
for(int i=0; i<n; i++){
scanf("%d", &weight[i]);
}
int u, v, wei;
for(int i=0; i<m; i++){
scanf("%d%d%d", &u, &v, &wei);
G[u].push_back(v);
G[v].push_back(u);
w[u][v] = w[v][u] = wei;
}
dfs(s);
printf("%d %d\n", way[t], max_weight[t]);
stack<int> path;
while(!path.empty()){
path.pop();
}
int temp = t;
while(temp!=s){
path.push(temp);
temp = pre[temp];
}
path.push(s);
int len = path.size();
for(int i=0; i<len-1; i++){
int temp = path.top();
path.pop();
printf("%d ", temp);
}
temp = path.top();
path.pop();
printf("%d\n", temp);
}
return 0;
}

模拟整除

然后积累一下怎么模拟加法和减法吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
char ans[1001];
int main()
{
int n, len=1;
int pos = 0, num=1;
scanf("%d", &n);
while(len++){
if(pos||num/n){
ans[pos++] = num/n+'0';
}
num %= n;
if(num == 0){
ans[pos] = '\0';
printf("%s %d", ans, len-1);
break;
}
num = num*10+1;
}
return 0;
}

优先队列重新定义运算符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
struct Node{
string name;
int top;
friend bool operator < (Node a, Node b){
return a.top>b.top;
}
};
priority_queue<Node> pq;
int main()
{
return 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
#include <cstdio>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
void update(int x, int v) {
for(int i = x; i < maxn; i += lowbit(i))
c[i] += v;
}
int getsum(int x) {
int sum = 0;
for(int i = x; i >= 1; i -= lowbit(i))
sum += c[i];
return sum;
}
void PeekMedian() {
int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
while(left < right) {
mid = (left + right) / 2;
if(getsum(mid) >= k)
right = mid;
else
left = mid + 1;
}
printf("%d\n", left);
}
int main() {
int n, temp;
scanf("%d", &n);
char str[15];
for(int i = 0; i < n; i++) {
scanf("%s", str);
if(str[1] == 'u') {
scanf("%d", &temp);
s.push(temp);
update(temp, 1);
} else if(str[1] == 'o') {
if(!s.empty()) {
update(s.top(), -1);
printf("%d\n", s.top());
s.pop();
} else {
printf("Invalid\n");
}
} else {
if(!s.empty())
PeekMedian();
else
printf("Invalid\n");
}
}
return 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
#include <cstdio>
#include <vector>
using namespace std;
bool isMirror;
vector<int> pre;
vector<int> post;
void getpost(int root, int tail) {
if(root > tail) return ;
int i = root + 1, j = tail;
if(!isMirror) {
while(i <= tail && pre[root] > pre[i]) i++;
while(j > root && pre[root] <= pre[j]) j--;
} else {
while(i <= tail && pre[root] <= pre[i]) i++;
while(j > root && pre[root] > pre[j]) j--;
}
if(i - j != 1) return ;
getpost(root + 1, j);///左
getpost(i, tail);///右
post.push_back(pre[root]);
}
int main() {
int n;
scanf("%d", &n);
pre.resize(n);
for(int i = 0; i < n; i++)
scanf("%d", &pre[i]);
getpost(0, n - 1);
if(post.size() != n) {
isMirror = true;
post.clear();
getpost(0, n - 1);
}
if(post.size() == n) {
printf("YES\n%d", post[0]);
for(int i = 1; i < n; i++)
printf(" %d", post[i]);
} else {
printf("NO");
}
return 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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n;
double z;
double r;
int val[maxn];
vector<int> child[maxn];
double sum = 0;
void solve(int u, double z){
if(val[u]) {
sum += val[u]*z;
return ;
}
for(int i=0; i<child[u].size(); i++){
solve(child[u][i], z*r);
}
}
void init(){
memset(val, 0, sizeof(val));
for(int i=0; i<maxn; i++) child[i].clear();
}
int main()
{
cin>>n>>z>>r;
r = (100-r)/100.0;
init();
for(int i=0; i<n; i++){
int k;
cin>>k;
if(k == 0){
int temp;
cin>>temp;
val[i] = temp;
continue;
}
else{
for(int j=0; j<k; j++){
int temp;
cin>>temp;
child[i].push_back(temp);
}
}
}
solve(0, z);
//cout<<sum<<endl;
long long ans = sum;
printf("%lld\n", ans);
return 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
69
70
71
72
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int heap[maxn];
int n;
void downadjust(int low, int high){
int i=low, j=low*2;
while(j<=high){
if(j+1<=high&&heap[j]<heap[j+1]) j++;
if(heap[i]<heap[j]){
swap(heap[i], heap[j]);
i=j;
j = i*2;
}
else break;
}
return ;
}
void creatheap(){
for(int i=n/2; i>=1; i--){
creatheap(i, n);
}
}
void upadjust(int low, int high){
int i = high, j=i/2;
while(j>=low){
if(heap[j]<heap[i]){
swap(heap[j], heap[i]);
i=j;
j=i/2;
}
else break;
}
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++){
cin>>heap[i];
}
return 0;
}
# 最长上升序列
``` c++
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int d[maxn];
int g[maxn];
const int INF = 1e9;
int main(){
int n;
cin>>n;
for(int i=0; i<n; i++)cin>>d[i];
for(int i=0; i<=n; i++) g[i]= INF;
for(int i=0;i<n; i++){
int k=lower_bound(g+1,g+n+1, d[i])-g;
g[k] = d[i];
d[i] = k;
}
for(int i=0; i<n; i++){
cout<<d[i]<<" ";
}
cout<<endl;
return 0;
}

```

未解决的问题

文章目录
  1. 1. 最短路维护多个属性的问题
    1. 1.1. 题目
    2. 1.2. AC代码
  2. 2. 模拟整除
  3. 3. 优先队列重新定义运算符号
  4. 4. 树状数组求中值,二分
  5. 5. 前序到后续
  6. 6. 建堆
  7. 7. 未解决的问题
{{ live2d() }}