2020 ICPC Universidad Nacional de Colombia Programming Contest

A. Approach

三分

显然答案可以三分，注意\(eps\)还有两条线平行的情况

view code

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
double dis2(double ox, double oy, double ex, double ey){ return (ox - ex) * (ox - ex) + (oy - ey) * (oy - ey); }
const double eps = 1e-12;
typedef long long ll;
ll asx, asy, aex, aey;
ll bsx, bsy, bex, bey;
double alen, blen;
double check(double t){
    double x1, y1, x2, y2, dx, dy, d;
    dx = 1.0*aex - asx, dy = 1.0*aey - asy;
    d = alen;
    if(t>=d-eps) x1 = aex, y1 = aey;
    else x1 = asx + t * (dx / d), y1 = asy + t * (dy / d);
    dx = bex - bsx, dy = bey - bsy;
    d = blen;
    if(t>=d-eps) x2 = bex, y2 = bey;
    else x2 = bsx + t * (dx / d), y2 = bsy + t * (dy / d);
    return dis2(x1,y1,x2,y2);

}
int main(){
    cin >> asx >> asy >> aex >> aey;
    cin >> bsx >> bsy >> bex >> bey;
    alen=sqrt(dis2(asx,asy,aex,aey)),blen=sqrt(dis2(bsx,bsy,bex,bey));
    double l = 0, r = min(alen,blen);
    double ans=1e25;
    for(int i = 1; i <= 100000; i++){
        double ml = (2*l+r) / 3;
        double mr = (l+2*r) / 3;
        double sl=check(ml),sr=check(mr);
        if(sl+eps <= sr) r = mr;
        else l = ml;
        ans=min({ans,sl,sr});
    }
    l=min(alen,blen);r=max(alen,blen);
    for(int i = 1; i <= 100000; i++){
        double ml = (2*l+r) / 3;
        double mr = (l+2*r) / 3;
        double sl=check(ml),sr=check(mr);
        if(sl+eps <= sr) r = mr;
        else l = ml;
        ans=min({ans,sl,sr});
    }
    cout << fixed << setprecision(12) << sqrt(ans) << endl;
    return 0;
} 

B. Baby name

\(SA\)

第二个串必然是选字典序最大的后缀，的一个串选择字典序最大的后缀的一个前缀，除了第一个字符之外所有字符都要比第二个串的首字母大或等

直接\(SA\)排序即可

view code

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

#define LL long long
const int N=2e6+5,MOD=1e9+7;

int rk[N],sec[N],sa[N],c[N];
void SA(char *s,int n,int m){
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[rk[i]=(int)(s[i])]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)sa[c[rk[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k+1;i<=n;i++)sec[++p]=i;
        for(int i=1;i<=n;i++)if(sa[i]>k)sec[++p]=sa[i]-k;
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[rk[sec[i]]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[rk[sec[i]]]--]=sec[i];
        swap(rk,sec);
        p=1;
        rk[sa[1]]=1;
        for(int i=2;i<=n;i++)rk[sa[i]]=(sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k]?p:++p);
        if(p==m)break;
        m=p;
    }
}

char s[N],t[N];

int main()
{
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);

    cin>>s+1>>t+1;
    int ls=strlen(s+1),lt=strlen(t+1);

    SA(t,lt,300);
    int pt=sa[lt];

    SA(s,ls,300);
    int ps=sa[ls];

    string ans;

    for(int i=ps;i<=ls;i++)
        if(i==ps||s[i]>=t[pt])ans+=s[i];else break;
    for(int i=pt;i<=lt;i++)ans+=t[i];

    cout<<ans<<endl;
} 

C. Cipher count

埃氏筛

一个串为需要被计数的串，当且仅当它的最小循环节为其本身

枚举每个长度，\(f(i)\)表示长度为\(i\)的且最小循环节为为自身的串的数量，那么可以得到\(f(i)=a^i - \sum_{d\mid i}f(d)\)

直接类似埃氏筛一样处理即可

view code

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MOD = (int)1e9+7;
const int MAXN = 5e6+7;
int f[MAXN], a, k, ret;

