比赛链接
| Solved | Time | Penalty |
|---|---|---|
| 7/7 | 122min | 390 |
注意可能会出现跨到第二天的情况。
#define multiple_test_cases
const int N = 15;
int n, H, M, h[N], m[N];
int ans;
void solve(){
n = rdi;
H = rdi;
M = rdi;
ans = 0x3f3f3f3f;
for(int i = 1; i <= n; ++ i){
h[i] = rdi;
m[i] = rdi;
if(h[i] > H || (h[i] == H && m[i] >= M)){
ans = min(ans, (h[i]-H)*60+m[i]-M);
}
h[i] += 24;
if(h[i] > H || (h[i] == H && m[i] >= M)){
ans = min(ans, (h[i]-H)*60+m[i]-M);
}
}
write(ans/60);
writen(ans%60);
}
B. Remove Prefix
从右往左遍历，记录每一个数出现的次数。
#define multiple_test_cases
const int N = 2e5 + 10;
int n, a[N], cnt[N];
void solve(){
n = rdi;
for(int i = 1; i <= n; ++ i){
a[i] = rdi;
}
for(int i = n; i; -- i){
if(cnt[a[i]]){
writen(i);
for(int j = 1; j <= n; ++ j){
cnt[j] = 0;
}
return;
}
++ cnt[a[i]];
}
writen(0);
for(int j = 1; j <= n; ++ j){
cnt[j] = 0;
}
return;
}
C. Minimum Varied Number
显然答案类似于 x56789。
#define multiple_test_cases
int n, ans[10];
void solve(){
n = rdi;
for(int i = 9; i >= 0; -- i){
if(n >= i){
ans[i] = i;
n -= i;
if(n == 0){
for(int j = i; j <= 9; ++ j){
putchar(ans[j] + '0');
}
endl;
return;
}
} else {
ans[i] = n;
for(int j = i; j <= 9; ++ j){
putchar(ans[j] + '0');
}
endl;
return;
}
}
puts("123456789");
}
D. Color with Occurrences
？？？
暴力。枚举第 i i i 位与第 j j j 个串的第 x x x 位对应是否能匹配。
#define multiple_test_cases
const int N = 100;
int n, res[N][2], tot;
char t[N], s[15][15];
bool cmp(int x, int i, int j){
int k = strlen(s[i]+1);
for(int p = 1; p <= k; ++ p){
if(s[i][p] != t[x-j+p]){
return false;
}
}
return true;
}
void solve(){
scanf("%s", t+1);
int l = strlen(t+1);
n = rdi;
for(int i = 1; i <= n; ++ i){
scanf("%s", s[i] + 1);
}
int ans = 0;
for(int i = 1; i <= l;){
int mx = 0, pi = 0, pj = 0;
for(int j = 1; j <= n; ++ j){
int k = strlen(s[j]+1);
for(int x = 1; x <= k; ++ x){
if(cmp(i, j, x)){
if(mx < k-x+1){
mx = k-x+1;
pi = j;
pj = x;
}
}
}
}
if(!mx){
puts("-1");
return;
}
++ ans;
int k = strlen(s[pi]+1);
res[ans][0] = pi;
res[ans][1] = i - (pj-1);
i = i + k-pj+1;
}
writen(ans);
for(int i = 1; i <= ans; ++ i){
write(res[i][0]);
write(res[i][1]);
endl;
}
}
E. Add Modulo 10
考虑每种个位：
- 1 , 2 , 4 , 8 , 16 , . . . 1,2,4,8,16,... 1,2,4,8,16,...；
- 2 , 4 , 8 , 16 , . . . 2,4,8,16,... 2,4,8,16,...；
- 3 , 6 , . . . 3,6,... 3,6,...；
- 4 , 8 , 16 , . . . 4,8,16,... 4,8,16,...；
- 5 , 10 , 10 , . . . 5,10,10,... 5,10,10,...；
- 6 , 12 , 14 , 18 , 26 , . . . 6,12,14,18,26,... 6,12,14,18,26,...；
- 7 , 14 , 18 , 26 , . . . 7,14,18,26,... 7,14,18,26,...；
- 8 , 16 , . . . 8,16,... 8,16,...；
- 9 , 18 , 26 , . . . 9,18,26,... 9,18,26,...；
- 0 , 0 , . . . 0,0,... 0,0,...；
所以我们可以把所有数按个位以及十位的奇偶性分为三组：
- 十位为奇数，个位为 1 , 2 , 4 , 8 1,2,4,8 1,2,4,8；十位为偶数，个位为 3 , 6 , 7 , 9 3,6,7,9 3,6,7,9。
- 十位为偶数，个位为 1 , 2 , 4 , 8 1,2,4,8 1,2,4,8；十位为奇数，个位为 3 , 6 , 7 , 9 3,6,7,9 3,6,7,9。
- 个位为 0 , 5 0,5 0,5。
如果原序列中所有数不全位于同一组，则无解，否则：
- 若所有数都位于前两组其中一组，有解。
- 若所有数位于第三组，则判断序列中最小值和最大值，如果相差 ≤ 5 leq5 ≤5 且最大值个位为 0 0 0，有解。否则无解。（因为个位为 0 0 0 就变不了了）
#define multiple_test_cases
const int N = 2e5 + 10;
int n, a[N];
void solve(){
n = rdi;
bool flg = false;
int cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= n; ++ i){
a[i] = rdi;
if(a[i]%10 == 5 || a[i]%10 == 0){
flg = true;
}
int tmp = a[i]%10;
if(tmp == 1 || tmp == 2 || tmp == 4 || tmp == 8){
if((a[i]/10) % 2){
++ cnt1;
} else {
++ cnt2;
}
}
if(tmp == 3 || tmp == 6 || tmp == 7 || tmp == 9){
if((a[i]/10) % 2){
++ cnt2;
} else {
++ cnt1;
}
}
}
if(flg){
int mn = a[1], mx = a[1];
for(int i = 2; i <= n; ++ i){
if(a[i]%5){
puts("NO");
return;
}
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
if(mx == mn || (mx == mn + 5 && mx%10 == 0)){
puts("YES");
} else {
puts("NO");
}
} else {
if(cnt1 && cnt2){
puts("NO");
} else {
puts("YES");
}
}
}
F. Build a Tree and That Is It
全场最难题。
如果有解， 1 − 2 , 2 − 3 , 3 − 1 1-2,2-3,3-1 1−2,2−3,3−1 三条路径只有如下四种情况：
接下来具体考虑：
- 若 d 12 , d 23 , d 31 d_{12},d_{23},d_{31} d12,d23,d31 其一大于另两数之和，无解。
- 可以发现四种解中每条路径都在 d 12 , d 23 , d 31 d_{12},d_{23},d_{31} d12,d23,d31 中出现两次，所以若 d 12 + d 23 + d 31 d_{12}+d_{23}+d_{31} d12+d23+d31 为奇数，无解。
- 若 d 12 + d 23 + d 31 > 2 n − 2 d_{12}+d_{23}+d_{31} > 2n-2 d12+d23+d31>2n−2，无解。
- 若 d 12 , d 23 , d 31 d_{12},d_{23},d_{31} d12,d23,d31 其一等于另两数之和，分情况构造左上、左下、右上三种情况。
否则设 1 , 2 , 3 1,2,3 1,2,3 到中间节点 x x x 的三条路径长度分别为 x , y , z x,y,z x,y,z，可以列出方程组：
{ x + y = d 12 y + z = d 23 z + x = d 31 begin{cases}x+y=d_{12}\y+z=d_{23}\z+x=d_{31}end{cases} ⎩ ⎨ ⎧x+y=d12y+z=d23z+x=d31
解得
{ x = ( d 12 − d 23 + d 31 ) ÷ 2 y = ( d 23 − d 31 + d 12 ) ÷ 2 z = ( d 31 − d 12 + d 23 ) ÷ 2 begin{cases}x=(d_{12}-d_{23}+d_{31})div2\y=(d_{23}-d_{31}+d_{12})div2\z=(d_{31}-d_{12}+d_{23})div2end{cases} ⎩ ⎨ ⎧x=(d12−d23+d31)÷2y=(d23−d31+d12)÷2z=(d31−d12+d23)÷2
此时如果 x , y , z x,y,z x,y,z 中不全是整数，无解。否则按照右下图构造即可。
考场代码，很丑。
#define multiple_test_cases
const int N = 2e5 + 10;
int n, d12, d23, d31, fa[N];
void build(int x, int l, int r, int xl, int xr){
stack st;
st.push(x);
int tmp = 4;
for(int i = 1; i < xl; ++ i){
st.push(tmp);
++ tmp;
}
st.push(l);
while(!st.empty()){
int x = st.top();
st.pop();
if(!st.empty()) fa[x] = st.top();
}
st.push(x);
for(int i = 1; i < xr; ++ i){
st.push(tmp);
++ tmp;
}
st.push(r);
while(!st.empty()){
int x = st.top();
st.pop();
if(!st.empty()) fa[x] = st.top();
}
for(int i = tmp; i <= n; ++ i){
fa[i] = 1;
}
}
void buildd(int x, int y, int z){
stack st;
st.push(4);
int tmp = 5;
for(int i = 1; i < x; ++ i){
st.push(tmp);
++ tmp;
}
st.push(1);
while(!st.empty()){
int ww = st.top();
st.pop();
if(!st.empty()) fa[ww] = st.top();
}
st.push(4);
for(int i = 1; i < y; ++ i){
st.push(tmp);
++ tmp;
}
st.push(2);
while(!st.empty()){
int ww = st.top();
st.pop();
if(!st.empty()) fa[ww] = st.top();
}
st.push(4);
for(int i = 1; i < z; ++ i){
st.push(tmp);
++ tmp;
}
st.push(3);
while(!st.empty()){
int ww = st.top();
st.pop();
if(!st.empty()) fa[ww] = st.top();
}
for(int i = tmp; i <= n; ++ i){
fa[i] = 1;
}
}
void solve(){
n = rdi;
d12 = rdi;
d23 = rdi;
d31 = rdi;
if((d12 + d23 + d31) & 1){
puts("NO");
} else if((d12 + d23 + d31) > n+n-2){
puts("NO");
} else {
if(d12 == d23 + d31){
build(3, 1, 2, d31, d23);
} else if(d23 == d12 + d31){
build(1, 2, 3, d12, d31);
} else if(d31 == d12 + d23){
build(2, 1, 3, d12, d23);
} else {
int x = d12 - d23 + d31;
int y = d23 - d31 + d12;
int z = d31 - d12 + d23;
if((x&1) || (y&1) || (z&1) || x<0 || y<0 || z<0){
puts("NO");
return;
} else {
x >>= 1;
y >>= 1;
z >>= 1;
buildd(x, y, z);
}
}
puts("YES");
for(int i = 1; i <= n; ++ i){
if(fa[i]){
write(i);
writen(fa[i]);
fa[i] = 0;
}
}
}
}
G. Path Prefixes
dfs，设 d i s i dis_i disi 表示 1 − i 1-i 1−i 路径上的 a a a 和。用一个栈记录 1 − i 1-i 1−i 路径上每个点到 1 1 1 路径上的 b b b 和。每遍历到一个节点 x x x，在栈中跑二分，找出最大的 ≤ a x leq a_x ≤ax 的值。
#define multiple_test_cases
const int N = 2e5 + 10;
struct edge{
ll a, b;
};
vector > G[N];
ll st[N];
int n, ans[N];
ll dis[N];
void dfs(int x, int fa, int dep){
for(int i = 0; i < G[x].size(); ++ i){
int y = G[x][i].first;
int a = G[x][i].second.a;
int b = G[x][i].second.b;
if(y == fa){
continue;
}
dis[y] = dis[x] + a;
st[dep+1] = st[dep] + b;
int l = 0, r = dep+1;
while(l < r){
int mid = l + r + 1 >> 1;
if(st[mid] <= dis[y]){
l = mid;
} else {
r = mid - 1;
}
}
ans[y] = l;
dfs(y, x, dep+1);
}
}
void solve(){
n = rdi;
for(int i = 2; i <= n; ++ i){
int p = rdi;
int a = rdll;
int b = rdll;
G[p].push_back(make_pair(i, (edge){ a,b }));
}
dfs(1, 0, 0);
for(int i = 2; i <= n; ++ i){
write(ans[i]);
}
endl;
for(int i = 1; i <= n; ++ i){
st[i] = ans[i] = dis[i] = 0;
G[i].clear();
}
}
