题目ABCDEFGHIJKLMNSolved$\bullet$$\bullet$$\bullet$$♠$$\bullet$$♠$$♠$$\bullet$$♠$

^{$♠$比赛时通过；$\bullet$：赛后通过；$\oslash$ ：比赛时尝试了未通过；$\circ$：比赛时未尝试}

A.Approach

这题有个坑点，首先三分算法肯定是想得到的了，主要是当一个点走完以后，另一个点在走的过程中可能还会出现小的抛物线，所以需要分两种情况讨论，详情见代码

#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; }

---

B.Baby name

一道思维题，赛内没通过可惜到裂开。要找到A字符串与B字符串的最大字典序子串开始的位置。先输出A最大字典序子串的首个字符，然后一个个和B中的最大字典序串的头一个字符比较，若大，则继续输出，若小，则输出B最大字典序子串。详见代码。

#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) { int 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 int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 3e5 + 10; const int M=1e7+10; const double eps=1e-8; int len1,len2,pos1,pos2; char s1[N],s2[N]; int main() { // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); scanf("%s %s",s1,s2); len1=strlen(s1); len2=strlen(s2); char max1=0,max2=0; for(int i=0;i<len1;i++){ if(s1[i]>max1){ max1=s1[i]; pos1=i+1; } else if(s1[i]==max1&&i>0&&s1[i-1]!=max1){ for(int j=1;j<=2*i-pos1+2;++j){ if(s1[pos1-1+j]==s1[i+j]) continue; else if(s1[pos1-1+j]<s1[i+j]){ pos1=i+1; break; } else break; } } } for(int i=0;i<len2;i++){ if(s2[i]>max2){ max2=s2[i]; pos2=i; } else if(s2[i]==max2&&i>0&&s2[i-1]!=max2){ for(int j=1;i+j<=2*i-pos2+1;++j){ if(s2[pos2+j]==s2[i+j]) continue; else if(s2[pos2+j]<s2[i+j]){ pos2=i; break; } else break; } } } printf("%c",max1); for(int i=pos1;i<len1;i++){ if(s1[i]>=max2) printf("%c",s1[i]); else break; } for(int i=pos2;i<len2;i++){ printf("%c",s2[i]); } return 0; }

D. Dice

这题首先比较容易想到的是使用余数来进行计数，最后$n$个骰子的余数总和为0就是答案。 一开始没有别的想法，暴力$dp$一波，结果还是$T$了 这道题首先的思路是，假如有两个骰子，结果余数 $num[(i+j)\%m]=num[i]\ast num[j]$,由这个可以知道，是有关乘法的运算，面对这么庞大的数据，可以想到的是就是使用矩阵快速幂。 左边矩阵表示的是 当前 $[nu{m}_0,nu{m}_1,nu{m}_2....nu{m}_{k-1}]$,右矩阵表示的是通过新的乘法得到新的左矩阵 右矩阵： $$\left[\begin{array}{ccccc}{a}_0& a_1& a_2& a_{...}& a_{m-1}\\ a_{m-1}& a_0& a_1& a_{...}& a_{m-2}\\ a_{m-2}& a_{m-1}& a_0& a_{...}& a_{m-3}\\ a_{...}& a_{...}& a_{...}& a_{...}& a_{...}\\ a_1& a_2& a_3& a_{...}& a_0\end{array}\right]\text{\hspace{1em}(ai表示数量)}$$ 详情见代码

#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 int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 2e4 + 1; const int M=1e7+10; const double eps=1e-8; struct matrix{ ll a[210][210]; matrix(){ memset(a,0,sizeof a); } matrix cal(const matrix &A,int n){ matrix ans; for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ for(int k=0;k<n;++k){ ans.a[i][j]+=a[i][k]*A.a[k][j]%mod; ans.a[i][j]%=mod; } } } return ans; } }; int num[200]; int n,k,m; ll fp(ll x,ll y){ ll ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; } ll solve(){ matrix ans; for(int i=0;i<m;++i) ans.a[i][i]=1; matrix tmp; for(int i=0;i<m;++i){ int pos=0; for(int j=i;j>=0;--j) tmp.a[pos++][i]=num[j]; for(int j=m-1;;--j){ if(pos==m) break; tmp.a[pos++][i]=num[j]; } } while(n){ if(n&1) ans=ans.cal(tmp,m); tmp=tmp.cal(tmp,m); n>>=1; } return ans.a[0][0]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); while(~scanf("%d %d %d",&n,&k,&m)){ for(int i=0;i<m;++i){ num[i]=k/m; } k%=m; for(int i=1;i<=k;++i) ++num[i]; num[0]=0; ll ans=0; for(int i=1;i<m;++i) ans+=num[i]; ans=fp(ans,n); printf("%lld\n",solve()*fp(ans,mod-2)%mod); } return 0; }

