我 AK 了一场欧洲的算法竞赛，直呼过瘾！

ACM算法日常

发布于 2021-11-17 13:11:55

9260

文章被收录于专栏：ACM算法日常ACM算法日常

The Benelux Algorithm Programming Contest (BAPC) 是一项集中了来自卢森堡、比利时和荷兰的顶尖大学的约 50 支队伍的算法竞赛。

在这个比赛中通过题目最多的队伍将会被推荐参加 Northwestern European Regional Contest，而在 NERC 中优胜的队伍可以参加 ICPC World Final ，也就是说，这是一个区域赛的选拔赛。

今天我们来看看 2018 Benelux Algorithm Programming Contest (BAPC 18) 的题目。

题目链接

https://2018.bapc.eu/ 或者 http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=006313

Problem A

非常简单的签到题。

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

const int MAXN = 1e5+5;

int a[MAXN], n, x;


int main(){

    scanf("%d%d", &n, &x);
    for (int i=0; i<n; ++i) scanf("%d", &a[i]);
    int ans = 1;
    sort(a, a+n);
    for (int i=1; i<n; ++i) {
        if (a[i]+a[i-1] > x) {
            break;
        } else ans = max(ans, i+1);
    }
    cout << ans << endl;

    return 0;
}

Problem B

题意：办公室内有一些人，这些人有生日。现在你想把你的生日安排在距离上一次有人过生日最久的一天，如果多解则尽可能靠近上一个 10月27日，求最终会安排在哪一天。

题解：改掉喜欢找最优解的习惯，暴力一下就过了。

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=400;
const int days[14]={0,31,28,31,30,31,30,31,31,30,31,30,31,0};
int bef[14];
int trans(int mm,int dd){
    return bef[mm]+dd;
}
void _trans(int day,int &mm,int &dd){
    for (mm=1;mm<=12;mm++) if (bef[mm+1]>=day){
        dd=day-bef[mm];
        return;
    }
}
char s[20];
bool exi[maxn];
int cal(int n){
    int ans=0;
    while (!exi[n]){
        n--;
        if (n==0) n=365;
        ans++;
    }
    return ans;
}
int main(){
    int i,n,m,d;
    int ans,day,cur;
    bef[1]=0;
    for (i=1;i<=13;i++) bef[i]=bef[i-1]+days[i-1];
    scanf("%d",&n);
    for (i=0;i<n;i++){
        scanf("%s %d-%d",s,&m,&d);
        exi[trans(m,d)]=true;
    }
    ans=-1; cur=-1;
    day=trans(10,28);
    for (i=day;i!=day-1;i=i%365+1){
        if (cal(i)>ans){
            ans=cal(i); cur=i;
        }
    }
        if (cal(day-1)>ans){
            ans=cal(day-1); cur=day-1;
        }
    _trans(cur,m,d);
    printf("%02d-%02d\n",m,d);
    return 0;
}

Problem C

题意：构造一个三条边长都是整数的立方体，使得体积等于给定数值且表面积最小。

题解：在根号范围枚举前两条边的长度即可。

#include<iostream>
#include<cstdio>
using namespace std;
const int inf=1e9;
int main(){
    int v;
    int a,b,c;
    int ans;
    scanf("%d",&v);
    ans=inf;
    for (a=1;a*a<=v;++a) if (v%a==0)
        for (b=1;b*b<=v/a;++b) if (v/a%b==0){
            c=v/a/b;
            ans=min(ans,2*(a*b+b*c+c*a));
        }
    printf("%d\n",ans);
    return 0;
}

Problem D

题意：在一个无向图中，两个人开车玩。一个人假定目前在A,一个假定在B。有一个人是对的，告诉你每个点是否能看到塔，每个点出度为2，求最少走多少步能判断哪个人对（如果一个和事实不符就说明另一个对了），或者无解。

题解：思维好题。bfs有

n^2

个状态,end up in TLE。最骚的是正解就是bfs优化。如果(a,b)在队列中，(b,c)在队列中，那么(a,c)也不需要搜认定它无解。为什么呢，如果(a,b)无解，(b,c)无解那么显然(a,c)无解，因为都是相同的，那么将无解看作等价关系。如果(a,c)有解，说明(a,b)(b,c)至少有一个也有解，那么也能找到解。为什么会比(a,c)优呢，因为假设(a,c)有一段怎么走都会有的公共前缀，那么如果(a,b)的前缀短，显然(a,b)更优。如果(a,b)的前缀长，那么(a,c)答案会和(b,c)一样（其实这里也是用到有限步数下无解是等价关系的原理）。用上并查集之后我们发现状态变成

