2019牛客暑期多校训练营（第四场）k题、j题

超、凢脫俗 2023-10-11 09:30 21阅读 0赞

[传送门][Link 1]

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

上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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，只好拿出来分层最短路模板了

分层最短路讲解---->[传送门][Link 2]

我在这里就把他的模板拿过来^\_^

第一种（加点）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

第二种（增加维度）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11268087.html

[Link 1]: https://ac.nowcoder.com/acm/contest/884/K
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[Link 2]: https://blog.csdn.net/sugarbliss/article/details/86551050