长乐集训Day5

2023年10月2日王子晔, 王子晔无评论

A. 基因序列（dna）

这里计算一个串的 Hash 值有两种方法，第一种是每个串都重新计算一遍，时间复杂度为o(ok)，第二种是利用位运算将无用状态取出，并加入新状态，时间复杂度为o(n)。这两个复杂度的代码均可通过。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 100;
inline ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
struct edge {
    int a[5], con, fa;
    ll sz;
} d[2 * N];
char s[N];
int len, k, sum, cnt;
int tong[N], xl[2 * N];
ll ans;
int took(char x) {
    if (x == &#039;A&#039;) {
        return 0;
    }
    if (x == &#039;T&#039;) {
        return 1;
    }
    if (x == &#039;G&#039;) {
        return 2;
    }
    if (x == &#039;C&#039;) {
        return 3;
    }
}
void check(int x) {
    int n = sum;
    int m = ++cnt;
    sum = m;
    d[m].con = d[n].con + 1;
    d[m].sz = 1;
    for (; n && !d[n].a[x]; n = d[n].fa) {
        d[n].a[x] = m;
    }
    if (!n) {
        d[m].fa = 1;
    } else {
        int n1 = d[n].a[x];
        if (d[n1].con == d[n].con + 1) {
            d[m].fa = n1;
        } else {
            int m1 = ++cnt;
            d[m1] = d[n1];
            d[m1].sz = 0;
            d[m1].con = d[n].con + 1;
            d[n1].fa = d[m].fa = m1;
            for (; n && d[n].a[x] == n1; n = d[n].fa) {
                d[n].a[x] = m1;
            }
        }
    }
}
int main() {
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    cin >> s + 1;
    len = strlen(s + 1);
    cin >> k;
    sum = cnt = 1;
    for (int i = 1; i <= len; i++) {
        check(took(s[i]));
    }
    for (int i = 1; i <= cnt; i++) {
        tong[d[i].con]++;
    }
    for (int i = 1; i <= len; i++) {
        tong[i] += tong[i - 1];
    }
    for (int i = 1; i <= cnt; i++) {
        xl[tong[d[i].con]--] = i;
    }
    for (int i = cnt; i >= 1; i--) {
        d[d[xl[i]].fa].sz += d[xl[i]].sz;
    }
    for (int i = 1; i <= cnt; i++) {
        if (d[i].con >= k && d[d[i].fa].con + 1 <= k) {
            ans = max(ans, d[i].sz);
        }
    }
    cout << ans << endl;
    return 0;
}

B. 质数查询(prime)

线性筛

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e6 + 100;
inline ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c) && c != &#039;-&#039;) c = getchar();
    if (c == &#039;-&#039;)
        f = -1, c = getchar();
    while (isdigit(c)) x = x * 10 + c - &#039;0&#039;, c = getchar();
    return f * x;
}
struct edge {
    int a[5], con, fa;
    ll sz;
} d[2 * N];
char s[N];
int len, k, sum, cnt;
int tong[N], xl[2 * N];
ll ans;
int took(char x) {
    if (x == &#039;A&#039;) {
        return 0;
    }
    if (x == &#039;T&#039;) {
        return 1;
    }
    if (x == &#039;G&#039;) {
        return 2;
    }
    if (x == &#039;C&#039;) {
        return 3;
    }
}
void check(int x) {
    int n = sum;
    int m = ++cnt;
    sum = m;
    d[m].con = d[n].con + 1;
    d[m].sz = 1;
    for (; n && !d[n].a[x]; n = d[n].fa) {
        d[n].a[x] = m;
    }
    if (!n) {
        d[m].fa = 1;
    } else {
        int n1 = d[n].a[x];
        if (d[n1].con == d[n].con + 1) {
            d[m].fa = n1;
        } else {
            int m1 = ++cnt;
            d[m1] = d[n1];
            d[m1].sz = 0;
            d[m1].con = d[n].con + 1;
            d[n1].fa = d[m].fa = m1;
            for (; n && d[n].a[x] == n1; n = d[n].fa) {
                d[n].a[x] = m1;
            }
        }
    }
}
int main() {
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    cin >> s + 1;
    len = strlen(s + 1);
    cin >> k;
    sum = cnt = 1;
    for (int i = 1; i <= len; i++) {
        check(took(s[i]));
    }
    for (int i = 1; i <= cnt; i++) {
        tong[d[i].con]++;
    }
    for (int i = 1; i <= len; i++) {
        tong[i] += tong[i - 1];
    }
    for (int i = 1; i <= cnt; i++) {
        xl[tong[d[i].con]--] = i;
    }
    for (int i = cnt; i >= 1; i--) {
        d[d[xl[i]].fa].sz += d[xl[i]].sz;
    }
    for (int i = 1; i <= cnt; i++) {
        if (d[i].con >= k && d[d[i].fa].con + 1 <= k) {
            ans = max(ans, d[i].sz);
        }
    }
    cout << ans << endl;
    return 0;
}

