HGOI20190811 省常中互测4

　　Problem A magic

给出一个字符串$S$,和数字$n$，要求构造长度为$n$只含有小写字母的字符串$T$，

使得在$T$中存在删除且仅删除一个子串使得$S=T$成立。

输出$T$的构造方案数，mod 998244353的值。

对于$100 \% $的数据 $2 \leq n \leq 10^{18} , |S| \leq 10^6$

Sol : 考虑$T$合法的条件是和$S$有相同的前缀和相同的后缀，且相同前后缀长度和是$|S|$

若最长公共前缀长度为$0$ ，那么说明$S$和$T$最后$|S|$位相同，合法情况$T$的取值有$26^{n - |S|}$ 种。

　若最长公共前缀长度不为$0$ ，那么说明前半部分至少有$k$是$S$的前缀，后半部分就有$|S| - k $的长度是后缀，这个时候由于倒数$|S| - k$ 个不能和上一次一样，这个位置只有$25$种可能，其他位置是$26$种可能，这种情况下方案数时$26^{n-|S|-1}$

最后答案就是$26^n - 26^{n-1} - |S|\times 25 \times 26^{n-|S|-1}$

　注意需要特判$n = |S|$的情况，答案就是$26 ^ n - 1$

　复杂度是$O(log_2 n)$

#include<bits/stdc++.h>

using namespace std;

const long long mod=;

long long n,m;

char tmp[];

long long Pow(long long x,long long k)

{

    if(k<) return 0ll;

    if(!k) return 1ll;

    long long res=Pow(x,k/);

    res=res*res%mod;

    if(k%) res=res*x%mod;

    return res;

}

int main()

{

    scanf("%lld %s",&n,tmp);

    m=strlen(tmp);

    printf("%lld",(long long)(Pow(26ll,n)-(Pow(26ll,n-m)%mod+(m*25ll%mod)*Pow(26ll,n-m-)%mod)%mod+mod)%mod);

    return ;

}

A.cpp

　　Problem B graph

　　给出可重边无自环不保证连通的无向图$G$ ,询问$u $到$v$简单路径上经过边权的最大值最小。

　　对于$100\% $ 的数据$n,m,q \leq 3 \times 10^5$

Sol: 建出最小生成树（在建树过程考虑了重边了）。、

　　　　然后用并查集维护连通性。

　　　　最大边权最小等价于在最小生成树树上路径的最大值。

　　　　复杂度就是$O(m log_2 m)$

# include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + ;

map<int,int>mp[N];

int g[N][],d[N][],dep[N],fc[N],n,m,q;

vector<pair<int , int> >E[N];

struct edge{

    int u,v,w;

};

vector<edge>Edge;

bool cmp(edge a,edge b){return a.w < b.w;}

inline int read()

{

    int X=,w=; char c=;

    while(c<''||c>'') {w|=c=='-';c=getchar();}

    while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();

    return w?-X:X;

}

void write(int x)

{

    if (x<) x=-x,putchar('-');

    if (x>) write(x/);

    putchar(''+x%);

}

void writeln(int x)

{

    write(x); putchar('\n');

}

int father(int x)

{

    if (fc[x]==x) return x;

    return fc[x]=father(fc[x]);

}

void kruskal()

{

    sort(Edge.begin(),Edge.end(),cmp);

    for (int i = ; i <= n; i++) fc[i] = i;

    for (int i = ; i < Edge.size(); i++) {

        int u=Edge[i].u,v=Edge[i].v,w=Edge[i].w;

        int fx = father(Edge[i].u),fy = father(Edge[i].v);

        if (fx == fy) continue;

        fc[fx] = fy;

        E[u].push_back(make_pair(v,w));

        E[v].push_back(make_pair(u,w));

    }

}

void dfs(int u,int fa)

{

    dep[u]=dep[fa]+; g[u][]=fa;

    for (int i=;i<E[u].size();i++) {

        int v=E[u][i].first,w=E[u][i].second;

        if (v==fa) continue;

        d[v][]=w;

        dfs(v,u);

    }

}

void init()

{

    for (int i =  ; i<=n ; i++)

        if (!dep[i]) dfs(i,);

    for (int i = ; i <=  ; i++)

     for (int j = ; j <= n ; j++)

       g[j][i] = g[g[j][i-]][i-],

       d[j][i] = max(d[j][i-] , d[g[j][i-]][i-]);

}

int query(int u,int v)

{

    int fx = father(u), fy = father(v);

    if (fx != fy) return -;

    if (dep[u] < dep[v]) swap(u,v);

    int ret = ;

    for (int i =  ; i >=  ; i--)

     if (dep[g[u][i]] >= dep[v])

        ret = max(ret,d[u][i]),u=g[u][i];

    if (u == v) return ret;

    for (int i =  ; i >=  ;i--)

     if (g[u][i] != g[v][i])

        ret = max(max(ret , d[u][i]) , d[v][i]),

        u = g[u][i] , v = g[v][i];

    return max(max(ret,d[u][]),d[v][]);

}

int main()

