CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/25 21:20]
wzx27
+++ 2020-2021:teams:wangzai_milk:20200624比赛记录 [2020/06/26 20:41] (当前版本)
infinity37 [C. Consonant Fencity]
@@ 行 16: / 行 16: @@
 ===== 题解 =====
-=== A. Auxiliary Project ===
+==== A. Auxiliary Project ====
 恰好用点亮 $n$ 根数码管能构成的数字的和最大是多少。
-$\text{dp]$一下就可以了。
+$\text{dp}$ 一下就可以了。
 <hidden>
@@ 行 59: / 行 59: @@
 </hidden>
 \\
+==== B. Boolean Satisfiability ====
+=== 题目大意 ===
+给一个逻辑表达式，符号只有或，非，问其中的变量有多少种赋值方法可以使整个表达式为真。
+=== 数据范围 ===
+表达式长度$\leq 1000$
+=== 题解 ===
+我们知道，对于一个只有或的表达式，那么赋值方法应该为2的变量数目次方-1，另外，对于一个变量，如果只有变量本身或者只有变量取非那么效果是一样的，所以我们需要特殊判断的情况只有一个变量同时有其本身也有其取非的情况，我们知道这两者必有一个为真，那么这个时候我们的答案就是2的变量数目次方。
-=== H. Hidden Supervisors ===
+=== 代码 ===
+<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 ====
 一个森林合并成一棵树，且求最大的匹配数，匹配是指取一个父亲和它的一个儿子。一个节点不能匹配多次。
@@ 行 154: / 行 281: @@
 </code>
 </hidden>
+\\
+==== I. Intelligence in Perpendicularia ====
+=== 题目大意 ===
+在坐标系里放一圈平行于x轴或y轴的栅栏，人分别站在$(0,inf)$,$(0,-inf)$,$inf,0$,$-inf,0$四个位置看栅栏，问有多长的栅栏不论站在这四个位置哪里都没法看到。
+=== 数据范围 ===
+n节栅栏，$1\leq n\leq 1000$
+栅栏坐标$-10^6 \leq x_i,y_i \leq 10^6$
+=== 题解 ===
+由于栅栏只有平行于x轴和y轴的，而且栅栏围成了一个封闭图形，所以必有一种平移方案把栅栏移动成一个矩形和剩余的一些栅栏，易知人能看到的就是这个矩形的长度，所以剩余的就是看不到的栅栏。我们只需要计算总的栅栏长度和这个矩形的周长接口。
+=== 代码 ===
+<hidden>
+<code c++>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <algorithm>
+using namespace std;
+typedef long long ll;
+const int N = 1005;
+int x[N],y[N];
+int main()
+{
+	freopen("intel.in","r",stdin);
+	freopen("intel.out","w",stdout);
+	int n;
+	scanf("%d",&n);
+	int maxx = -1e7;
+	int maxy = -1e7;
+	int minx = 1e7;
+	int miny = 1e7;
+	for (int i = 1;i<= n;i++)
+	{
+		scanf("%d%d",&x[i],&y[i]);
+		maxx = max(maxx,x[i]);
+		minx = min(minx,x[i]);
+		maxy = max(maxy,y[i]);
+		miny = min(miny,y[i]);
+	}
+	int ans = 0;
+	x[n+1] = x[1],y[n+1] = y[1];
+	for (int i = 1;i <= n;i++)
+		ans += (abs(x[i]-x[i+1])+abs(y[i]-y[i+1]));
+	ans -= (maxx-minx + maxy-miny)*2;
+	if (maxx == minx || maxy == miny) ans = 0;
+	printf("%d\n",ans);
+	return 0;
+}
+</code>
+</hidden>
+\\
 ===== replay =====

CVBB ACM Team

用户工具

站点工具

页面工具