2020-2021:teams:wangzai_milk:20200624比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/26 20:24] infinity37 [题解] |
2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/26 20:41] (当前版本) infinity37 [C. Consonant Fencity] |
||
|---|---|---|---|
| 行 59: | 行 59: | ||
| </hidden> | </hidden> | ||
| \\ | \\ | ||
| + | ==== B. Boolean Satisfiability ==== | ||
| + | === 题目大意 === | ||
| + | 给一个逻辑表达式，符号只有或，非，问其中的变量有多少种赋值方法可以使整个表达式为真。 | ||
| + | === 数据范围 === | ||
| + | 表达式长度$\leq 1000$ | ||
| + | === 题解 === | ||
| + | 我们知道，对于一个只有或的表达式，那么赋值方法应该为2的变量数目次方-1，另外，对于一个变量，如果只有变量本身或者只有变量取非那么效果是一样的，所以我们需要特殊判断的情况只有一个变量同时有其本身也有其取非的情况，我们知道这两者必有一个为真，那么这个时候我们的答案就是2的变量数目次方。 | ||
| + | === 代码 === | ||
| + | <hidden> | ||
| + | <code c++> | ||
| + | #include <stdio.h> | ||
| + | #include <string.h> | ||
| + | #include <stdlib.h> | ||
| + | #include <algorithm> | ||
| + | using namespace std; | ||
| + | char s[1005]; | ||
| + | int ts[300],fs[300]; | ||
| + | int main() | ||
| + | { | ||
| + | freopen("boolean.in","r",stdin); | ||
| + | freopen("boolean.out","w",stdout); | ||
| + | scanf("%s",s); | ||
| + | for (int i = 0;s[i];i++) | ||
| + | { | ||
| + | if (s[i]=='~') | ||
| + | { | ||
| + | fs[s[i+1]]++; | ||
| + | i++; | ||
| + | } | ||
| + | else if ((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) | ||
| + | ts[s[i]]++; | ||
| + | } | ||
| + | long long ans = 1; | ||
| + | int dec = 1; | ||
| + | for (int i = 'a';i <= 'z';i++) | ||
| + | { | ||
| + | if (ts[i] && fs[i]) dec = 0; | ||
| + | if (ts[i] || fs[i]) ans = ans << 1; | ||
| + | } | ||
| + | for (int i = 'A';i <= 'Z';i++) | ||
| + | { | ||
| + | if (ts[i] && fs[i]) dec = 0; | ||
| + | if (ts[i] || fs[i]) ans = ans << 1; | ||
| + | } | ||
| + | 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; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | \\ | ||
| ==== H. Hidden Supervisors ==== | ==== H. Hidden Supervisors ==== | ||
| 一个森林合并成一棵树，且求最大的匹配数，匹配是指取一个父亲和它的一个儿子。一个节点不能匹配多次。 | 一个森林合并成一棵树，且求最大的匹配数，匹配是指取一个父亲和它的一个儿子。一个节点不能匹配多次。 | ||
| 行 207: | 行 334: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | \\ | ||
| ===== replay ===== | ===== replay ===== | ||
2020-2021/teams/wangzai_milk/20200624比赛记录.1593174279.txt.gz · 最后更改: 2020/06/26 20:24 由 infinity37
