AC修炼计划（AtCoder Beginner Contest 334）A~G

传送门：UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) - AtCoder

A题是最最基础的语法题就不再讲解。

B - Christmas Trees

该题虽然分低，但我觉得还是很不错的。

给你 l 和 r ，设满足题意的数字是x则让你找在区间中有多少个x是x%k==a%k。我们要算出左右满足题意的两端点值，而后可以求出。左端点向上取整，右端点向下取整。

分别是l+=((x-l%m)%m+m)%m? ? 以及r-=((r%m-x)%m+m)%m。

最后可以算出答案。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;

void icealsoheat(){
    int a,l,r;
    cin>>a>>m>>l>>r;
    int x=a%m;

    l+=((x-l%m)%m+m)%m;
    r-=((r%m-x)%m+m)%m;
    if(l>r)cout<<"0";
    else cout<<(r-l)/m+1;


    

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

C - Socks 2

这题比较经典。看到绝对值我们首先就要想到拆绝对值，则有数量相等的正负数。2*n-k为偶数的话，我们就直接计算就可以了。若为奇数，我们可以提前预处理出前缀和而后遍历每一个数去除来求最小值。注意去除当前数，后面的后缀和应该变成相反数，才是最终答案。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;
int k;
void icealsoheat(){
    cin>>n>>k;
    vector<int>a(n+5,2);
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        a[x]=1;
    }
    if((2*n-k)&1){
        int id=0;
        vector<int>sum(2*n+5,0);
        for(int i=1;i<=n;i++){
            id++;
            if(id&1){
                sum[id]=sum[id-1]-i;
            }
            else sum[id]=sum[id-1]+i;
            if(a[i]==2){
                id++;
                if(id&1)sum[id]=sum[id-1]-i;
                else sum[id]=sum[id-1]+i;
            }
        }
        int ans=MX;
        for(int i=1;i<=2*n-k;i++){
            ans=min(ans,sum[i-1]-(sum[2*n-k]-sum[i]));
        }
        cout<<ans;
    }
    else{
        int id=0;
        int ans=0;
        for(int i=1;i<=n;i++){
            id++;
            if(id&1)ans-=i;
            else ans+=i;
            if(a[i]==2){
                id++;
                if(id&1)ans-=i;
                else ans+=i;
            }
        }
        cout<<ans;
    }
    

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

D - Reindeer and Sleigh

前缀和加二分操作，太经典了就不多说了。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,q;
int k;
int a[500005];
int sum[500005];
void icealsoheat(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        if(x<sum[1]){
            cout<<"0\n";
            continue;
        }
        int l,r,mid;
        l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(sum[mid]<=x)l=mid;
            else r=mid-1;
        }
        cout<<l<<"\n";
    }
    

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

E - Christmas Color Grid 1

通过dfs求解出联通量的个数，而后暴力枚举每一个红色，情况还是挺好特判的，要用到逆元。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;
int k;
string s[500005];
int kuai(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void icealsoheat(){
    cin>>n>>m;
    vector<vector<int>>c(n+5,vector<int>(m+5,0));
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]='-'+s[i];
    }
    int an=0;
    auto dfs=[&](auto self,int x,int y)->void{
        for(int i=0;i<4;i++){
            int xx=dx[i]+x;
            int yy=dy[i]+y;
            if(xx>0&&xx<=n&&yy>0&&yy<=m&&c[xx][yy]==0&&s[xx][yy]=='#'){
                c[xx][yy]=an;
                self(self,xx,yy);
            }
        }
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'&&!c[i][j]){
                an++;
                c[i][j]=an;
                dfs(dfs,i,j);
            }
        }
    }
    int sum=0;
    int cnt=0;
    // cout<<an<<"***\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='.'){
                sum++;
                set<int>q;
                for(int o=0;o<4;o++){
                    int xx=dx[o]+i;
                    int yy=dy[o]+j;
                    if(xx>0&&xx<=n&&yy>0&&yy<=m&&s[xx][yy]=='#'){
                        q.insert(c[xx][yy]);
                    }
                }
                if(!q.size())cnt+=an+1;
                else cnt+=an-q.size()+1;
                // cout<<cnt<<"---\n";
            }
        }
    }
    // cout<<cnt<<"+++"<<sum<<"+++\n";
    cout<<cnt%mod*kuai(sum,mod-2)%mod;

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