O(n)

Problem E

题意：给定一个序列，问其所有不同的排列中有哪些是完全乱序的，完全乱序的定义是每一个位置都是乱序的，一个位置是乱序的被定义为其左边有比他大的点或右边有比它小的点。

题解：二维 dp。

我们先将序列排序，并将其根据元素值分类。设

cnt_i

代表第

种元素的数量，

tot_i

代表前

种元素的数量，

dp[i][j]

代表考虑最小的

类元素，前

位乱序且

j+1

位不乱序的情况总数。初始时，只有

dp[0][0]=0

。将

dp[i+1][j]

按照范围分为三类：

第一类

0 \le j < tot_i

。这种情况下，第

i+1

种元素要插在第

个元素后面。

第二类

j=tot_i

。这种情况下，第

i+1

种元素全部在最后面。

第三类 tot_i<j \le="" tot_{i+1}i+1="" 种元素第一次出现的位置前面的部分一定是已经乱序的，而且末尾有="" tot_{i+1}-j="" 个连续的第="" i="" 种元素。<="" p="">

设共有

种

个数字，对每种情况算出 dp 值，

dp[m][n]

就是答案。

Problem F

题意；有

个物品可供选择，每个物品需要花费

c_i

，之后每天都能获得的

p_i

的价值，求最小的天数获得价值

。

题解：二分天数，对于所有能赚的物品都收入囊中，和

比较大小即可。

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

int n;
LL m;
struct data
{
    LL c,p;
}a[100010];

bool check(LL x)
{
    LL ans=0;
    for (int i=1;i<=n;i++)
        if (a[i].p*x>a[i].c)
        {
            ans+=a[i].p*x-a[i].c;
            if (ans>=m) return true;
        }
    return ans>=m;
}

int main()
{
    scanf("%d%lld",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].p,&a[i].c);
    LL l=1,r=2000000010LL,mid,res;
    while(l<=r)
    {
        mid=l+r>>1;
        if (check(mid)) res=mid,r=mid-1;else l=mid+1;
    }
    printf("%lld\n",res);
    return 0;
}

Problem G

题意：环上坐着三个队伍，要求同一个队伍的人都坐在一起，求最小化被交换的人数。

题解：首先如果确定了最终状态，那么被交换的人数最少就是和最终状态位置不一样的人数。

于是就是枚举最终状态，枚举三个队伍的相对关系，用暴力，一

种情况；

枚举每种情况下所有的队伍关系按照环移动的情况，用六个指针来表示没一个队伍的开头个结尾，用滑动窗口

O(1)

维护就好了。

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

int n,A,B,C,ans;
char s[100010];

void solve(int la,int ra,int lb,int rb,int lc,int rc,int suma,int sumb,int sumc)
{
    for (int i=1;i<=n;i++)
    {
        if (s[la]!='A') suma--;la++;if (la>n) la-=n;
        ra++;if (ra>n) ra-=n;if (s[ra]!='A') suma++;
        if (s[lb]!='B') sumb--;lb++;if (lb>n) lb-=n;
        rb++;if (rb>n) rb-=n;if (s[rb]!='B') sumb++;
        if (s[lc]!='C') sumc--;lc++;if (lc>n) lc-=n;
        rc++;if (rc>n) rc-=n;if (s[rc]!='C') sumc++;
        //printf("%d %d %d %d %d %d %d %d %d\n",la,ra,lb,rb,lc,rc,suma,sumb,sumc);
        ans=min(ans,suma+sumb+sumc);
    }
}

void work(int la,int ra,int lb,int rb,int lc,int rc)
{
    int suma=0,sumb=0,sumc=0;
    for (int i=1;i<=n;i++)
        if (i>=la&&i<=ra&&s[i]!='A') suma++;
        else if (i>=lb&&i<=rb&&s[i]!='B') sumb++;
        else if (i>=lc&&i<=rc&&s[i]!='C') sumc++;
    //printf("!!!!!!!%d %d %d %d %d %d %d %d %d\n",la,ra,lb,rb,lc,rc,suma,sumb,sumc);
    ans=min(ans,suma+sumb+sumc);
    solve(la,ra,lb,rb,lc,rc,suma,sumb,sumc);
    //cout<<ans<<endl;
}

