2018 ACM-ICPC World Finals - Beijing

时间:2021-06-24 18:21:29

2018 ACM-ICPC World Finals - Beijing


A. Catch the Plane

\(dp[v_i,t_i]\)表示时刻\(t_i\)\(v_i\)点,到达终点的最大概率,那么转移方程为:
\(dp[(v_i,t_i)] = max(P_{ij}*dp[(v_{j+1},t_{j+1})] + (1-Pij)*dp[(v_{i+1},t_{i+1})])\)
\(dp[(v_i,t_i)] = max(dp[v_{i+1},t_{i+1}])\)
其中\((v_i,t_i)\)的一个后继状态为\((v_j,t_j)\)两个状态之间的转移概率为\(P_{ij}\),第一种转移:沿\(P_{ij}\)这个方向转移,以及继续留在这个点等待下次转移(\((v_{i+1},t_{i+1})\)为同一位置下与\(t_i\)最接近的下一个时间);第二种转移是:直接选择继续等待的概率。想出这些后,以为可以愉快的ac了。然而调到早上7点。。。才弄好

  • 问题一:%I64d读1e18,蜜汁爆了,换了几个编译器才发现。。。
  • 问题二:为简化代码省略了讨论,导致后面一个点wa
  • 问题三:起点和终点要单独加进去,导致后面一个点wa
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
typedef long double LD;
typedef unsigned long long ll;
const int N = 5e6 + 100;
using namespace std;
struct node {
    int x; ll t;
    node(){}node(int a,ll b) {x=a,t=b;}
    bool operator < (const node a) const {
        if(t==a.t) return  x<a.x;
        return t < a.t;
    }
};
bool cmp(node a,node b) {
    if(a.x==b.x) return a.t < b.t;
    return a.x < b.x;
}
bool cmp0(node a,node b) {
    if(a.t==b.t) return a.x > b.x;
    return a.t < b.t;
}
vector<node> v;
map<node,int> id;
node fid[N];
int cnt;

int nxt[N];
LD dp[N];
vector< pair<int,LD> > E[N];
void nwnode(node a) {
    if(id[a]!=0) return;
    ++cnt;
    fid[cnt] = a;
    id[a] = cnt;
}
void add(int a,int b,LD p){
    E[a].pb(make_pair(b,p));
}
int n,m;
ll k;

int main() {int f=0;
    ll MX=0,MN=1000000000000000002LL;
    scanf("%d%d%llu",&m,&n,&k);
    rep(i,1,m) {int a,b;ll s,t; double p;
        scanf("%d %d %llu %llu %lf",&a,&b,&s,&t,&p);
        if(t<=k){
            nwnode(node(a,s));
            nwnode(node(b,t));

            add(id[node(a,s)],id[node(b,t)],(LD)p);
            v.pb(node(a,s));
            v.pb(node(b,t));
            if(b == 1LL) {
                dp[id[node(b,t)]] = 1.0;
                MX = max(t,MX);
            }
            if(a==0){
                if(!f)MN=t;
                else MN=min(MN,t);
                f=1;
            }
        }
    }

    nwnode(node(1,MX));
    nwnode(node(1,k));
    nxt[id[node(1,MX)]] = id[node(1,k)];
    dp[id[node(1,k)]] = 1.0;
    v.pb(node(1,k));
    add(id[node(1,MX)],id[node(1,k)],1.0);

    nwnode(node(0,0));
    v.pb(node(0,0));
    nxt[id[node(0,0)]] = id[node(0,MN)];
    add(id[node(0,0)],id[node(0,MN)],1.0);

    sort(v.begin(),v.end(),cmp);
    for(int i=v.size()-2;i>=0;--i) {
        if(v[i].x==v[i+1].x){
            if(v[i].t == v[i+1].t) nxt[id[v[i]]] = nxt[id[v[i+1]]];
            else nxt[id[v[i]]] = id[v[i+1]];
        }
    }
    sort(v.begin(),v.end(),cmp0);

    for(int i=v.size()-1;i>=0;--i) if(dp[id[v[i]]]==0){
        LD mx = 0;int t = id[v[i]];
        for(int j=0;j<E[t].size();++j) {
            if(fid[nxt[E[t][j].first]].x == fid[E[t][j].first].x && fid[nxt[t]].x == fid[t].x && dp[nxt[t]]!=0 && dp[nxt[E[t][j].first]]!=0 )
                mx = max(mx, E[t][j].second*dp[nxt[E[t][j].first]] + (1.0-E[t][j].second)*dp[nxt[t]]);
            else if(fid[nxt[E[t][j].first]].x == fid[E[t][j].first].x && dp[nxt[E[t][j].first]]!=0)
                mx = max(mx, E[t][j].second*dp[nxt[E[t][j].first]]);
            else if(fid[nxt[t]].x == fid[t].x && dp[nxt[t]]!=0)
                mx = max(mx, (1.0-E[t][j].second)*dp[nxt[t]]);
        }
        if(fid[nxt[t]].x == fid[t].x)
            mx = max(mx, dp[nxt[t]]);
        dp[t] = mx;
    }
    printf("%.10f\n",(double)dp[id[node(0,0)]]);
    return 0;
}

