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

标签：Summer typedef Beginner Contest int LL long solve include

A - Count Takahashi (abc359 A)

解题思路

遍历判断即可

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;


void solve(){
    int n;cin>>n;
    int res=0;
    while(n--){
        string s;
        cin>>s;
        res+=(s=="Takahashi");
    }
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B - Couples (abc359 B)

解题思路

枚举i和i+2，判断颜色是否相等

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;


void solve(){
    int n;cin>>n;
    vector<int>a(2*n);
    for(int i=0;i<2*n;i++){
        cin>>a[i];
    }
    int res=0;
    for(int i=0,j=2;j<2*n;i++,j++){
        res+=(a[i]==a[j]);
    }
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

C - Tile Distance 2 (abc359 C)

解题思路

可以发现，dy是一定需要的代价，我们可以计算在dy的代价下，我们能够到达的最左端和最右端l,r，如果x2在这个范围内答案就是0，否则再加上横着走的代价

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;


void solve(){
    LL x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    LL dy=abs(y1-y2);
    
    LL l,r;
    if((x1+y1)%2==0){
        l=x1-dy,r=x1+1+dy;
    }else{
        l=x1-1-dy,r=x1+dy;
    }
    
    if(l<=x2 and x2<=r){
        cout<<dy<<endl;
    }else{
        cout<<(min(abs(r-x2),abs(l-x2))+1>>1)+dy<<endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

D - Avoid K Palindrome (abc359 D)

解题思路

不管时间复杂度的话，搜索显然是正确的，然后尝试用DP优化，如果能够正确维护状态，那么就可以用DP优化，这里只有最后k个数需要维护，于是我们可以状压维护

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

const int N=1100,mod=998244353;
LL f[N][N];
bool st[N];
int n,k;

LL add(LL a,LL b){
    return (a+b)%mod;
}

void solve(){
    cin>>n>>k;
    string s;cin>>s;
    s='?'+s;

    for(int i=0;i<(1<<k);i++){
        vector<int>v(k);
        for(int j=0;j<k;j++)v[j]=i>>j&1;
        vector<int>rv=v;
        reverse(rv.begin(),rv.end());
        st[i]=(v==rv);
    }

    char op[2]={'A','B'};
    f[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<k);j++){
            for(int t=0;t<2;t++){
                if(s[i+1]==op[t] or s[i+1]=='?'){
                    int nj=((j<<1)&((1<<k)-1))+t;
                    if(i+1>=k and st[nj])continue;
                    f[i+1][nj]=add(f[i+1][nj],f[i][j]);
                }
            }
        }
    }

    LL res=0;
    for(int j=0;j<(1<<k);j++)res=add(res,f[n][j]);
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

E - Water Tank (abc359 E)

解题思路

通过把玩样例，可以发现这是一个单调栈的过程，维护即可

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int INF=0x3f3f3f3f;

const int N=2e5+10;
LL a[N];
int n;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<PLL>stk;
    LL sum=0;
    for(int i=1;i<=n;i++){
        LL cnt=1;
        sum+=a[i];
        while(stk.size() and stk.back().first<=a[i]){
            auto [v,c]=stk.back();
            stk.pop_back();
            sum-=v*c;
            sum+=a[i]*c;
            cnt+=c;
        }
        stk.push_back({a[i],cnt});
        cout<<sum+1<<' ';
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

F - Tree Degree Optimization (abc359 F)

解题思路

我们假设连接了一个以1为根的菊花图，此时除了1以外，其余的点的d都是1，然后通过移动连向1的边，发现可以实现任意点d的加1，于是我们先将所有点的d设置为1，剩余的n-2个d贪心的去挑，用优先队列维护每个点的代价

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<stdlib.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int INF=0x3f3f3f3f;

int n;

LL qr(LL x){
    return x*x;
}

void solve(){
    cin>>n;
    vector<LL>a(n),c(n,1);
    LL res=0;
    for(int i=0;i<n;i++)cin>>a[i],res+=a[i];
    priority_queue<PLL,vector<PLL>,greater<PLL>>q;
    
    auto cal = [&](int i){
        return ((c[i]+1)*(c[i]+1)-(c[i]*c[i]))*a[i];
    };

    for(int i=0;i<n;i++){
        q.push({cal(i) , i});
    }

    for(int i=0;i<n-2;i++){
        auto [v1,id1]=q.top();
        q.pop();
        res+=v1;
        c[id1]++;
        q.push({cal(id1) , id1});
    }
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

G - Sum of Tree Distance (abc359 G)

解题思路

树上2个点a,b之间的距离可以转化为dep(a)+dep(b)-2dep(lca(a,b))，这里也是一样，我们分别对dep(a)+dep(b)和2dep(lca(a,b))进行求和，前面的直接扫一遍即可，后面的可以枚举每个点作为lca,然后使用启发式合并来计算贡献

神奇的代码

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<cstring>
#include<stdlib.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int INF=0x3f3f3f3f;

const int N=2e5+10;
vector<int>G[N];
map<int,int> p[N];
LL sum[N],cnt[N],d[N];
int a[N];
int n;
LL res;

void dfs(int u,int fa){
    for(auto &v:G[u]){
        if(v==fa)continue;
        d[v]=d[u]+1;
        dfs(v,u);
    }
}

void dfs2(int u,int fa){
    for(auto &v:G[u]){
        if(v==fa)continue;
        dfs2(v,u);
        if(p[u].size()<p[v].size())swap(p[u],p[v]);
        for(auto [v,c]:p[v]){
            res-=2ll*p[u][v]*c*d[u];
            p[u][v]+=c;
        }    
    }
    res-=2ll*p[u][a[u]]*d[u];
    p[u][a[u]]++;
}


void solve(){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,-1);
    for(int i=1;i<=n;i++){
        res+=sum[a[i]]+d[i]*cnt[a[i]];
        sum[a[i]]+=d[i],cnt[a[i]]++;
    }
    dfs2(1,-1);
    cout<<res<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

标签：Summer,typedef,Beginner,Contest,int,LL,long,solve,include
From： https://www.cnblogs.com/F-beginner/p/18263172

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

A - Count Takahashi (abc359 A)

解题思路

B - Couples (abc359 B)

解题思路

C - Tile Distance 2 (abc359 C)

解题思路

D - Avoid K Palindrome (abc359 D)

解题思路

E - Water Tank (abc359 E)

解题思路

F - Tree Degree Optimization (abc359 F)

解题思路

G - Sum of Tree Distance (abc359 G)

解题思路

相关文章

赞助商

阅读排行