2020 ICPC Universidad Nacional de Colombia Programming Contest 题解
M. Magic spells
题意：
一个模式串 \(T\) ，以及 \(n\) 个文本 \(s\)
输出 \(T\) 包含 \(s\) 前缀的最长子序列
思路：
处理模式串，依次记录所有字符出现的位置
在匹配文本串时，通过二分查找大于 模式串当前匹配位置后是否还有相同的字符，找到第一个出现的位置，并更新匹配位置
总复杂度为 \(O(log(len_t)*len_s)\)
K. Katastrophic sort
题意：
一个字符串由两个部分构成 字母部分和数字部分
给出两个字符串，比较字典序大小
其中数字部分的大小比较为真实数字的大小比较
如 "11" 表示 11 > "2" 表示 2
思路：
对字符串部分和数字部分分别处理一下即可
G. Great dinner
题意：
给定固定序列 \(n\) , 其中 \(m\) 个固定顺序求出满足该顺序要求的排列数量
思路：
观察可得规律 \(n! / 2^m\)
E. Enter to the best problem of this contest!
题意：
交互题
给出一个完全二叉树，标号如下
给定树的深度为 \(n\) , 你可以询问最多不超过29次
询问一个节点 \(x\) , 将会得到需要猜出的节点与当前询问节点的最短距离。
输出 \(!x\) 表示猜出的节点
思路:
从根节点开始
询问 1 , 得到需要猜出节点的距离（深度），为 0 则结束
当前所猜节点深度小于所需要猜出节点深度时，询问左儿子。如果距离增大则在右子树，否则在左子树。到达猜出节点深度时，向同层的兄弟节点移动。
所猜次数 小于等于 \(log(n)\)
B. Baby name
题意
给出两个串，取两个串中的子串并按顺序拼接为一个串，使得该串字典序最大
思路
首先如何找到一个串的字典序最大的字串？
记录字符串中最大字母出现的位置，最大位置连续的只记录第一个出现的位置（第一个位置字典序最大）
依次比较每个起始位置的字典序大小，复杂度 \(0(n)\) 常数有点大
code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
char s[maxn],s1[maxn];
int ms[maxn],ms1[maxn];
int m,m1,cur,cur1;
//处理最大字典序子串，依次比较，2n复杂度
int func(int mss[],char ss[],int len,int cur){
int ans = mss[0];
for (int i = 1; i <= cur; ++i) {
int tmp = mss[i];
int a = ans;
while (tmp < len && ss[a] == ss[tmp]) {
a++;
tmp++;
}
if (tmp < len && ss[a] < ss[tmp]) ans = mss[i];
}
return ans;
}
int main(){
scanf("%s %s",s,s1);
int len = strlen(s);
int len1 = strlen(s1);
ms[0] = ms1[0] = 0;
m = cur = 0;
//找到该串最大字母的位置
for(int i=1;i<len;i++){
if(s[i] > s[m]){
m = i;
cur = 0;
ms[cur] = i;
//重复长度以首位置为起点,必然最大
while(i<len && s[i+1]==s[i]) ++i;
}else if(s[i]==s[m]){
ms[++cur] = i;
while(i<len && s[i+1]==s[i]) ++i;
}
}
m1 = cur1 = 0;
for(int i=1;i<len1;i++){
if(s1[i] > s1[m1]){
m1 = i;
cur1 = 0;
ms1[cur1] = i;
//重复长度以首位置为起点,必然最大
while(i<len1 && s1[i+1]==s1[i]) ++i;
}else if(s1[i]==s1[m1]){
ms1[++cur1] = i;
while(i<len1 && s1[i+1]==s1[i]) ++i;
}
}
int res1 = func(ms,s,len,cur);
int res2 = func(ms1,s1,len1,cur1);
printf("%c",s[res1]);
res1 += 1;
while(res1<len && s[res1] >= s1[res2])
printf("%c",s[res1++]);
for(int i=res2;i<len1;i++){
printf("%c",s1[i]);
}
//puts("");
}
L. Lonely day
题意
给定一个 \(n\times m\) 的图，途中的$ ’S’ \(为起点，\)E$ 为终点。每次移动只能横向或纵向地移向最近的一个干净的点 \('.'\) 或终点，\('X'\) 为脏的点。如果能到达终点，则输出步数最少并且字典序最小的路径（下移为D、左移为L、右移为R、上移为U）。否则输出-1
思路
最短路径 \(BFS\) , 按照字典序大小放到队列中, 这样第一个到达终点的即为字典序最小且步数最小的路径
记录前驱，从终点进行dfs递推回起点
code
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define _for(i,a,b) for(int i=a;i<=b;++i)
#define _rep(i,a,b) for(int i=a;i>=b;--i)
const int maxn = 2e3+10;
int n,m;
int sx,sy;
int vis[maxn][maxn];
int pre_x[maxn][maxn];
int pre_y[maxn][maxn];
int dir[][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char dirr[] = "DLRU";
char ans[maxn<<1];
int cnt =0;
char G[maxn][maxn];
struct node
{
int x,y;
};
bool check(int x ,int y){
if(x < 1 || x > n || y < 1 || y > m ) return false;
return true;
}
void dfs(int x,int y){
if(x == sx && y== sy){
cout<<cnt<<endl;
_rep(i,cnt-1,0){
cout<<ans[i];
}
return ;
}
int prex = pre_x[x][y];
int prey = pre_y[x][y];
if(prey == y){
if(prex < x) ans[cnt++] = dirr[0];
else ans[cnt++] = dirr[3];
}else{
if(prey < y) ans[cnt++] = dirr[2];
else ans[cnt++] = dirr[1];
}
dfs(prex,prey);
}
void bfs(){
queue<node> q;
q.push(node{sx,sy});
vis[sx][sy] = 1;
while(!q.empty()){
node u = q.front();
q.pop();
if(G[u.x][u.y] == 'E') {
dfs(u.x,u.y); //回溯路径
return ;
}
_for(i,0,3){
int nex = u.x + dir[i][0];
int ney = u.y + dir[i][1];
while(check(nex,ney)){
if(vis[nex][ney]) break;
if(G[nex][ney] == '.' || G[nex][ney] == 'E'){
vis[nex][ney] = 1;
pre_x[nex][ney] = u.x;//上一个点位置
pre_y[nex][ney] = u.y;
q.push(node{nex,ney});
break;
}
//没找到 . 或者 e 之前一直移动直到移出边界
nex += dir[i][0], ney += dir[i][1];
}
}
}
cout<<-1<<endl;
}
int main(){
IOS
cin>>n>>m;
_for(i,1,n){
_for(j,1,m){
cin>>G[i][j];
if(G[i][j] == 'S') sx = i,sy = j;
}
}
bfs();
return 0;
}
A. Approach
题意
给定二维坐标轴上给出四个点\(A,B,C,D\) , 其中 \(AB\) 、 \(CD\) 分别组成两组线段。现有两个点从线段\(AB\) ， \(CD\) 的起点，\(A\) 和 \(C\) 以相同的速度同时出发到另一个端点。到达终点的点不再移动，直到两个点均到达终点即结束。
求出两点间的最短距离
思路
两点间的距离是一个凹函数，所以采取典型的三分方法来进行缩小范围。同时由于精度的问题，要注意三分次数。
由于两个点有可能其中一个点停止时另一个点仍在移动，所以可以分为两段时间来计算。
- 没有点到达终点
- 第一个到达终点 - 所有到达终点
然后对于点所在下标，先使用tan2处理与 \(x\) 轴的夹角 \(\delta\) , 然后再使用 \(cos,sin\) 函数转换 \(x,y\) 方向的移动距离
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
template <typename T>
inline void rd(T& x)
{
ll tmp = 1; char c = getchar(); x = 0;
while (c > '9' || c < '0') { if (c == '-')tmp = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
x *= tmp;
}
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9+7;
const ll N = 2e3 + 10;
const ll M=1e7+10;
const double eps=1e-8;
struct Point{
double x,y;
Point(){}
Point(double x, double y):x(x),y(y){}
Point operator+(const Point &B){ return Point(x+B.x,y+B.y);}
Point operator-(const Point &B){ return Point(x-B.x,y-B.y);}
Point operator*(double k){ return Point(x*k,y*k);}
void input(){
cin>>x>>y;
}
}st1,ed1,st2,ed2;
struct Line{
Point st,ed;
double len,ang;
void input(){
st.input();ed.input();
ang=atan2(ed.y-st.y,ed.x-st.x);
}
}a,b;
double Distance(Point A,Point B){
double ans=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
return sqrt(ans);
}
double get_dis(double mid){
Point p1=Point(a.st.x+min(mid,a.len)*cos(a.ang),a.st.y+min(mid,a.len)*sin(a.ang));
Point p2=Point(b.st.x+min(mid,b.len)*cos(b.ang),b.st.y+min(mid,b.len)*sin(b.ang));
double ans=Distance(p1,p2);
return ans;
}
double solve(double l,double r){
for(int i=1;i<=1e2;++i){
double midl=(l*2+r)/3,midr=(l+r*2)/3;
if(get_dis(l)<get_dis(r)){
r=midr;
}
else{
l=midl;
}
}
double ans=get_dis(l);
if(ans-get_dis(r)>eps){
ans=get_dis(r);
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
a.input();b.input();
double l=0,r=max(a.len=Distance(a.st,a.ed),b.len=Distance(b.st,b.ed));
printf("%.12lf\n",min(solve(0,min(a.len,b.len)),solve(min(a.len,b.len),max(a.len,b.len))));
return 0;
}