Nebius Welcome Round (Div. 1 + Div. 2)

2023-03-13 14:05:38 来源：博客园

(资料图)

Nebius Welcome Round (Div. 1 + Div. 2)

A Lame King

Solution:

比较water，直接放代码了。

void solve(){int a, b;cin >> a >> b;a = abs(a);b = abs(b);int ans = abs(a) + abs(b);ans += max(ll(0),(max(a, b) - min(a , b) - 1));cout << ans << endl;}

B Vaccination

Solution:

一个比较显然的贪心策略，这种区间题一般都会这么考虑，把每个点能到的最右的边界算出来，即\(t_{i} + d + w\)考虑之后的点在这个边界前能放多少个，能放尽量放。重复此操作即可。

void solve(){int n , k, d, w;cin >> n >> k >> d >> w;vector t(n + 1);for (int i = 1;i <= n;i ++) cin >> t[i];int ans = 1;int r = t[1] + w + d;int cnt = 1;for (int i = 2;i <= n;i ++) {if(t[i] <= r && cnt < k) {// cout << i << endl;cnt++;continue;}else {cnt = 1;r = t[i] + w + d;// cout << r << endl;ans++;}}cout << ans << endl;}

C Pull Your Luck

Solution:

可以想想这个点是在一个数轴上跳跃，不难发现，\(n\)的范围是\(1e5\)，并且，考虑一个点，跳\(n\)步和跳\(2 n\)步的效果是一样，循环节为\(2n\)，问题就解决了。

void solve(){int n, x, p;cin >> n >> x >> p;for (int i = 1;i <= min(n * 2, p);i ++){x = (x + i) % n;if(x == 0) {cout << "Yes" << endl;return ;}}cout << "No" << endl;}

D Accommodation

Solution:

其实真的挺一眼的，以为他太难所以在想\(DP\)之类的方法，其实就是很简单的贪心

先考虑最小，我们希望每个\(1\)做的贡献尽量少，所以我们需要让两个连着的\(1\)尽量用\(\frac{m}{4}\)的房间去填充，这样原本两个\(1\)对答案的贡献是\(2\)，现在变成\(1\)了，所以有

\[ans_{min} = ans_{min} + cnt_{total} - cnt_{two}\]

\(cnt_{total}\)是\(1\)的总数\(cnt_{two}\)是双\(1\)的个数

再考虑最大，我们希望每个\(1\)做的贡献尽量多，所以我们要尽可能地让\(\frac{m}{2}\)地方去填充\(1\)，但这样不是特别好考虑，所以我们可以反着来思考，即考虑每个\(01,10,00\)用\(\frac{m}{4}\)去填充，记\(cnt_{two"}\)为除了\(11\)外地个数，如果有框住\(01,10,00\)，\(1\)的贡献不变，否则会有一对\(11\)的贡献为1，所以有:

\[ans_{max} = ans_{max} + cnt_{total} - (\frac{m}{4} - min\left\{\frac{m}{4},cnt_{two"}\right\})\]

void solve(){int n , m;cin >> n >> m;vector s(n + 10);for (int i = 1;i <= n;i ++) cin >> s[i];for (int i = 1;i <= n;i ++) s[i] = " " + s[i],s[i] += " ";int ans1 = 0;int ans2 = 0;for (int i = 1;i <= n;i ++) {int cnt = count(s[i].begin(),s[i].end(),"1");int cnt1 = 0;int cnt2 = 0;for (int j = 1;j <= m - 1;j ++) {if(s[i][j] == "1" && s[i][j + 1] == "1") {j ++;cnt1 ++;}}for (int j = 1;j <= m - 1;j ++) {if(s[i][j] != "1" || s[i][j + 1] != "1") {j ++;cnt2++;}}ans1 += cnt - min(m / 4,cnt1);ans2 += cnt - (m / 4 - min(m / 4,cnt2));}cout << ans1 << " " <<  ans2 << endl;}

关键词：