int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    A=0,B=0,C=0;
    for (

Problem H

题意：两个人轮流操作一个棋子在有向图上走，第一个人想让走的路程尽可能长，第二个人想让走的路程尽可能短，求最后走的路程长度，并特判无限长。

题解：我们考虑把每个点拆成两个，第一个点代表棋子在这里时第一个人走，第二个点代表第二个人走。

对于第一类点，只有它能到达的所有第二类点到终点的的路径长度都确定了才能确定它的路径长度。对于第二类点，只要它的最小可能路径长度是当前所有未确定的第二类点中最小的，就能确定它的路径长度。

我们知道终点拆出的两个点的路径长度都是

，因此从终点按照这种规律扩展答案，如果能扩展到起点拆出的第一类点就输出答案，无法确定则这种情况下路程无限长。


#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int maxn=2e5+5,maxm=4e5+5,inf=2e9+5;
int head1[maxn],to1[maxm],wei1[maxm],next1[maxm],tot1;
int head2[maxn],to2[maxm],wei2[maxm],next2[maxm],tot2;
int du[maxn],dp[maxn];
int que[maxn];
struct node{
    int id,val;
    node(int _i=0,int _v=0){
        id=_i; val=_v;
    }
};
bool operator < (node a,node b){
    if (a.val!=b.val) return a.val<b.val;
    return a.id<b.id;
}
void add1(int u,int v,int w){
    tot1++;
    next1[tot1]=head1[u];
    head1[u]=tot1;
    to1[tot1]=v;
    wei1[tot1]=w;
}
void add2(int u,int v,int w){
    tot2++;
    next2[tot2]=head2[u];
    head2[u]=tot2;
    to2[tot2]=v;
    wei2[tot2]=w;
}
set<node> st;
int main(){
    int i,n,m;
    int u,v,w,ed,s,t;
    int l,r;
    int ans;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    if (s==t){
        puts("0");
        return 0;
    }
    tot1=tot2=0;
    for (i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        add1(u,v,w);
        du[u]++;
        add2(v,u,w);
    }
    for (i=0;i<n;i++) dp[i]=inf;
    dp[t]=0;
    for (ed=head2[t];ed;ed=next2[ed]){
   //     du[to2[ed]]--;
        dp[to2[ed]]=wei2[ed];
    }
    for (i=0;i<n;i++) st.insert(node(i,dp[i]));
    while (!st.empty()){
        u=st.begin()->id;
        st.erase(st.begin());
        for (ed=head2[u];ed;ed=next2[ed]){
            v=to2[ed];
            du[v]--;
            if (!du[v]){
                ans=0;
                for (i=head1[v];i;i=next1[i]){
                    ans=max(ans,dp[to1[i]]+wei1[i]);
                }
                if (v==s){
                    if (ans<=inf-3) printf("%d\n",ans);
                    else puts("infinity");
                    return 0;
                }
                for (i=head2[v];i;i=next2[i])
                    if (dp[to2[i]]>ans+wei2[i]){
                        st.erase(node(to2[i],dp[to2[i]]));
                        dp[to2[i]]=ans+wei2[i];
                        st.insert(node(to2[i],dp[to2[i]]));
                    }
            }
        }
    }
    puts("infinity");
    return 0;
}

Problem I

题意：

个点

条边的图中有

个避难所，要求所有的人进到其中一个避难所，并且花费时间最长的人时间最少。

题解：二分答案，于是可以根据预处理的距离得到

个点分别能到达那些避难所，根据能到达的不同避难所进行状压，由于只有

个避难所，所以最多只有

1024

种状态。

由于避难所有容量，每一个状态的人有总量，要求所有的人都至少能够到达一个避难所，考虑网络流建图。

对于每一个状态，限制流入的流量表示每一个状态最多的人数，限制每一个避难所流出的流量，表示每个避难所的最大容量。

如果最大流 = 总人数，那么显然这个时间是可行的，我们可以考虑把时间变得更小。

#include <bits/stdc++.h>
#define INF 0x3fffffffffffffff
#define LL long long
using namespace std;

struct E
{
    int to;LL cp;
    E(int to,LL cp):to(to),cp(cp){}
};
struct Dinic
{
    static const int M=1E5*5;
    int m;
    vector<E> edges;
    vector<int> G[M];
    int d[M];
    int cur[M];
    void init(int n)
    {
        for (int i=0;i<=n;i++) G[i].clear();
        edges.clear();m=0;
    }
    void addedge(int u,int v,LL cap)
    {
        //cout<<u<<" "<<v<<" "<<cap<<endl;
        edges.push_back(E(v,cap));
        edges.push_back(E(u,0LL));
        G[u].push_back(m++);
        G[v].push_back(m++);
    }
    bool BFS(int s,int t)
    {
        memset(d,0,sizeof(d));
        queue<int> Q;
        Q.push(s),d[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();Q.pop();
            int k = G[x].size();
            for (int j=0; j<k; ++j)
            {
                int &i = G[x][j];
                E &e=edges[i];
                if (!d[e.to]&&e.cp>0)
                {
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return d[t];
    }
    LL DFS(int u,LL cp,int s,int t)
    {
        if (u==t||!cp) return cp;
        LL tmp=cp,f;
        for (int& i=cur[u];i<G[u].size();i++)
        {
            E& e=edges[G[u][i]];
            if (d[u]+1==d[e.to])
            {
                f=DFS(e.to,min(cp,e.cp),s,t);
                e.cp-=f;
                edges[G[u][i]^1].cp+=f;
                cp-=f;
                if (!cp) break;
            }
        }
        return tmp-cp;
    }
    LL go(int s,int t)
    {
        LL flow=0;
        while(BFS(s,t))
        {
            memset(cur,0,sizeof cur);
            flow+=DFS(s,INF,s,t);
        }
        return flow;
    }
}DC;

struct edge
{
    int to;
    LL cost;
    edge(int to, LL cost):to(to), cost(cost){}
};
const int MAXN = 1e5+5;
vector<edge> G[MAXN];
void add(int u, int v, LL w)
{
    G[u].push_back(edge(v, w));
    G[v].push_back(edge(u, w));
}
struct Dij
{

    LL dist[MAXN];
    struct pqNode {
        int p;
        LL v;
        pqNode(int p, LL v):p(p), v(v){}
        bool operator < (const pqNode &other) const {
            return v > other.v;
        }
    };

    priority_queue<pqNode> pq;

    void dij(int s, int n) {
        while (!pq.empty()) pq.pop();

        for (int i=0; i<=n; ++i) {
            dist[i] = INF;
        }

        pq.push(pqNode(s, 0));

        dist[s] = 0;

        while (!pq.empty()) {
            pqNode now = pq.top();
            pq.pop();
            if (now.v > dist[now.p]) continue;
            int siz = G[now.p].size();
            for (int i=0; i<siz; ++i) {
                edge &e = G[now.p][i];
                if (dist[e.to] > dist[now.p] + e.cost) {
                    dist[e.to] = dist[now.p] + e.cost;
                    pq.push(pqNode(e.to, dist[e.to]));
                }
            }
        }
    }


    LL getDist(int j) {
        return dist[j];
    }
}dij[11];

int n,m,s;
LL c[100010],b[5010],sum;
struct data
{
    int s;LL c;
}a[20];

bool check(LL x)
{
    int z=1;
    for (int i=1;i<=s;i++)
        z*=2;
    for (int i=0;i<=z;i++) b[i]=0;
    DC.init(z+s+2);int S=z+s+1,T=z+s+2;
    for (int i=1;i<=n;i++)
    {
        int y=0;
        for (int j=1;j<=s;j++)
            if (dij[j].getDist(i)<=x) y=y*2+1;else y=y*2;
        b[y]+=c[i];
    }
    for (int i=0;i<z;i++)
    {
        DC.addedge(S,i+1,b[i]);
        int y=i;
        for (int j=s;j>=1;j--)
        {
            if (y%2==1) DC.addedge(i+1,z+j,INF);
            y/=2;
        }
    }
    for (int i=1;i<=s;i++)
        DC.addedge(z+i,T,a[i].c);
    return DC.go(S,T)>=sum;
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    sum=0;
    for (int i=1;i<=n;i++)
        scanf("%lld",&c[i]),sum+=c[i];
    int x,y;LL z;
    for (int i=1;i<=m;i++)
        scanf("%d%d%lld",&x,&y,&z),add(x,y,z);
    for (int i=1;i<=s;i++)
        scanf("%d%lld",&a[i].s,&a[i].c),
        dij[i].dij(a[i].s,n);
    LL l=0,r=1E15,mid,res;
    while(l<=r)
    {
        mid=l+r>>1;
        if (check(mid)) res=mid,r=mid-1;else l=mid+1;
    }
    cout<<res<<endl;
    return 0;
}

Problem J

题意：给定四条边长，求能构成的四边形面积的最大值。

题解：在猜结论1一定是梯形失败后，猜结论2：四边形面积和其中一条对角线的长度成单峰函数的关系。

在这种情况下，先枚举四条边的位置，再三分法求凸函数最大值，过了，说明猜对了。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double ee=1e-12;
double tri(double a,double b,double c){
    double p=(a+b+c)/2;
    return sqrt(fabs(p*(p-a)*(p-b)*(p-c)));
}
double split(double a,double b,double c,double d,double l,double r){
    if (r-l<ee) return tri(a,b,(l+r)/2)+tri(c,d,(l+r)/2);
    double m1,m2;
    m1=(l+r)/2; m2=(m1+r)/2;
    if (tri(a,b,m1)+tri(c,d,m1)>tri(a,b,m2)+tri(c,d,m2))
        return split(a,b,c,d,l,m2);
    else return split(a,b,c,d,m1,r);
}
double solve(double a,double b,double c,double d){
    double l,r;
    l=max(fabs(a-b),fabs(c-d));
    r=min(a+b,c+d);
    if (l>=r) return 0.0;
    return split(a,b,c,d,l,r);
}
int main(){
    double a,b,c,d;
    double ans;
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    ans=0;
    ans=max(ans,solve(a,b,c,d));
    ans=max(ans,solve(a,c,b,d));
    ans=max(ans,solve(a,d,b,c));
    printf("%.12f\n",ans);
    return 0;
}

Problem K

题意：给一棵树，求加多少边使得整个树变成双连通分量

题解：问加多少边是原题，但是本题要构造解。本着犹豫就会败北冲上去瞎连边吃了一发罚时果断白给了，后来想想好像构造解也是多校里有过的结论。度数为1的点按dfs序排序，保证间隔n/2个点，奇数中间的连两边就行了。因为连边无效是因为两个点连在同一个子树下，且lca不是根节点。如果隔着一半连能两两匹配，而且一定能覆盖连完所有的子树，因为不可能两个子树的和加起来超过总叶子节点数，它们两个必定会相连。

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

const int MAXN = 1e5+5;

int n, h;
int deg[MAXN];

vector<int> List, G[MAXN];

int ansu[MAXN], ansv[MAXN], acnt;
int r[MAXN], cnt;
bool vis[MAXN];



void dfs(int now) {

    vis[now] = 1;
    r[now] = cnt++;
//    printf("dfs now->%d r[now]->%d\n", now, r[now]);
    int sz = G[now].size();
    for (int i=0; i<sz; ++i) {
        int v = G[now][i];
        if (!vis[v]) dfs(v);
    }
}

bool cmp(int a, int b) {
    return r[a] < r[b];
}

int main()
{
    scanf("%d%d", &n, &h);
    int u, v;
    for (int i=0; i<n-1; ++i) {
        scanf("%d%d", &u, &v);
        ++deg[u]; ++deg[v];
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int ans = 0, root = 0;
    for (int i=0; i<n; ++i) {
        if (deg[i] == 1) List.push_back(i);
        else root = i;
    }
    dfs(root);
    sort(List.begin(), List.end(), cmp);

    int siz = (int)List.size(), del = (siz+1)/2;
//    printf("%d\n", siz);
    int ansc = siz/2;
    for (int i=0; i<ansc; ++i) {
        ansu[acnt] = List[i];
        ansv[acnt++] = List[i+del];
    }
    if (siz%2) {
        ++ansc;
        ansu[acnt] = List[siz/2];
        ansv[acnt++] = List[0];
    }
    printf("%d\n", ansc);
    for (int i=0; i<acnt; ++i) {
        printf("%d %d\n", ansu[i], ansv[i]);
    }



    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-14，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

node.js

登录后参与评论

0 条评论

热度