ABC335总结
A.202<s>3</s>
翻译
给你一个由小写英文字母和数字组成的字符串 \(S\)。
\(S\) 保证以 2023
结尾。
将 \(S\) 的最后一个字符改为 4
,并打印修改后的字符串。
分析
两种做法:
- 直接把最后一个字符改为
4
,然后输出。 - 输出前 \(n\) 个字符后输出
4
。
code
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int main ()
{
string s;
cin>>s;
for(int i=1;i<s.size();i++) cout<<s[i-1];
cout<<4<<"\n";
//string s;
//cin>>s;
//s[s.size()-1]='4';
//cout<<s<<"\n";
return 0;
}
B.Tetrahedral Number
翻译
给你一个整数 \(N\)。
请按字典序升序输出所有与 \(x+y+z\leq N\) 相等的非负整数 \((x,y,z)\) 的三元组。
什么是非负整数三元组的字典序?
当且仅当以下条件之一成立时,非负整数\((x,y,z)\)的三元组字典序小于\((x',y',z')\):
- \(x < x'\);
- \(x=x'\)和\(y< y'\);
- \(x=x'\)和\(y=y'\)及\(z< z'\)。
分析
暴力算法,三层循环加判断解决。
code
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,t,a[N];
int main ()
{
cin>>n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int l=0;l<=n;l++)
if(i+j+l<=n) printf("%d %d %d\n",i,j,l);
return 0;
}
C.Loong Tracking
翻译
高桥制作了一款游戏,玩家要在坐标平面上控制一条龙。
龙由\(N\)部分组成,编号为\(1\)至\(N\),其中\(1\)部分称为头。
最初,\(i\)部分位于坐标\((i,0)\)处。过程\(Q\)查询如下。
1 C
:将头部向\(C\)方向移动\(1\)。这里,\(C\)是 "R"、"L"、"U "和 "D "中的一个,分别代表正\(x\)/方向、负\(x\)/方向、正\(y\)/方向和负\(y\)/方向。除头部外,其他每个部分都会跟随前面的部分移动。也就是说,\(i\)部分\((2\leq i \leq N)\) 移动到部件 \(i-1\) 移动前的坐标位置。2 p
:找出部件 \(p\) 的坐标。
分析
一段固定长度的区间,需要做到在头部插入尾部删除,则可以使用双端队列进行维护,查询操作直接访问即可。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+5;
int n,m,a[N];
deque<PII> q;
void insert(char p)
{
PII u=q.front();
int x=u.first,y=u.second;
if(p=='R') q.push_front({x+1,y});
else if(p=='L') q.push_front({x-1,y});
else if(p=='U') q.push_front({x,y+1});
else q.push_front({x,y-1});
q.pop_back();
}
int main ()
{
cin>>n>>m;
int op,p;
char c;
for(int i=1;i<=n;i++) q.push_back({i,0});
while(m--)
{
cin>>op;
if(op==1) cin>>c,insert(c);
else cin>>p,cout<<q[p-1].first<<" "<<q[p-1].second<<"\n";
}
return 0;
}
D.Loong and Takahashi
翻译
问题陈述
有一个网格,网格中有 \(N\) 行和 \(N\) 列,其中 \(N\) 是奇数,最多为 \(45\)。
让 \((i,j)\) 表示从上往下第 \(i\) 行,从左往上第 \(j\) 列的单元格。
在这个网格中,你将放置高桥和一条由\(N^2-1\)部分组成的龙,这些部分的编号为\(1\)至\(N^2-1\),以满足以下条件:
- 高桥必须放在网格的中心,即\((\frac{N+1}{2},\frac{N+1}{2})\)单元格。
- 除了高桥所在的单元格外,每个单元格中都必须放置一个龙形部件。
- 对于每个满足\(2 \leq x \leq N^2-1\)的整数\(x\),龙部件\(x\)必须放置在与包含部件\(x-1\)的单元格相邻的单元格中。
- 当且仅当 \(|i-k|+|j-l|=1\) 时,单元格 \((i,j)\) 和 \((k,l)\) 被认为是相邻的。
打印一种满足条件的部件排列方式。保证至少有一种排列方式满足条件。
分析
固定一种走法,顺时针绕圈走,方向依次为右下左上。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50;
int n,f[6][5]={{0,1},{1,0},{0,-1},{-1,0}};
int a[N][N];
int main ()
{
cin>>n;
int x=1,y=0,t=0;
for(int i=1;i<=n*n-1;i++)
{
int u=x+f[t][0],v=y+f[t][1];
if(u>=1&&u<=n&&v>=1&&v<=n&&a[u][v]==0) a[u][v]=i;
else
{
t=(t+1)%4;
u=x+f[t][0],v=y+f[t][1];
a[u][v]=i;
}
x=u,y=v;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==(n+1)/2&&j==(n+1)/2) cout<<"T"<<" ";
else cout<<a[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}
E.Non-Decreasing Colorful Path
翻译
有一个连通的无向图,图中有 \(N\) 个顶点和 \(M\) 条边,其中 \(i\) 条边双向连接顶点 \(U_i\) 和顶点 \(V_i\)。
每个顶点上都写有一个整数,顶点\(v\)上写有整数 \(A_v\)。
对于从顶点 \(1\) 到顶点 \(N\) 的简单路径(一条不多次通过相同顶点的路径),分数的确定方法如下:
- 假设 \(S\) 是写在路径沿线顶点上的整数序列,按照顶点被访问的顺序排列。
- 如果 \(S\) 不是非递减,则该路径的得分为 \(0\)。
- 否则,得分就是 \(S\) 中不同整数的个数。
找出所有简单路径中得分最高的从顶点 \(1\) 到顶点 \(N\) 的路径,并打印该得分。
\(S\) 不递减是什么意思?长度为 \(l\) 的序列 \(S=(S_1,S_2,\dots,S_l)\) 是非递减的,当且仅当 \(S_i \le S_{i+1}\) 为所有整数 \(1 \le i < l\) 时。
分析
算是一道好题,思路比较清奇,一般想法是找到所有简单路径然后判断是否为非递减,计算答案。但所有简单路径的枚举太浪费时间,所以考虑其他做法。
为何能使用 \(dp\)?
点权大的点一定是由点权小的点推导过来的,否则该路径答案就为零,相当于无意义。其次,若所有比 \(i\) 点小的且与 \(i\) 点连通的点已经都用来更新过 \(i\) 点,则 \(i\) 点的值不会再被改变,即满足无后效性。只需要按点权的大小排序,按照边的信息进行更新即可。
需要明确一点,由于一条路径上相同的点权只会贡献一个,所以对于相邻的点权相同的点,把他们压缩成一个,使答案记录在最靠近点 \(1\) 的点上。这样就不用考虑两点权值相同的情况,存边时只用存从点权小的到点权大的边即可。
code
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],f[N],dp[N];
struct node
{
int w,u,v;
};
vector<node> b;
bool cmp(node x,node y)
{
return x.w<y.w;
}
int find(int x)
{
if(f[x]==x) return x;
else return f[x]=find(f[x]);
}
int main ()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],f[i]=i;
for(int i=1,u,v;i<=m;i++)
{
cin>>u>>v;
if(a[u]>a[v]) swap(u,v);
if(a[u]==a[v]) f[find(v)]=find(u);//将v并入u
else b.push_back({a[u],u,v});
}
sort(b.begin(),b.end(),cmp);
memset(dp,-0x3f,sizeof(dp));
dp[find(1)]=1;
for(auto x : b)
{
int u=find(x.u),v=find(x.v);
dp[v]=max(dp[v],dp[u]+1);
}
cout<<max(0,dp[find(n)])<<"\n";
return 0;
}
- Beginner AtCoder Contest 335beginner atcoder contest 335 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310 beginner atcoder contest 327 beginner atcoder contest 332