UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)

发表于 2024-06-25 分类于 atcoder

UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)

Complete problemset

C - Tile Distance 2

题意

问题陈述

坐标平面上覆盖有 $2\times1$ 瓷砖。瓷砖按照以下规则排列:

对于整数对 $(i,j)$ ，正方形 $A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace$ 包含在一个平铺中。
当 $i+j$ 为偶数时， $A _ {i,j}$ 和 $A _ {i + 1,j}$ 包含在同一块瓷砖中。

瓷砖包括它们的边界，没有两个不同的瓷砖共享一个正面区域。

在原点附近，瓷砖的布局如下:

高桥从坐标平面上的点 $(S _ x+0.5,S _ y+0.5)$ 开始。

他可以随心所欲地重复以下动作:

选择一个方向(上、下、左或右)和一个正整数 $n$ 。向该方向移动 $n$ 个单位。

每次他进入一个瓦片，他支付的通行费为 $1$ 。

找到他必须支付到达点 $(T _ x+0.5,T _ y+0.5)$ 的最低通行费。

思路

为了便于找规律。

一个方块有两个单元格，我们将起点和终点都统一移动到所属方块的右侧单元格，发现如果行列坐标同奇偶性那么就位于方块左侧单元格。

对于y坐标我们一定会通过$|T_y-S_y|$个边界。

对于x坐标需要通$\frac{|T_x-S_x|}{2}$个边界，实际上通过一个y方向的边界可以减少一个x方向的边界

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    ll sx, sy;
    ll tx, ty;
    cin >> sx >> sy;
    cin >> tx >> ty;
    if (sx%2 == sy%2) sx++;
    if (tx%2 == ty%2) tx++;
    // cout << sx << " " << sy << endl;
    // cout << tx << " " << ty << endl;
    ll dy = abs(ty-sy);
    ll dx = abs(tx-sx);
    cout << dy+max(0LL, dx/2-dy/2) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D - Avoid K Palindrome

题意

问题陈述

您得到一个长度为 $N$ 的字符串 $S$ ，由字符‘ A’、‘ B’和‘ ?’组成。

您还将获得一个正整数 $K$ 。包含“ A”和“ B”的字符串 $T$ 如果满足以下条件，则被认为是 好字符串:

$T$ 中长度为 $K$ 的不连续子串是回文。

让 $q$ 是“ ？“ $S$ 中的字符。有 $2^q$ 字符串可以通过替换每个‘ ？在 $S$ 中加上“ A”或“ B”。找出这些字符串中有多少是好字符串。

计数可能非常大，因此请找到它的模数 $998244353$ 。

$2 \leq K \leq N \leq 1000$
$K \leq 10$
$S$ is a string consisting of A, B, and ?.
The length of $S$ is $N$.
$N$ and $K$ are integers.

思路

状态压缩dp

$f_{i,j}$代表前i个字符末尾k个字符的状态为j的时候且非回文串，的方案数。

$f_{i,j} = \sum f_{i-1, j’}$，$j$和$j’$非回文串，且类似滑动窗口只存在最高位和最低位的差异。$O(1)$可以通过$j$计算得出$j’$

总复杂度$O(n2^k)$

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

bool isPalindrome(int x, int k) {
    for (int i=0; i<k/2; i++) {
        if ((x>>i&1) != (x>>(k-i-1)&1)) return false;
    }
    return true;
}

void sol() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int msk = (1<<k);
    vector f(n, vector<int>(1<<k));
    for (int j=0; j<msk; j++) {
        if (isPalindrome(j, k)) continue;
        int ok = 1;
        for (int t=0; t<k; t++) {
            int c = (j>>t&1);
            if ('A'+c != s[k-t-1] && s[k-t-1] != '?') ok = 0;
        }
        if (ok) {
            f[k-1][j]++;
        }
    }
    for (int i=k; i<n; i++) {
        for (int j=0; j<msk; j++) {
            if (isPalindrome(j, k)) continue;
            int ok = 1;
            for (int t=0; t<k; t++) {
                int c = (j>>t&1);
                if ('A'+c != s[i-t] && s[i-t] != '?') ok = 0;
            }
            if (ok) {
                if (!isPalindrome(j>>1, k)) f[i][j] = (f[i][j] + f[i-1][j>>1]) % MOD;
                if (!isPalindrome(j>>1 | (1<<(k-1)), k)) f[i][j] = (f[i][j] + f[i-1][j>>1 | (1<<(k-1))]) % MOD;
            }
        }
    }
    // cout << f << endl;
    int ans = 0;
    for (int i=0; i<msk; i++) {
        ans += f[n-1][i];
        ans %= MOD;
    }
    cout << ans << endl;
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E - Water Tank