C. 最短路径（minimum）

这道题最麻烦的地方就是最终搞成的图有可能有很多个联通块，考虑怎么将它们整合在一起而不会对最后结果产生影响。
因此考虑增加一个点：S点，让S点连接所有的黑点，边权为0；
处理从S出发到每个点的最短距离，将每个在最短路上的边留下来，形成一个新图，做一遍最小生成树即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+100;
typedef long long ll;
int n,m,tot,S,cnt;
int a[maxn],head[maxn],vis[maxn],fa[maxn];
ll dist[maxn];
struct EDGE
{
    int from;
    int to;
    int next;
    int l;
    int fl;
}edge[maxn<<5];
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (!(ch>=&#039;0&#039;&&ch<=&#039;9&#039;)) {if (ch==&#039;-&#039;) f=-1;ch=getchar();}
    while (ch>=&#039;0&#039;&&ch<=&#039;9&#039;) {s=(s<<3)+(s<<1)+ch-&#039;0&#039;;ch=getchar();}
    return s*f;
}
void add(int x,int y,int l)
{
    edge[++tot]=(EDGE)
    {
        x,y,head[x],l,0
    };
    head[x]=tot;
    edge[++tot]=(EDGE)
    {
        y,x,head[y],l,0
    };
    head[y]=tot;
}
void spfa(int x)
{
    memset(dist,0x3f3f3f3f,sizeof(dist));
    queue <int> q;
    dist[x]=0;vis[x]=1;q.push(x);
    while (!q.empty())
    {
        int k=q.front();q.pop();vis[k]=0;
        for (int i=head[k];i;i=edge[i].next)
        {
            int y=edge[i].to;
            if (dist[y]>dist[k]+1ll*edge[i].l)
            {
                dist[y]=dist[k]+1ll*edge[i].l;
                if (!vis[y])
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
bool cmp(EDGE aa,EDGE bb) {return aa.l<bb.l;}
int find(int x)
{
    if (fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    freopen("minimum.in", "r", stdin);
    freopen("minimum.out", "w", stdout);
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=m;i++) 
    {
        int u=read(),v=read(),l=read();
        add(u,v,l);
    } 
    for (int i=1;i<=n;i++)
    {
        if (a[i]) add(S,i,0);
        fa[i]=i;
    }
    spfa(S);

    for (int i=1;i<=n;i++)
    {
        if (a[i]) continue;
        for (int j=head[i];j;j=edge[j].next)
        {
            int y=edge[j].to;
            if (y==0) continue;
            if (dist[y]+1ll*edge[j].l==dist[i]) edge[j].fl=1;
        }
    }
    sort(edge+1,edge+1+tot,cmp);
    ll ans=0;
    int p=0;
    for (int i=1;i<=tot;i++)
    {
        if (!edge[i].fl) continue;
        int x=edge[i].from,y=edge[i].to;
        int xx=find(x),yy=find(y);
        if (xx!=yy)
        {
            fa[xx]=yy;
            ++p;
            ans+=1ll*edge[i].l;
            if (p==n-1) 
            {
                break;
            }
        }
    }
    if(!ans) 
    {
        puts("impossible");
    }
    else 
    {
        cout<<ans<<endl;
    }
    return 0;
 }

D. 奇偶游戏(kokomi)

不会

总结

今天两百分

训练日志

发表回复取消回复

要发表评论，您必须先登录。