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);
}
从右往左遍历,记录每一个数出现的次数。
#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;
}
显然答案类似于 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");
}
???
暴力。枚举第 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;
}
}
考虑每种个位:
所以我们可以把所有数按个位以及十位的奇偶性分为三组:
如果原序列中所有数不全位于同一组,则无解,否则:
#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");
}
}
}
全场最难题。
如果有解, 1 − 2 , 2 − 3 , 3 − 1 1-2,2-3,3-1 1−2,2−3,3−1 三条路径只有如下四种情况:
接下来具体考虑:
否则设 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
解得
{
x
=
(
d
12
−
d
23
+
d
31
)
÷
2
y
=
(
d
23
−
d
31
+
d
12
)
÷
2
z
=
(
d
31
−
d
12
+
d
23
)
÷
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<int> 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<int> 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;
}
}
}
}
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<pair<int, edge> > 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();
}
}