2020-2021:teams:wangzai_milk:20200624比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/26 20:28] infinity37 [A. Auxiliary Project] |
2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/26 20:41] (当前版本) infinity37 [C. Consonant Fencity] |
||
|---|---|---|---|
| 行 61: | 行 61: | ||
| ==== B. Boolean Satisfiability ==== | ==== B. Boolean Satisfiability ==== | ||
| === 题目大意 === | === 题目大意 === | ||
| + | 给一个逻辑表达式，符号只有或，非，问其中的变量有多少种赋值方法可以使整个表达式为真。 | ||
| === 数据范围 === | === 数据范围 === | ||
| + | 表达式长度$\leq 1000$ | ||
| === 题解 === | === 题解 === | ||
| + | 我们知道，对于一个只有或的表达式，那么赋值方法应该为2的变量数目次方-1，另外，对于一个变量，如果只有变量本身或者只有变量取非那么效果是一样的，所以我们需要特殊判断的情况只有一个变量同时有其本身也有其取非的情况，我们知道这两者必有一个为真，那么这个时候我们的答案就是2的变量数目次方。 | ||
| === 代码 === | === 代码 === | ||
| 行 104: | 行 105: | ||
| } | } | ||
| printf("%lld\n",ans-dec); | printf("%lld\n",ans-dec); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| + | ==== C. Consonant Fencity ==== | ||
| + | === 题目大意 === | ||
| + | 题目重新定义元音字母（bushi），现在有19个辅音字母个7个元音字母。定义一个字符串的幸福值，为相邻两个辅音字母的大小写不同的数目，现在给你一个全为小写字母的字符串，想通过把某些字母全部变为大写来达到最大的幸福值，问应该怎么修改才能幸福值最大。 | ||
| + | |||
| + | === 数据范围 === | ||
| + | 字符串长度$\leq 10^6$ | ||
| + | === 题解 === | ||
| + | 首先我们知道只有修改辅音字母的时候会对幸福值产生影响，而现在辅音字母只有19个，所以只需要二进制枚举每一个字母是否改为大写然后进行计算即可。 | ||
| + | |||
| + | === 代码 === | ||
| + | <hidden> | ||
| + | <code c++> | ||
| + | #include <stdio.h> | ||
| + | #include <string.h> | ||
| + | #include <stdlib.h> | ||
| + | #include <algorithm> | ||
| + | using namespace std; | ||
| + | const int N = 1e6+5; | ||
| + | int myno[300]; | ||
| + | int ps[25][25]; | ||
| + | char s[N]; | ||
| + | bool isbig[25]; | ||
| + | int main() | ||
| + | { | ||
| + | freopen("consonant.in","r",stdin); | ||
| + | freopen("consonant.out","w",stdout); | ||
| + | int cnt = 0; | ||
| + | for (int i = 'a';i <= 'z';i++) | ||
| + | { | ||
| + | if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u' || i == 'w' || i == 'y') | ||
| + | continue; | ||
| + | myno[i] = ++cnt; | ||
| + | } | ||
| + | scanf("%s",s); | ||
| + | for (int i = 1;s[i];i++) | ||
| + | if (myno[s[i]] && myno[s[i-1]]) { | ||
| + | if (s[i] > s[i-1])ps[myno[s[i-1]]][myno[s[i]]]++; | ||
| + | else ps[myno[s[i]]][myno[s[i-1]]]++; | ||
| + | } | ||
| + | int maxf = -1; | ||
| + | int ans = 0; | ||
| + | for (int i = 0;i < (1<<19);i++) { | ||
| + | for (int j = 0;j < 19;j++) | ||
| + | { | ||
| + | if ((i >> j) & 1) | ||
| + | isbig[j+1] = true; | ||
| + | else | ||
| + | isbig[j+1] = false; | ||
| + | } | ||
| + | int tmpf = 0; | ||
| + | for (int j = 1;j<= 19;j++) | ||
| + | for (int k = j+1;k<= 19;k++) | ||
| + | if (isbig[j]^isbig[k]) | ||
| + | tmpf += ps[j][k]; | ||
| + | if (tmpf > maxf) { | ||
| + | maxf = tmpf; | ||
| + | ans = i; | ||
| + | } | ||
| + | } | ||
| + | for (int j = 0;j < 19;j++) | ||
| + | { | ||
| + | if ((ans >> j) & 1) | ||
| + | isbig[j+1] = true; | ||
| + | else | ||
| + | isbig[j+1] = false; | ||
| + | } | ||
| + | for (int i = 0;s[i];i++) | ||
| + | { | ||
| + | if (isbig[myno[s[i]]]) | ||
| + | printf("%c",s[i]-'a'+'A'); | ||
| + | else printf("%c",s[i]); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| 行 256: | 行 334: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| ===== replay ===== | ===== replay ===== | ||
2020-2021/teams/wangzai_milk/20200624比赛记录.1593174504.txt.gz · 最后更改: 2020/06/26 20:28 由 infinity37