{

    n=read();m=read();q=read();

    for (int i=;i<=m;i++) {

        int u=read(),v=read(),w=read();

        if (mp[u].count(v) != ) w = min(w , mp[u][v]);

        mp[u][v] = mp[v][u] = w;

    }

    map<int,int>::iterator it;

    for (int i = ; i <= n ; ++i )

        for (it = mp[i].begin() ; it != mp[i].end() ; ++it)

            Edge.push_back((edge){i , it->first , it->second});

    kruskal(); init();

    while (q--) {

        int u=read(),v=read();

        writeln(query(u,v));

    }

    return ;

}

B.cpp

Problem C number

　　定义不算前导零，只由两个数字构成的数为“好数”，如$101010$, $11111$

给出$T$个询问，询问$x$至少由几个好数相加组成的（可以同一个数用多次）。

　　对于$100\%$的数据$1 \leq n \leq 10^{18} ,1 \leq T \leq 100$

　　Sol:考虑$01$ , $02$ , $03$ , $04$最多四个数字就可以创造世界了，所以我们只需要判断$3$及以下的情况，剩余情况就输出$4$

　　我们可以枚举$C_{10}^{2} = 45$种选择数的方案$mask[i]$来构成这些数，然后用dp验证即可。

　　我们只至少这若干个数加起来是多少，我们要还原他为0，才能检验是否合法。

　　对于每个三个数累加的方案，我们都有这三个数中任意选2个任意选1个不选这7种子方案，也能获得相同的效果，我们特殊考虑，记录在$Sub[i]$中。

　　我们可以预处理出每个个选择数的方案，可以构成哪些最小合法的数（显然这些数都是小于等于$3 \times 9 =27$的）

设$f[i][j]$表示使用标号为$i$的方案，到达$j$数位上的信息，这个信息是一个3位二进制数，分别表示高位向低位退位为$i , i\in[0,2]$是否合法。

　　转移的话可以用位运算转移。

　　最后如果当前数位为1，并且可以退0位的方案是ok的，那么我们就对对应取数的个数求min即可。（如果无法构成答案就是4了）

　　复杂度是$O(T \times C_{45}^{3} \times 18 \times 3 \times 3)$

# include <bits/stdc++.h>

# define int long long

using namespace std;

int mask[],f[][],s[][][],val[],a[];

bool ok[][];

int size;

vector<int>Sub[];

signed main()

{

    for (int i =  ; i <=  ; i++ )

        for (int j = i +  ; j <=  ; j++ )

             mask[++mask[]] = i *  + j;

    memset(ok, false, sizeof(ok));

    int t = mask[] ; mask[] = ;

    for (int i =  ;i <= t ; i++)

        for (int j = i ; j <= t ; j++)

            for (int k = j ; k <= t ;k++) {

                val[++size] =  - (i==) - (j==) - (k==);

                ok[size][mask[i]/ + mask[j]/ + mask[k]/] = ok[size][mask[i]% + mask[j]/ + mask[k]/] = true;

                ok[size][mask[i]/ + mask[j]% + mask[k]/] = ok[size][mask[i]/ + mask[j]/ + mask[k]%] = true;

                ok[size][mask[i]% + mask[j]% + mask[k]/] = ok[size][mask[i]% + mask[j]/ + mask[k]%] = true;

                ok[size][mask[i]/ + mask[j]% + mask[k]%] = ok[size][mask[i]% + mask[j]% + mask[k]%] = true;

                s[i][j][k] = s[i][k][j] = s[j][i][k] = s[j][k][i] = s[k][i][j] = s[k][j][i] = size;

                if (s[][j][k] != size) Sub[size].push_back(s[][j][k]);

                if (s[i][][k] != size) Sub[size].push_back(s[i][][k]);

                if (s[i][j][] != size) Sub[size].push_back(s[i][j][]);

                if (s[][][k] != size) Sub[size].push_back(s[][][k]);

                if (s[][j][] != size) Sub[size].push_back(s[][j][]);

                if (s[i][][] != size) Sub[size].push_back(s[i][][]);

                if (s[][][] != size) Sub[size].push_back(s[][][]);

            }

    int T; scanf("%lld",&T);

    while (T--) {

        memset(f,  , sizeof(f));

        int x; scanf("%lld",&x); a[] = ;

        while (x) { a[++a[]] = x%; x/=;}

        for (int i = ; i<= size; i++) f[i][a[]+] = ;

        for (int i = a[] ; i>= ; i--) {

            for (int j = ; j <= size ; j++) {

                for (int last =  ; last <=  ; last++) if (f[j][i+] & (<<last))

                    for (int to = ; to <=  ; to++) if (last* + a[i] - to >=  && ok[j][last* + a[i] - to]) {

                        f[j][i] |= (<<to) ;

                    }

                for (int k =  ;k < Sub[j].size() ; k++) {

                        int tmp = Sub[j][k] ;

                        f[j][i] |= f[tmp][i];

                }

            }

        }

        int ans = ;

        for (int i =  ; i <= size ; i++) if (f[i][] & )   ans = min(ans , val[i]);

        printf("%lld\n",ans);

    }

    return ;

}

C.cpp

巴特西

HGOI20190811 省常中互测4

最新文章

热门文章