长乐集训DAY4

Posted on By 学伟宸 长乐集训DAY4无评论

55，改后150

基因序列

考试时没思路跳过
10进制的哈希50+，一般是WA（哈希冲突）、RE（没开long long）或者MLE（数组太大）
map可以到80左右，错因TLE
正解是位运算+哈希
附50分代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
const long long N=66666666;
ll a[N+10],k,maxx=-1,maxxx=-1;
inline int pw(ll a,ll b,ll mod){
    ll ans=1;
    while(b){
        if(b&1){
            ans*=a%=mod;
        }
        b>>=1;
        a*=a%=mod;
    }
    return ans;
}
int main(){
    freopen("dna.in","r",stdin);
    freopen("dna.out","w",stdout);
    memset(a,0,sizeof(a));
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>s>>k;
    for(ll i=0;i<=s.size()-k;i++){
        ll cs=1;
        for(ll j=0;j<=k-1;j++){
            if(s[i+j]==&#039;A&#039;){
                cs*=1;
                cs%=N;
            }
            if(s[i+j]==&#039;C&#039;){
                cs*=pw(2,j+1,N);
                cs%=N;
            }
            if(s[i+j]==&#039;G&#039;){
                cs*=pw(3,j+1,N);
                cs%=N;
            }
            if(s[i+j]==&#039;T&#039;){
                cs*=pw(5,j+1,N);
                cs%=N;
            }
        }
        cs%=N;
        a[cs]++;
        maxxx=max(maxxx,cs);
    }
    for(ll i=1;i<=maxxx;i++){
        maxx=max(a[i],maxx);
    }
    cout<<maxx;
    return 0;
}

质数查询

考试时朴实无华打暴力，喜提TLE55
实际上把判断质数的方法改为线性筛即可
附改后AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
bool like[N];
int vis[N],prime[N],sum[N],tot=1,q;
inline void read(int &x) {
    x = 0; int f = (int) 1;
    char c = getchar();
    for(;!isdigit(c); c = getchar()) {if(c == &#039;-&#039;) f = -f;}
    for(;isdigit(c); c = getchar()) x = x * 10 + c - 48;
    x *= f;
}
inline void solve(){
    for(int i=2;i<=N-10;i++){
        if(vis[i]==0){
            prime[tot]=i;
            tot++;
            like[i]=true;
            for(int j=1;j<=tot&&i*prime[j]<=N-10;j++){
                vis[i*prime[j]]=1;
                like[i*prime[j]]=true;
            }
        }
        else{
            for(int j=1;j<=tot&&i*prime[j]<=N-10;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0){
                    break;
                }
            }
        }
    }
    for(int i=1;i<=10000000;i++){
        sum[i]=sum[i-1]+like[i];
    }
}
int main(){
    freopen("prime.in","r",stdin);
    freopen("prime.out","w",stdout);
    ios::sync_with_stdio(false);
    cout.tie(0);
    read(q);
    solve();
    for(int i=1;i<=q;i++){
        int l,r;
        read(l);read(r);
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}

最短路径

考试时Floyd爆炸，喜提鸭蛋
直接SPFA为30左右
正解应为超级源点+SPFA
附标程

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

const int N = 1e5 + 10;
const int M = 4e5 + 10;

struct node {
     int where, cost;
     node *next;
} *first[N], w[M << 1]; 
struct line {
     int x, y, value;
     bool operator < (const line &A) const {
          return value < A.value;
     }
} a[M];
long long dist[N];
int f[N];
int cnt, n, m, c[M << 1], l;
bool b[N];

int gf(int i) {
     if (i == f[i]) return i;
     return f[i] = gf(f[i]);
}

inline void makelist(int x, int y, int z) {
     w[++l].where = y; w[l].cost = z; 
     w[l].next = first[x];
     first[x] = &w[l];
}

inline void spfa() {
     memset(dist, 127, sizeof(dist));
     memset(b, false, sizeof(b)); 
     dist[0] = 0; c[1] = 0;
     for (int k = 1, l = 0; l != k; ) {
          if (++l > 200000) l = 1;
          int m = c[l]; b[m] = false; 
          for (node *x = first[m]; x; x = x->next) 
               if (dist[m] + x->cost < dist[x->where]) {
                    dist[x->where] = dist[m] + x->cost;
                    if (!b[x->where]) {
                         b[x->where] = true;
                         if (++k > 200000) k = 1;
                         c[k] = x->where;
                    }
               }
     }
}   

int main() {
     freopen("minimum.in", "r", stdin);
     freopen("minimum.out", "w", stdout);

     scanf("%d%d", &n, &m);
     memset(first, 0, sizeof(first)); l = 0;
     for (int i = 1; i <= n; i++) {
          int x;
          scanf("%d", &x);
          if (x == 1) makelist(0, i, 0);
     }
     for (int i = 1; i <= m; i++) {
          int x, y, z;
          scanf("%d%d%d", &x, &y, &z);
          makelist(x, y, z);
          makelist(y, x, z);
     }
     spfa(); // 推荐用dijkstra……
     bool ok = true;
     for (int i = 1; i <= n && ok; i++) // 检验答案是否合法
          if (dist[i] > 1LL << 60LL) ok = false;
     if (!ok) { // 如果从黑点出发，有白点到不了
          printf("impossible\n"); // 不合法
          return 0;
     }
     int len = 0;
     for (int i = 1; i <= n; i++) 
          for (node *x = first[i]; x; x = x->next)  
               if (dist[x->where] + x->cost == dist[i]) // 在最短路上的边
                    a[++len].x = i, a[len].y = x->where, a[len].value = x->cost;
     // a[]存储新图，上面的for循环即为提取最短路上的边
     sort(a + 1, a + len + 1);

     for (int i = 0; i <= n; i++) f[i] = i;
     long long ans = 0;
     cnt = n;
     for (int i = 1; i <= len && cnt; i++)
          if (gf(a[i].x) != gf(a[i].y))
               ans += a[i].value, f[gf(a[i].x)] = gf(a[i].y), --cnt;
     printf("%lld\n", ans);

     return 0;
}

奇偶游戏

二分图+BFS

总结

炸裂ing

训练日志

发表回复