牛客算法周周练5(CDE)

图片说明
C:很显然最后会变成n个1，第一次替换k个(包含1),然后就是不断的替换(k-1)个，直到没有可替换。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 1e5 + 10;
int a[maxn];
void solved(){
    int n,k;cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>a[i];
    int cnt = 1;
    n -= k;
    while(n > 0){
        n -= (k - 1);cnt ++;
    }
    cout<<cnt<<endl;
}
int main(){
    solved();
    return 0;
}

图片说明
E：这个题目还有点意思。。。一开始愣是没看懂。。。暴力的做法O(100^100)超时，因为最终要是求得所有不同数的个数，我们考虑用二进制 $01$ 表示这个数能出现或者不能出现。二进制操作有一个非常好用的工具是bitset。如果不会bitset，http://www.cplusplus.com/reference/bitset/bitset/。因为数字最大无非是， $O(100 * 100 ^ 2)$ ，所以bitset开到1e6就行了，bitset从右边往左边走，它的位置表示十进制位置。感觉说不太清，直接举例子吧。
如果输入
2
1 2
1 2
先考虑 $n = 1$ ,我们有 $1 ^ 1 = 1,2 ^ 2 = 4$ ,
看一下二进制是如何操作的。
图片说明
给定 $l = 1,r = 2,s1 << (i * i)$ 表示 $01$ 二进制串向左移动 $(i * i)$ 个位置，这个位置刚好就是i所对应的十进制数，一开始设 $s1[0]=1$ ,表示答案串最后一位为1没有实际意义就是为了后面的操作。然后 $s1 << (1 * 1)$ ,这个时候字符串下标1的位置字符串0变1(|有1则1)，然后 $s1 << (2 * 2)$ ，这个时候字符串4的位置0变1，看到这里应该明白了，01二进制串第 $i$ 为 $0$ 表示这个数不会出现，为 $1$ 表示这个数出现，并且下标就是对应这个数的值。我们再来考虑 $n=2$ ,看它是怎么累加的。 $n=1$ 结束后我们要保存这个结果串 $s1= s2$ ,然后继续遍历 $[l,r]$ ，这个时候 $s1<<(i * i)$ ,s1已经是上一个区间数的串了，在这个基础上继续左移， $1^1 + 1 ^ 2 = 2,1 ^ 2 + 2^2=3,2^2+1^1=3,2^2+2^2=4$ ,当 $i=1$ 有 $1^2+1^2=2,2^2+1^2=3$
图片说明
注意到 $n=2的第二行,00100100000$ ，表示的就是 $2,3$ (对应下标看)。然后还有 $1^2+2^2=3,2^2+2^=4$ ,就是最后一个串，因为我们只要求出现一次的数，出现多次的会被 $|$ 运算覆盖掉，然后不断迭代，最后答案串的 $1$ 的个数就是 $S$ 的种类数。
代码：

#include<iostream>
#include<bitset> 
using namespace std;

const int maxn = 1100000 ;
void solved(){
    int n;cin>>n;
    bitset<maxn>s1,s2;
    s1.set(0);
    while(n--){
        s2.reset(); 
        int l,r;cin>>l>>r;
        for(int i = l ; i <= r; i++){
            s2 |= s1 << (i * i);
        }
        s1 = s2;
    }
    cout<<(int)s1.count()<<endl;
}
int main(){
    solved();
    return 0;
}

图片说明
D:这个题困扰了我好久，最终还是解决了~
分层最短路，这个题主要是难在建图上面， $m$ 条地铁线我们就建立 $m+1$ 层图，每一层图将每个结点连到对应的 $n$ 的节点上面，上车对应的权是 $a$ ，下车即换乘对应的权是 $0$ 。然后层与层之间连权为 $b$ 的双向边。然后画个图稍微理解一下(就样例而言)：
图片说明
大概就是这样子去建图，看到除了 $m$ 层地铁线为，我们还需要描述 $n$ 个点，我们把他们放到一层去描述这个虚点，我们可以把这层放到 $n * m + u$ 。
层与层怎么建边？ $add(u + (i - 1) * n,v + (i - 1) * n,b); add(v + (i - 1) * n,u + (i - 1) * n,b);$
双向边，u表示起点，v表示终点我们认为每层都是n个点，尽管我们可能并不需要这么多，(i - 1)表示当前层从0开始。
层与层建立完了后，每个地铁站怎么与车站建边？ $add(n * m + v,v + (i - 1) * n,a); add(v + (i - 1) * n,n * m + v,0);$
我们把车站建在n*m层，这样不会与别的层冲突，然后就是一样的了，上车权a，下车0.
建完图后就可以快乐的从 $n * m + s$ 到 $n * m + t$ 跑jikstra了。
代码:

#include<bits/stdc++.h>
using namespace std;

const int maxn =1e6 + 10;
struct edge{
    int v,w,next;
    edge(){}
    edge(int a,int b,int c):v(a),w(b),next(c){}
}e[maxn << 2];
int head[maxn << 2],tot,dis[maxn << 2];
struct node{
    int u,di;
    node(){}
    node(int a,int b):u(a),di(b){}
    bool operator < (const node & rhs)const{
        return di > rhs.di;
    }
};
void add(int u,int v,int w){
    e[++tot].w = w;
    e[tot].v = v;
    e[tot].next = head[u];
    head[u] = tot;
}
void dij(int s){
    memset(dis,0x3f,sizeof(dis));
    priority_queue<node>st;
    st.push(node(s,0));
    dis[s] = 0;
    while(!st.empty()){
        node cur = st.top();st.pop();
        int u = cur.u;int d = cur.di;
        if(dis[u] != d)continue;
        for(int i = head[u]; i ;i = e[i].next){
            if(dis[e[i].v] > d + e[i].w){
                dis[e[i].v] = d + e[i].w;
                st.push(node(e[i].v,dis[e[i].v]));
            }
        } 
    } 
}
void solved(){
    int n,m,s,t;cin>>n>>m>>s>>t;
    for(int i = 1; i <= m; i++){
        int a,b,c;cin>>a>>b>>c;
        int u;
        for(int j = 1; j <= c; j++){
            int v;cin>>v;
            if(j > 1){
                add(u + (i - 1) * n,v + (i - 1) * n,b);
                add(v + (i - 1) * n,u + (i - 1) * n,b);
            }
            add(n * m + v,v + (i - 1) * n,a);
            add(v + (i - 1) * n,n * m + v,0);
            u = v;
        }
    }
    dij(m * n + s);
    if(dis[n * m + t] < 0x3f3f3f3f){
        cout<<dis[n * m + t]<<endl;
    }else{
        cout<<"-1"<<endl;
    }
}
int main(){
    solved();
    return 0;
}