2019牛客暑期多校训练营第六场

今天药忘吃喽~ 2021-11-02 13:38 386阅读 0赞

题目链接：[https://ac.nowcoder.com/acm/contest/886\#question][https_ac.nowcoder.com_acm_contest_886_question]

--------------------

A：

光速签到。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

B：

一开始认为可以直接找最长的最靠后的0串进行压缩，后来发现有个大坑：首尾和中间同样长度的0对答案贡献不一样大。在中间的连续0压缩后能少1长度。

可以直接枚举删去哪一段0再计算答案，保证正确。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /* basic header */
     2 #include <bits/stdc++.h>
     3 /* define */
     4 #define ll long long
     5 #define dou double
     6 #define pb emplace_back
     7 #define mp make_pair
     8 #define sot(a,b) sort(a+1,a+1+b)
     9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
    10 #define rep0(i,a,b) for(int i=a;i<b;++i)
    11 #define eps 1e-8
    12 #define int_inf 0x3f3f3f3f
    13 #define ll_inf 0x7f7f7f7f7f7f7f7f
    14 #define lson (curpos<<1)
    15 #define rson (curpos<<1|1)
    16 /* namespace */
    17 using namespace std;
    18 /* header end */
    19 
    20 const int maxn = 10;
    21 int a[maxn];
    22 
    23 int main() {
    24     int t; scanf("%d", &t);
    25     for (int caseNum = 1; caseNum <= t; caseNum++) {
    26         int startPos = 0, maxLen = 0, currLen = 0;
    27         for (int i = 1; i <= 8; i++) {
    28             a[i] = 0;
    29             for (int j = 1; j <= 16; j++) {
    30                 int x; scanf("%1d", &x);
    31                 a[i] = a[i] * 2 + x;
    32             }
    33             if (!a[i]) currLen++; // currLen记录当前连续的全0段个数
    34             else { // 如果遇到全1段，维护答案
    35                 if (currLen >= maxLen && currLen > 1) {
    36                     startPos = i - currLen;
    37                     maxLen = currLen;
    38                 }
    39                 currLen = 0;
    40             }
    41             if (i == 8 && currLen > 1) { // 如果全0段延续到末尾
    42                 if (currLen > maxLen) // 如果是最长，照常处理
    43                     startPos = i - currLen + 1, maxLen = currLen;
    44                 if (currLen == maxLen && startPos == 1) // 否则判断开头有长度跟最大长度相同的全0段
    45                     startPos = i - currLen + 1;
    46             }
    47         }
    48         printf("Case #%d: ", caseNum);
    49         if (startPos == 1) printf(":");
    50         for (int i = 1; i <= 8; i++) {
    51             if (i == startPos) {
    52                 printf(":"); i += maxLen;
    53             }
    54             if (i > 8) puts("");
    55             else printf("%x%c", a[i], ":\n"[i == 8]);
    56         }
    57     }
    58     return 0;
    59 }

D：

这道题很容易想到二分箱子容积，然后就错了。因为这个题箱子容积跟答案没有单调性！

为了保证正确性，这个题最好的方法就是枚举答案。答案下界显然是max(max(vi),sumV/k)，上界则为sumV/k+max(vi)，这样容积的箱子一定能放下所有东西。然后再逐个物品check一次就好了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

G：

一看就是蔡勒公式相关题。通过一些简单性质可以进行剪枝：日份第一位只能是0123，月份第一位只能是0和1，年份第一位不可能为0。而且合法日期+星期五的限制很紧，题解里谈到对于任何一个加密后的日期，只有几万个排列能将其映射到合法日期。故可只对前弱冠个日期求出所有合法的排列之后，再依次检查是否对所有日期合法。注意要对重复日期去重。

顺便这里补充一下**蔡勒公式**：

对于1752年9月3日前的日期，ans = (d+2\*m+3\*(m+1)/5+y+y/4+5) % 7；而对于1752年9月3日后的日期，ans = (d + 2\*m+3\*(m+1)/5+y+y/4-y/100+y/400)%7。这是因为罗马教皇决定在1582年10月4日后使用格利戈里历法，而英国则是在1752年9月3日后才接受使用格利戈里历法。要注意这个点。

计算出来的答案从0到6分别为星期日到星期六。使用时要注意，对于1月和2月的日期，要变为上一年的13月和14月参与计算。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /* basic header */
     2 #include <bits/stdc++.h>
     3 /* define */
     4 #define ll long long
     5 #define dou double
     6 #define pb emplace_back
     7 #define mp make_pair
     8 #define sot(a,b) sort(a+1,a+1+b)
     9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
    10 #define rep0(i,a,b) for(int i=a;i<b;++i)
    11 #define eps 1e-8
    12 #define int_inf 0x3f3f3f3f
    13 #define ll_inf 0x7f7f7f7f7f7f7f7f
    14 #define lson (curpos<<1)
    15 #define rson (curpos<<1|1)
    16 /* namespace */
    17 using namespace std;
    18 /* header end */
    19 
    20 int a[15], mon[15] = {
         0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    21 const int maxn = 1e5 + 10;
    22 string s[maxn];
    23 
    24 int check(int x) {
    25     int year = 0, month = a[s[x][5] - 'A'] * 10 + a[s[x][6] - 'A'], day = a[s[x][8] - 'A'] * 10 + a[s[x][9] - 'A'];
    26     for (int i = 0; i < 4; i++)
    27         year = year * 10 + a[s[x][i] - 'A'];
    28     if (year % 4 == 0 && year % 100 || year % 400 == 0) mon[2] = 29;
    29     else mon[2] = 28;
    30     if (year < 1600 || year > 9999 || month < 1 || month > 12 || day < 1 || day > mon[month])
    31         return 0;
    32     if (month <= 2) month += 12, year--;
    33     int ans = (day + 2 * month + 3 * (month + 1) / 5 + year + year / 4 - year / 100 + year / 400 + 1) % 7;
    34     if (ans == 5) return true;
    35     else return false;
    36 }
    37 
    38 int main() {
    39     int t; scanf("%d", &t);
    40     for (int caseNum = 1; caseNum <= t; caseNum++) {
    41         printf("Case #%d: ", caseNum);
    42         for (int i = 0; i < 10; i++) a[i] = i;
    43         int n; scanf("%d", &n);
    44         for (int i = 1; i <= n; i++) cin >> s[i];
    45         sot(s, n);
    46         n = unique(s + 1, s + 1 + n) - s - 1;
    47         int tmp = min(n, 20), flag = 1;
    48         do {
    49             int haveSolution = 1;
    50             for (int i = 1; haveSolution && i <= tmp; i++)
    51                 if (!check(i)) haveSolution = 0;
    52             if (haveSolution)
    53                 for (int i = tmp + 1; haveSolution && i <= n; i++)
    54                     if (!check(i)) haveSolution = 0;
    55             if (haveSolution) {
    56                 for (int i = 0; i < 10; i++) printf("%d", a[i]);
    57                 puts("");
    58                 flag = 0;
    59                 break;
    60             }
    61         } while (next_permutation(a, a + 10));
    62         if (flag) puts("Impossible");
    63     }
    64     return 0;
    65 }

J：

一个人有n个技能，每个技能最高可以升到m级。初始状态下n个技能的等级都是0级。第i个技能从(j-1)级升到j级要花费cij点代价(有可能是负数)。如果所有技能都达到了j级，就可以获得dj点代价(有可能是负数)。输出这个人能获得的最大代价是多少。

这个题很容易想到贪心，然后就踩坑了：枚举有j个等级升满，然后对第i种技能从pre\[i\]\[j\]到pre\[i\]\[m\]中选择最小的那个作为第i种等级的最终等级。pre\[i\]\[j\]表示第i种技能升j级所需代价和。这种做法的问题在于d\[j\]可能是负的，贪心选最小的pre可能导致j+1之后某些负的level使得答案变小。可以这样修正得到正解：枚举一种等级i作为level最低的技能，并枚举它的等级j，那么其他技能的等级可以在j到m之间任取。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /* basic header */
     2 #include <bits/stdc++.h>
     3 /* define */
     4 #define ll long long
     5 #define dou double
     6 #define pb emplace_back
     7 #define mp make_pair
     8 #define sot(a,b) sort(a+1,a+1+b)
     9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
    10 #define rep0(i,a,b) for(int i=a;i<b;++i)
    11 #define eps 1e-8
    12 #define int_inf 0x3f3f3f3f
    13 #define ll_inf 0x7f7f7f7f7f7f7f7f
    14 #define lson (curpos<<1)
    15 #define rson (curpos<<1|1)
    16 /* namespace */
    17 using namespace std;
    18 /* header end */
    19 
    20 const int maxn = 1e3 + 10;
    21 ll c[maxn][maxn], d[maxn], sum[maxn], val[maxn], tem[maxn];
    22 int n, m;
    23 
    24 int pos(ll *c, int l, int r) {
    25     ll val = ll_inf; int minI;
    26     for (int i = l; i <= r; i++)
    27         if (c[i] <= val) {
    28             val = c[i];
    29             minI = i;
    30         }
    31     return minI;
    32 }
    33 
    34 int main() {
    35     int t; scanf("%d", &t);
    36     for (int casenum = 1; casenum <= t; casenum++) {
    37         scanf("%d%d", &n, &m);
    38         for (int i = 1; i <= n; i++) sum[i] = 0;
    39         for (int i = 1; i <= n; i++) {
    40             c[i][0] = 0; val[i] = ll_inf;
    41             for (int j = 1; j <= m; j++) {
    42                 scanf("%lld", &c[i][j]);
    43                 sum[j] += c[i][j];
    44                 c[i][j] += c[i][j - 1];
    45                 if (c[i][j] <= val[i]) {
    46                     val[i] = c[i][j];
    47                     tem[i] = j;
    48                 }
    49             }
    50         }
    51         d[0] = 0;
    52         for (int i = 1; i <= m; i++) {
    53             scanf("%lld", &d[i]);
    54             d[i] -= sum[i]; d[i] += d[i - 1];
    55         }
    56         ll ans = 0, tmp, maxv;
    57         for (int i = 0; i <= m; i++) {
    58             tmp = d[i]; int cnt = 0;
    59             if (i != m) {
    60                 ll minv; maxv = -ll_inf;
    61                 for (int j = 1; j <= n; j++) {
    62                     if (tem[j] <= i) tem[j] = pos(c[j], i + 1, m);
    63                     minv = c[j][tem[j]];
    64                     if (minv - c[j][i] < 0) {
    65                         maxv = max(maxv, minv - c[j][i]);
    66                         tmp -= minv - c[j][i];
    67                         cnt++;
    68                     }
    69                 }
    70             }
    71             if (cnt == n) tmp += maxv;
    72             ans = max(ans, tmp);
    73         }
    74         printf("Case #%d: %lld\n", casenum, ans);
    75     }
    76     return 0;
    77 }

也可以这样做：显然升级过程没有后效性，考虑dp。设dp\[i\]\[j\]为前i种科技最小等级为j时，所付出的最小代价。

状态转移方程dp\[i+1\]\[j\]=min(dp\[i\]\[k\]+pre\[i+1\]\[u\])，其中k>=j，u>=j，且k和u至少有一个为j。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /* basic header */
     2 #include <bits/stdc++.h>
     3 /* define */
     4 #define ll long long
     5 #define dou double
     6 #define pb emplace_back
     7 #define mp make_pair
     8 #define sot(a,b) sort(a+1,a+1+b)
     9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
    10 #define rep0(i,a,b) for(int i=a;i<b;++i)
    11 #define eps 1e-8
    12 #define int_inf 0x3f3f3f3f
    13 #define ll_inf 0x7f7f7f7f7f7f7f7f
    14 #define lson (curpos<<1)
    15 #define rson (curpos<<1|1)
    16 /* namespace */
    17 using namespace std;
    18 /* header end */
    19 
    20 const int maxn = 2e3 + 10;
    21 ll a[maxn][maxn], sum[maxn], dp[maxn][maxn][20];
    22 int n, m;
    23 
    24 void init() {
    25     for (int i = 1; i <= n; i++)
    26         for (int j = 1; j <= m + 1; j++)
    27             dp[i][j][0] = a[i][j];
    28     for (int k = 1; k <= n; k++)
    29         for (int j = 1; (1 << j) <= m + 1; j++)
    30             for (int i = 1; i + (1 << j) - 1 <= m + 1; i++)
    31                 dp[i][k][j] = min(dp[i][k][j - 1], dp[i][k + (1 << j - 1)][j - 1]);
    32 }
    33 
    34 ll rmq(int j, int l, int r) {
    35     int k = log2(r - l + 1);
    36     return min(dp[j][l][k], dp[j][r - (1 << k) + 1][k]);
    37 }
    38 
    39 int main() {
    40     int t; scanf("%d", &t);
    41     for (int caseNum = 1; caseNum <= t; caseNum++) {
    42         scanf("%d%d", &n, &m);
    43         for (int i = 1; i <= n; i++)
    44             for (int j = 2; j <= m + 1; j++) {
    45                 scanf("%lld", &a[i][j]); // 同一技能升级代价做前缀和
    46                 a[i][j] += a[i][j - 1];
    47             }
    48         init();
    49         for (int i = 2; i <= m + 1; i++) {
    50             scanf("%lld", &sum[i]); // 技能最低等级奖励也做前缀和
    51             sum[i] += sum[i - 1];
    52         }
    53         ll ans = 0;
    54         for (int j = 1; j <= m + 1; j++) {
    55             ll tmp1 = 0;
    56             for (int i = 1; i <= n; i++) tmp1 += rmq(i, j, m + 1);
    57             for (int i = 1; i <= n; i++) {
    58                 ll tmp = tmp1;
    59                 tmp -= rmq(i, j, m + 1); tmp += a[i][j];
    60                 tmp = sum[j] - tmp; ans = max(ans, tmp);
    61             }
    62         }
    63         printf("Case #%d: %lld\n", caseNum, ans);
    64     }
    65     return 0;
    66 }

转载于:https://www.cnblogs.com/JHSeng/p/11296837.html

[https_ac.nowcoder.com_acm_contest_886_question]: https://ac.nowcoder.com/acm/contest/886#question
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/505d1177d0214e42a68fc2b4e9af0020.png