void solve(){
    scanf("%d %d",&a,&k);
    f[0] = 1;
    for(int i = 1; i <= k; i++) f[i] = 1ll * f[i-1] * a % MOD;
    for(int i = 1; i <= k; i++) {
        ret = (ret + f[i]) % MOD;
        for(int j = i + i; j <= k; j += i) f[j] = (f[j] - f[i] + MOD) % MOD;
    }
    cout << ret << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    // freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

D. Dice

矩阵快速幂

view code

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

#define LL long long
const int N=2e6+5,MOD=1e9+7;

int SIZ;
struct node{
    int a[205][205];
    node(){memset(a,0,sizeof a);}
    int* operator[](int x){ return a[x]; }
    friend node operator*(node a,node b){
        node c;
        for(int i=0;i<SIZ;i++){
            for(int j=0;j<SIZ;j++){
                for(int k=0;k<SIZ;k++){
                    c[i][j]=(c[i][j]+(LL)a[i][k]*b[k][j])%MOD;
                }
            }
        }
        return c;
    }
}f,f0;

node qpow(node a,LL b){
    node res;
    for(int i=0;i<SIZ;i++)res[i][i]=1;
    for(;b;b>>=1,a=a*a)
        if(b&1)res=res*a;
    return res;
}

LL qpow(LL a,LL b){
    LL res=1;
    for(;b;b>>=1,a=a*a%MOD)
        if(b&1)res=res*a%MOD;
    return res;
}

int w[N];

int main()
{
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);

    int n,k,m;
    cin>>n>>k>>m;

    int inv=qpow(k-k/m,MOD-2);
    for(int i=1;i<=k;i++){
        if(i%m==0)continue;
        w[i%m]++;
    }

    for(int i=0;i<m;i++)w[i]=(LL)w[i]*inv%MOD;

    SIZ=m;
    f0[0][0]=1;
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            f[i][j]=w[(j-i+m)%m];
        }
    }

    auto fto=qpow(f,n);
    auto ans=f0*fto;

    cout<<ans[0][0]<<endl;
} 

E. Enter to the best problem of this contest!

交互

先询问\(1\)号点，记录距离，然后每次询问当前点的一个儿子，如果距离当前点的距离大就进入另一个儿子的子树，否则进入当前儿子的子树

view code

#include<bits/stdc++.h>
using namespace std;
int query(int x){
    cout << x << endl;
    cin >> x;
    return x;
}
void print(int x){ cout << "! " << x <<endl; }

int main(){
    int n;
    scanf("%d",&n);
    int u = 1;
    int dis = query(1);
    if(!dis){
        print(1);
        return 0;
    }
    for(int i = 2; i <= n; i++){
        int ndis = query(u<<1);
        if(dis==1){
            if(ndis==2) print(u<<1|1);
            else print(u<<1);
            return 0;
        }
        if(ndis>dis) u = u << 1 | 1, dis = ndis - 2;
        else u = u << 1, dis = ndis;
    }
    return 0;
} 

F. Free restricted flights

分层图最短路

建正图和反图，对于两个点，分别正图反图跑一次最短路，\(dis[ta][tb][i][kk]\)表示人为\(a\)或\(b\)，跑的是正图或反图，起始点到\(i\)点，用了\(kk\)次\(ticket\)的最小花费

然后枚举每个点计算最小值即可

