2020 ICPC Universidad Nacional de Colombia Programming Contest 题解

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!

题意:

交互题

给出一个完全二叉树,标号如下

2020 ICPC Universidad Nacional de Colombia Programming 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\) 以相同的速度同时出发到另一个端点。到达终点的点不再移动,直到两个点均到达终点即结束。

求出两点间的最短距离

思路

两点间的距离是一个凹函数,所以采取典型的三分方法来进行缩小范围。同时由于精度的问题,要注意三分次数。

由于两个点有可能其中一个点停止时另一个点仍在移动,所以可以分为两段时间来计算。

  1. 没有点到达终点
  2. 第一个到达终点 - 所有到达终点

然后对于点所在下标,先使用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;
}
上一篇:BP算法中的链式求导法则详解


下一篇:几何原本研究