JSCPC 2016 赛后笔记

发表于   |   分类于   |     |   阅读次数

今天参加了一场 JSCPC ，靠队友带飞了。为了今后可以不拖队友后腿，我决定写题解。

A

这是一道模拟题，翻译莫斯密码。
先是强行手打莫斯密码表（只含 ‘.’ 和 ‘-‘ ）
然后一个 ‘.’ 为一个 ‘=’ ；一个 ‘-‘ 转为 ‘===’；每两个符号间加一个 ‘.’；
然后每两个字母间加’…’；
每两个单词间加’…….’；
Over

//代码过于繁琐并且没什么价值不再手打。

B

n 个结点二叉树（ i 的子节点是 2i 和 2i+1 ）
求中序遍历的第 x 个值。（1 ≤ x ≤ n ≤ 10000）

由于 n 的范围不算大，所以强行中序就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>

bool flag = false;
int ans;

int n, x;

void deal(int r)
{
	if (2*r <= n) deal(2*r);
	if (flag) return;
	x--;
	if (x==0) {
		flag = true;
		ans = r;
		return;
	}
	if (2*r+1 <= n) deal(2*r+1);
	if (flag) return;
}

int main()
{
	int T;
	scanf("%d", &T);
	
	for (int id=1;id<=T;id++)
	{
		scanf("%d%d", &n, &x);
		flag = false;
		deal(1);
		printf("Case #%d: %d\n", id, ans);
	}
}

C

给 n （n ≤ 10）个格子涂色（颜色少于等于3种），如果考虑旋转对称可以涂多少种结果。（例如001和010和100算同一种）
由于数据量都不大（3^10 = 59049），所以考虑直接暴力。
扫一遍，如果这个数还没有被考虑过就轮换一圈做上标记，并结果数 +1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <cstring>

const int maxn = 60000;

int ans;
int n, k;
bool v[maxn];

void deal()
{
	memset(v,false,sizeof(v));
	ans=0;
	int nn=k; 
	for (int i=1;i<n;i++)
		nn *= k;
	for (int i=0;i<nn;i++)
	{
		if (!v[i]) {
			ans++;
			int ii=i;
			v[i] = true;
			for (int j=1;j<n;j++)
			{
				ii = (ii%k)*(nn/k)+ii/k;
				v[ii] = true;
			}
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	
	for (int id=1;id<=T;id++)
	{
		scanf("%d%d", &n, &k);
		deal();
		printf("Case #%d: %d\n", id, ans);
	}
}

D

将四维的 1×1×1×2 的方块放进 2×2×4×n 四维空间（可旋转），问有多少种放置的方法。
暂时还是不会 QAQ

E

在 2×n 的网格里每次随机放置一个矩阵，问覆盖全图所需次数的数学期望。
同上

F

有 n 个人，每个人初始有 a[i]（1≤i≤n） 的钱，相互间通过给钱来似的所有人钱一样多，然而每次给钱需要交倍率为 k 的税（交易额 × k ），问最终每人最多多少钱。
我们队使用的是二分。
答案 ans 应该满足 (1-k)*∑(a[i]-ans)(1≤i≤n && a[i]>ans) == ∑(ans-a[i])(1≤i≤n && ans>a[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>

const int maxn = 100100;

double ans,k;
int n;
int a[maxn];
bool flag;

double abs(double x)
{
	return x>0? x:-x;
}

void deal(double l, double r)
{
	double m = (l+r)/2;
	double s1=0;
	double s2=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i]>m) s1 += a[i] - m;
		else s2 += m - a[i];
	}
	s1 *= (1-k);
	if (abs(s1-s2) < 1e-7) {
		ans = m;
		flag = false;
	} 
	else if (s1 > s2)
		deal(m,r);
	else deal(l,m);
}

int main()
{
	int T;
	scanf("%d", &T);
	
	for (int id=1;id<=T;id++)
	{
		scanf("%d%lf", &n, &k);
		for (int i=1;i<=n;i++) 
		{
			scanf("%d",&a[i]);
		}
		flag = true;
		deal(1, 10000);
		printf("Case #%d: %lf\n", id, ans);
	}
}

G

猜数游戏。 B 想一个数（1 到 n），A 猜对了可以从 B 那里赢1刀，如果 A 猜了 x 而 B 想的是 x+1 则 A 要支付1刀给 B 。
B 使用随机数发生器，同时 B 能决定每个数字的分布。而 A 知道 B 的决定，所以 A 会挑选一个获利期望最大的选择。
B 现在要将 A 的获利最小化，问最小化的 A 的获利期望是多少。

问题模型简化为：
∑(P[i]) = 1, 求 max{ P[i]-P[i+1] , P[n] } (1 ≤ i < n) 的最小值。
记 a[i]=P[i]-P[i+1](1 ≤ i < n), a[n]=P[n]，则有 

1
2
a[1] + 2·a[2] + …… + (n-1)·a[n-1] + n·a[n] = 1,
求： max{a[i]} (1 ≤ i ≤ n) 的最小值.

显然取等号时有最小值，最小值为 2/(n·(n+1)).
所以输出2/(n·(n+1))即可。

H

给定 n 和 m ，求∑∑(i^2·j^2·gcd(i,j)) (1 ≤ i ≤ n, 1 ≤ j ≤ m).
要用到一个叫莫比乌斯函数的东西。暂时还没搞明白，搞清楚以后会在单独写一篇。

I

有两种公交线路，一种是每次2刀（A 类），一种是免费的（B 类）。给出所有线路和起点终点，求解出最小花费。
思路是将所有站点和线路相间建立无向图。若站点在线路上则连接站点和线路。若与 A 类线路连接，则边权为 1，若与 B 类线路连接则为 0.
然后一遍spfa过了。
代码再过两天补吧。

J

这题真的是有意思，人肉机器学习。
题意大概是给了一段西班牙语，一段中文拼音，然后将会给一段 100 - 500 词的文本（从报纸、杂志上摘取），判断这段文本是什么语言（英语 / 西班牙语 / 拼音）。

我们起初用一些 y、es 这样的单词来判断西班牙语；the、be 动词这些来判断英语，然而 WA 了。

队友后来开始统计词频，然而还是呵呵了。

最后的处理方式是：先查英文，出现特征词直接认定为 English；
接下来统计字长，出现长度大于6的单词认定不是中文拼音（拼音最长为6个字母）；
然后很诡异的作了一步判断首字母是不是元音字母的单词比例，大于 0.8 则断定为中文拼音（也不知道是不是这个操作起了效果我觉得不是然而队友这么写了并且过了那现在就无从得知了）；
接下来再用西班牙语特征词判断西班牙语；
还判断不出来就返回英文。
具体代码不写了，没什么意思。

其实现在想想这个逻辑还是有问题的。但是不管怎么说，过了、拿到分了就行。