2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)

賽后補了幾道

賽中我就寫了兩個...

A - Altruistic AmphibiansGym - 101933A

看了眼榜沒幾個人做。就沒看。

最后發現就是一個DP（但是我覺得復雜度有點迷）

題意：$n$只青蛙有參數$l,w,h$分別表示彈跳力，體重，身高，在一口深為$d$的井里

一只青蛙不能承受比他重的重量，問最多有多少只能出去（達到高度嚴格大于d）

重的肯定比輕的晚出去，那么輕的肯定由重的來轉移，所以先排序，從重到輕的排

$dp_{i}$表示體重為i最高能疊多高瞎jb轉移一下就好了

#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}const int N = 1e5 + 10;
const int M = 1e8 + 10;
struct P {int l, w, h;bool operator < (const P &rhs) const {return w > rhs.w;}
} p[N];
int dp[M], n, d, ans;int main() {n = read(), d = read();for (int i = 1; i <= n; i++) p[i].l = read(), p[i].w = read(), p[i].h = read();ans = 0;sort(p + 1, p + n + 1);for (int i = 1; i <= n; i++) {if (dp[p[i].w] + p[i].l > d) ans++;for (int j = p[i].w + 1; j < min(p[i].w * 2, M); j++) {dp[j - p[i].w] = max(dp[j-p[i].w], dp[j] + p[i].h);} }printf("%d\n", ans);return 0;
}

View Code

B - Baby Bites Gym - 101933B

#include <cstdio>
#include <cstring>
using namespace std;const int N = 1010;
int a[N];
int n;
char s[N];int main() {scanf("%d", &n);bool ans = true;for (int i = 1; i <= n; i++) {scanf("%s", s);int len = strlen(s);if (s[0] == 'm') a[i] = i;else {int x = 0;for (int j = 0; j < len; j++) x = x * 10 + s[j] - '0';a[i] = x;if (x != i) {ans = false;}}}puts(ans?"makes sense":"something is fishy");return 0;
}

View Code

C - Code Cleanups Gym - 101933C

閱讀理解題啊。自己瞎糊了一發。讀不下去。就丟給隊友了。

不管了。

E - Explosion Exploit Gym - 101933E

題意：分別有$n,m$個士兵，每個士兵有一個血量，有d個攻擊，等概率分給每一個士兵。

問敵方士兵全死（m）的概率是多少

隊友過的。學習了新知識，概率記憶化+狀壓

用一個long long來表示狀態

unordered_map來存狀態對應的概率再回溯搜索即可 tql

#include <bits/stdc++.h>
#define ll long long
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}unordered_map<ll, double> mp;
int a[2][10];ll getsta() {ll ret = 0;for (int i = 1; i <= 6; i++) ret = ret * 10 + 1LL * a[1][i];for (int i = 1; i <= 6; i++) ret = ret * 10 + 1LL * a[0][i];return ret;
}double dfs(ll sta, int d) {if (mp.count(sta)) return mp[sta];if (sta < 1000000) return 1;if (d == 0) return 0;int sum = 0;for (int i = 0; i < 2; i++) for (int j = 1; j <= 6; j++)sum += a[i][j];double ret = 0;for (int i = 0; i < 2; i++) {for (int j = 1; j <= 6; j++) {if (!a[i][j]) continue;a[i][j]--;a[i][j-1]++;ll s = getsta();double res = dfs(s, d - 1);a[i][j]++;a[i][j-1]--;mp[s] = res;ret += a[i][j] * 1.0 / sum * res;}}return ret;
}int main() {int n = read(), m = read(), d = read();for (int i = 1, x; i <= n; i++) x = read(), a[0][x]++;for (int i = 1, x; i <= m; i++) x = read(), a[1][x]++;double res = dfs(getsta(), d);printf("%.8f\n", res);return 0;
}

View Code

H - House Lawn Gym - 101933H

題意：有m臺機器，每臺機器有名字，價格p，每分鐘能工作多少c，充一次電能工作多久t，充電需要多久r

有l面積的地待作，問平均每周能工作一次的機器中價格最小的那個，相同的按輸入順序輸出

隊友把10080說成10800能忍？

平均一下直接就把充電需要的時間給平均進來得到每分鐘工作多少的p'

再用$l/p'$和10080比就得出答案了

可能難就難在輸入部分吧。