F - Christmas Present 2

这题感觉还是挺好的。首先想到是dp的思想，但暴力dp是O(n*n)的复杂度，显然，会t。而后我们开始想他的优化。我们想要算得的就是贡献值也就是从当前点回到家所产生的距离值和正常到下一个点儿的差（三角形任意两边之和大于第三边，所以正常情况是比回家的情况小的）。这个差值越小越好，同时我们还要保证两个回家的点儿之间差不超过k。我们用dp来迭代这个差值。优化dp的方式我们可以用单调队列的方式进行求解，以此来满足条件，并尽可能的使改变的值变少。

代码如下：

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,k;
double s[500005];
double sum[500005];
double xx[500005];
double yy[500005];
double suan(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void icealsoheat(){
    cin>>n>>k;
    double xe,ye;
    cin>>xe>>ye;
    for(int i=1;i<=n;i++)cin>>xx[i]>>yy[i],s[i]=suan(xx[i],yy[i],xe,ye);
    for(int i=2;i<=n;i++)sum[i]=sum[i-1]+suan(xx[i],yy[i],xx[i-1],yy[i-1]);
    vector<double>dp(n+5,0);
    int l=1,r=0;
    vector<int>id(n+5,0);
    #define d(i) dp[i]-sum[i+1]+s[i+1]

    for(int i=1;i<=n;i++){
        while(l<=r&&d(id[r])>d(i-1))r--;
        id[++r]=i-1;
        while(l<=r&&id[l]<i-k)l++;
        dp[i]=d(id[l])+s[i]+sum[i];
    }
    printf("%.10lf",dp[n]);

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

G - Christmas Color Grid 2

写的时候忘记了，其实也是很经典的双端强连通分量问题。也是很板子，双端强连通分量可以解决无向图中去掉一个点求剩下强两桶分量的问题。详情可以看AcWing 1183. 电力 - AcWing

代码如下：

#pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,m;
// vector<string>s(500005);
string s[500005];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int kuai(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}
int co[1000005];
int dfn[1000005];
int low[1000005];
int hh[1000005];
int num;
int top;
int col;
void icealsoheat(){
    int ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        ans+=count(s[i].begin(),s[i].end(),'#');
    }
    int an=0;
    vector<vector<int>>c(n+5,vector<int>(m+5,0));
    vector<vector<int>>ve(1000005);
    auto dfs=[&](auto self,int x,int y)->void{

        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='#'&&c[xx][yy]==0){
                c[xx][yy]=an;
                // ve[x*m+y].push_back(xx*m+yy);
                // ve[xx*m+yy].push_back(x*m+y);
                self(self,xx,yy);
            }
        }
    };
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'&&c[i][j]==0){
                c[i][j]=++an;
                dfs(dfs,i,j);
            }
            if (s[i][j] == '#')
                for (int k = 0; k < 4; k ++ ){}
                    int av = i + dx[k], bv = j + dy[k];
                    if (av<0||av>=n||bv<0||bv>=m) continue;
                    if (s[av][bv]!='#') continue;
                    ve[i*m+j].push_back(av*m+bv);
                    ve[av*m+bv].push_back(i*m+j);
                }
        }
    }

    auto tarjan=[&](auto self,int u,int fa)->void{
        dfn[u]=low[u]=++num;
        int cnt=0;
        for(auto v:ve[u]){
            if(dfn[v]==0){
                self(self,v,u);
                low[u]=min(low[u],low[v]);
                if(dfn[u]<=low[v]){
                    cnt++;
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
        if(fa!=-1)cnt++;
        hh[u]=cnt;
    };

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'&&!dfn[i*m+j]){
                tarjan(tarjan,i*m+j,-1);
            }
        }
    }

    // cout<<ans<<"---\n";
    int chu=kuai(ans,mod-2)%mod;
    ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                ans+=an-1+hh[i*m+j];
                // cout<<an-1+hh[i*m+j]<<"++++\n";
                ans%=mod;
            }
        }
    }
    cout<<ans*chu%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}