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+并查集 \]为何能使用 \(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;
}