#include <bits/stdc++.h>
using namespace std;struct Node
{string name;int p , c, t, r;double cc;
}b[105];
bool vis[105];int main()
{ios::sync_with_stdio(false);int m;int l;cin >> l >> m;string a;getline(cin,a);for(int i=1;i<=m;i++){getline(cin,a);int sta = 0;b[i].name = "";b[i].p = b[i].c = b[i].r = b[i].t = 0;for(int j=0;j<a.length();j++){if(a[j]==','){sta++;continue;}if(sta == 0){b[i].name+=a[j];}if(sta == 1){b[i].p*=10;b[i].p+=a[j]-'0';    }if(sta == 2){b[i].c*=10;b[i].c+=a[j]-'0';    }if(sta == 3){b[i].t*=10;b[i].t+=a[j]-'0';    }if(sta == 4){b[i].r*=10;b[i].r+=a[j]-'0';    }}}int ans = 1e9;for (int i = 1; i <= m; i++) {b[i].cc = (b[i].c * b[i].t) * 1.0 / (b[i].t + b[i].r);if (l / b[i].cc <= 10080) {ans = min(ans, b[i].p);vis[i] = 1;}}if (ans == (int)1e9) puts("no such mower");else {for (int i = 1; i <= m; i++) {if (vis[i] && ans == b[i].p) {cout << b[i].name << '\n';}}    }return 0;
}

View Code

J - Jumbled String Gym - 101933J

題意： 0 1串給你00出現的次數a 01出現的次數b 10出現的次數c 11出現的次數d

問能否構造出01串

WA了好幾發一度崩潰

首先由a d能推出0和1的個數必定是一個C(n, 2) 把a和d乘二開根和加一相乘是否等于2a和2d來判斷

第二部分

用兩個數組表示

$a_{i}$表示第i個0后面出現了幾個1

$b_{i}$表示第i個0前面出現了幾個1

必定有$a_{i} + b_{i} = cnt_{1}$??????? $a_{i}\geq a_{i+1}$??????? $b_{i}\leq b_{i+1}$

$\sum ^{cnt_{0}}_{i=1}a_{i} = b$??????????? $\sum ^{cnt_{0}}_{i=1}b_{i} = c$

所以$b + c = cnt_{0}\times cnt_{1}$才有解

隨便舉幾個例子發現貪心的構造均能滿足答案

如樣例 3 4 2 1

得到$cnt_{0} = 3$?? $cnt_{1} = 2$

$a_{i}$ : 2 2 0

$b_{i}$ : 0 0 2

得到 00110 也符合

所以直接構造就完了

不過要注意

0 0 0 0直接輸出0或1就可以了

a為0或d為0的情況如果$b + c = 0$ 那么對應的0的個數或1的個數為0 否則才為1

然后瞎jb輸出就完了

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;inline int read() {int x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }return x * f;
}int main() {int a = read(), b = read(), c = read(), d = read();int sqra = sqrt(2 * a), sqrd = sqrt(2 * d);bool ans = true;if ((a + b + c + d) == 0) {puts("0");return 0;}if (sqra * (sqra + 1) != a * 2 || sqrd * (sqrd + 1) != d * 2) {ans = false;} else {int cnt0 = sqra, cnt1 = sqrd;cnt0++, cnt1++;if (cnt1 == 1 && (b + c) == 0) cnt1 = 0;if (cnt0 == 1 && (b + c) == 0) cnt0 = 0;//printf("%d %d\n", cnt0, cnt1);if (b + c != cnt0 * cnt1) {ans = false;} else {if (cnt1 == 0) {while (cnt0--) putchar('0');return 0;}if (cnt0 == 0) {while (cnt1--) putchar('1');return 0;}int k = b / cnt1;for (int i = cnt0; i > cnt0 - k; i--) putchar('0');cnt0 -= k;k = b - k * cnt1;if (k) {k = cnt1 - k;for (int i = cnt1; i > cnt1 - k; i--) putchar('1');cnt1 -= k;putchar('0'), cnt0--;}    while (cnt1--) putchar('1');while (cnt0--) putchar('0');return 0;}}if (!ans) puts("impossible");return 0; 
}

View Code

K - King's Colors Gym - 101933K

題意：一棵樹n個節點，k種顏色，問有多少種方案用上k個顏色并且相鄰兩節點顏色不同

我以為要用樹形dp做，賽后看題解才明白是個容斥。

用k種的情況是$k\times \left( k-1\right) ^{n-1}$然后其中包含了只用了k-1種只用了k-2種...的情況

容斥一下就好了

#include <bits/stdc++.h>
#define ll long long
using namespace std;inline ll read() {ll x = 0, f = 1; char ch = getchar();while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f;
}const ll mod = 1e9 + 7;
const int N = 2550;
ll C[N][N];
void init() {for (int i = 0; i < N; i++) C[i][0] = 1, C[i][1] = i;for (int i = 1; i < N; i++)for (int j = 2; j <= i; j++)C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
}ll qm(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}int main() {init();ll n = read(), k = read();for (int i = 1; i < n; i++) read();ll ans = 0, flag = 1;for (int i = k; i >= 1; i--) {ll temp = flag * i * qm((ll)i - 1, n - 1) % mod * C[k][i];ans = (ans + temp + mod) % mod;flag = -flag;}        printf("%lld\n", ans);return 0;
}