| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/11 | O | O | O | O | O | O | O | Ø | O | . | Ø |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
题目来源：2016-2017 ACM-ICPC, Asia Tsukuba Regional Contest
A Rearranging a Sequence
题目描述
有个$1-n$的序列，每次把一个数扔到序列前，输出最终序列。
解题思路
签到题。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
using namespace std;
int b[400010];
int vis[200010];
int main(){
int i,n,m,a;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)b[i+m]=i;
for(i=1;i<=m;i++){
scanf("%d",&a);
b[m-i+1]=a;
}
for(i=1;i<=n+m;i++){
if(vis[b[i]]);
else vis[b[i]]=1,printf("%d\n",b[i]);
}
return 0;
}
B Quality of Check Digits
题目描述
给定一个$table$定义的$\times $运算，求有多少个五元组$(a,b,c,d,e)$不满足$(((a\times b)\times c)\times d\times e=0$且任意改变$a,b,c,d,e$的值或者交换相邻两个元素得到的值均非零。
解题思路
暴力模拟一下即可。
AC代码 - by Mogg
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
using namespace std;
typedef long long ll;
const int ms = 10 * 2;
const int inf = 0x3f3f3f3f;
int table[10][10];
int f[10][10][10][10];
int cal(int a, int b, int c, int d)
{
a = table[0][a];
b = table[a][b];
c = table[b][c];
return table[c][d];
}
int check2(int a, int b, int c, int d, int e)
{
if (a != b && table[cal(b, a, c, d)][e] == 0) return 1;
if (b != c && table[cal(a, c, b, d)][e] == 0) return 1;
if (c != d && table[cal(a, b, d, c)][e] == 0) return 1;
if (d != e && table[cal(a, b, c, e)][d] == 0) return 1;
return 0;
}
int check(int a, int b, int c, int d)
{
if (check2(a, b, c, d, f[a][b][c][d])) return 1;
for (int i = 0; i < 10; ++i)
{
if (i != a)
{
if (table[cal(i, b, c, d)][f[a][b][c][d]] == 0) return 1;
}
if (i != b)
{
if (table[cal(a, i, c, d)][f[a][b][c][d]] == 0) return 1;
}
if (i != c)
{
if (table[cal(a, b, i, d)][f[a][b][c][d]] == 0) return 1;
}
if (i != d)
{
if (table[cal(a, b, c, i)][f[a][b][c][d]] == 0) return 1;
}
if (i != f[a][b][c][d])
{
if (table[f[a][b][c][d]][i] == 0) return 1;
}
}
return 0;
}
int main()
{
for (int i = 0; i < 10; ++i)
{
for (int j = 0; j < 10; ++j)
{
scanf("%d", &table[i][j]);
}
}
for (int i = 0; i < 10; ++i)
{
for (int j = 0; j < 10; ++j)
{
for (int k = 0; k < 10; ++k)
{
for (int l = 0; l < 10; ++l)
{
f[i][j][k][l] = cal(i, j, k, l);
}
}
}
}
int res = 0;
for (int i = 0; i < 10; ++i)
{
for (int j = 0; j < 10; ++j)
{
for (int k = 0; k < 10; ++k)
{
for (int l = 0; l < 10; ++l)
{
res += check(i, j, k, l);
}
}
}
}
printf("%d\n", res);
return 0;
}
C Distribution Center
题目描述
有$n$个轨道，某些道路的某些位置上有$m$个机器人，机器人可以将$i,i+1$之间的货物双向运输，问最右端每个轨道上的货物可以从多少个轨道上过来。
解题思路
记录一下每个轨道分别从上面、下面运来的种类数更新答案即可。
AC代码 - by qxforever
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
using namespace std;
const int maxn = 2e5+23;
int ans[maxn];
int u[maxn],d[maxn];
struct P
{
int x,y;
bool operator < (const P&a)
{
return x<a.x;
}
};
int n,m;
P a[maxn];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
for(int i=1;i<=n;i++) u[i]=d[i]=ans[i]=1;
sort(a,a+m);
for(int i=0;i<m;i++){
int t=a[i].y;
ans[t]+=u[t+1];
ans[t+1]+=d[t];
u[t]+=u[t+1];u[t+1]=0;
d[t+1]+=d[t];d[t]=0;
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
}
D Hidden Anagrams
题目描述
问两个字符串中最长的同构串的长度。
解题思路
给每个字母编号双$hash$，暴力枚举子集即可。复杂度$O(n^2\log n)$。
AC代码 - by qxforever & Potassium
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
typedef long long ll;
using namespace std;
char a[4010],b[4010];
int la,lb;
ll bas=929292929,mod=991145149;
ll table[26]={73243,76343,78539,79669,80207,81031,81509,83219,86137,86341,87433,88993,89653,90271,90473,90731,90931,92243,93103,93493,93607,93979,95071,95239,95311,95917};
ll table1[26]={73243,76343,78539,79669,80207,81031,81509,83219,86137,86341,87433,88993,89653,90271,90473,90731,90931,92243,93103,93493,93607,93979,95071,95239,95311,95917};
int check(int x){
int i;
set<ll>S;S.clear();
set<ll> S1;
ll hash1=0,hash2=0;
ll hash11=0,hash22=0;
for(i=0;i<x;i++)(hash1+=table[a[i]-'a'])%=mod,(hash11+=table1[a[i]-'a'])%=mod;
S.insert(hash1);S1.insert(hash11);
for(i=0;i+x<la;i++){
hash1=(hash1+(table[a[i+x]-'a']-table[a[i]-'a'])+mod)%mod;
hash11=(hash11+(table1[a[i+x]-'a']-table1[a[i]-'a'])+mod)%mod;
S.insert(hash1);S1.insert(hash11);
}
for(i=0;i<x;i++)(hash2+=table[b[i]-'a'])%=mod,(hash22+=table1[b[i]-'a'])%=mod;
for(i=0;i+x<=lb;i++){
if(S.find(hash2)!=S.end()&&S1.find(hash22)!=S1.end())return 1;
hash2=(hash2+(table[b[i+x]-'a']-table[b[i]-'a'])+mod)%mod;
hash22=(hash22+(table1[b[i+x]-'a']-table1[b[i]-'a'])+mod)%mod;
}
return 0;
}
int main(){
int i;
scanf("%s%s",a,b);
for(int i=0;i<26;i++) table[i]*=(i*13+11),table1[i]*=(i*131+7);
la=strlen(a),lb=strlen(b);
for(i=min(la,lb);i>=0;i--)if(check(i))break;
printf("%d",i);
return 0;
}
E Infallibly Crack Perplexing Cryptarithm
题目描述
给一串加密后的、原串只由$+-01()=*$构成的字符串，问有多少种安排方法使得原串是一个合法且正确的表达式。
解题思路
爆搜，利用$python$库中的$eval$加一些特判解决问题。
AC代码 - by Mogg & qxforever
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
l2 = ['0','1']
l3 = ['-', '(','0','1']
def to2(ss):
i = 1
while i < len(ss):
if ss[i-1] in l1 and ss[i] in l2:
ss = ss[0:i] + "0b" + ss[i:]
i+=2
i+=1
if(ss[0]=='1' or ss[0]=='0'):
ss = "0b" + ss
return ss
def check(ss):
try:
eval(ss)
except (SyntaxError,TypeError):
return False
if(ss[0] == "+"):
return False
for i in range(1,len(ss)):
if ss[i] in ["+","*"] and ss[i-1] in ["+","-","*"]:
return False
if ss[i] in ["+","-","*"] and (i+1==len(ss) or ss[i+1] not in l3):
return False
if ss[i] == "+" and ss[i-1] == "(":
return False
if ss[i] == '0':
tmp = i
while tmp>=0 and ss[tmp] == '0':
tmp -= 1
if (i-tmp > 1) and (tmp<0 or ss[tmp] != "1"):
return False
if ss[i]==")" and ss[i-1] == "(":
return False
return True
def solve(ss):
ss = ss.split("=")
if (len(ss)!=2):
return False
if(not check(ss[0])):
return False
if(not check(ss[1])):
return False
ss[0] = to2(ss[0])
ss[1] = to2(ss[1])
return eval(ss[0]) == eval(ss[1])
l = ['0','1', '+', '-', '*', '(', ')', '=']
d = []
v = [False for i in range(len(l))]
def dfs(ss,x):
if(x==len(d)):
if(solve(ss)):
#print(ss)
return 1
return 0
res = 0
for i in range(len(l)):
if not v[i]:
v[i] = True
dd = []
for j in range(len(ss)):
if(ss[j] == d[x]):
ss =ss[0:j]+ l[i]+ss[j+1:]
dd.append(j)
res += dfs(ss,x+1)
for j in dd:
ss =ss[0:j]+ d[x]+ss[j+1:]
v[i] = False
return res
while False:
s = input()
if(check(s)):
print(to2(s))
print(eval(to2(s)))
s = input()
for i in s:
if (i not in l) and (i not in d):
d.append(i)
res = 0
if len(d) == 0:
if(solve(s)):
res+=1
elif len(d) <= 8:
res = dfs(s,0)
print(res)
F Three Kingdoms of Bourdelot
题目描述
有$n$个文件，每个文件中描述一堆形如$a_i$是$b_i$祖先的言论。对于每个文件，他可能是真的，也可能是假的，但是必定是全真或全假。
问有没有一种方式分配文件的真假，使得$p$是$q$的祖先。
解题思路
对于每一对$a,b$，若$a$是$b$的祖先，那么所有提到“$a$是$b$的祖先”言论的文件都需要判断成真的。同时，对于$a$的每一个既有祖先$i$，$b$的每一个既有后辈$j$，都有$i$是$j$的祖先。
于是很容易想到$dfs$的方法去合并一对确定关系的$a,b$，用一个二维数组$f[i][j]$记录祖先关系。为了保证复杂度，在枚举$j$的时候，从未被$i$合并过的$j$集合中寻找。所以可以用$bitset$存这个二维数组，每次寻找$j$只需要从
~f[i]&f[b])中枚举。AC代码
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
typedef long long ll;
using namespace std;
map<string,int>mp;int tot;
vector<pair<int,int>>doc[1010];
vector<int>id[1010][1010];
string a,b;
bitset<1010>f[1010],temp;
int vis[100010],n;
void merge(int fa,int son){
for(auto i:id[fa][son]){
if(!vis[i]){
vis[i]=1;
for(auto j:doc[i])if(!f[j.first][j.second])getf(j.first,j.second);
}
}
}
void getf(int fa,int son){
f[fa][son]=1;
merge(fa,son);
int i,j;
for(i=1;i<=tot;i++){//ancestor of fa
if(!f[i][fa])continue;
temp=(f[son])&(~f[i]);//new added
f[i]|=f[son];
for(j=1;j<=tot;j++){
if(!temp[j])continue;
merge(i,j);
}
}
}
int main(){
int i,j,m;
cin>>a>>b;
scanf("%d",&n);
if(mp.count(a)==0)mp[a]=++tot;
if(mp.count(b)==0)mp[b]=++tot;
int st=mp[a],ed=mp[b];
for(i=1;i<=n;i++){
scanf("%d",&m);
for(j=0;j<m;j++){
cin>>a>>b;
if(!mp.count(a))mp[a]=++tot;
if(!mp.count(b))mp[b]=++tot;
int ida=mp[a],idb=mp[b];
doc[i].push_back(make_pair(ida,idb));
id[ida][idb].push_back(i);
}
}
for(i=1;i<=tot;i++)f[i][i]=1;
getf(st,ed);
for(i=1;i<=tot;i++)
for(j=i+1;j<=tot;j++)
if(f[i][j]&&f[j][i])return printf("No"),0;
printf("Yes");
return 0;
}
G Placing Medals on a Binary Tree
题目描述
依次存放$n$个物品，每个物品$i$有要求放在满二叉树的第$dep_i$层。放置完后，这个点到根的路径就不可以再放其他物品了，依次输出物品能否放置。
解题思路
很容易看出来问题就是$1-\frac 1 {2^{dep_i}}-…$，要求这个和式不小于零。可以用二进制表示减去的部分，存一个$map$表示第$i$位的状态（$0$或$1$），当插入某个$dep$的时候，如果$dep$位前没有全满，或者全满了但这一个位置是最后一个（加上恰好总和为$1$）那么就可以插入。插入的时候模拟一下二进制进位即可，复杂度$O(n\log n)$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
using namespace std;
map<int,int>mp;
int mn=1;
int main(){
int i,n,x;
mp[0]=0;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
if(x<mn-1||mp[0]==1||(mp.size()&&x==mn-1&&(*(--mp.end())).first>x))printf("No\n");
else{
while(mp[x])mp.erase(x),x--;
mp[x]++;
while(mp.count(mn))mn++;
printf("Yes\n");
}
}
return 0;
}
H Animal Companion in Maze
题目描述
给一个混合图，两点之间的边权为$1$，求最长路。
解题思路
如果有环，那么答案显然为$infinite$，故可以先求一下强连通分量，在每个强连通分量里$dfs$找环特判掉这种情况。
显然，如果一个有向边在某个强连通分量里，那么这个强连通分量必然存在环。所以不存在环时必然有：每个强连通分量都是一棵树，树与树之间通过单向边连接。
于是考虑对强连通分量拓扑序$dp$，再对于每一个强连通分量进行树形$dp$，分两种情况从根节点向下走、从叶子节点向上走，设$dp[i]$表示到达$i$点的最大权值是多少。第一种情况很容易得到，$dp[son]=max(dp[fa]+1,dp[son])$；但当考虑第二种情况时，因为不能走回头路，需要判断一下每一个$dp$是从哪一个孩子节点过来的。所以保存一个到达$i$节点的最大权值、次大权值以及从最大权值是从哪里过来的即可。
AC代码
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
typedef long long ll;
using namespace std;
int n,m;
struct Edge{
int e,n;
}e[N<<4];
int hd[N],cnt;
int sign[N<<4];
void add(int a,int b,int s){e[++cnt].e=b;e[cnt].n=hd[a];hd[a]=cnt;sign[cnt]=s;}
int sta[N],top,vis[N];
int col[N],num,val[N];
int dfn[N],low[N],tot;
int root[N];//tree root in SCC
void tarjan(int p){
int i,q;
low[p]=dfn[p]=++tot;
sta[++top]=p;vis[p]=1;
for(i=hd[p];i;i=e[i].n){
q=e[i].e;
if(!dfn[q])tarjan(q),low[p]=min(low[p],low[q]);
else if(vis[q])low[p]=min(low[q],low[p]);
}
if(dfn[p]==low[p]){
num++;
while(sta[top+1]!=p){
q=sta[top];
col[q]=num;
vis[q]=0;
val[num]++;
top--;
}
root[num]=p;
}
}
struct E2{
int b,e,n;
}E[N<<2];
int HD[N],CNT,indeg[N];//directed edge from different SCCs
void add2(int a,int b){E[++CNT].e=b;E[CNT].b=a;E[CNT].n=HD[col[a]];HD[col[a]]=CNT;}
int scccircle(int p,int f){//同一个强连通分量中的环（不含双向边）
int i;
vis[p]=1;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(col[q]==col[p]&&(sign[i]==1||(sign[i]==2&&q!=f))&&(vis[q]||scccircle(q,p)))return 1;
}
return 0;
}
int find_circle(){
int i;
for(i=1;i<=n;i++)if(!vis[i]&&scccircle(i,-1))return 1;
return 0;
}
int dp[N][2];//到这个点的最大，次大
int from[N];
void dfs1(int p,int f){
int i;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(q!=f&&col[p]==col[q]){
dfs1(q,p);
if(dp[p][0]<dp[q][0]+1){
dp[p][1]=dp[p][0];
dp[p][0]=dp[q][0]+1;
from[p]=q;
}else dp[p][1]=max(dp[p][1],dp[q][0]+1);
}
}
}
void dfs2(int p,int f){
int i;
for(i=hd[p];i;i=e[i].n){
int q=e[i].e;
if(q!=f&&col[p]==col[q]){
if(q==from[p]){
if(dp[q][0]<dp[p][1]+1){
dp[q][1]=dp[q][0];
dp[q][0]=dp[p][1]+1;
from[q]=p;
}else dp[q][1]=max(dp[q][1],dp[p][1]+1);
}else{
if(dp[q][0]<dp[p][0]+1){
dp[q][1]=dp[q][0];
dp[q][0]=dp[p][0]+1;
from[q]=p;
}else dp[q][1]=max(dp[q][1],dp[p][0]+1);
}
dfs2(q,p);
}
}
}
queue<int>Q;
int main(){
int i,j;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
if(w==2)add(b,a,w);
add(a,b,w);
}
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
if(find_circle())return printf("Infinite"),0;
for(i=1;i<=n;i++)
for(j=hd[i];j;j=e[j].n)
if(col[i]!=col[e[j].e])
add2(i,e[j].e),++indeg[col[e[j].e]];
for(i=1;i<=num;i++)if(!indeg[i])Q.push(i);
while(!Q.empty()){
int tp=Q.front();Q.pop();
dfs1(root[tp],0);
dfs2(root[tp],0);
for(i=HD[tp];i;i=E[i].n){
int b=E[i].b,e=E[i].e;
if(!--indeg[col[e]])Q.push(col[e]);
dp[e][0]=max(dp[e][0],dp[b][0]+1);
}
}
int res=0;
for(i=1;i<=n;i++)res=max(res,dp[i][0]);
printf("%d",res);
return 0;
}
I Skinny Polygon
题目描述
给定一个$1e9$范围内的$x,y$，求构造一个三角形或四边形满足：
- 所有点的横坐标至少包含一个$0$一个$x$
- 所有点的纵坐标至少包含一个$0$一个$y$
- 围成的面积小于$25000$
解题思路
在对角线上做文章。要么是一个凹四边形，要么是一个三角形。
分类讨论一下即可，假设$gcd(x,y)=g$，$xg=\frac xg,yg=\frac yg$。
求一下$(0,0)(x,y-1)(xg,yg)(x-1,y)$构成的凹四边形面积，显然是$\frac{xg+ yg}2$，故当这个面积小于$25000$的时候可以输出这个凹四边形。
再找到一点$(a,b)$满足$(0,0)(x,y)(a,b)$构成的三角形面积满足条件，也即$\frac{|bx-ay|}2\leq 25000$。而由于$xg+yg>50000$，则$\frac{x+y}{g}>50000,g<\frac{2\times 10^{9}}{5\times 10^4}=40000<50000$。对于$|b\times xg-a\times yg|=1$很容易用扩展欧几里得求出$a,b$，故$|bx-ay|=g\times |b\times xg-a\times yg|=g$有解。解出即可。
AC代码
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
typedef long long ll;
using namespace std;
void exgcd(int a,int b,int&gcd,int&x,int&y){
if(b==0)x=1,y=0,gcd=a;
else{
exgcd(b,a%b,gcd,y,x);
y-=x*(a/b);
}
}
int main(){
int i,n,x,y;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&x,&y);
int a,b,d;
exgcd(x,y,d,a,b);
int xg=x/d,yg=y/d;
if((xg+yg)<=50000)printf("4\n%d %d\n0 0\n%d %d\n%d %d\n",x-1,y,x,y-1,xg,yg);
else{
printf("3\n0 0\n%d %d\n",x,y);
while(a>0&&b>0)a-=yg,b-=xg;
printf("%d %d\n",(int)fabs(b),(int)fabs(a));
}
}
return 0;
}
J Cover the Polygon with Your Disk
题目描述
解题思路
AC代码
2
K Black and White Boxes
题目描述
有黑白两种方块，摞成一摞，有两个人分别只能取走黑色和白色的块。取走某个块后，上面的所有块都会消失，当某个人无法取块的时候他就输了。
有$n$摞，选择其中的某些摞使得每个人先手后手的胜负状态不一致，最大化黑白块的总个数。
解题思路
神秘博弈，$surreal\space number$，具体看$cf$题解吧。
AC代码
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
typedef long long ll;
using namespace std;
char a[45];
map<ll,int>mp;
ll ans[45];
int len[45],sc[225];
ll calc(char a[]){
int i,mx=40;
ll now=sc[a[0]]*(1LL<<mx);
for(i=1;a[i];i++){
if(a[i]!=a[0])break;
now+=sc[a[i]]*(1LL<<mx);
}
for(;a[i];i++){
mx--;
now+=sc[a[i]]*(1LL<<mx);
}
return now;
}
int main(){
int i,j,n;
sc['W']=1;sc['B']=-1;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%s",a);
ans[i]=calc(a);
len[i]=strlen(a);
}
int num1=n/2,s1=(1<<num1)-1;
for(i=0;i<=s1;i++){
ll t=0,num=0;
for(j=0;j<num1;j++)if(i&(1<<j))t+=ans[j],num+=len[j];
if(mp.count(t)==0||mp[t]<num)mp[t]=num;
}
int num2=n-n/2,s2=(1<<num2)-1;ll res=0;
for(i=0;i<=s2;i++){
ll t=0,num=0;
for(j=num1;j<num1+num2;j++)if(i&(1<<(j-num1)))t+=ans[j],num+=len[j];
if(mp.count(-t))res=max(res,mp[-t]+num);
}
printf("%lld\n",res);
return 0;
}