Preliminaries for Benelux Algorithm Programming Contest 2019

A. Architecture

如果行最大值中的最大值和列最大值中的最大值不同的话，那么一定会产生矛盾，可以手模一个样例看看。

当满足行列最大值相同条件的时候，就可以判定了。

因为其余的地方一定可以构造出来符合条件的值，行列是很多的，填0就好了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main()

{

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

    int t1, t2;

    t1 = t2 = 0;

    for(int i = 1, x; i <= n; i++)

    {

        scanf("%d", &x);

        t1 = max(t1, x);

    }

    for(int i = 1, x; i <= m; i++)

    {

        scanf("%d", &x);

        t2 = max(t2, x);

    }

    if(t1 == t2) puts("possible");

    else puts("impossible");

    return 0;

}

B. Bracket Sequence

用栈模拟即可，注意要取模

const int N = 300000 + 5;

const int mod = 1e9 + 7;

ll st[N], top, cnt;

int n;

char op[20];

ll get(char *s){

    int len = strlen(s);

    ll x = 0;

    for(int i=0;i<len;i++) x = x * 10 + s[i] - '0';

    return x;

}

int main() {

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%s",op);

        if(op[0] == '(') {

            cnt ++;

            st[++top] = -1;

            continue;

        }

        else if(op[0] == ')'){

            if(st[top] == -1) {

                top --;

                continue;

            }

            ll x = st[top];

            while(top >= 2 && st[top-1] != -1){

                if(cnt % 2 == 0)x = (st[top-1] + x)%mod;

                else x = st[top-1] * x % mod;

                top--;

            }

            cnt --;

            top -= 2;

            st[++top] = x;

        }

        else{

            ll x = get(op);

            st[++top] = x;

        }

    }

    ll res = 0;

    while(top) res = (res + st[top--]) % mod;

    printf("%lld\n", res);

    return 0;

}

C. Canyon Crossing

二分一下最低高度，然后整个图变成了 n*m 个点，边权为0或1的图，第一排为起点，最后一排为终点，跑最短路即可，由于边权只有0和1，所以用双端队列维护即可

const int N = 1000 + 5;

#define mk make_pair

int n, m, k, a[N][N];

int d[N][N],c[N][N];

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

pair<int,int> q[2000010];

bool check(int mid){

    memset(d, 0x3f, sizeof d);

    int l = 1000005,r = 1000004;

    for(int j=1;j<=m;j++)q[++r] = mk(0,j), d[0][j] = 0;

    while(l<=r){

        auto t = q[l++];

        int x = t.first, y = t.second;

        for(int i=0;i<4;i++){

            int nx = x + dx[i], ny = y + dy[i];

            if(nx < 1 || nx > n || ny < 1 || ny > m)continue;

            if(a[nx][ny] >= mid){

                if(d[nx][ny] > d[x][y]){

                    d[nx][ny] = d[x][y];

                    q[--l] = mk(nx,ny);

                }

            }else{

                if(d[nx][ny] > d[x][y] + 1){

                    d[nx][ny] = d[x][y] + 1;

                    q[++r] = mk(nx,ny);

                }

            }

        }

    }

    for(int i=1;i<=m;i++)if(d[n][i] <= k) return true;

    return false;

}

int main() {

    scanf("%d%d%d",&n,&m,&k);

    int l = inf, r = 0;

    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            scanf("%d",&a[i][j]);

            l = min(l, a[i][j]);

            r = max(r, a[i][j]);

        }

    }

    while(l < r){

        int mid = l + r + 1 >> 1;

        if(check(mid))l = mid;

        else r = mid - 1;

    }

    printf("%d\n",l);

    return 0;

}

D. Deceptive Dice

\(ans\) 为 \(i-1\) 轮的期望，设 \(t = \lfloor ans \rfloor\) ，那么第 \(i\) 轮的期望是

\[\frac{t}{n} * ans + \frac{\sum_{t+1}^{n}i}{n}
\]

前面的表示有 \(t/n\) 的概率小于等于ans，那么第 i 次就不再掷色子。后面的就是取 [i+1, n] 的期望

const int N = 100 + 5;

int n, m;

double ans;

int get(int x){return x*(x+1) / 2;}

int main() {

    scanf("%d%d",&n,&m);

    ans = 1.0 * get(n) / n;

    for(int i=2;i<=m;i++){

        int t = ans;

        ans = 1.0 * t / n * ans + 1.0 * (get(n) - get(t)) / n;

    }

    printf("%.7f\n",ans);

    return 0;

}

E. Exits in Excess

这个题有个关键的性质在于无自环。

设两个集合\(S,T\)。

考虑一条边\(<x,y>\)，如果\(x<y\)，将这条边插入\(S\)；否则插入\(T\)。

输出边集大小较小的集合。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> t1, t2;

int n, m;

int main()