view code

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define INF 0x3f3f3f3f
const int MAXN = 1e4+7;
int n, m, a, b, k;
int dis[2][2][MAXN][11];
vector<pii> G[2][MAXN];
void dijkstra(int ta, int tb, int s){
    priority_queue<pair<int,pii>,vector<pair<int,pii> >, greater<pair<int,pii> > > que;
    dis[ta][tb][s][0] = 0;
    que.push(make_pair(0,make_pair(s,0)));
    while(!que.empty()){
        auto p = que.top(); que.pop();
        int d = p.first, u = p.second.first, kk = p.second.second;
        if(dis[ta][tb][u][kk]!=d) continue;
        for(auto &e : G[tb][u]){
            int v = e.first, w = e.second;
            if(dis[ta][tb][v][kk] > dis[ta][tb][u][kk] + w){
                dis[ta][tb][v][kk] = dis[ta][tb][u][kk] + w;
                que.push(make_pair(dis[ta][tb][v][kk],make_pair(v,kk)));
            }
            if(kk!=k){
                if(dis[ta][tb][v][kk+1] > dis[ta][tb][u][kk]){
                    dis[ta][tb][v][kk+1] = dis[ta][tb][u][kk];
                    que.push(make_pair(dis[ta][tb][v][kk+1],make_pair(v,kk+1)));
                }
            }
        }
    }
}
int main(){
    scanf("%d %d %d %d %d",&n,&m,&a,&b,&k);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        scanf("%d %d %d",&u,&v,&w);
        G[0][u].push_back(make_pair(v,w));
        G[1][v].push_back(make_pair(u,w));
    }
    memset(dis,0x3f,sizeof(dis));
    dijkstra(0,0,a);
    dijkstra(0,1,a);
    dijkstra(1,0,b);
    dijkstra(1,1,b);
    int u = INT_MAX;
    int ret = INF;
    for(int i = 0; i < n; i++) if(i!=a and i!=b){
        int da = INF, db = INF;
        for(int j = 0; j <= k; j++) for(int jj = 0; jj + j <= k; jj++){
            if(dis[0][0][i][j]+dis[0][1][i][jj]<da) da = dis[0][0][i][j]+dis[0][1][i][jj];
            if(dis[1][0][i][j]+dis[1][1][i][jj]<db) db = dis[1][0][i][j]+dis[1][1][i][jj];
        }
        if(da+db<ret){
            ret = da + db;
            u = i;
        }
    }
    if(ret>=INF) cout << ">:(" << endl;
    else cout << u << ' ' << ret << endl;
    return 0;
} 

G. Great dinner

组合数学

\(m\)对学生和剩下的\(n-2m\)个分别算

假设现在已经有\(x\)个学生在队列中，那么放入一对学生，枚举第一个学生在的位置，一共有\(\sum_{i=1}^{x+1}i\)种安置方法法

放入一个学生，则有\(x+1\)种安置方法，乘起来即可

view code

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

int n, m;
const int MOD = 1e9+7;
long long cal(int x){ return (1ll + x) * x / 2 % MOD; }
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d",&x,&y);
    }
    long long ret = 1;
    int tot = 0;
    for(int i = 1; i <= m; i++){
        ret = ret * cal(tot+1) % MOD;
        tot += 2;
    }
    int num = n - 2 * m;
    for(int i = 1; i <= num; i++) ret = ret * (tot + 1ll) % MOD, tot += 1;
    cout << ret << endl;
    return 0;
} 

H. Happy game

\(PAM\)板子题

答案就是本质不同的长度大于\(1\)的奇数回文子串的数量

view code

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

#define LL long long
const int N=6e5+5,MOD=1e9+7;

class PAM{
public:
    int tot,sz[N],len[N],ch[N][26],fail[N],n,last,ans;
    char s[N];
    void init(){
        cin>>n>>s+1;
        len[0]=0;
        len[1]=-1;
        fail[0]=1;
        fail[1]=0;
        tot=1;
        last=0;
        ans=0;
    }
    int getfail(int x,int pos){
        while(s[pos]!=s[pos-len[x]-1])x=fail[x];
        return x;
    }
    void insert(int x,int pos){
        int u=getfail(x,pos);
        int c=s[pos]-'a';
        if(!ch[u][c]){
            len[++tot]=len[u]+2;
            fail[tot]=ch[getfail(fail[u],pos)][c];
            sz[tot]=sz[fail[tot]]+1;
            ch[u][c]=tot;

            if(len[tot]>=3&&(len[tot]&1))ans++;
        }
        last=ch[u][c];
    }
    void build(){
        for(int i=1;i<=n;i++){
            insert(last,i);
        }
    }
}t;

int main()
{
//    freopen("H.in","r",stdin);
    ios::sync_with_stdio(0);

    t.init();
    t.build();
    cout<<t.ans<<endl;

    return 0;
} 

I. Incredible photography

单调栈

显然我们需要从高度最高的位置开始枚举来计算答案，对于枚举的每个位置，分别找到其左边和右边比当前高度高的第一个建筑，如果存在高度相同的要继续往两边找（为了保证走的最远），记位置\(i\)的答案是\(f(i)\)，找到的左边位置为\(l\)，右边位置为\(r\)，则\(f(i) = \max(f(l)+dis(l,i),f(r)+dis(i,r))\)