B. Comma Sprinkler

这题没什么难度,把单词取出来直接搜索即可。

#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
const int N = 1000100;
using namespace std;
string s, word[N];
int cnt;
void chai(string s) {
    int n = s.size();
    cnt = 1;
    for(int i=0;i<n;++i) {
        if(s[i]==' '){
            word[cnt] += ' ';
            ++cnt;
        }
        else
            word[cnt]+=s[i];
    }
}
map< string,vector<string> > pre,last;
string delco(string s) {
    string t;t.clear();
    for(auto c: s) if(c>='a'&&c<='z') t+=c;
    return t;
}
int iscolst(string s) {
    int t = s.size()-1;
    while(t>=0){
        if(s[t]==',')return 1;
        --t;
    }
    return 0;
}
int isbiaolst(string s) {
    int t = s.size()-1;
    while(t>=0){
        if(s[t]=='.'||s[t]==',')return 1;
        --t;
    }
    return 0;
}
map<string,bool> vispre,vislst;
void X(string s);
void Y(string s);
void X(string s) {
    vislst[s] = 1;
    for(int x=0;x<last[s].size();++x) if(!vispre[last[s][x]]) Y(last[s][x]);
}
void Y(string s) {
    vispre[s] = 1;
    for(int x=0;x<pre[s].size();++x) if(!vislst[pre[s][x]]) X(pre[s][x]);
}
string update(string s) {
    s+=',';
    int t=s.size()-1;
    swap(s[t],s[t-1]);
    return s;
}
int main() {
    getline(cin,s); chai(s);
    for(int i=2;i<=cnt;++i) if(!isbiaolst(word[i-1])){
        pre[delco(word[i])].pb(delco(word[i-1]));
    }
    for(int i=1;i<cnt;++i) if(!isbiaolst(word[i])){
        last[delco(word[i])].pb(delco(word[i+1]));
    }
    for(int i=1;i<cnt;++i) {
        string t = delco(word[i]);
        if(!vislst[t]&&iscolst(word[i]))X(t);
    }
    for(int i=2;i<=cnt;++i) {
        string t=delco(word[i]);
        if(!vispre[t]&&iscolst(word[i-1])) Y(t);
    }
    for(int i=1;i<=cnt;++i) {
        string t = delco(word[i]);
        if(vislst[t]&&!isbiaolst(word[i]))
            cout << update(word[i]);
        else
            cout << word[i];
    }puts("");
    return 0;
}

F. Go with the Flow

把单词的长度记录下来,模拟放单词,把所有位置上是空格的位置按从上到下存起来。顺序dp求出每个位置向上最长走多远,dp过程中取最大值即可,这样复杂度与空格数成正比,看大佬代码学习了一下,巧妙地解决了dp数组的开法用一维存,这样空间就不随着宽度变化。一开始写的暴力bfs炸的妥妥的。

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define PII pair<int,int>
#define MP make_pair
#define fr first
#define sc second
typedef long long ll;
const int N = 5600;
using namespace std;
int n,L[N],len;
char s[88];
PII A[N];
int cnt,f[N*188];