{

    cin >> n >> m;

    for(int i = 1, x, y; i <= m; i++)

    {

        scanf("%d%d", &x, &y);

        if(x < y) t1.push_back(i);

        else t2.push_back(i);

    }

    if(t1.size()>t2.size()) t1 = t2;

    cout << t1.size() << endl;

    for(auto x : t1)

        printf("%d\n", x);

    return 0;

}

F. Floor Plan

int n;

int main() {

    cin >> n;

    int flag = false;

    for(int i=2;i*i<=n;i++){

        if(n % i == 0){

            int res = n / i;

            if((res + i)%2 == 0){

                flag = true;

                int a = (res + i) / 2;

                int b = res - a;

                printf("%d %d\n",b, a);

                break;

            }

        }

    }

    if(!flag) puts("impossible");

    return 0;

}

G. Greetings!

const int N = 100000 + 5;

char s[N];

int main() {

    cin >> s;

    int n = strlen(s);

    printf("h");

    for(int i=0;i<2*(n-2);i++)printf("e");

    printf("y");

    return 0;

}

H. Hexagonal Rooks

从起点走两步走到终点，枚举中间的那个点，判断它与起点和终点是否可以一步达到即可，判断细节比较重要，把大于纵坐标大于 'f' 的对称往上翻即可，用几种case找找规律即可。

char x, x2;

int y, y2;

bool check(int x, int y, int x2, int y2){

    if(x == x2 && y == y2) return false;

    if(x == x2) return true;

    if(x > 6) y += x - 6;

    if(x2 > 6) y2 += x2 - 6;

    if(y == y2 || y - x == y2 - x2) return true;

    return false;

}

int main() {

    cin >> x >> y >> x2 >> y2;

    int res = 0;

    for(int i=1;i<=11;i++){

        int cnt = 11 - abs(6 - i);

        for(int j=1;j<=cnt;j++){

            if(check(i, j, x-'a'+1, y) && check(i, j, x2-'a'+1, y2)) res++;

        }

    }

    cout << res << endl;

    return 0;

}

I. Inquiry I

const int N = 1000000 + 5;

ll a[N], b[N], sa[N], sb[N];

int n;

int main() {

    scanf("%d",&n);

    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i] = a[i]*a[i];

    ll res = 0;

    for(int i=1;i<=n;i++) sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];

    for(int i=0;i<=n;i++){

        res = max(res, sb[i] * (sa[n] - sa[i]));

    }

    printf("%lld\n",res);

    return 0;

}

K. Knapsack Packing

首先排个序，最小的一定是0（空集产生的和），然后次小的就是集合中最小的数了。之后每次找到一个新的数字（即最终答案集合中的数字），都用它与之前所有组合出来的数字进行求和，将这些新的数字填入到一个集合中，再接下来的扫描过程中，如果发现有该集合的数字，则一定不是答案集合中的数字，将其从集合中删除即可。

const int N = 300000 + 5;

int n, m, a[N];

multiset<int> st, tmp;

map<int,int> mp;

vector<int> res;

int main() {

    scanf("%d",&n);

    m = 1 << n;

    for(int i=1;i<=m;i++)scanf("%d",&a[i]);

    sort(a+1,a+1+m);

    if(a[1] != 0){

        puts("impossible");

        return 0;

    }

    int cnt = 0;

    for(int i=2;i<=m;i++){

        if(mp[a[i]]){

            mp[a[i]] --;

            continue;

        }else{

            cnt ++;

            res.push_back(a[i]);

            for(auto x:st){

                tmp.insert(x + a[i]);

            }

            for(auto x : tmp) {

                st.insert(x);

                mp[x] ++;

            }

            st.insert(a[i]);

            tmp.clear();

        }

        if(cnt > n){

            puts("impossible");

            return 0;

        }

    }

    sort(res.begin(),res.end());

    for(auto x : res)printf("%d\n",x);

    return 0;

}

L. Lifeguards

将点按照坐标轴排序，找到中间的点，对于n的奇偶进行分别处理。

n 为奇数则构造一个几乎平行于y轴且通过中间点的直线，可以想到做这条直线的垂直平分线可以将所有点分成两半

n 为偶数则构造一个几乎平行于y轴且不通过中间点的直线，这样的直线的垂直平分线也同样会把所有点分成两半

const int N = 100000 + 5;

pair<ll,ll> a[N];

int n;

int main() {

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].first, &a[i].second);

    sort(a + 1, a + 1 + n);

    int mid = (n + 1) / 2;

    ll Len = 1000000000000ll;

    ll x = a[mid].first, y = a[mid].second;

    if(n & 1){

        printf("%lld %lld\n", x - Len, y-1);

        printf("%lld %lld\n", x + Len, y+1);

    }else{

        printf("%lld %lld\n", x - Len, y);

        printf("%lld %lld\n", x + Len, y+1);

    }

    return 0;

}

巴特西