组队排位赛11 NWERC 2018

2018-2019 ICPC Northwestern European Regional Programming Contest (NWERC 2018)

题解 (opens new window)

Gym 102483C 几何

我的题解

Gym 102483H 细节

明明巨简单的题，训练的时候做了超久（而且还没做出来），心态锻炼得还不够好。

假设开头为$0$，可以发现如果当前位为$0$，那么一定经历了偶数次变换。

将上述规律拓展，又因为结尾一定是$0$，因而如果$c$为奇数，那么第一位一定是$1$，否则第一位一定是$0$。

#include <bits/stdc++.h>
using namespace std;
char ans[500010] = {0};
int n, c, b;

int main(){
    cin >> n >> c >> b;
    for(int i=0, z; i<b; i++){
        cin >> z;
        ans[z] = '0';
    }
    ans[1] = (c&1)?'1':'0';
    for(int i=2; i<=n; i++){
        if(ans[i] == 0){
            ans[i] = c?(ans[i-1] ^ 1):ans[i-1];
        }
        if(ans[i] != ans[i-1]) c--;
    }
    cout << ans + 1 << endl;
}

Gym 102483G 细节

其实不难，就是debug比较烦。静下来想一想就能1A，但是一急躁肯定就过不了。

题解给了三种做法，下面代码属于第二种

关键点在于：

1. 如果玩家转弯了，那么就让他再也无法碰到之前的砖块。这样一来我们就不用去查询当前方向是否有砖块阻隔，进而免去了用二位数组储存地图的麻烦。（当然，也可以判断一下接下来是否为"LRLR"重复的情况，如果是的话直接跳过）
2. 输出"impossible"只有两种情况
   1. 以"LRL"、"RLR"、"UDU"、"DUD"结尾
   2. 两个相邻的指令重复，如"LL"、"RR"。

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

const int maxn = 60, inf = 0x3f3f3f3f;
char buffer[maxn], pattern[][4] = {"LRL", "RLR", "UDU", "DUD"};
int len;
int delta_x[] = {-1, 1, 0, 0};
int delta_y[] = {0, 0, 1, -1};
map<char, int> id = { {'L', 0}, {'R', 1}, {'U', 2}, {'D', 3} };

signed main(){
    cin >> buffer;
    len = strlen(buffer);
    bool fail = false;
    for(int i=1; i<len; i++) if(buffer[i] == buffer[i-1]) fail = true;
    if(len >= 3){
        for(int i=0; i<4; i++){
            bool check = true;
            for(int j=len-3, p=0; j<len; j++) if(buffer[j] != pattern[i][p++]) check = false;
            if(check) fail = true;
        }
    }
    if(fail){ // 排除掉不能的情况
        cout << "impossible\n";
        return 0;
    }
    pii prev_pos = {inf, inf}, cur_pos = {0, 0};
    vector<pii> blocks;
    int step_abs = 1;
    for(int i=0; i<len; i++){
        if(i >= 2 && (id[buffer[i-1]]^1) == id[buffer[i]] && id[buffer[i-2]] == id[buffer[i]]){ // 判断"LRLR"这一类情况
            swap(cur_pos, prev_pos);
        }else{
            int op = id[buffer[i]];
            int nx = cur_pos.first + step_abs * delta_x[op];
            int ny = cur_pos.second + step_abs * delta_y[op];
            swap(cur_pos, prev_pos);
            cur_pos = {nx, ny};
            blocks.push_back({nx + delta_x[op], ny + delta_y[op]});
            step_abs *= 2; // 这里直接*2，由于n<=20，因此不会超过1e9
        }
    }
    int dx = cur_pos.first, dy = cur_pos.second;
    cout << -dx << " " << -dy << '\n' << blocks.size() << '\n';
    for(pii block: blocks){
        cout << block.first - dx << " " << block.second - dy << "\n";
    }
}

---

介绍一下另外两种做法

1. 每个格子有$5\%$的几率为墙，然后跑一遍，如果能跑通并且到达一个从未访问过的点则输出，否则就重新随机

2. 设定一个大小为$x=2$的方格，并在方格两端都添加方块。每次转向时，$x$增大并在两端添加方块

   例如：现在$x=2$，玩家在$(1,0)$，上一个命令是$L/R$而当前命令是$U/D$，那么$x$增大变为$3$，并且在$(1,3),(1,-3)$放置方格。

Gym 102483J 观察 贪心