void cal_A(int w) {
    int x=1,y=0;cnt=0;
    rep(j,1,n) {
        if(y+L[j]<=w){
            if(y)A[++cnt]=MP(x,y);
            y+=L[j]+1;
        }
        else {
            ++x;
            y=L[j]+1;
        }
    }
}
int cal_id(int x,int y,int m) {
    if(x<1)return 0;
    if(y<1||y>m)return 0;
    return (x-1)*m + y;
}
int main() {
    int MX = 0;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf(" %s",s);
        L[i]=strlen(s);
        MX = max(MX,L[i]);
        len += L[i];
    }
    len += (n-1);

    int ans=0,ans1=0,tmp;
    rep(i,MX,len) {
        cal_A(i);tmp = 0;

        rep(j,1,cnt){
            int x=A[j].fr, y=A[j].sc;
            f[cal_id(x,y,i)] = max(f[cal_id(x-1,y-1,i)],f[cal_id(x,y,i)]);
            f[cal_id(x,y,i)] = max(f[cal_id(x-1,y,i)],f[cal_id(x,y,i)]);
            f[cal_id(x,y,i)] = max(f[cal_id(x-1,y+1,i)],f[cal_id(x,y,i)]);
            ++f[cal_id(x,y,i)];
            tmp = max(tmp,f[cal_id(x,y,i)]);
        }
        if(tmp>ans){
            ans=tmp;
            ans1=i;
        }
        rep(j,1,cnt)f[cal_id(A[j].fr,A[j].sc,i)]=0;
    }
    printf("%d %d\n",ans1,ans);
    return 0;
}

K. Wireless is the New Fiber

贪心,首先答案是一棵树,既有n-1条边,所以要减少的总边数固定,所以我们尽量要改变度数大的点,换一句话一定先满足分叉少的。现在考虑如何满足,注意到度数为1的点是很特殊的,我们一定要先满足他们,并且最好他们不互相连接,那就把他们接在其他度数较小的点上,显然最好不接满。我们已经确定,如果有度为1的点,一定要先满足它,那么考虑如何把度非1的点转换为度为1的点,显然就是把度数为1的点接上去使他恰好多余一个位置,这些点组成的集合便是一个新的度为1的点,如此反复到无法产生新的度为1的点集。接下来我们仍然优先满足度数小的点,先把所有的1接上去,剩下的位置怎么办,我用度数最大的点接上去,把他们当作度数为1的点,为什么?因为这些点的度数最大,可以尽可能的把减少的边用在他们身上,重复上述操作,直到不足以产生新的度数为1的点集。最后把剩余的点全部加到当前节点上。如果最终有多个的度数为1的点集,那把他们任意连成一棵树树即可。这题的贪心,我之前一直在胡写,也没证明出来做法的正确性。。GG。。。。膜了大佬的写法

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pb push_back
typedef long long ll;
const int N = 10000 + 10;
using namespace std;
int n,m,d[N];
vector<int> G[N];
void add(int u,int v) {G[u].pb(v);}
struct node {
    int id,d;
    node(){}node(int a,int b){id=a,d=b;}
}a[N];
int b[N];
int cnt,cnt0;
bool cmp(node a,node b) {return a.d < b.d;}
vector<int> v;
int main() {
    scanf("%d%d",&n,&m);
    rep(i,1,m) {int x,y;
        scanf("%d%d",&x,&y);
        ++d[x],++d[y];
    }

    for(int i=0;i<n;++i) a[cnt++] = node(i,d[i]);
    sort(a,a+cnt,cmp);

    for(int i=0;i<cnt;++i) {
        if(a[i].d==1) v.push_back(a[i].id);
        else if(v.size() >= a[i].d-1){
            for(int j=0;j<a[i].d-1;++j) {
                add(a[i].id,v[v.size()-1]);
                v.pop_back();
            }
            v.push_back(a[i].id);
        }
        else if(v.size()+cnt-i-1>=a[i].d-1){
            for(int j=0;j<v.size();++j) {
                add(v[j],a[i].id);
            }
            for(int j=0;j<a[i].d-1-v.size();++j){
                add(a[i].id,a[--cnt].id);
            }
            v.clear();
            v.push_back(a[i].id);
        }
        else {
            for(int j=0;j<v.size();++j){
                add(a[i].id,v[j]);
            }
            for(int j=i+1;j<cnt;++j){
                add(a[i].id,a[j].id);
            }
            v.clear();
            break;
        }
    }
    if(v.size()>0){
        for(int i=1;i<v.size();++i){
            add(v[0],v[i]);
        }
    }


    for(int i=0;i<n;++i){
        for(int j=0;j<G[i].size();++j) {
            --d[i],--d[G[i][j]];
        }
    }
    int num=0;
    rep(i,0,n-1)if(d[i])++num;
    printf("%d\n",num);
    printf("%d %d\n",n,n-1);
    rep(i,0,n-1){
        rep(j,0,(int)G[i].size()-1) {
            printf("%d %d\n",i,G[i][j]);
        }
    }

    return 0;
}