B - Longest Palindrome
难度: ⭐
题目大意
找一个字符串中最长的回文子串
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
signed main(){
string s;
cin>>s;
int maxn=1;
int len=s.size();
for(int i=1;i<len;i++){
if(i+1<len&&s[i-1]==s[i+1]){
int x=1;
while(i-x>=0&&i+x<len&&s[i-x]==s[i+x])x++;
x--;
maxn=max(maxn,1+2*x);
}
if(s[i-1]==s[i]){
int x=0;
while(i-1-x>=0&&i+x<len&&s[i-1-x]==s[i+x]) x++;
x--;
maxn=max(maxn,2*(x+1));
}
}
cout<<maxn;
return 0;
}
C - Slot Strategy 2 (Easy)
难度: ⭐⭐
题目大意
现有三个转盘, 每个转盘都是一个长度为n的数列, 数的下标是0~n-1; 对于每个转盘, 我们在t时间按下按钮会得到其中第(t%m)个数; 问我们最短什么时间有在三个转盘上得到三个相同的数, 注意同一时间只能按一个按钮;
解题思路
最差的情况就是三个转盘中只有一个相同的数, 并且这个数在三个转盘上的同一位置, 最差情况就是相当于把这个n的数列重复三次就好了 我们每次都遍历3n, 然后记录当前选择了哪个数, 哪个时间点按下了按钮, 暴力遍历即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, maxn=1e9;
string s1,s2,s3;
int st[N];
signed main(){
cin>>n;
cin>>s1>>s2>>s3;
for(int x1=0;x1<3*n;x1++){
char c = s1[x1%n];
st[x1]=1;
for(int x2=0;x2<3*n;x2++){
if(s2[x2%n]!=c||st[x2]) continue;
st[x2]=1;
for(int x3=0;x3<3*n;x3++){
if(s3[x3%n]!=c||st[x3]) continue;
maxn=min(maxn, max(x1,max(x2,x3)));
}
st[x2]=0;
}
st[x1]=0;
}
if(maxn==1e9) maxn=-1;
cout<<maxn;
return 0;
}
D - Relative Position
难度: ⭐⭐
题目大意
在一个二维坐标系上有n个人, 编号为1~n, 已知1号在坐标原点位置, 现在给出m对关系(a,b,x,y), 即b号相对于a号的坐标; 询问最后每个人的坐标是多少;
解题思路
最初我们已知1号的坐标, 然后给出m个两人之间的相对坐标, 那我们可以用建树的思想, 只要我们知道父节点的坐标, 那么根据相对位置就可以知道它所有子节点的坐标, 所以我们只需要建立无向边, 然后设立1为根节点进行bfs即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, maxn=1e9;
typedef struct stu{
int u,x,y;
}stu;
vector<stu> v[N];
PII d[N];
bool st[N];
void bfs(){
queue<int> q;
q.push(1);
d[1]={0,0};
st[1]=true;
while(q.size()){
int t=q.front();
q.pop();
for(stu k: v[t]){
int u=k.u,x=d[t].first+k.x,y=d[t].second+k.y;
if(!st[u]){
st[u]=true;
d[u]={x,y};
q.push(u);
}
}
}
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,x,y;
cin>>a>>b>>x>>y;
v[a].push_back({b,x,y});
v[b].push_back({a,-x,-y});
}
bfs();
for(int i=1;i<=n;i++){
if(st[i]){
cout<<d[i].first<<' '<<d[i].second<<endl;
}
else cout<<"undecidable"<<endl;
}
return 0;
}
E - Somen Nagashi
难度: ⭐⭐⭐
题目大意
现在有n个人在吃流水面条, n个人按照1到n从前往后排; 一共有m次面条流过来, 来的时间为ti, 数量是wi; 该面条会全部被当前最靠前的人吃掉, 并且吃的时间是si, 在吃面条的时间内不能在去拿流过来的面条, 并且吃完后他还是原来的那个位次; 最后问每个人吃掉的面条个数;
解题思路
数据范围较大, 我们肯定不能每次来面条都遍历所有人; 所以我们可以考虑用堆来维护当前优先吃面条的人; 我们可以开两个优先队列, 一个表示当前没在吃面条的人, 这些人要求按照座次排序; 一个表示正在吃面条的人, 这些人要求按照吃完的时间排序; 对于每次来的面条, 我们可以先遍历第二个优先队列, 把当前吃完面条的人调到第一个优先队列中, 然后再取出第一个优先队列中的第一个人去吃面条, 然后把他放到第二个优先队列中即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, maxn = 1e9;
struct stu {
int v, t;
};
struct cmp1 {
bool operator()(const stu& a, const stu& b) {
return a.v > b.v;
}
};
struct cmp2 {
bool operator()(const stu& a, const stu& b) {
return a.t > b.t;
}
};
int res[N];
priority_queue<stu, vector<stu>, cmp1> heap;
priority_queue<stu, vector<stu>, cmp2> cal;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
heap.push({ i,0 });
}
for (int i = 1; i <= m; i++) {
int t, w, s;
cin >> t >> w >> s;
while (cal.size()&&cal.top().t <= t) {
heap.push(cal.top());
cal.pop();
}
if (heap.empty()) continue;
stu x = heap.top();
heap.pop();
res[x.v] += w;
cal.push({ x.v, t + s });
}
for (int i = 1; i <= n; i++) {
cout << res[i] << endl;
}
return 0;
}
F - Fuel Round Trip
难度: ⭐⭐⭐⭐
题目大意
小莫开车从坐标0出发, 道路上有n个加油站, 坐标分别为X1 ~ Xn, 小莫开车从0到Xn然后再折返回到0; 小莫初始有m升油, 每走一个单位就消耗掉一升油, 对于每个加油站, 小莫可以选择花费Pi元, 加Fi升油, 注意汽车的油箱最多就只能乘m升油, 多加的相当于浪费了; 每个加油站在往返中最多使用一次; 请问小莫最少花费多少元可以完成这次旅行;
解题思路
一道比较特殊的dp, 如果不往返的话就是一道普通的dp, 但是加上返回的情况就比较难想状态的表示, 由于数据范围较小, 所以题解开了一个三维的状态表示, dp[i][j][k]表示从0到达第i个加油站时有j升油, 从终点返回到第i个加油站时有k升油; 对于每个加油站我们可以选择不加油, 去的时候加油, 回来的时候加油这三种状态; 并且要注意, 状态转移时, 我们从第i-1个加油站转移到第i个加油站时, 去时的油量j是减少的, 但是回来时的油量k是增加的(相当于从第i-1个加油站倒回第i个加油站, 怎么说也不对, 反正就那个意思); 这样状态表示也比较好写, 具体见代码; 最后找答案的时候dp[n][i][j]不能直接遍历, 因为按照逻辑, i是去时经过第n个加油站时的油量, j是回来时经过第n个加油站时的油量, i和j之间的区别就在于第n个加油站是否加油, 所以j一定是大于等于i;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 300 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
int X[N], P[N], F[N];
int dp[N][N][N];
signed main() {
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>X[i];
for(int i=1;i<n;i++) cin>>P[i]>>F[i];
memset(dp, 0x3f,sizeof dp);
dp[0][m][0]=0;
for(int i=1;i<=n;i++){
int d=X[i]-X[i-1];
for(int j=0;j<=m;j++){
for(int k=0;k<=m;k++){
int x=j-d, y=k+d;
//去的时候, j是从第i-1个加油站出来时的状态, x是刚到第i个加油站时的状态(还没决定是否加油);
//回来的时候, k是刚到第i-1个加油站时的状态, y是从第i个加油站出来时的状态(已经决定是否加油);
if(x<0||y>m) continue;
//都不加油
dp[i][x][y] = min(dp[i][x][y], dp[i-1][j][k]);
//去时加油
dp[i][min(x+F[i],m)][y] = min(dp[i][min(x+F[i],m)][y], dp[i-1][j][k]+P[i]);
//回来时加油
dp[i][x][max(0ll,y-F[i])] = min(dp[i][x][max(0ll,y-F[i])], dp[i-1][j][k]+P[i]);
}
}
}
int res=1e18;
for(int i=0;i<=m;i++){
for(int j=0;j<=m;j++){
if(j<=i) res=min(res,dp[n][i][j]);
}
}
if(res==1e18) cout<<-1;
else cout<<res;
return 0;
}
- Beginner AtCoder Contest 320 abcbeginner atcoder contest 320 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334