view code

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
#define LL long long
int n, A[MAXN], last[MAXN];
int B[MAXN][20], lp[MAXN], rp[MAXN], lt[MAXN], rt[MAXN];
LL f[MAXN];
int stk[MAXN], top;
vector<int> vec;

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&A[i]), vec.push_back(A[i]);
    sort(vec.begin(),vec.end()); vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i = 1; i <= n; i++) A[i] = lower_bound(vec.begin(),vec.end(),A[i]) - vec.begin() + 1;
    for(int i = 1; i <= n; i++) B[i][0] = A[i];
    for(int j = 1; (1 << j) <= n; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++){
        B[i][j] = max(B[i][j-1],B[i+(1<<(j-1))][j-1]);
    }
    auto qmax = [&](int L, int R){
        if(L>R) return -1;
        int d = log2(R - L + 1);
        return max(B[L][d],B[R-(1<<d)+1][d]);
    };
    memset(last,0,sizeof(last));
    for(int i = 1; i <= n; i++){
        if(!last[A[i]] or qmax(last[A[i]],i)>A[i]) lp[i] = i;
        else lp[i] = lp[last[A[i]]];
        last[A[i]] = i;
    }
    memset(last,0,sizeof(last));
    for(int i = n; i >= 1; i--){
        if(!last[A[i]] or qmax(i,last[A[i]])>A[i]) rp[i] = i;
        else rp[i] = rp[last[A[i]]];
        last[A[i]] = i;
    }
    top = 0;
    for(int i = 1; i <= n; i++){
        lt[i] = i;
        while(top and A[i]>=A[stk[top]]) lt[i] = lt[stk[top--]];
        stk[++top] = i;
    }
    top = 0;
    for(int i = n; i >= 1; i--){
        rt[i] = i;
        while(top and A[i]>=A[stk[top]]) rt[i] = rt[stk[top--]];
        stk[++top] = i;
    }
//    for(int i = 1; i <= n; i++) cout << lt[i] << ' ' <<rt[i] <<endl;
    vector<pair<int,int> > vcc;
    for(int i = 1; i <= n; i++) vcc.push_back(make_pair(A[i],i));
    sort(vcc.begin(),vcc.end(),greater<pair<int,int> >());
    for(int i = 0; i < n; i++){
        int id = vcc[i].second;
        // cout << id << ' ' << lt[i] - 1  << ' ' << rt[i] + 1 <<endl;
        if(lt[id]-1!=0){
            int p = lt[id] - 1;
            f[id] = max(f[id],f[lp[p]] + id - lp[p]);
        }
        if(rt[id]+1!=n+1){
            int p = rt[id] + 1;
            f[id] = max(f[id],f[rp[p]] + rp[p] - id);
        }
    }
    for(int i = 1; i <= n; i++) cout << f[i] << " \n"[i==n];
    return 0;
} 

J. Java exam

K. Katastrophic sort

view code

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

#define LL long long
const int N=2e6+5,MOD=1e9+7;

char s[N],t[N],s1[N],t1[N];

int main()
{
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);

    cin>>s>>t;
    int n=strlen(s),l2=strlen(t);

    if(strcmp(s,t)==0){
        cout<<"="<<endl;
        return 0;
    }

    int p1=0,p2=0;
    for(int i=0;i<n;i++){
        if(p1<n){
            if(s[p1]>='a'&&s[p1]<='z'){
                if(s[p1]==t[p2]){
                    p1++,p2++;
                    continue;
                }
                else {
                    if(s[p1]<t[p2]){
                        cout<<"<"<<endl;
                        return 0;
                    }
                    else {
                        cout<<">"<<endl;
                        return 0;
                    }
                }
            }
            else{
                int t1=p1,t2=p2;
                while(t1<n&&s[t1]>='0'&&s[t1]<='9')t1++;
                while(t2<l2&&t[t2]>='0'&&t[t2]<='9')t2++;
                if(t1-p1!=t2-p2){
                    if(t1-p1<t2-p2){
                        cout<<"<"<<endl;
                        return 0;
                    }
                    else {
                        cout<<">"<<endl;
                        return 0;
                    }
                }
                else{
                    for(int i=0;i<t1-p1;i++){
                        if(s[p1+i]<t[p2+i]){
                            cout<<"<"<<endl;
                            return 0;
                        }
                        else if(s[p1+i]>t[p2+i]){
                            cout<<">"<<endl;
                            return 0;
                        }
                    }
                    p1=t1,p2=t2;
                }
            }
        }
        else break;
    }
} 