通过观察可以得知，记除Julia外最高分的人人数为$x$，最坏的情况下，$x$个人中有$\lceil x/2\rceil$个人选了同一个队伍。模拟一下可以发现，在$1+\lfloor log_2x\rfloor$个回合后，这$x$个人每人都 正好 加了$\lfloor log_2x\rfloor$分（换句话说，循环节长度为$1+\lfloor log_2x\rfloor$），而其他人（除了Julia）都加了$1+\lfloor log_2x\rfloor$分。

通过上述操作，高分的人总会慢慢地被低分的人追上，我们只需要处理好合并即可。

当Julia不再领先时，输出答案即可。

---

AC代码:

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 1e5 + 1000;

ll tmp[maxn], diff[maxn];
ll score[maxn], cnt[maxn], scnt = -1;

void solve(){
    int n; cin >> n;
    for(int i=0; i<n; i++) cin >> tmp[i];
    sort(tmp, tmp + n, greater<ll>());
    ll julia = tmp[0];
    tmp[0] = -1;
    int cur_cnt = 1;
    for(int i=1; i<n; i++){
        if(tmp[i] != tmp[i-1]){
            score[++scnt] = tmp[i];
            cur_cnt = 1;
        }else{
            cur_cnt++;
        }
        cnt[scnt] = cur_cnt;
    }
    for(int i=1; i<=scnt; i++) diff[i] = score[i-1] - score[i];
    
    ll ans = 0;
    for(int i=1; i<=scnt; i++){
        ll delta = floor(log2(cnt[0]));
        if(diff[i] * delta > julia - score[0]) break;
        ans += diff[i] * (delta + 1);
        score[0] += diff[i] * delta;
        cnt[0] += cnt[i];
    }
    ll delta = floor(log2(cnt[0])), dif = julia - score[0], t = dif / delta;
    ans += t * (delta + 1);
    dif -= t * delta;
    ans += dif;
    cout << ans << '\n';
}

signed main(){
    Android;
    solve();
}

Gym 102483A 求导取最值

记$i$对应的接入点为$a_i$，所求的点为$p_i$

首先观察到，代价函数$cost(a_i,p_i)=(p_{ix}-a_{ix})^2+(p_{iy}-a_{iy})$

显然横纵坐标互不影响，因而可以转化为1维的问题，对应的代价函数$cost_{1D}(a_i,p_i)=(p_i-a_i)^2$

仅对于某一个点，最优的方案是使得$p_i$与$a_i$重合，但又因为要满足题设，因而要稍加限制。

进一步观察可以发现，如果一个点集相互影响，那么他们的坐标相等，举个例子，对于$a=\{2,1\}$，$p_0,p_1$的最优位置分别为$2,1$，又因为必须满足$p_0\le p_1$，所以这两个点相互影响，他们的坐标相等。

问题转化为：对于一个点集，如何计算他们的最优坐标。

只需对代价函数求导，得到$cost'_{1D}(x,\{a_1,a_2,...\})=2kx-2\sum\limits_{i=0}\limits^{k} a_i$，其中$k$为点集的大小

倒数为0的点即为最优点

在遍历$a_i$时，只需不断合并会相互影响的点集即可。

---

AC代码:

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define sqr(x) ((x)*(x))

using namespace std;

const int maxn = 1e5 + 1000;

int pos[2][maxn], n;

struct block{ // 维护点集的参数
    ll sum_a, cnt_a, sum_sqr;
    double x; // 最优点

    void merge(const block & other){
        sum_a += other.sum_a;
        cnt_a += other.cnt_a;
        sum_sqr += other.sum_sqr;
        x = 1.0 * sum_a / cnt_a;
    }
};

double calc(int arr[]){
    vector<block> blocks;
    block tmp;
    for(int i=0; i<n; i++){
        tmp = {arr[i], 1, sqr(1ll * arr[i]), (double)arr[i]};
        while(!blocks.empty() && blocks.back().x >= tmp.x){
            block back = blocks.back();
            blocks.pop_back();
            tmp.merge(back);
        }
        blocks.push_back(tmp);
    }
    double ans = 0;
    for(block & b:blocks){
        ans += sqr(b.x) * b.cnt_a - 2.0 * b.x * b.sum_a + b.sum_sqr;
    }
    return ans;
}

signed main(){
    Android;
    cin >> n;
    for(int i=0; i<n; i++) cin >> pos[0][i] >> pos[1][i];
    double ans = calc(pos[0]) + calc(pos[1]);
    cout << fixed << setprecision(10) << ans << '\n';
}

Gym 102483E 模拟 *

一道挺恶心的题目

Gym 102483F 最小树形图（朱刘算法）*

Gym 102483D *