✔：比赛时通过；🚫：赛后通过；⚪：比赛时尝试了未通过；-：比赛时未尝试
solved by Tryna. (-)
题意 ：给出四个点，前两个点确定一条直线，后面两个点确定另外一条直线。有两个人，分别从两条直线的起点以同样的速度出发，当一个人到达终点时，另外一个人继续前进，问两个人移动过程中的最短距离。
题解 ：这两个人前进过程中的距离函数是一个有极值的凹函数，所以只需要三分一下时间，求出该时间下两点的坐标，然后在求出距离。需要注意一个人到达终点后，另外一个人继续前进，所以需要分成两段，第一段为0 - min(d1,d2)，第二段为min(d1,d2) - max(d1,d2) 。还有个难点就是求出该时间下各个点的坐标。需要预先用反正切求出直线与x轴的夹角，然后配合正弦函数和余弦函数求出点的坐标，最后在计算两点距离。注意这题卡精度，要限定三分的次数。
#include<bits/stdc++.h> using namespace std; const double pi = acos(-1); #define inf 0x3f3f3f3f #define ll long long const int maxn = 20010; const int mod = 1e9 + 7; double X1,X2,X3,X4,Y1,Y2,Y3,Y4,angle1,angle2,d1,d2,midl,midr; double getDist(double ax, double ay, double bx, double by){ return sqrt((ax - bx)*(ax - bx) + (ay - by)*(ay - by)); } double f(double t){ double t1 = min(d1, t); double t2 = min(d2, t); double xt1 = t1*cos(angle1); double yt1 = t1*sin(angle1); double xt2 = t2*cos(angle2); double yt2 = t2*sin(angle2); double _x1 = X1 + xt1; double _y1 = Y1 + yt1; double _x2 = X3 + xt2; double _y2 = Y3 + yt2; return getDist(_x1, _y1, _x2, _y2); } double sf(double l, double r){ for(int i = 1;i <= 10000; i++){ midl = (l + r)/2; midr = (midl + r)/2; if(f(midl) > f(midr)) l = midl; else r = midr; } return f(midr); } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>X1>>Y1>>X2>>Y2; cin>>X3>>Y3>>X4>>Y4; angle1 = atan2(Y2 - Y1, X2 - X1); angle2 = atan2(Y4 - Y3, X4 - X3); d1 = getDist(X1,Y1,X2,Y2); d2 = getDist(X3,Y3,X4,Y4); double mn = min(d1,d2); double mx = max(d1,d2); double result = min(sf(0, mn), sf(mn, mx)); cout<<fixed<<setprecision(12)<<result<<endl; return 0; }solved by Sstee1XD. 03:03(+3)
题意 ：给你父亲和母亲的名字，各取父亲和母亲名字的一个字串，将它们拼在一起成为子代的名字，问最大字典序的名字。
题解：分别把父母亲名字中最大的字母的下标记录下来，最后再比较各个下标开始的字串字典序大小。这里注意一下连续相同的字母只用取第一位，比较连续的字母是没有意义的。得到两个字符串的下标之后，先输出父亲的第一个字母，再一个个比较，最后输出母亲的字串。
P.S：刚开始没想清楚直接冲了一发，后来想出来写代码没写完整，但是以为会RE，报了WA，考虑了很久才交最后一发。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl;} template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } const int maxn = 2e5 + 7; char s1[maxn], s2[maxn]; int m1 = 0, m2 = 0; int n1 = 0, n2 = 0; int G1[maxn >> 1], G2[maxn >> 1]; int gao(int G[], int n, int len, char s[]) { int ans = G[0]; for (int i = 1; i <= n; ++i) { int tmp = G[i]; int a = ans; while (tmp < len && s[a] == s[tmp]) { a++; tmp++; } if (tmp < len && s[a] < s[tmp]) ans = G[i]; } return ans; } void run(){ int len1 = strlen(s1), len2 = strlen(s2); G1[0] = 0, G2[0] = 0; for (int i = 1; i < len1; ++i) { if (s1[i] > s1[m1]) { m1 = i; n1 = 0; G1[n1] = i; while (i < len1 && s1[i + 1] == s1[i]) ++i; } else if(s1[i] == s1[m1]) { G1[++n1] = i; while (i < len1 && s1[i + 1] == s1[i]) ++i; } } for (int i = 1; i < len2; ++i) { if (s2[i] > s2[m2]) { m2 = i; n2 = 0; G2[n2] = i; while (i < len2 && s2[i + 1] == s2[i]) ++i; } else if(s2[i] == s2[m2]) { G2[++n2] = i; while (i < len2 && s2[i + 1] == s2[i]) ++i; } } m1 = gao(G1, n1, len1, s1); m2 = gao(G2, n2, len2, s2); printf("%c", s1[m1]); m1++; while (m1 < len1 && s1[m1] >= s2[m2]) { printf("%c", s1[m1++]); } for (int i = m2; i < len2; ++i) printf("%c", s2[i]); } int main(){ scanf("%s %s", s1, s2); run(); return 0; }solved by Sstee1XD. 01:37(+1)
题意 : 一个人藏在一个最多 29 29 29层的二叉树里，你最多可以询问29次，每次询问一个节点，它会返回人藏在的节点和你询问的节点的距离，最后输出人所在的节点。
题解：这题运用到二叉树的性质。我们第一次询问点 1 1 1，即可得到点所在的深度。然后每次询问最左边的节点，设得到的距离为 d d d，当前节点的层数减去 d 2 \frac{d}{2} 2d即可得到它和目标节点的 L C A LCA LCA，就能确定目标节点在另一边的子树上。重复这个操作就能得到目标节点的位置。在极端情况下，每次询问只能让子树的层数减少 1 1 1，由于第一次询问并不能减少子树的层数，所以为了保证 29 29 29次能找完，最后询问到 d < = 2 d <= 2 d<=2即停止。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl;} template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } int qpow(int a, int b) { int res = 1; for(; b; b >>= 1) { if (b & 1) res *= a; a *= a; } return res; } int n; void gao(int d) { int now = qpow(2, d); d = 10; while (d > 2) { cout << endl << now << endl; cout.flush(); cin >> d; if (d == 0) break; now /= qpow(2, d / 2); now = now * 2 + 1; now *= qpow(2, d / 2 - 1); } cout << endl << "! " << now; cout.flush(); } void run(){ int d; cout << 1 << endl; cout.flush(); cin >> d; if (d == 0) { cout << endl << "! 1" << endl; return; } gao(d); } int main(){ // freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; run(); return 0; }solved by Tryna .1:04(+1)
题解 ：n！除 m^2
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl; } template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } const ll mod = 1e9 + 7; const int maxn = 100010; int n , m; ll ans = 1; int main() { cin >> n >> m; for(int i = 1, u, v; i <= m; i++) cin >> u >> v; for(int i = 2; i <= n ; i++) { ans = ans * i; if(ans % 2 == 0 && m) { m--; ans /= 2; } if(ans >= mod) ans %= mod; } cout << ans << endl; return 0; }solved by Sstee1XD.(-)
题意 ：给你一段序列，以某点为起点，你的移动规则是找到一个你能看到的高度严格大于你的点，然后你可以移动到那个点，之后又可以以相同的规则进行移动。求出以每个点为起点时能移动的最长距离。
题解 ：每个点都要找，很像一道记忆化搜索，又看到了视野中严格大于，就想到了单调栈，所以就用单调栈去维护左右要去的点就行了。当视野中有相同高度的点时，我们要想移动的距离最长，就要选择能看到的最远的点，同时也要注意到，相同高度的点可能是不连续的，比如5 3 5 3 5这个例子。最后debug的时候也是过了这个例子A的，但是感觉写得有点麻烦。
#include <bits/stdc++.h> using namespace std; #define endl "\n" typedef long long ll; const int maxn = 1e5 + 7; ll l[maxn], r[maxn], n, h[maxn], ans[maxn]; ll sta[maxn], top; vector<ll> G[maxn]; ll dfs(int u) { if (ans[u] != -1) return ans[u]; ll tl = 0, tr = 0; if (l[u] != 0) tl = max(u - l[u] + dfs(l[u]), tl); if (r[u] != 0) tr = max(r[u] - u + dfs(r[u]), tr); ans[u] = max(tl, tr); return ans[u]; } void solve() { memset(ans, -1, sizeof(ans)); for (int i = 1; i <= n; ++i) cin >> h[i]; for (int i = 1; i <= n; ++i) { int left = i; int tag = 0; while (h[i] == h[i + 1] && i < n) i++; while (top && h[i] >= h[sta[top - 1]]) { if (h[sta[top - 1]] == h[i]) { tag = sta[top - 1]; break; } r[sta[top - 1]] = i; G[i].push_back(sta[top - 1]); top--; } for (int j = left; j <= i; ++j) { sta[top++] = j; } if (tag) { for (int j = 0; j < G[tag].size(); ++j) { G[i].push_back(G[tag][j]); r[G[tag][j]] = i; } } } top = 0; for (int i = 1; i <= n; ++i) G[i].clear(); for (int i = n; i >= 1; --i) { int tag = 0; int right = i; while (h[i] == h[i - 1] && i > 1) i--; while (top && h[i] >= h[sta[top - 1]]) { if (h[sta[top - 1]] == h[i]) { tag = sta[top - 1]; break; } l[sta[top - 1]] = i; G[i].push_back(sta[top - 1]); top--; } for (int j = right; j >= i; --j) { sta[top++] = j; } if (tag) { for (int j = 0; j < G[tag].size(); ++j) { G[i].push_back(G[tag][j]); l[G[tag][j]] = i; } } } for (int i = 1; i <= n; ++i) dfs(i); for (int i = 1; i <= n; ++i) { if (i > 1) cout << ' '; cout << ans[i]; } cout << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); cin >> n; solve(); return 0; }solved by Tryna.0:29(+)
题意 ：给定两个只含字母和数字的字符串，保证字母部分长度相等，字母和字母比较，若相同，则比较数字。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl;} template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } const int maxn = 100010; char a1[maxn],b2[maxn],a2[maxn],b1[maxn]; string st1,st2; int main(){ cin>>st1; cin>>st2; int cnt = 0; for(int i = 0;i<st1.size();i++){ if(st1[i]<='z'&&st1[i]>='a'){ cnt++; a1[cnt] = st1[i]; } else break; } for(int i = cnt;i<st1.size();i++) a2[i-cnt+1] = st1[i]; cnt = 0; for(int i = 0;i<st2.size();i++){ if(st2[i]<='z'&&st2[i]>='a'){ cnt++; b1[cnt] = st2[i]; } else break; } for(int i = cnt;i<st2.size();i++) b2[i-cnt+1] = st2[i]; if(strcmp(a1+1,b1+1)>0){ cout<<">"<<endl; } else if(strcmp(a1+1,b1+1)<0) cout<<"<"<<endl; else{ if(strlen(a2+1)<strlen(b2+1)) cout<<"<"<<endl; else if(strlen(a2+1)>strlen(b2+1)) cout<<">"<<endl; else{ if(strcmp(a2+1,b2+1)>0) cout<<">"<<endl; else if(strcmp(a2+1,b2+1)<0) cout<<"<"<<endl; else cout<<"="<<endl; } } return 0; }solved by lllllan、Sstee1XD.04:52(+13)
题意： 给定一个n*m的图，途中的’S’为起点，‘E’为终点。每次移动只能横向或纵向地移向最近的一个干净的点’.'或终点，'X’为脏的点。如果能到达终点，则输出步数最少并且字典序最小的路径（下移为D、左移为L、右移为R、上移为U）。否则输出-1。
曲折经历： 比赛时想的没有那么周到，用BFS+DFS，结构体里携带各种参数，并且实时传递移动路径，导致空间占用比较大，加上本来算法的效率就不高，所以WA的和TLE的次数累计到达了13发。最后各种修改，卡常1980ms极限AC。又因为参加过这个比赛和做过这个题目的人很少，我甚至找不到题解可以学习。所以自己又花了一个上午的时间研究，最后得出一个时间和空间以及代码长度都最优的代码（对我的能力而言）
最终思路：
BFS。 众所周知：一个图 + 起点到终点 + 最短路径 = BFS。定义一个结构体的队列，结构体node中只需携带某个点的坐标即可。定义vis[][] 避免重复访问。pre_x[][]、pre_y[][]。 因为广搜的特性，从某个点出发，最多可能有四个可达的目标点。而因为vis避免重复访问，每个点一定只能来自于一个点。所以定义两个数组来记录某一个干净的点的前驱节点的坐标。DFS。 用BFS一直搜索到终点，结束广搜。我们记录路径的方式是用两个pre数组记录前驱节点的坐标，并没有记录移动的方向。所以可以通过dfs从终点递推回起点，比较每个点与前驱节点的坐标关系，记录下移动方向。最后倒叙输出答案即可。 #include<bits/stdc++.h> using namespace std; const int N = 2e3 + 10; int n, m; int sx, sy, cnt; //sx\sy记录起点坐标。cnt为路径的字符个数 int pre_x[N][N]; //记录前驱节点的坐标 int pre_y[N][N]; int vis[N][N]; //访问标记，避免重复访问 char G[N][N]; //存图 char ans[2 * N]; //记录路径 int dir[][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; char Dir[] = "DLRU"; struct node { int x, y;}; int check(int x, int y) { //检查移动后是否还在图的范围内 if(x < 1 || x > n || y < 1 || y > m) return 0; return 1; } void dfs(int x, int y) { //从终点推回起点，标出移动路径 if(x == sx && y == sy){ //回到起点，输出答案 cout << cnt << endl; for(int i = cnt - 1; i >= 0; i--) cout << ans[i]; return; } int prex = pre_x[x][y]; int prey = pre_y[x][y]; if(prey == y) //比较节点与前驱节点的关系，得出移动方向 if(prex < x) ans[cnt++] = Dir[0]; else ans[cnt++] = Dir[3]; else if(prey < y) ans[cnt++] = Dir[2]; else ans[cnt++] = Dir[1]; dfs(prex, prey); } void BFS() { queue<node> Q; Q.push({sx, sy}); vis[sx][sy] = 1; while(!Q.empty()) { node u = Q.front(); Q.pop(); if(G[u.x][u.y] == 'E') { //找到终点，dfs找到移动路径 dfs(u.x, u.y); return ; } for(int i = 0; i < 4; i++) { 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({nex, ney}); break; //找到最近的第一个干净点，插入队列即可推出 } //干净点不一定相邻，可能隔着几个'X'才能到达，所以需要不断移动查找 nex += dir[i][0], ney += dir[i][1]; } } } cout << -1 << endl; } int main() { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { cin >> G[i][j]; if(G[i][j] == 'S') sx = i, sy = j; } BFS(); return 0; }solved by Sstee1XD. 00:52(+2)
题意：给你一个主串，然后给你n个子串，询问是否存在公共子序列符合子串，输出能符合的最长的子串。
题解：用一个 d p dp dp二维数组来记录这位之后各个字母第一次出现的位置，从后往前预处理一下，就可以开始做了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; #define endl "\n" #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl;} template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); } const int maxn = 2e5 + 10; char s[maxn]; int dp[maxn][30]; int id[maxn]; int ch(char c) { return c - 'a' + 1; } int n; char str[maxn], ans[maxn]; void run(){ memset(id, -1, sizeof(id)); memset(dp, -1, sizeof(dp)); int len = strlen(s); id[ch(s[len - 1])] = len - 1; for (int i = len - 2; i >= 0; --i) { for (int j = 1; j <= 26; ++j) dp[i][j] = id[j]; id[ch(s[i])] = i; } scanf("%d", &n); while (n--) { scanf("%s", str); int f = id[ch(str[0])]; int num = 1; if (f == -1) { puts("IMPOSSIBLE"); continue; } int rear = strlen(str); f = dp[f][ch(str[num])]; while (f != -1 && num < rear) { num++; f = dp[f][ch(str[num])]; } str[num] = '\0'; printf("%s", str); puts(""); } } int main(){ scanf("%s", s); run(); return 0; }