A Nucleic Acid Test

一个floyd加最小生成树。证明什么的题解里都有，就不放了。

#include <bits/stdc++.h>
using namespace std;
const int N=310;

int n,m,k,t;
unsigned long long x,y,z;
unsigned long long a[N][N];
int b[N];
unsigned long long d[N];
bool v[N];

int main(){
    memset(a,0x3f,sizeof a);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>t;
    for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    for(int i=1;i<=k;i++){
        cin>>b[i];
        v[b[i]]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int l=1;l<=n;l++){
                a[j][l]=min(a[j][l],a[j][i]+a[i][l]);
            }
        }
    }
    bool f=1;
    unsigned long long res1=0;
    for(int i=1;i<=n;i++){
        if(v[i]) continue;
        unsigned long long maxn1=1e18;
        for(int j=1;j<=k;j++){
            maxn1=min(maxn1,a[i][b[j]]);
        }
        if(maxn1==1e18||maxn1==0x3f3f3f3f3f3f3f3f) f=0;
        res1=max(res1,maxn1);
    }
    if(!f||!t){
        cout<<-1<<'\n';
        return 0;
    }
    memset(v,0,sizeof v);
    memset(d,0x3f,sizeof d);
    d[b[1]]=0;
    for(int i=1;i<k;i++){
        int x=0;
        for(int j=1;j<=k;j++){
            if(!v[b[j]]&&(!x||d[b[j]]<d[x])) x=b[j];
        }
        v[x]=1;
        for(int j=1;j<=k;j++){
            if(!v[b[j]]) d[b[j]]=min(d[b[j]],a[x][b[j]]);
        }
    }
    if(!f||!t){
        cout<<-1<<'\n';
    }
    else{
        unsigned long long res2=0;
        for(int i=1;i<=k;i++){
            if(d[b[i]]==0x3f3f3f3f3f3f3f3f){
                cout<<-1<<'\n';
                return 0;
            }
            res2=max(res2,d[b[i]]);
        }
        unsigned long long ans=max(res1<<1,res2);
        cout<<(ans+t-1)/t<<'\n';
    }
}

J – Palindrome Reversion

判断回文部分用了字符串哈希。想思路的话应该是先倒退出所有能达到的状态，然后再写。

#include <bits/stdc++.h>

using namespace std;
const int N=1e5+10;
const int P=131;

char s[N];

int n;

unsigned long long h[N],p[N],f[N];

unsigned long long query1(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

unsigned long long query2(int l,int r){
    return f[l]-f[r+1]*p[r-l+1];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>(s+1);
    n=strlen(s+1);
    p[0]=1;
    for(int i=1;i<=n;i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+s[i];
    }
    for(int i=n;i>=1;i--){
        f[i]=f[i+1]*P+s[i];
    }
    int l1=1,r1=n;
    while(s[l1]==s[r1]&&l1<r1) l1++,r1--;
    if(l1>r1) swap(l1,r1);
    int m=(r1-l1+1)/2;
    for(int i=0;i<=m;i++){
        if(query1(l1,l1+i-1)==query1(l1+i,l1+i+i-1)&&query1(l1+i+i,r1)==query2(l1+i+i,r1)){
            cout<<l1+i<<' '<<r1<<'\n';
            return 0;
        }
        else if(query1(l1,l1+i-1)==query1(r1-i+1,r1)&&query1(l1+i,r1-i)==query2(l1+i,r1-i)){
            cout<<r1-i+1<<' '<<r1<<'\n';
            return 0;
        }
        else if(query1(r1-i+1,r1)==query1(r1-i-i+1,r1-i)&&query1(l1,r1-i-i)==query2(l1,r1-i-i)){
            cout<<l1<<' '<<r1-i<<'\n';
            return 0;
        }
    }
    cout<<"-1 -1\n";
}

K – PTT

纯水题，别忘特判就行

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>

using namespace std;

int t;
int n;
double c;
double ans;

int main(){
    cin>>t;
    while(t--){
        cin>>n>>c;
        if(n>=10000000) c+=2;
        else if(n>9800000) c+=1.0+1.0*(n-9800000)/200000;
        else c+=1.0*(n-9500000)/300000;
        if(c>0)printf("%.7lf\n",c);
        else printf("0\n");
    }
}

L – Chtholly and the Broken Chronograph

线段树板子题，刚开始加懒标记版本的写了一半觉得写不下去，就没加，没过之后再想就想通了，纯板子

#include <bits/stdc++.h>
#define pl tr<<1
#define pr tr<<1|1

using namespace std;
const int N=1e5+10;

int n,m,x,l,r,op;
int a[N],b[N];
struct node{
    int l,r,cnt;
    long long lz;
    long long sum;
}t[N<<4];

void pushup1(int tr){
    t[tr].sum=(t[pl].sum+t[pr].sum);
}
void pushup2(int tr){
    t[tr].cnt=(t[pl].cnt+t[pr].cnt);
}
void pushdown(int tr){
    if(t[tr].lz){
        t[pl].sum+=(t[tr].lz)*t[pl].cnt;
        t[pr].sum+=(t[tr].lz)*t[pr].cnt;
        t[pl].lz+=t[tr].lz;
        t[pr].lz+=t[tr].lz;
        t[tr].lz=0;
    }
}
void build(int l,int r,int tr){
    t[tr].l=l,t[tr].r=r;
    if(l==r){
        t[tr].sum=a[l];
        t[tr].cnt=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,pl);
    build(mid+1,r,pr);
    pushup1(tr);
    pushup2(tr);
}

void update1(int l,int r,int tr,long long x){
    if(l<=t[tr].l&&t[tr].r<=r){
        t[tr].sum+=(t[tr].cnt)*x;
        t[tr].lz+=x;
        return;
    }
    pushdown(tr);
    int mid=(t[tr].l+t[tr].r)>>1;
    if(l<=mid) update1(l,r,pl,x);
    if(mid<r) update1(l,r,pr,x);
    pushup1(tr);
}

void update2(int l,int r,int tr,int x){
    if(t[tr].l==t[tr].r){
        if(x) t[tr].cnt+=1;
        else t[tr].cnt-=1;
        return;
    }
    int mid=(t[tr].l+t[tr].r)>>1;
    if(l<=mid) update2(l,r,pl,x);
    if(mid<r) update2(l,r,pr,x);
    pushup2(tr);
}

long long query(int l,int r,int tr){
    if(l<=t[tr].l&&t[tr].r<=r){
        return t[tr].sum;
    }
    pushdown(tr);
    int mid=(t[tr].l+t[tr].r)>>1;
    long long res=0;
    if(l<=mid) res=query(l,r,pl);
    if(mid<r) res+=query(l,r,pr);
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    build(1,n,1);
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>x;
            query(x,x,1);
            update2(x,x,1,0);
        }
        else if(op==2){
            cin>>x;
            query(x,x,1);
            update2(x,x,1,1);
        }
        else if(op==3){
            cin>>l>>r>>x;
            update1(l,r,1,x);
        }
        else{
            cin>>l>>r;
            cout<<query(l,r,1)<<'\n';
        }
    }
}