2019牛客暑期多校训练营（第四场）k题、j题
2024-10-12 04:07:00
k题：
题意：
给你一串由数字构成的字符串，你从这个字符串中找子字符串使这个字符串是300的倍数
题解：
这道题和第三场的B题极其相似
首先可以把是三百的倍数分开，必须要是100和3的倍数
是100的倍数就要求后面必须有两个0
是3的倍数就可以通过这个子字符串的数字之和是3的倍数来判断
那么暴力来计算子字符串肯定会超时，所以这个3的倍数这里要优化
首先我们要对这个字符串进行初始化，计算它的前缀和取余3后的结果
首先对一个0的出现要特判，因为题目上说了0也算300的倍数
其次大家想一下如果字符串两个位置取余3后的结果一样（假设结果为2），那么这两个位置中间一段就是3的倍数
因为我们预处理的是前缀和取余3后的结果，那么如果第一个位置之前取余3后的结果2，后面还有一个位置取余后也是2，那么让这后一个位置的前缀减去前一个位置的前缀，那么不就把这个2给消了吗，因此可以通过这样把复杂度降低
还有上边只是说了是3的倍数，并没有说是300的倍数，因此还要判断这个位置和前边那个位置是不是0
上代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=1e5+10;
7 char str[maxn];
8 int w[maxn],v[maxn];
9 int main()
10 {
11 scanf("%s",str+1);
12 int len=strlen(str+1);
13 int ans=0;
14 for(int i=1;i<=len;++i)
15 {
16 ans=ans+str[i]-'0';
17 ans%=3;
18 v[i]=ans;
19 }
20 long long sum=0;
21 for(int i=1;i<=len;++i)
22 {
23 if(str[i]=='0')
24 {
25 sum++;
26 if(str[i-1]=='0')
27 {
28 sum+=w[v[i]];
29 }
30 }
31 w[v[i-1]]++; //这一点就是来限制子字符串的个数要大于1， //因为一个0的已经特判了
32 }
33 printf("%lld\n",sum);
34 return 0;
35 }
j题：
这道题时遇到分层图最短路问题，我原来是想通过记录最短路路径，然后在对这个最短路路径上的最大边剔除，但是一直RE，只好拿出来分层最短路模板了
分层最短路讲解---->传送门
我在这里就把他的模板拿过来^_^
第一种（加点）
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<queue>
6 using namespace std;
7 const int INF=0xffffff;
8 const int maxn=1e7+10;
9 int n,m,nnn[maxn],fir[maxn],to[maxn],val[maxn],cnt,dis[maxn],d[maxn],w[maxn],q[maxn];
10 //int flag[maxn][maxn];
11 struct shudui1
12 {
13 int start,value;
14 bool operator <(const shudui1 q)const
15 {
16 return value>q.value;
17 }
18 } str1;
19 priority_queue<shudui1>r;
20 void JK()
21 {
22 memset(dis,0,sizeof(dis));
23 while(!r.empty())
24 {
25 str1=r.top();
26 r.pop();
27 int x=str1.start;
28 if(dis[x]) continue;
29 dis[x]=1;
30 for(int i=fir[x]; i!=-1; i=nnn[i])
31 {
32 if(!dis[to[i]] && d[to[i]]>d[x]+val[i])
33 {
34 str1.value=d[to[i]]=d[x]+val[i];
35 str1.start=to[i];
36 r.push(str1);
37 }
38 }
39 }
40 }
41 void init()
42 {
43 memset(d,0x3f,sizeof(d));
44 memset(fir,-1,sizeof(fir));
45 cnt=0;
46 }
47 void add_edge(int x,int y,int z)
48 {
49 nnn[++cnt]=fir[x];
50 fir[x]=cnt;
51 to[cnt]=y;
52 val[cnt]=z;
53 }
54 int main()
55 {
56 int s,t,k;
57 //memset(path,-1,sizeof(path));
58 scanf("%d%d%d%d%d",&n,&m,&s,&t,&k);
59 init();
60 while(m--)
61
62 {
63
64 int u, v, w;
65
66 scanf("%d%d%d",&u, &v, &w);
67
68 for(int i = 0; i <= k; i++)
69
70 {
71
72 add_edge(u + i * n, v + i * n, w);
73
74 add_edge(v + i * n, u + i * n, w);
75
76 if(i != k)
77
78 {
79
80 add_edge(u + i * n, v + (i + 1) * n, 0);
81
82 add_edge(v + i * n, u + (i + 1) * n, 0);
83
84 }
85
86 }
87
88 }
89 str1.start=s;
90 d[s]=0;
91 str1.value=0;
92 r.push(str1);
93 JK();
94 int ans=INF;
95 for(int i = 0; i <= k; i++)
96 ans = min(ans, d[t + i * n]);
97 printf("%d\n",ans);
98 return 0;
99 }
第二种（增加维度）
1 #include <iostream>
2
3 #include <string.h>
4
5 #include <stdio.h>
6
7 #include <algorithm>
8
9 #include <queue>
10
11 #include <vector>
12
13 #define ll long long
14
15 #define inf 0x3f3f3f3f
16
17 #define pii pair<int, int>
18
19 const int mod = 1e9+7;
20
21 const int maxn = 1e5+7;
22
23 using namespace std;
24
25 struct node{int to, w, next, cost; } edge[maxn];
26
27 int head[maxn], cnt;
28
29 int dis[maxn][15], vis[maxn][15];
30
31 int n, m, s, t, k;
32
33 struct Dijkstra
34
35 {
36
37 void init()
38
39 {
40
41 memset(head,-1,sizeof(head));
42
43 memset(dis,127,sizeof(dis));
44
45 memset(vis,0,sizeof(vis));
46
47 cnt = 0;
48
49 }
50
51
52
53 void add(int u,int v,int w)
54
55 {
56
57 edge[cnt].to = v;
58
59 edge[cnt].w = w;
60
61 edge[cnt].next = head[u];
62
63 head[u] = cnt ++;
64
65 }
66
67
68
69 void dijkstra()
70
71 {
72
73 priority_queue <pii, vector<pii>, greater<pii> > q;
74
75 dis[s][0] = 0;
76
77 q.push({0, s});
78
79 while(!q.empty())
80
81 {
82
83 int now = q.top().second; q.pop();
84
85 int c = now / n; now %= n;
86
87 if(vis[now][c]) continue;
88
89 vis[now][c] = 1;
90
91 for(int i = head[now]; i != -1; i = edge[i].next)
92
93 {
94
95 int v = edge[i].to;
96
97 if(!vis[v][c] && dis[v][c] > dis[now][c] + edge[i].w)
98
99 {
100
101 dis[v][c] = dis[now][c] + edge[i].w;
102
103 q.push({dis[v][c], v + c * n});
104
105 }
106
107 }
108
109 if(c < k)
110
111 {
112
113 for(int i = head[now]; i != -1; i = edge[i].next)
114
115 {
116
117 int v = edge[i].to;
118
119 if(!vis[v][c+1] && dis[v][c+1] > dis[now][c])
120
121 {
122
123 dis[v][c+1] = dis[now][c];
124
125 q.push({dis[v][c+1], v + (c + 1) * n});
126
127 }
128
129 }
130
131 }
132
133 }
134
135 }
136
137 }dj;
138
139
140
141 int main()
142
143 {
144
145 while(~scanf("%d%d%d%d%d", &n, &m,&s,&t &k))
146
147 {
148
149 dj.init(); //scanf("%d%d",&s,&t);
150
151 while(m--)
152
153 {
154
155 int u, v, w;
156
157 scanf("%d%d%d",&u, &v, &w);
158
159 dj.add(u, v, w);
160
161 dj.add(v, u, w);
162
163 }
164
165 dj.dijkstra();
166
167 int ans = inf;
168
169 for(int i = 0; i <= k; i++)
170
171 ans = min(ans, dis[t][i]);
172
173 printf("%d\n", ans);
174
175 }
176
177 }
最新文章
- /var/log/messages
- ubuntu升级内核后vmware-player启动失败
- Centos 6.5 rsync+inotify 两台服务器文件实时同步
- Vue系列：通过vue-router如何传递参数
- [ZOJ2760]How Many Shortest Path(floyd+最大流）
- “FAIL - Deployed application at context path but context failed to start”错误的解决
- CAN Timing Sample Point
- 最短路(Bellman_Ford) POJ 1860 Currency Exchange
- Android Studio开发RecyclerView遇到的各种问题以及解决
- CentOS 6.3 安装ATI显卡驱动
- 使用gSoap规避和修改ONVIF标准类型结构的解析
- Pycharm常用快捷键（后期慢慢补充）
- Python新手学习基础之运算符——成员运算与身份运算
- react-native 入门资源合集
- 新鲜出炉的Using Qt 3D to visualize music
- php中des加密解密 匹配C#des加密解密 对称加密
- [国嵌攻略][149][Yaffs2文件系统应用]
- Ex 6_3 修建酒店所获得的利润..._第五次作业
- Java中List、integer[]、int[]之间的转化
- 蜗牛慢慢爬 LeetCode 16. 3Sum Closest [Difficulty: Medium]