---

E. Enter to the best problem of this contest!

一道简单交互题，首先询问第1号点，知道距离后询问下一层的左子树节点，如果返回距离减小，则在左子树的下一层询问，若返回距离增加，则在右子树的下一层询问，若返回距离增加且返回距离为2，则答案在同层同祖先的另一侧。若返回距离为0，则找到答案。详见代码。

#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) { int 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 int inf = 0x3f3f3f3f; const int mod = 1e9+7; const int N = 1e5 + 10; const int M=1e7+10; const double eps=1e-8; int n; int query(int q){ printf("%d\n",q); fflush(stdout); int k; scanf("%d",&k); return k; } int main() { // ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); scanf("%d",&n); int temp=query(1),pos=1,ans; if(temp==0){ printf("! 1\n"); return 0; } while(1){ temp--; ans=query(pos*2); if(ans==0){ printf("! %d\n",pos*2); return 0; } else if(ans==temp) pos*=2; else if(temp==0&&ans==2){ printf("! %d\n",pos*2+1); return 0; } else pos=pos*2+1; } return 0; }

F. Free restricted flights

这题是需要对每条边进行拆边，就每条边拆成

付费边免费边，标序号 $[1,k]$,表示是路途中第k个免费的边 这题还有一个大坑点，k有可能用不完，意思就是路途全程都是免费的，真坑 剩下的就是建边问题，对于后面返回原点的路径，直接建立反边从原点出发一个道理，并且当访问到一个点时已经用了 $k_1$次免费机票，那么剩下的路径能使用的是 $i\in [0,k-k_1]$个免费机票 详情见代码 #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 int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int N = 1e4 + 1; const int M = 1e6 + 10; const double eps = 1e-8; struct edge { int next, to, w; }e1[M], e2[M]; int head1[N*15], head2[N*15], cnt1, cnt2; void add(edge e[], int head[], int& cnt, int u, int v, int w) { e[cnt].to = v; e[cnt].next = head[u]; e[cnt].w = w; head[u] = cnt++; } int n, m, a, b, k; int id[N][15]; ll dis1[N*15], dis2[N*15], dis3[N*15], dis4[N*15]; bool vis[N*15]; struct node { int v; ll len; bool friend operator<(const node& a, const node& b) { return a.len > b.len; } node(int v, ll len) :v(v), len(len) {} }; void dijkstra(edge e[], int head[], int& cnt, ll dis[], int st) { for (int i = 0; i < N * 15; ++i) dis[i] = 1e16; dis[st] = 0; memset(vis, false, sizeof vis); priority_queue<node>que; que.push(node(st, 0)); while (!que.empty()) { node vn = que.top(); que.pop(); if (vis[vn.v]) continue; int u = vn.v; vis[u] = true; dis[u] = vn.len; for (int i = head[u]; ~i; i = e[i].next) { int v = e[i].to; if (vis[v]) continue; que.push(node(v, vn.len + e[i].w)); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); memset(head1, -1, sizeof head1); memset(head2, -1, sizeof head2); cnt1 = cnt2 = 0; rd(n), rd(m), rd(a), rd(b), rd(k); int num = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j <= k; ++j) { id[i][j] = ++num; } } while (m--) { int u, v, w; rd(u), rd(v),rd(w); for (int j = 0; j < k; ++j) { add(e1, head1, cnt1, id[u][j], id[v][j], w); add(e1, head1, cnt1, id[u][j], id[v][j + 1], 0); add(e2, head2, cnt2, id[v][j], id[u][j], w); add(e2, head2, cnt2, id[v][j], id[u][j + 1], 0); } add(e1, head1, cnt1, id[u][k], id[v][k], w); add(e2, head2, cnt2, id[v][k], id[u][k], w); } dijkstra(e1, head1, cnt1, dis1, id[a][0]); dijkstra(e1, head1, cnt1, dis2, id[b][0]); dijkstra(e2, head2, cnt2, dis3, id[a][0]); dijkstra(e2, head2, cnt2, dis4, id[b][0]); int pos = -1; ll ans = 1e16; for (int i = 0; i < n; ++i) { if (a == i || b == i) continue; ll ans1 = 1e16, ans2 = 1e16; for (int j1 = 0; j1 <= k; ++j1) { for (int j2 = 0; j2 <= k - j1; ++j2) { int v1 = id[i][j1]; int v2 = id[i][j2]; if (ans1 > dis1[v1] + dis3[v2]) { ans1 = dis1[v1] + dis3[v2]; } if (ans2 > dis2[v1] + dis4[v2]) { ans2 = dis2[v1] + dis4[v2]; } } } if (ans > ans1 + ans2) { ans = ans1 + ans2; pos = i; } } if (ans == 1e16) puts(">:("); else printf("%d %lld\n", pos, ans); return 0; }

