Panasonic Programming Contest 2024（AtCoder Beginner Contest 375）题解

A - Seats

思路：从前往后扫，判断有多少个'.'的左右各有一个'#'

 

#include<bits/stdc++.h>
using namespace std;
#define int long longint n;
string s;signed main()
{cin>>n;cin>>s;int cnt=0;if(s.size()<3){cout<<0<<"\n";return 0;}if(s.size()>=3)for(int i=1;i<=s.size()-2;i++){if(s[i]=='.'&&s[i-1]=='#'&&s[i+1]=='#'){cnt++;}}cout<<cnt<<"\n";return 0;
}

B - Traveling Takahashi Problem

 思路：正常用double模拟一下

#include<bits/stdc++.h>
using namespace std;
#define int long longint n;
double x,y;
signed main()
{double flagx=0,flagy=0;double sum;cin>>n;for(int i=1;i<=n;i++){cin>>x>>y;sum+=sqrt((x-flagx)*(x-flagx)+(y-flagy)*(y-flagy));flagx=x,flagy=y;}sum+=sqrt(flagx*flagx+flagy*flagy);printf("%.7lf",sum);return 0;
}

 

C - Spiral Rotation

题意：就是说，最外层操作一次，然后往里一层就多操作一次，这个操作就是说将整个图顺指针旋转90度，我们可以记录每个点操作多少次，然后直接输出即可

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  int n;  
char s[3005][3005];  
char c[3005][3005];  signed main()  
{  cin >> n;  for(int i = 1; i <= n; i++)  {  for(int j = 1; j <= n; j++)  {  cin >> s[i][j];  }  }  for(int x = 1; x <= n; x++)  {  for(int y = 1; y <= n; y++)  {  int num = min(min(x, n - x + 1), min(y, n - y + 1)) % 4;  if(num == 0) {  c[x][y] = s[x][y]; }  else if(num == 1) {  c[x][y] = s[n - y + 1][x]; }  else if(num == 2) {  c[x][y] = s[n - x + 1][n - y + 1];  }  else if(num == 3) {  c[x][y] = s[y][n - x + 1]; }  }  }  for(int i = 1; i <= n; i++)  {  for(int j = 1; j <= n; j++)  {  cout << c[i][j];  }  cout << "\n";  }  return 0;  
}

D - ABA

思路：一开始我想的使用map<char,vector<int>> 去统计每个字符之前出现的位置，然后都用当前位置进行操作，然后判断有哪些是符合的，然后发现时间复杂度是O(n^2)肯定会超时，后面就想到了优化后的思路

我们可以用一个map<char,int>cnt去统计当前所有字符之前所出现的次数，然后用map<char,int>sum去统计之前出现的字符串的位置和

然后我们每次的贡献就是(i-1)*cnt[s[i]]-sum[s[i]]

输出即可

#include<bits/stdc++.h>
using namespace std;
#define int long longstring s;
map<char,int> mpsum;//统计之前出现的位数总和 
map<char,int> mpcnt;//统计上之前出现的次数 
signed main()
{cin>>s;int sum=0;for(int i=0;i<s.size();i++){sum+=(i-1)*mpcnt[s[i]]-mpsum[s[i]];mpsum[s[i]]+=i;mpcnt[s[i]]++;}cout<<sum;return 0;
}

 E - 3 Team Division

思路：就是看将整个分成三等份最小的操作次数，我们可以用dp去存储将其分成三等份所需的最小步数，dp[j][k]表示前i个分成j和k的容量的最小操作次数

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node
{int x;//表示组数 int y;//表示强度 
}a[105];
int n;
void solve()
{cin>>n;vector<int> pre(n+1,0);for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;pre[i]=pre[i-1]+a[i].y;}if(pre[n]%3!=0){cout<<"-1\n";return ;}int s=pre[n]/3;int f[s+1][s+1];int g[s+1][s+1];memset(f,0x3f3f3f3f,sizeof(f));memset(g,0x3f3f3f3f,sizeof(g));f[0][0]=0;for(int i=1;i<=n;i++){int pos=a[i].x;int val=a[i].y;for(int j=0;j<=s;j++){for(int k=0;k<=s;k++){g[j][k]=0x3f3f3f3f;if(val<=j){g[j][k]=min(g[j][k],f[j-val][k]+(pos!=1));}if(val<=k){g[j][k]=min(g[j][k],f[j][k-val]+(pos!=2));}if(val<=pre[i]-j-k){g[j][k]=min(g[j][k],f[j][k]+(pos!=3));}}}for(int j=0;j<=s;j++){for(int k=0;k<=s;k++){swap(f[j][k],g[j][k]);}}}cout<<(f[s][s]==0x3f3f3f3f?-1:f[s][s])<<"\n";
}signed main()
{int t=1;while(t--)solve();return 0;
}