题意

问题陈述

给定一个长度为 $N$ : $H=(H _ 1,H _ 2,\dotsc,H _ N)$ 的正整数序列。

有一个长度为 $N+1$ : $A=(A _ 0,A _ 1,\dotsc,A _ N)$ 的非负整数序列。最初， $A _ 0=A _ 1=\dotsb=A _ N=0$ 。

在 $A$ 上重复执行下列操作:

将 $A _ 0$ 的值增加 $1$ 。
对于此顺序中的 $i=1,2,\ldots,N$ ，执行以下操作:

如果 $A _ {i-1}\gt A _ i$ 和 $A _ {i-1}\gt H _ i$ ，则将 $A _ {i-1}$ 的值减少1，并将 $A _ i$ 的值增加 $1$ 。

对于每个 $i=1,2,\ldots,N$ ，查找第一次保持 $A _ i>0$ 之前的操作数。

$1\leq N\leq2\times10 ^ 5$
$1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N)$
All input values are integers.

input
5
3 1 4 1 5

output
4 5 13 14 26

思路

通过图片发现，就是单调栈，找左侧第一个最近一个大于自身的位置，然后计算这段区间的水量，在用个dp，保留前缀子问题的答案，当前区间的水量加上区间左端前的前缀答案就是当前的答案。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    ll n;
    cin >> n;
    vector<ll> a(n+1, 1e9+7), st(1, 0);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    vector<ll> ans(n+1, 0);
    for (int i=1; i<=n; i++) {
        while (a[st.back()] < a[i]) st.pop_back();
        ans[i] = (i-st.back())*a[i]+ans[st.back()];
        // cout << i <<  " " << st.back() << "\n";
        st.push_back(i);
    }
    // cout << ans << "\n";
    for (int i=1; i<=n; i++) {
        cout << ans[i]+1 << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

F - Tree Degree Optimization

题意

问题陈述

给定一个整数序列 $A=(A_1,\ldots,A_N)$ 。对于具有 $N$ 顶点的树 $T$ ，定义 $f(T)$ 如下:

设 $d_i$ 为 $T$ 中顶点 $i$ 的度。然后， $f(T)=\sum_{i=1}^N {d_i}^2 A_i$ 。

查找可能的最小值 $f(T)$ 。

约束保证答案小于 $2^{63}$ 。

$2\leq N\leq 2\times 10^5$
$1\leq A_i \leq 10^9$
All input values are integers.

思路

总的度数$\sum d_i = 2n-2$

先初始化所有$d_i=1$

对于$d_i^2A_i$和$d_j^2A_j$，让$d_i$还是$d_j$增长1取决于谁增长的贡献较少。

二者增长1分别会增长贡献$(2d_i+1)A_i$和$(2d_j+1)A_j$

所以可以用优先队列维护最小的增长值，n-2次出队和入队就得到了$d$序列。

然后计算答案$\sum d_i^2A_i$

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}


void sol() {
    ll n;
    cin >> n;
    vector<ll> a(n+1, 1e9+7), st(1, 0);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
    }
    vector<ll> ans(n+1, 0);
    for (int i=1; i<=n; i++) {
        while (a[st.back()] < a[i]) st.pop_back();
        ans[i] = (i-st.back())*a[i]+ans[st.back()];
        // cout << i <<  " " << st.back() << "\n";
        st.push_back(i);
    }
    // cout << ans << "\n";
    for (int i=1; i<=n; i++) {
        cout << ans[i]+1 << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}