---

G. Great dinner

这题不用管后面给出哪两个数字前后关系，只要知道有多少对就行了 首先 令 $k$是剩下的没有限制关系的成员 ,$ans=A_k^k$ 令 $k_1$是当前已经排好序的人员数量，则新一对的加入到队伍中的情况总数是$\frac{[(1+k_1)+1]\ast (1+k_1)}{2}$ 详情见代码

#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) { int 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 int inf = 0x3f3f3f3f; const int mod = 1e9 + 7; const int N = 1e5 + 10; const int M = 1e7 + 10; const double eps = 1e-8; ll n, m; ll bully[N], victim[N]; ll fac[N]; ll get(ll x) { ll ans = 1; if (x & 1) ans = ans * (1 + x) / 2 % mod * x % mod; else ans = ans * x / 2 % mod * (1 + x) % mod; return ans % mod; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); fac[0] = 1; for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i % mod; rd(n), rd(m); for (int i = 1; i <= m; i++) { scanf("%lld %lld", &bully[i], &victim[i]); } m <<= 1; ll ans = fac[n - m]; m >>= 1; for (int i = 0; i < m; ++i) { ans = ans * get(n - m * 2 + i * 2 + 1) % mod; } printf("%lld\n", ans); return 0; }

---

K. Katastrophic sort

#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; string s1, s2; int check(string x, string y) { int len1 = x.size(), len2 = y.size(); for (int i = 0; i < len1 && i < len2; ++i) { if (x[i] != y[i]) { if (x[i] < y[i]) return -1; else return 1; } } if (len1 == len2) return 0; else if (len1 < len2) return -1; else return 1; } int check1(string x, string y) { int len1 = x.size(), len2 = y.size(); if (len1 != len2) { if (len1 < len2) return -1; else return 1; } for (int i = 0; i < len1 && i < len2; ++i) { if (x[i] != y[i]) { if (x[i] < y[i]) return -1; else return 1; } } return 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> s1 >> s2; string x = "", y = ""; int posx = 0, posy = 0; for (int i = 0; i < s1.size(); ++i) { if (!isalpha(s1[i])) { posx = i; break; } x += s1[i]; } for (int i = 0; i < s2.size(); ++i) { if (!isalpha(s2[i])) { posy = i; break; } y += s2[i]; } int tmp = check(x, y); if (tmp > 0) puts(">"); else if (tmp < 0) puts("<"); else { string xx = "", yy = ""; for (int i = posx; i < s1.size(); ++i) { xx += s1[i]; } for (int i = posy; i < s2.size(); ++i) { yy += s2[i]; } int tmp = check1(xx, yy); if (tmp > 0) puts(">"); else if (tmp < 0) puts("<"); else puts("="); } return 0; }

---

L.Lonely day

