Face++ 办的比赛,题目非常有意思。
最后一天做出门票题,进了决赛。

Sudoku

问9*9的数独有多少种排列方案使对角线不含1
数独一共的排列方案有 6670903752021072936960 种
这个结论来自Frazer Jarvis的研究成果

有了这个结论,我们可以通过枚举数独的对称性来概率统计。
我们知道数独前三列(行),中间三列(行),最后三列(行) 中的三列(行) 任意交换数独依然成立
这个变换一共有(3!)6(3!)^6种,与每种变换等价的数独数目一致,所以我们来枚举这些变换,再统计对角线含1的情况,我们可以算出的概率。
最后的答案即为 cnt对角线含1(3!)6\frac{cnt_{\text{对角线含1}}}{(3!)^6}

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<n;++i)
const int sz = 9;
const int P[6][3] = { {0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0} };

int pic[sz][sz];
int ans,cnt;

int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}

void input()
{
rep(i,sz) rep(j,sz) scanf("%d",&pic[i][j]);

rep(i,sz)
{
int sum = 0;
rep(j,sz) sum += pic[i][j];
assert(sum == 45);
}

rep(j,sz)
{
int sum = 0;
rep(i,sz) sum += pic[i][j];
assert(sum == 45);
}
}

void output()
{
rep(i,sz)
{
rep(j,sz) printf("%d ",pic[i][j]);
puts("");
}
puts("-*-*-*-*-*-*-*-*-*-*-*-*-*");
}

bool check()
{
rep(i,sz)
{
if(pic[i][i] == 1 || pic[i][sz - 1 - i] == 1 ) return true;
if(pic[i][i] == 2 || pic[i][sz - 1 - i] == 2 ) return true;
}
return false;
}

void SWAP(int a,int b)
{
for(int i=0;i<sz;++i) swap(pic[i][a],pic[i][b]);
}

void make(int num,int p)
{
switch(p)
{
case 0:break;
case 1:swap(pic[num*3+1],pic[num*3+2]);break;
case 2:swap(pic[num*3],pic[num*3+1]);break;
case 3:swap(pic[num*3],pic[num*3+1]);swap(pic[num*3+1],pic[num*3+2]);break;
case 4:swap(pic[num*3],pic[num*3+1]);swap(pic[num*3],pic[num*3+2]);break;
case 5:swap(pic[num*3],pic[num*3+2]);break;
}
}

void MAKE(int num,int p)
{
switch(p)
{
case 0:break;
case 1:SWAP(num*3+1,num*3+2);break;
case 2:SWAP(num*3,num*3+1);break;
case 3:SWAP(num*3,num*3+1);SWAP(num*3+1,num*3+2);break;
case 4:SWAP(num*3,num*3+1);SWAP(num*3,num*3+2);break;
case 5:SWAP(num*3,num*3+2);break;
}
}

void solve()
{
input();

cnt = 0;
ans = 0;
int tmp[sz][sz],tmp1[sz][sz],tmp2[sz][sz],tmp3[sz][sz],tmp4[sz][sz],tmp5[sz][sz];
memcpy(tmp,pic,sizeof pic);

rep(a,6)
{
memcpy(pic,tmp,sizeof pic);
make(0,a);
memcpy(tmp1,pic,sizeof pic);

rep(b,6)
{
memcpy(pic,tmp1,sizeof pic);
make(1,b);
memcpy(tmp2,pic,sizeof pic);
rep(c,6)
{
memcpy(pic,tmp2,sizeof pic);
make(2,c);
memcpy(tmp3,pic,sizeof pic);

rep(i,6)
{
memcpy(pic,tmp3,sizeof pic);
MAKE(0,i);
memcpy(tmp4,pic,sizeof pic);

rep(j,6)
{
memcpy(pic,tmp4,sizeof pic);
MAKE(1,j);
memcpy(tmp5,pic,sizeof pic);

rep(k,6)
{
memcpy(pic,tmp5,sizeof pic);
MAKE(2,k);
++cnt;
if(!check())
{
++ans;
}
}
}
}
}
}
}
int t = gcd(ans,cnt);
printf("%d/%d\n",ans/t,cnt/t);
// ans/cnt * 6670903752021072936960 --- by python
}

int main()
{
freopen("test.txt","r",stdin);
rep(i,3) solve();
return 0;
}
/* 即海报那个数独,其实任意数独均可
2 1 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
1 2 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 2 6 4 1 9 7 8
6 4 8 9 7 2 5 3 1
9 7 1 5 3 8 6 4 2
*/

MegCup

就是简单的模拟,数据水到手算都比写程序简单

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;

const int maxn = 110;
const int INF = 0x3f3f3f3f;
map<string,int> id;

double mo;

void init()
{
mo = 0;
for(int i=1;i<=16;++i)
{
mo += pow((double)i,-1.2);
}
// printf("%lf\n",(88888 - 4000)*1/mo);
}

