[AC代码] N01p 2018 普及组

[AC代码] N01p 2018 普及组

全是真实的比赛代码，思路不明确请原谅。

第一题

事实证明可以getline。

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned int U;

int main() {
    freopen("title.in","r",stdin);
    freopen("title.out","w",stdout);
    ios::sync_with_stdio(false);

    string s;
    getline(cin,s);

    U egg=0;
    for(U i=0;i<s.length();i++) {
        if(
            (s[i]>='A' && s[i]<='Z') ||
            (s[i]>='a' && s[i]<='z') ||
            (s[i]>='0' && s[i]<='9')
        ) egg++;
    }

    cout<<egg<<endl;

    return 0;
}

第二题

O(n)枚举天降神兵位置即可（我都不知道Exile是如何写出O(n²)的）。

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned int U;
typedef unsigned long long ull;

//18446744073709551615
//10000000000000000000

ull c[100100];
int main() {
    freopen("fight.in","r",stdin);
    freopen("fight.out","w",stdout);
    ios::sync_with_stdio(false);

    ull n;
    cin>>n;
    ull f1=0,f2=0;
    for(ull i=1;i<=n;i++) {
        cin>>c[i];
    }
    ull m,p1,s1,s2;
    cin>>m>>p1>>s1>>s2;

    for(ull i=1;i<=n;i++) {
        if(i<m) {
            f1+=(m-i)*c[i];
        }
        else if(i>m) {
            f2+=(i-m)*c[i];
        }
    }
    if(p1<m) f1+=(m-p1)*s1;
    else if(p1>m) f2+=(p1-m)*s1;

    ull best1=18446744073709551614ull,egg=-1;
    for(ull i=1;i<=n;i++) {
        ull ff1=f1,ff2=f2;
        if(i<m) ff1+=(m-i)*s2;
        else if(i>m) ff2+=(i-m)*s2;

        ull diff1=0;
        if(ff1>ff2) diff1=ff1-ff2;
        else diff1=ff2-ff1;
        if(diff1<best1) {
            best1=diff1;
            egg=i;
        }
    }

    cout<<egg<<endl;

    return 0;
}

第三题

具体思路我也不知道…反正AC了（说实话我当时写代码时头昏脑胀）。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned int U;

int t[600];
int hash2[4003000];
int suf[4003000];
int tPre[600];
int n,m,maxt;

void boom() {
    boom();
}

void printSuffixMap() {
    cout<<"Suffix Array: ";
    for(int i=0;i<=maxt;i++) {
        cout<<suf[i]<<" ";
    }
    cout<<endl;
}

int _dp[600][50010];

int dp(int x,int tDelta) { //X=Last-Departure-Time
    int &ret=_dp[x][tDelta];
    if(ret!=-1) return ret;

    if(x>=n) {
        ret=0;
    } else {
        if(suf[t[x]+m+tDelta]<=n) {
            if(suf[t[x]+m+tDelta]-1 != x) {
                int wait=0;
                int R=suf[t[x]+m+tDelta];
                int L=x+1;
                wait=(R-L)*(t[x]+m+tDelta);
                wait-=tPre[R-1]-tPre[L-1];
                ret=wait+dp(suf[t[x]+m+tDelta]-1,t[x]+m+tDelta-t[suf[t[x]+m+tDelta]-1]);
            }
            else ret=1429066277;
            for(int i=suf[t[x]+m+tDelta];i<=n;i++) {
                int wait=0;
                int R=i;
                int L=x+1;
                wait=(R-L)*(t[i]);
                wait-=tPre[R-1]-tPre[L-1];
                ret=min(ret,wait+dp(i,0));
            }
        }
        else {
            int wait=0;
            int R=suf[t[x]+m+tDelta];
            int L=x+1;
            wait=(R-L)*(t[x]+m+tDelta);
            wait-=tPre[R-1]-tPre[L-1];
            ret=wait;
        }
    }

    return ret;
}

int main() {
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout);
    ios::sync_with_stdio(false);
    memset(_dp,255,sizeof(_dp));

    cin>>n>>m;
    t[0]=-m;
    for(int i=1;i<=n;i++) {
        cin>>t[i];
        if(t[i]+m+10 > maxt) {
            maxt=t[i]+m+10;
        }
    }
    sort(t+1,t+1+n);
    for(int i=1;i<=n;i++) {
        if(hash2[t[i]]<=400) hash2[t[i]]=400+i;
        tPre[i]=tPre[i-1]+t[i];
    }
    int curr=n+1;
    for(int j=maxt;j>=0;j--) {
        if(hash2[j]>400) curr=hash2[j]-400;
        suf[j]=curr;
    }
    cout<<dp(0,0)<<endl;

    //printDpMap();

    return 0;
}

第四题

首先，建两棵树，DFS暴力。

为了防止被链状数据卡住，优化是，当一个节点发现其孩子不对称（只有左或只有右）时，直接退出，判为不对称（当时比赛时并没有想到做这个优化，可是歪打正着）。

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned int U;

struct node {
    int data;
    int l,r;
    node(){
        l=-1;r=-1;
    }
}nodes[1000010],rnodes[1000010];

int equalTravel(int o,int r){
    if(o==-1 && r==-1) return 0;
    if(o==-1 || r==-1) return -1;
    if(nodes[o].data != rnodes[r].data) return -1;
    int left= equalTravel(nodes[o].l,rnodes[r].l);
    int right=equalTravel(nodes[o].r,rnodes[r].r);
    if(left==-1 || right==-1) return -1;
    else return 1+left+right;
}

int isOK(int x) {
    return equalTravel(x,x);
}

int main() {
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>nodes[i].data;
        rnodes[i].data=nodes[i].data;
    }
    for(int i=1;i<=n;i++) {
        cin>>nodes[i].l>>nodes[i].r;
        rnodes[i].r=nodes[i].l;
        rnodes[i].l=nodes[i].r;
    }

    int egg=0;
    for(int i=1;i<=n;i++) {
        int m=isOK(i);
        if(m!=-1) egg=max(egg,m);
    }

    cout<<egg<<endl;

    return 0;
}