题意：给定一个$n\ast m$的矩阵。矩阵中有四种元素。 $.$ : 可以通过。 $X$ : 不可通过。 $S$ : 起点。 $E$ : 终点。 找出一种字典序最小的方法从$S$走到$E$。输出步数并输出这个走法，若没有解则输出$-1$。 有四种走法。 $D$ : 向下走。 $L$ : 向左走。 $R$ : 向右走。 $U$ : 向上走。 有两种方法可以到$.$元素，符号$M$表示现在所在的位置。 $$\left[\begin{array}{cc}M& .\end{array}\right]\text{\hspace{1em}(1)}$$ 此时$M$可以走到$.$。

$$\left[\begin{array}{ccccc}M& X& ......& X& .\end{array}\right]\text{\hspace{1em}(2)}$$ 此时$M$可以走到$.$。 题解：使用$BFS$来解决最短路径的问题（因为太菜导致一开始想的时候居然使用了$DFS$）。按照$D$，$L$，$R$，$U$的顺序依次搜索（这样就能保证第一个解必定是字典序最小的）。并且使用两个二维前驱数组来保存搜索过的路径。这两个数组分别为$x\_pre[][]$和$y\_pre[][]$，前者保存当前点的前驱点的$x$坐标，后者保存当前点的前驱点的$y$坐标。找到解后即可直接使用$DFS$回溯查找路径并结束$BFS$。 切记要使用一个布尔类型的$vis[][]$输出来保证入队列的点不会被重复访问到。

#include <cstdio> #include <cstring> #include <iostream> #include <queue> using namespace std; const int NN = 2e3 + 5; struct Node { int x, y; }; int n, m, sx, sy, ex, ey, num; int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}}; int x_pre[NN][NN], y_pre[NN][NN]; char ans[NN * 2]; char str[NN][NN]; bool vis[NN][NN]; void init() {} void dfs_ans(int x, int y) { if (x == sx && y == sy) { cout << num << endl; for (int i = num - 1; i >= 0; i--) cout << ans[i]; puts(""); return; } int xx = x_pre[x][y], yy = y_pre[x][y]; if (yy == y) { if (xx > x) ans[num++] = 'U'; else ans[num++] = 'D'; } else if (xx == x) { if (yy > y) ans[num++] = 'L'; else ans[num++] = 'R'; } dfs_ans(xx, yy); } void bfs() { queue<Node> q; q.push({sx, sy}); vis[sx][sy] = true; while (!q.empty()) { Node u = q.front(); q.pop(); if (u.x == ex && u.y == ey) { dfs_ans(ex, ey); return; } for (int i = 0; i < 4; i++) { int xx = u.x, yy = u.y; while (1) { xx += dir[i][0]; yy += dir[i][1]; if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) break; if (str[xx][yy] == '.') { vis[xx][yy] = true; q.push({xx, yy}); x_pre[xx][yy] = u.x; y_pre[xx][yy] = u.y; break; } } } } printf("-1\n"); } 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 >> str[i][j]; if (str[i][j] == 'S') { sx = i; sy = j; str[i][j] = '.'; } else if (str[i][j] == 'E') { ex = i; ey = j; str[i][j] = '.'; } } bfs(); return 0; }

---

M. Magic spells

普通的二分查找，将每个字母的下标存进vector里，查找的时候尽量往最左边查找，找不到就返回答案。

#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; string s; vector<int>vec[30]; int len; string check(string x) { if (vec[x[0] - 'a'].empty()) return "IMPOSSIBLE"; int len1 = x.size(), pos = vec[x[0] - 'a'][0]; string ans = ""; ans += x[0]; for (int i = 1; i < len1; ++i) { int ansn = -1; int l = 0, r = vec[x[i] - 'a'].size() - 1; while (l <= r) { int mid = l + r >> 1; if (vec[x[i] - 'a'][mid] > pos) { r = mid - 1; ansn = mid; } else l = mid + 1; } if (ansn == -1) return ans; pos = vec[x[i] - 'a'][ansn]; ans += x[i]; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> s; len = s.size(); for (int i = 0; i < len; ++i) { vec[s[i] - 'a'].push_back(i); } int n; rd(n); while (n--) { string x; cin >> x; cout << check(x) << endl; } return 0; }