struct P
{
string name;
bool vis[maxn];
int t,num,t1;

P()
{
memset(vis,0,sizeof vis);
t1 = t = INF;
num = 0;
}

bool operator<(const P& rhs) const
{
return num > rhs.num || (num == rhs.num && t1 < rhs.t1);
}
} p[maxn];

vector<pair<string,double> > ans;

int main()
{
//freopen("test.txt","r",stdin);
freopen("megcup.in","r",stdin);
freopen("out.txt","w",stdout);
init();
int cnt = 0;
id.clear();
int t;
char ch ;
string name,st;
while(cin>>t>>ch>>st>>name)
{
if(id[name])
{
if(st != "WA")
{
p[id[name]].t1 = t;
if(p[id[name]].vis[ch - 'A']) continue;
p[id[name]].vis[ch - 'A'] = 1;
++p[id[name]].num;
if(p[id[name]].num<=5) p[id[name]].t = t;
}
}
else
{
id[name] = ++cnt;
p[id[name]].name = name;
if(st != "WA")
{
p[id[name]].vis[ch - 'A'] = 1;
++p[id[name]].num;
p[id[name]].t = t;
p[id[name]].t1 = t;
}
}
}
// printf("%d\n",cnt);
sort(p+1,p+cnt+1);
ans.clear();
for(int i = 1; i <= cnt ; ++ i)
{
// cout<<p[i].name<<" "<<p[i].num<<'\n';
if(p[i].num >= 5)
ans.push_back(make_pair(p[i].name,(double)(88888 - p[i].t)*pow(i,-1.2)/mo));
else
ans.push_back(make_pair(p[i].name,(double)(88888 - 55000)*pow(i,-1.2)/mo));
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i) printf("%.2lf\t%s\n",ans[i].second,ans[i].first.c_str());
return 0;
}

Decryption

给出两组密码,以英文字母的全排列作为密钥,要求在180s内解密
竟然有在线解密的工具quipqiup
而且不用clue(即指定类似于 abc=ijk) 的情况下都能10s内得到结果…
用到的算法看这里

Gem

很有意思的一道题目,和服务器交互玩游戏,需要curl或者postman等工具,或者自己写脚本
游戏很简单:

  1. Youmu 会创造一个游戏盘,游戏盘上有 8 个不超过 31 的非负整数。
  2. 接下来由您来选择先手或者后手,然后游戏开始。
  3. 每回合,当前的游戏者选择游戏盘上的一个非 0 的整数 a,再选择一个 2 到 32 之间的的正整数 t,然后把游戏盘上的 a 替换为 floor(a / t)。
  4. 如果某方无法操作,则他输掉游戏。

可以搜索出必胜策略

然后就是交互了,我好不容易学会了postman可是玩了一局就被虐了然后比赛就结束了QAQ
唉~以后一定要好好学习脚本的各种姿势…

Language

实现一个C语言函数,要求判断给定的200组数据是否是英文,限制140个字符以内
由于数据已经给定,我们按照出现的词的频率过滤。

下面是用python统计出现词频率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
f = open ('yes.txt')
dic = {}

for line in f:
cnt = 0
words = line.split()
for word in words:
if word in dic:
dic[word] += 1
else:
dic[word] = 1

lst = []

for word,freq in dic.items():
lst.append((freq,word))

lst.sort(reverse = True)

for freq,word in lst[:15]:
print word,freq

下面是统计结果(前15个),与英语中的词频率较为一致,注意还剩几组时要局部统计一次。

the 90
of 85
to 53
and 49
a 42
in 29
is 20
that 19
our 18
for 16
or 15
which 14
we 14
on 13
have 13

然后取几组,对于引起误判的,加空格,或者去掉。
最后还能保证代码风格,.,

1
2
3
4
5
6
int IsEnglish(char *a){
char s[8][5] = {" the"," of "," and"," on ","you"," we ","his","3."};
int j = 0;
for(;j<9;++j) if(strstr(a,s[j])) return 1;
return 0;
}

数一下这张图片中有多少个logo…
logo
这题做法很多,统计联通块什么的,然而我并不会处理图片 ╮(╯▽╰)╭
所以我用了最暴力的方法 ———— 人肉数 Σ(|||▽||| )丧心病狂有木有
好吧,一个一个数肯定会出人命的,我数了一块,有217个,所以我估计答案在 32*217 = 6944 附近
于是乎我在附近试了几组,最后得出答案为 6970 …

Cake

nxn的蛋糕按题目要求分割,描述太长,直接看题目吧。

Knot

来来来,拿毛线,What!(好吧,自己拿跟绳子跟着图绕一下。

Sudoku 2

和门票题类似,问有多少种填法使一个数独上即没有1也没有2
我也考虑枚举对称性,和门票题类似,可是估计不会这么简单,不知道有没有问题。