L. Lonely day

\(BFS\)

预处理出每个方向连续块的数量

对于每个点向四周连边然后跑\(BFS\)同时记录边的方向即可

view code

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

#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define per(i,a,n) for(int i=(n);i>=(a);i--)
#define LL long long
const int N=6e6+5,MOD=1e9+7;

char s[2005][2005];
int to[4][2005][2005],dis[2005][2005],pre[2005][2005],px[2005][2005],py[2005][2005];

struct node{
    int x,y;
}src,des,que[N];
int st,ed;

int dx[]={1,0,0,-1};
int dy[]={0,-1,1,0};

string ans;
void dfs(int x,int y){
    if(src.x==x && src.y==y){
        return;
    }
    if(pre[x][y]==0)ans+='D';
    else if(pre[x][y]==1)ans+='L';
    else if(pre[x][y]==2)ans+='R';
    else if(pre[x][y]==3)ans+='U';

    dfs(px[x][y],py[x][y]);
}

int main()
{
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);

    int n,m;
    cin>>n>>m;

    rep(i,1,n){
        cin>>s[i]+1;
        rep(j,1,m){
            if(s[i][j]=='S')src=(node){i,j};
            else if(s[i][j]=='E')des=(node){i,j},s[i][j]='.';

            dis[i][j]=-1;
        }
    }

    rep(i,1,n){
        int las=0;
        rep(j,1,m){
            to[1][i][j]=las+1;
            if(s[i][j]=='X')las++;else las=0;
        }
        las=0;
        per(j,1,m){
            to[2][i][j]=las+1;
            if(s[i][j]=='X')las++;else las=0;
        }
    }

    rep(j,1,m){
        int las=0;
        rep(i,1,n){
            to[3][i][j]=las+1;
            if(s[i][j]=='X')las++;else las=0;
        }
        las=0;
        per(i,1,n){
            to[0][i][j]=las+1;
            if(s[i][j]=='X')las++;else las=0;
        }
    }

    st=1,ed=0;
    que[++ed]=src;dis[src.x][src.y]=0;

    while(st<=ed){
        auto u=que[st++];
        rep(i,0,3){
            int nx=to[i][u.x][u.y]*dx[i]+u.x,ny=to[i][u.x][u.y]*dy[i]+u.y;
            if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&s[nx][ny]=='.'&&dis[nx][ny]==-1){
                dis[nx][ny]=dis[u.x][u.y]+1;
                pre[nx][ny]=i;
                px[nx][ny]=u.x;
                py[nx][ny]=u.y;
                que[++ed]=(node){nx,ny};
            }
        }
    }

    int res=dis[des.x][des.y];
    cout<<res<<endl;
    if(~res){
        dfs(des.x,des.y);
        reverse(ans.begin(),ans.end());
        cout<<ans<<endl;
    }

    return 0;
} 

M. Magic spells

子序列自动机

用原串建子序列自动机，然后每个询问串在上面跑即可

view code

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

#define LL long long
const int N=2e6+5,MOD=1e9+7;

char s[N],t[N];
int las[N],nxt[(int)2e5+5][27];

int main()
{
//    freopen("in.txt","r",stdin);

    ios::sync_with_stdio(0);
    cin>>s+1;
    int n=strlen(s+1);

    for(int i=n;i>=1;i--){
        for(int j=0;j<26;j++)nxt[i][j]=las[j];
        las[s[i]-'a']=i;
    }
    for(int j=0;j<26;j++){
        nxt[0][j]=las[j];
    }

    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>t;

        int l2=strlen(t);

        int now=0,cnt=0,ok=1;
        for(int j=0;ok&&j<l2;j++){
            if(nxt[now][t[j]-'a']>now){
                cnt++;
                now=nxt[now][t[j]-'a'];
            }
            else ok=0;
        }

        if(!cnt){
            cout<<"IMPOSSIBLE\n";
        }
        else{
            for(int j=0;j<cnt;j++){
                cout<<t[j];
            }
            cout<<'\n';
        }
    }
} 

N. Name this problem