AtCoder Beginner Contest 375 A-E 题解

我的老师让我先做最后再交，看正确率（即以OI赛制打abc）
所以我用的小号（… …）

C 卡了老半天才出来，我把题读错了

难度：

A. Seats

题意

给你一个字符串 $S$，仅包含 . 和 #，找出子串 #.# 的个数

思路

若下标从 $0$ 开始，直接枚举 $i\in [0,n-3]$ 即可

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int ans;
int main(){cin>>n>>s;for(int i=0;i<n-2;i++){if(s[i]=='#'&&s[i+1]=='.'&&s[i+2]=='#'){ans++;}}cout<<ans<<endl;return 0;
}

B. Traveling Takahashi Problem

题意

给你平面上的 $n$ 个点，第 $i$ 个点坐标为 $(x_i,y_i)$，现在需要从原点 $(0,0)$ 出发，按顺序经过每个点，并回到原点 $(0,0)$，问最终走过的距离。

注：从 $(x_i,y_i)$ 到 $(x_j,y_j)$ 的距离是 $\sqrt{(x_j-x_i{)}^2+(y_j-y_i{)}^2}$

思路

记录上次停留的位置，按顺序模拟即可

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
long double ans;
int n;
int sqr(int x){return x*x;
}
signed main(){cin>>n;int curx=0,cury=0;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;ans+=sqrt(sqr(a-curx)+sqr(b-cury));curx=a,cury=b;}ans+=sqrt(sqr(curx)+sqr(cury));cout<<fixed<<setprecision(20)<<ans<<endl;return 0;
}

C. Spiral Rotation

题意

有一个 $n\ast n$ 的网格（ $n$ 为偶数），设 $(i,j)$ 为从上往下数第 $i$ 行，从左往右数第 $j$ 列的格子，每格要么是 . 要么是 #

对于 i ∈ { 1 , 2 , . . . , n / 2 } i \in \{ 1,2,\ ..., \ n/2\} i∈{1,2, ..., n/2}：

• 选择数对 $(x,y)$ ，其中 $1\le x,y\le n+1-i$，将 $(y,n+1-x)$ 的值换为 $(x,y)$
• 对于所有符合要求的 $(x,y)$，同时 进行以上操作

思路

由 $(y,n+1-x) $ = $(x,y)$ 可得：$(i,j)$ = $(n+1-j,i)$

那么共有以下四种情况：

• $(i,j)=(n+1-j,i)$

• $(n+1-j,i)=(n+1-i,n+1-j)$

• $(n+1-i,n+1-j)=(j,n+1-i)$

• $(j,n+1-i)=(i,j)$

• 下一次就又回到了第一种

所以只要看每一个操作了多少次 $\bmod 4 $ 的余数就可以了

C++ 代码

#include<bits/stdc++.h>
using namespace std;
string s[maxn];
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>s[i];s[i]=" "+s[i];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int curi=(i>k?n-i+1:i);int curj=(j>k?n-j+1:j);int cur=min(curi,curj)%4;if(cur%4==0){cout<<s[i][j];}else if(cur%4==1){cout<<s[n+1-j][i];}else if(cur%4==2){cout<<s[n+1-i][n+1-j];}else{cout<<s[j][n+1-i];}}cout<<endl;}return 0;
}

D. ABA

题意

给你一个字符串 $s$，你要选出三个下标：$1\le i<j<k\le |s|$，将 $s_i,s_j,s_k$ 拼接，使得拼接起来的字符串是 回文串

思路

对于 $26$ 个字母，分别记录每种出现在哪些位置，再统一加减

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> g[26];
string s;
signed main(){int n=sz(s);s=" "+s;for(int i=1;i<=n;i++){g[s[i]-'A'].push_back(i);}int ans=0;for(int i=0;i<26;i++){if(g[i].size()==0) continue;int sum=g[i][0];for(int j=1;j<g[i].size();j++){ans+=(j*g[i][j]-sum-j);sum+=g[i][j];}}cout<<ans<<endl;return 0;
}

E. 3 Team Division

题意

共有 $n$ 个人，已经分成了 $3$ 组，第 $i$ 个人在 $a_i$ 组 $(1\le a_i\le 3)$，权值为 $b_i$，你可以重新分组，使得每组的 权值和 相等，且 换组的人数 最少

问最少换组的人数

思路

首先可以想到 $dp[i][j][k][l]$ 表示：前 $i$ 个里面，第一组权值和为 $j$，第二组权值和为 $k$ ，第三组权值和为 $l$

那么如何优化？去掉最后一维

因为前 $i$ 个人权值和一定，所以直接用总和减去 $j+k$ 就得到了 $l$

C++ 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=2e15;
const int maxn=105;
const int maxk=1505;
int n;
int pos[maxn],v[maxn];
int dp[maxn][maxk][maxk];
int sum[maxn];
signed main(){cin>>n;for(int i=1;i<=n;i++){cin>>pos[i]>>v[i];sum[i]=sum[i-1]+v[i]; //计算前缀和}if(sum[n]%3!=0){//特判：只有和为3的倍数才能分成3组cout<<-1<<endl;return;}for(int i=0;i<=n;i++){//初始化dp数组for(int j=0;j<=sum[i];j++){for(int k=0;k<=sum[i]-j;k++){dp[i][j][k]=inf;}}}dp[0][0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=sum[i];j++){for(int k=0;k<=sum[i]-j;k++){if(j>=v[i]){dp[i][j][k]=min(dp[i-1][j-v[i]][k]+(pos[i]!=1),dp[i][j][k]);}if(k>=v[i]){dp[i][j][k]=min(dp[i-1][j][k-v[i]]+(pos[i]!=2),dp[i][j][k]);}if(sum[i]-j-k>=v[i]){dp[i][j][k]=min(dp[i-1][j][k]+(pos[i]!=3),dp[i][j][k]);}}}}int ans=dp[n][sum[n]/3][sum[n]/3];if(ans==inf){cout<<-1<<endl;}else{cout<<ans<<endl;}return 0;
}