南外Day4

Posted on By 陈麒润

T1&T2&T3&T5 (1000+1300+1400+1800)

水

T4（1500?->1500）

神奇

//D 100-AC with the help of zgc
//STO CGC OTZ
#include<bits/stdc++.h>
#define MX 100005
using namespace std;
int n,a[MX],b[MX],c[MX],d[MX],ans,p=INT_MAX;
signed main(){
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];}
    for(int i=1;i<=n;i++){cin>>d[i];c[d[i]]=i;}
    for(int i=1;i<=n+1;i++){
    a[i]=c[a[i]];
    if(a[i]<a[i-1]){
        cout<<n+1-i<<&#039;\n&#039;;
        break;
    }}
    return 0;
}

T6（0->2100）

全源最短路，每次询问枚举所有最大值的点更新答案

//F 100-AC
#include<bits/stdc++.h>
#define int long long
#define MP make_pair
#define GP pair<int,int>
#define MX 1005
using namespace std;
int n,m,qq,a,b,c,ans,dis[MX][MX],w[MX];
vector<int> v[MX],p[MX];
priority_queue<GP,vector<GP >,greater<GP > > q;
signed main(){
    scanf("%lld%lld%lld",&n,&m,&qq);
    for(int i=1;i<=n;i++){scanf("%lld",&w[i]);}
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        v[a].push_back(b);p[a].push_back(c);
        v[b].push_back(a);p[b].push_back(c);
    }
    for(int o=1;o<=n;o++){
        dis[o][o]=0;q.push(MP(0,o));
        while(!q.empty()){
            GP top=q.top();q.pop();
            int l=top.first;
            int u=top.second;
            if(l>dis[o][u]) continue;
            for(int i=0;i<v[u].size();i++){
                int mb=v[u][i];if(w[mb]>w[o]) continue;
                if(dis[o][mb]>l+p[u][i]){
                    dis[o][mb]=l+p[u][i];
                    q.push(MP(dis[o][mb],mb));
                }
            }
        }
    }
    for(int i=1;i<=qq;i++){
        scanf("%lld%lld",&a,&b);ans=LONG_LONG_MAX;
        for(int j=1;j<=n;j++)
            ans=min(ans,dis[j][a]+dis[j][b]+w[j]);
        printf("%lld\n",ans>10000000000ll?-1:ans); 
    }
    return 0;
}

T7（2400）

简单博弈论和记搜，不理解为什么是T7

//G 100-AC
#include<bits/stdc++.h>
using namespace std;
int T,cnt,qw,oc,xc,a[5][5],p[15][5],mq,ban[70000],p3[15];
string yq,str;
int ck(){
    for(int i=1;i<=4;i++){
        if(a[i][1]==1 && a[i][2]==1 && a[i][3]==1 && a[i][4]==1) return 1;
        if(a[1][i]==1 && a[2][i]==1 && a[3][i]==1 && a[4][i]==1) return 1;
        if(a[i][1]==3 && a[i][2]==3 && a[i][3]==3 && a[i][4]==3) return 3;
        if(a[1][i]==3 && a[2][i]==3 && a[3][i]==3 && a[4][i]==3) return 3;
    }
    if(a[1][1]==1 && a[2][2]==1 && a[3][3]==1 && a[4][4]==1) return 1;
    if(a[1][4]==1 && a[2][3]==1 && a[3][2]==1 && a[4][1]==1) return 1;
    if(a[1][1]==3 && a[2][2]==3 && a[3][3]==3 && a[4][4]==3) return 3;
    if(a[1][4]==3 && a[2][3]==3 && a[3][2]==3 && a[4][1]==3) return 3;
    return 2;
}
int dfs(int t){
    /*for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cout<<(a[i][j]==1?&#039;x&#039;:(a[i][j]==2?&#039;.&#039;:&#039;o&#039;));
        } cout<<&#039;\n&#039;;
    }cout<<&#039;\n&#039;;*/
    int mres=ck();
    if(mres!=2){return mres;}
    if(t>cnt){return mres;}
    if(ban[mq]){return ban[mq];}
    int ans=((t&1)?-1:qw);
    for(int i=1;i<=cnt;i++){
        int cz=p3[i-1];
        if((mq/cz)%3) continue;
        cz*=((t&1)?1:2);
        mq+=cz;int x=p[i][0],y=p[i][1];
        a[x][y]=((t&1)?1:3);int res=dfs(t+1);
        a[x][y]=0;mq-=cz;
        if(t&1){
            if(abs(ans-qw)>abs(res-qw))
                ans=res;
        }else{
            if(abs(ans-qw)<abs(res-qw))
                ans=res;
        }
    }
    //cout<<ans<<endl;
    return ban[mq]=ans;
}
signed main(){
    cin.tie(0);cout.tie(0);
    p3[0]=1;
    for(int i=1;i<=15;i++){p3[i]=p3[i-1]*3;}
    cin>>T;
    while(T--){
        cin>>yq;oc=xc=cnt=mq=0;//1-x 2-P 3-o
        memset(ban,0,sizeof(ban));
        if(yq=="WIN") qw=1;
        if(yq=="TIE") qw=2;
        if(yq=="LOSE") qw=3;
        for(int i=1;i<=4;i++){
            cin>>str;
            for(int j=1;j<=4;j++){
                a[i][j]=(str[j-1]==&#039;x&#039;?1:(str[j-1]==&#039;o&#039;?3:2));
                if(a[i][j]==1) xc++;
                if(a[i][j]==2){p[++cnt][0]=i;p[cnt][1]=j;}
                if(a[i][j]==3) oc++;
            }
        }
        if(xc!=oc){
        for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            a[i][j]=4-a[i][j];
        }
        int ures=dfs(1);//cout<<ures<<&#039; &#039;;
        if(ures==qw){cout<<"YES\n";}
        else{cout<<"NO\n";}
    }
    return 0;
}

T8（0）

WA自动机

训练日志