A A water problem
一.题目大意
\quad
问
n
n
n 是否同时为
73
73
73 和
137
137
137 的倍数.
\quad
l
e
n
g
t
h
(
n
)
≤
1
0
7
length(n) \leq 10^7
length(n)≤107.
二.分析
\quad
赛时产生失智行为，水题直接写.
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)1e7;
const int N
= (int)3e2;
const ll inf
= 0x3f3f3f3f3f3f3f3f;
const ll mod
= (ll
)1e9 + 7;
const double eps
= 1e-6;
char s
[M
+ 5];
int main()
{
int ca
= 0;
while(~scanf("%s", s
+ 1))
{
printf("Case #%d: ", ++ca
);
int n
= strlen(s
+ 1);
int r
= 0; for(int i
= 1; i
<= n
; ++i
) r
= (r
* 10 + s
[i
] - '0') % 10001;
puts(r
? "NO" : "YES");
}
return 0;
}
B Zhu and 772002
一.题目大意
\quad
给出
n
n
n 个数
a
[
1..
n
]
a[1..n]
a[1..n]，其中
a
[
1..
n
]
a[1..n]
a[1..n] 的最大质因数
≤
2
×
1
0
3
\leq 2\times 10^3
≤2×103.
\quad
每个数至多选一次，求有多少种选数方案使得选出来数的乘积为完全平方数.
\quad
n
≤
3
×
1
0
2
,
a
[
i
]
≤
1
0
18
n \leq 3 \times 10^2, a[i] \leq 10^{18}
n≤3×102,a[i]≤1018.
二.分析
\quad
对每一个质因子列一个方程
∑
j
=
1
n
A
i
,
j
x
j
=
0
(
m
o
d
2
)
\begin{aligned} \sum_{j=1}^n A_{i,j}x_{j} = 0 \; ( mod \; 2) \end{aligned}
j=1∑nAi,jxj=0(mod2).
\quad
上式中，
A
i
,
j
A_{i, j}
Ai,j 表示
a
[
j
]
a[j]
a[j] 含有第
i
i
i 个质数的指数的奇偶性，
x
j
x_j
xj 表示
a
[
j
]
a[j]
a[j] 选不选.
\quad
由此，得到异或方程组，用高斯消元求出矩阵的秩
r
r
r。由于
x
j
∈
{
0
,
1
}
x_j \in \{0, 1\}
xj∈{0,1}，所以答案为
2
n
−
r
−
1
2^{n-r} - 1
2n−r−1
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)2e3;
const int N
= (int)3e2;
const ll inf
= 0x3f3f3f3f3f3f3f3f;
const ll mod
= (ll
)1e9 + 7;
const double eps
= 1e-6;
int cnt
, prime
[M
+ 5];
bool is_prime
[M
+ 5];
bool a
[N
+ 5][N
+ 5];
void init()
{
cnt
= 0;
memset(is_prime
, 1, sizeof(is_prime
));
is_prime
[0] = is_prime
[1] = 0;
for(int i
= 2; i
<= M
; ++i
)
{
if(is_prime
[i
]) prime
[++cnt
] = i
;
for(int j
= 1; j
<= cnt
&& i
* prime
[j
] <= M
; ++j
)
{
is_prime
[i
* prime
[j
]] = 0;
if(i
% prime
[j
] == 0) break;
}
}
}
void divide(int p
, ll n
)
{
for(int i
= 1; i
<= cnt
; ++i
)
{
if(n
% prime
[i
] == 0)
{
int c
= 0; ll t
= n
;
while(t
% prime
[i
] == 0) ++c
, t
/= prime
[i
];
a
[i
][p
] = (c
& 1);
}
}
}
int gauss(int n
, int m
)
{
int c
, r
;
for(c
= 1, r
= 1; c
<= m
; ++c
)
{
int t
= r
;
for(int i
= r
; i
<= n
; ++i
)
{
if(fabs(a
[i
][c
]) > fabs(a
[t
][c
])) t
= i
;
}
if(fabs(a
[t
][c
]) < eps
) continue;
for(int i
= c
; i
<= m
+ 1; ++i
) swap(a
[t
][i
], a
[r
][i
]);
for(int i
= m
+ 1; i
>= c
; --i
) a
[r
][i
] /= a
[r
][c
];
for(int i
= 1; i
<= n
; ++i
)
{
if(i
== r
) continue;
if(fabs(a
[i
][c
]) > eps
)
{
for(int j
= m
+ 1; j
>= c
; --j
)
{
a
[i
][j
] -= a
[r
][j
] * a
[i
][c
];
}
}
}
++r
;
}
for(int i
= r
; i
<= n
; ++i
)
{
if(fabs(a
[i
][m
+ 1]) > eps
) return -1;
}
return m
- r
+ 1;
}
ll
quick(ll a
, ll b
, ll p
= mod
)
{
ll s
= 1;
while(b
)
{
if(b
& 1) s
= s
* a
% p
;
a
= a
* a
% p
;
b
>>= 1;
}
return s
;
}
void work()
{
memset(a
, 0, sizeof(a
));
int n
; scanf("%d", &n
);
ll x
; for(int i
= 1; i
<= n
; ++i
) scanf("%lld", &x
), divide(i
, x
);
int r
= gauss(cnt
, n
);
printf("%lld\n", ((quick(2, r
) - 1) % mod
+ mod
) % mod
);
}
int main()
{
init();
int T
; scanf("%d", &T
);
for(int ca
= 1; ca
<= T
; ++ca
)
{
printf("Case #%d:\n", ca
);
work();
}
return 0;
}
C Magic boy Bi Luo with his excited tree
一.题目大意
\quad
T
T
T 组测试，每次给一颗
n
n
n 个点的无根树，每个点有相应的价值
V
[
i
]
V[i]
V[i]，每条边有相应的花费
C
[
i
]
C[i]
C[i].
\quad
当以
i
i
i 号点为根时，树的权值定义为从
i
i
i 号点出发，{价值和 - 花费和} 的最大值.
\quad
注意：每个点的价值至多获得一次，每条边的花费可多次.
\quad
求当根
i
i
i 取
[
1
,
n
]
[1,n]
[1,n] 所有值时对应的树的权值.
\quad
T
≤
1
0
4
,
n
≤
1
0
5
,
∑
n
<
1
0
6
,
1
≤
V
[
i
]
,
C
[
i
]
≤
1
0
4
T \leq 10^4, n \leq 10^5, \sum n < 10^6, 1 \leq V[i], C[i] \leq 10^4
T≤104,n≤105,∑n<106,1≤V[i],C[i]≤104.
二.分析
\quad
很明显的换根 DP，但还是写了很久…
\quad
f
[
i
]
[
0
]
f[i][0]
f[i][0] 表示在以
1
1
1 号点为根的前提下，在以
i
i
i 号点为根的子树中走，终点不为
i
i
i 的最大收益.
\quad
f
[
i
]
[
1
]
f[i][1]
f[i][1] 表示在以
1
1
1 号点为根的前提下，在以
i
i
i 号点为根的子树中走，终点为
i
i
i 的最大收益.
\quad
f
[
i
]
[
2
]
f[i][2]
f[i][2] 表示在以
1
1
1 号点为根的前提下，在以
i
i
i 号点为根的子树中走，终点不为
i
i
i 的次大收益.
\quad
p
[
i
]
p[i]
p[i] 表示在以
1
1
1 号点为根的前提下，在以
i
i
i 号点为根的子树中走，终点不为
i
i
i 的最大收益对应的子节点编号.
\quad
g
[
i
]
[
0
]
g[i][0]
g[i][0] 表示在以
1
1
1 号点为根的前提下，从
i
i
i 号点往
f
a
[
i
]
fa[i]
fa[i] 的方向走，终点不为
i
i
i 的最大收益.
\quad
g
[
i
]
[
1
]
g[i][1]
g[i][1] 表示在以
1
1
1 号点为根的前提下，从
i
i
i 号点往
f
a
[
i
]
fa[i]
fa[i] 的方向走，终点为
i
i
i 的最大收益.
\quad
上述状态表示乍一看很晕，但其实画画图分析一下就自然而然地写出来了.
\quad
详见代码.
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)1e5;
const int N
= (int)25;
const int inf
= 0x3f3f3f3f;
const ll mod
= (ll
)772002;
const double eps
= 1e-6;
int n
, cnt
;
int head
[M
+ 5];
struct node
{
int v
, w
, nx
;
}Edge
[M
* 2 + 5];
int V
[M
+ 5];
int f
[M
+ 5][3];
int p
[M
+ 5];
int g
[M
+ 5][2];
void init()
{
cnt
= 0;
for(int i
= 1; i
<= n
; ++i
)
{
head
[i
] = -1;
}
}
void add(int u
, int v
, int w
)
{
Edge
[cnt
].v
= v
;
Edge
[cnt
].w
= w
;
Edge
[cnt
].nx
= head
[u
];
head
[u
] = cnt
++;
}
void dfs1(int u
, int fa
)
{
f
[u
][0] = V
[u
], f
[u
][1] = V
[u
], f
[u
][2] = -inf
;
int f0
, f1
;
for(int i
= head
[u
]; ~i
; i
= Edge
[i
].nx
)
{
int v
= Edge
[i
].v
;
if(v
== fa
) continue;
dfs1(v
, u
);
f0
= max(0, f
[v
][0] - Edge
[i
].w
);
f1
= max(0, f
[v
][1] - 2 * Edge
[i
].w
);
if(f
[u
][0] + f1
< f
[u
][1] + f0
) f
[u
][0] = f
[u
][1] + f0
, p
[u
] = v
;
else f
[u
][0] = f
[u
][0] + f1
;
f
[u
][1] += f1
;
}
for(int i
= head
[u
]; ~i
; i
= Edge
[i
].nx
)
{
int v
= Edge
[i
].v
;
if(v
== fa
|| v
== p
[u
]) continue;
f0
= max(0, f
[v
][0] - Edge
[i
].w
);
f1
= max(0, f
[v
][1] - 2 * Edge
[i
].w
);
f
[u
][2] = max(f
[u
][2], f
[u
][1] - f1
+ f0
);
}
}
void dfs2(int u
, int fa
)
{
int f1
;
for(int i
= head
[u
]; ~i
; i
= Edge
[i
].nx
)
{
int v
= Edge
[i
].v
;
if(v
== fa
) continue;
g
[v
][0] = V
[v
];
f1
= max(0, f
[v
][1] - 2 * Edge
[i
].w
);
g
[v
][0] = max(g
[v
][0], V
[v
] + g
[u
][0] - V
[u
] + f
[u
][1] - f1
- Edge
[i
].w
);
if(p
[u
] != v
) g
[v
][0] = max(g
[v
][0], V
[v
] + g
[u
][1] - V
[u
] + f
[u
][0] - f1
- Edge
[i
].w
);
else g
[v
][0] = max(g
[v
][0], V
[v
] + g
[u
][1] - V
[u
] + f
[u
][2] - f1
- Edge
[i
].w
);
g
[v
][1] = V
[v
] + max(0, g
[u
][1] - V
[u
] + f
[u
][1] - f1
- 2 * Edge
[i
].w
);
dfs2(v
, u
);
}
}
void work()
{
scanf("%d", &n
); init();
for(int i
= 1; i
<= n
; ++i
) scanf("%d", &V
[i
]);
for(int i
= 1, u
, v
, w
; i
<= n
- 1; ++i
) scanf("%d %d %d", &u
, &v
, &w
), add(u
, v
, w
), add(v
, u
, w
);
dfs1(1, 0);
g
[1][0] = V
[1], g
[1][1] = V
[1];
dfs2(1, 0);
for(int i
= 1; i
<= n
; ++i
) printf("%d\n", max(f
[i
][0] + g
[i
][1], f
[i
][1] + g
[i
][0]) - V
[i
]);
}
int main()
{
int T
; scanf("%d", &T
);
for(int ca
= 1; ca
<= T
; ++ca
)
{
printf("Case #%d:\n", ca
);
work();
}
return 0;
}
D Danganronpa
一.题目大意
\quad
有
n
n
n 种礼物，每种物品有
a
[
i
]
个
a[i] 个
a[i]个.
\quad
学生们排成一行，老师给每位学生发两个礼物，分别为普通礼物和神秘礼物，要求相邻两位同学的普通礼物不相同，神秘礼物没有限制，求最多能给多少位同学发礼物.
二.分析
\quad
记
s
s
s 为所有礼物个数之和，
m
x
mx
mx 为所有礼物中礼物个数的最大值.
\quad
当
m
x
≥
s
−
m
x
−
1
mx \geq s - mx - 1
mx≥s−mx−1 时，可以让其他礼物排成一行，最多数量的礼物插空，保证了相邻的普通礼物不同。此时，若
m
x
−
(
s
−
m
x
−
1
)
≥
s
−
(
s
−
m
x
)
−
(
s
−
m
x
−
1
)
mx - (s - mx - 1) \geq s-(s-mx) - (s-mx-1)
mx−(s−mx−1)≥s−(s−mx)−(s−mx−1)，则答案为
2
(
s
−
m
x
−
1
)
+
1
2(s - mx - 1) + 1
2(s−mx−1)+1；否则，需要结尾把后面的普通礼物放到神秘礼物中，答案为
s
2
\frac{s}{2}
2s.
\quad
否则，不难(用)证明答案为
s
2
\frac{s}{2}
2s.
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)1e5;
const int N
= (int)3e2;
const ll inf
= 0x3f3f3f3f3f3f3f3f;
const ll mod
= (ll
)1e9 + 7;
const double eps
= 1e-6;
int n
, a
[M
+ 5];
int main()
{
int T
; scanf("%d", &T
);
for(int ca
= 1; ca
<= T
; ++ca
)
{
scanf("%d", &n
);
for(int i
= 1; i
<= n
; ++i
) scanf("%d", &a
[i
]);
int s
= 0, mx
= 0; for(int i
= 1; i
<= n
; ++i
) s
+= a
[i
], mx
= max(mx
, a
[i
]);
int ans
= 0;
if(mx
>= s
- mx
- 1)
{
if(2 * mx
- s
+ 1 >= 2 * s
- 2 * mx
- 1) ans
= 2 * s
- 2 * mx
- 1;
else ans
= s
/ 2;
}
else ans
= s
/ 2;
printf("Case #%d: %d\n", ca
, ans
);
}
return 0;
}
G Mountain
一.题目大意
\quad
给一张
n
×
m
n \times m
n×m 的地图
s
s
s，
s
[
i
]
[
j
]
∈
{
′
′
X
′
,
′
.
′
}
s[i][j] \in \{''X', '.'\}
s[i][j]∈{′′X′,′.′}.
\quad
要求在每个位置填数，每个位置上的数
∈
[
1
,
n
×
m
]
\in [1, n\times m]
∈[1,n×m] 且两两不相同，满足
′
X
′
'X'
′X′ 位置上的数是它周围
8
8
8 个数的最小值且
′
.
′
'.'
′.′ 不是.
\quad
求填数的方案数.
\quad
n
,
m
≤
5
n,m \leq 5
n,m≤5.
二.分析
\quad
这数据范围显然是状压 DP.
\quad
易知图中若存在相邻的
′
X
′
'X'
′X′ 则方案数为
0
0
0，则图中最多存在
9
9
9 个
′
X
′
'X'
′X′.
\quad
考虑从小到大填数，
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示用了前
i
i
i 个数，
′
X
′
'X'
′X′ 的填充状态为
j
j
j 的方案数，即得状态转移方程.
\quad
可这样只保证了
′
X
′
'X'
′X′ 是极小的，无法保证
′
.
′
'.'
′.′ 不是极小的，所以这里非常妙可以用容斥来做.
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)5;
const int N
= (int)25;
const int inf
= 0x3f3f3f3f;
const ll mod
= (ll
)772002;
const double eps
= 1e-6;
int n
, m
, ans
;
char s
[M
][M
];
int id
[M
][M
];
int f
[N
+ 1][1<<9];
int c1
[1<<9], c2
[1<<9];
int dx
[] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy
[] = {1, 1, 0, -1, -1, -1, 0, 1};
bool check(int i
, int j
)
{
for(int k
= 0, x
, y
; k
< 8; ++k
)
{
x
= i
+ dx
[k
], y
= j
+ dy
[k
];
if(x
>= 0 && x
< n
&& y
>= 0 && y
< m
&& s
[x
][y
] == 'X') return 0;
}
return 1;
}
int cal(int c
)
{
int x
, y
, flag
;
for(int i
= 0; i
< (1<<c
); ++i
)
{
c1
[i
] = 0;
for(int j
= 0; j
< n
; ++j
)
{
for(int k
= 0; k
< m
; ++k
)
{
if(s
[j
][k
] != '.') continue;
flag
= 1;
for(int l
= 0; l
< 8; ++l
)
{
x
= j
+ dx
[l
], y
= k
+ dy
[l
];
if(x
>= 0 && x
< n
&& y
>= 0 && y
< m
&& s
[x
][y
] == 'X' && (((~i
)>>id
[x
][y
]) & 1)) flag
= 0;
}
c1
[i
] += flag
;
}
}
}
f
[0][0] = 1;
for(int i
= 1; i
<= n
* m
; ++i
)
{
for(int j
= 0; j
< (1<<c
); ++j
)
{
f
[i
][j
] = f
[i
- 1][j
] * (c1
[j
] - (i
- 1 - c2
[j
])) % mod
;
for(int k
= 0; k
< c
; ++k
)
{
if((j
>>k
) & 1) f
[i
][j
] = (f
[i
][j
] + f
[i
- 1][j
^(1<<k
)]) % mod
;
}
}
}
return f
[n
* m
][(1<<c
) - 1];
}
void dfs(int u
, int v
, int e
)
{
if(u
== n
* m
)
{
if(e
& 1) ans
= (ans
- cal(v
)) % mod
;
else ans
= (ans
+ cal(v
)) % mod
;
return;
}
int x
= u
/ m
, y
= u
% m
;
if(s
[x
][y
] == 'X') id
[x
][y
] = v
, dfs(u
+ 1, v
+ 1, e
);
else
{
dfs(u
+ 1, v
, e
);
if(check(x
, y
))
{
s
[x
][y
] = 'X';
id
[x
][y
] = v
, dfs(u
+ 1, v
+ 1, e
+ 1);
s
[x
][y
] = '.';
}
}
}
void work()
{
for(int i
= 0; i
< n
; ++i
) scanf("%s", s
[i
]);
bool f
= 1; for(int i
= 0; i
< n
; ++i
) for(int j
= 0; j
< m
; ++j
) if(s
[i
][j
] == 'X' && !check(i
, j
)) f
= 0;
if(!f
) {printf("0\n"); return;}
ans
= 0; dfs(0, 0, 0);
ans
= (ans
% mod
+ mod
) % mod
;
printf("%d\n", ans
);
}
int getOne(int n
)
{
int c
= 0;
while(n
) c
+= (n
& 1), n
>>= 1;
return c
;
}
int main()
{
for(int i
= 0; i
< (1<<9); ++i
) c2
[i
] = getOne(i
);
int ca
= 0;
while(~scanf("%d %d", &n
, &m
))
{
printf("Case #%d: ", ++ca
);
work();
}
return 0;
}
K Lweb and String
一.题目大意
\quad
给一个由小写字母组成的字符串，可将字母集合映射到任意数字集合，求将该字符串映射成数字串的严格最长上升子序列的长度.
\quad
l
e
n
g
t
h
(
s
)
≤
1
0
5
length(s) \leq 10^5
length(s)≤105.
二.分析
\quad
显然答案就是字符串的字符集大小.
三.代码实现
#include <bits/stdc++.h>
using namespace std
;
typedef unsigned long long ull
;
typedef long long ll
;
const int M
= (int)1e5;
const int N
= (int)1e5;
const ll inf
= 0x3f3f3f3f3f3f3f3f;
const ll mod
= (ll
)1e9 + 7;
const double eps
= 1e-6;
char s
[M
+ 5];
int cnt
[26];
int main()
{
int T
; scanf("%d", &T
);
for(int ca
= 1; ca
<= T
; ++ca
)
{
memset(cnt
, 0, sizeof(cnt
));
scanf("%s", s
+ 1);
int n
= strlen(s
+ 1);
for(int i
= 1; i
<= n
; ++i
) cnt
[s
[i
] - 'a']++;
int c
= 0; for(int i
= 0; i
< 26; ++i
) c
+= (cnt
[i
] > 0);
printf("Case #%d: %d\n", ca
, c
);
}
return 0;
}
