20200328题解
T1 纯模拟，额外维护每个工件最后的建造时间即可。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == '-') ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 21, MAXT = MAXN*MAXN*MAXN; int num[MAXN*MAXN], bel[MAXN][MAXN], cost[MAXN][MAXN], last[MAXN], isWork[MAXN][MAXT], cnt[MAXN]; int main(){ int m = read(), n = read(); for(int i=1; i<=m*n; i++) num[i] = read(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) bel[i][j] = read(); for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cost[i][j] = read(); for(int i=1; i<=n*m; i++){ cnt[num[i]]++; for(int t=last[num[i]]+1, sum=0; t<=MAXT; t++){ if(!isWork[bel[num[i]][cnt[num[i]]]][t]) sum++; else sum = 0; if(sum == cost[num[i]][cnt[num[i]]]){ for(int j=t-sum+1; j<=t; j++) isWork[bel[num[i]][cnt[num[i]]]][j] = true; last[num[i]] = t; break; } } } int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, last[i]); printf("%d", ans); return 0; }
T2 答案可以在$O(n^2)$的时间内解决，其中一维枚举r的位长$len$，另一维枚举r的最高位的数字$lim$（这样就轻松解决了它给我们的限制）
设一位的最大值为$size$，最后答案相当于将$size$个数中大于$lim$的数中选出$len-1$个数按照升序进行排列，即$C_{size-lim}^{len-1}$，最后注意高精度即可。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; inline long long read(){ long long ans = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) f *= (ch == '-') ? -1 : 1, ch = getchar(); do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar(); while(isdigit(ch)); return ans * f; } const int MAXN = 600; const int BITLEN = 10000, BIGSIZE = 53; struct Big{ int val[BIGSIZE], len; void operator = (int x){ memset(val, 0, sizeof(val)); len = 1, val[1] = x; } Big(int x = 0){this->operator = (x);} Big operator + (Big x){ Big ans; ans.len = max(len, x.len) + 1; ans.len = max(ans.len, BIGSIZE - 2); for(int i=1; i<=ans.len; i++){ ans.val[i] += val[i] + x.val[i]; ans.val[i + 1] += ans.val[i] / BITLEN; ans.val[i] %= BITLEN; } while(ans.len > 1 && ans.val[ans.len] == 0) ans.len--; return ans; } void print(){ for(int i=len; i>=1; i--){ if(i != len) for(int j=BITLEN/10; j>1; j/=10) if(val[i] < j) putchar('0'); printf("%d", val[i]); } } }; Big C[MAXN][MAXN]; int main(){ int q = read(), w = read(); int n = w / q, lim = (1 << (w % q)) - 1, size = (1 << q) - 1; if(lim) n++; else lim = size; Big ans = 0; for(int i=0; i<=size+1; i++) for(int j=0; j<=i; j++) C[i][j] = (j == 0 || i == j) ? 1 : C[i-1][j-1] + C[i-1][j]; for(int len=2; len<=n; len++){ int temp = (len == n) ? lim : size; for(int i=1; i<=temp && size-i>=len-1; i++) ans = ans + C[size-i][len-1]; } ans.print(); return 0; }