我重写行不？
签到题，类似于BFS用两个队列维护每种单词前/后是否有逗号向前/后扩展，需要注意如果有句号挡着是不能扩展过去的，不过样例有。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e6 + 10; 4 map<string, vector<int>> M; 5 bool pre[maxn], suc[maxn]; 6 bool st[maxn], ed[maxn]; 7 queue<string> QP, QS; 8 set<string> SP, SS; 9 string str[maxn]; 10 11 int main() { 12 string s; 13 getline(cin, s); 14 int l = s.length(), p = 1; 15 st[p] = true; 16 for(int i = 0; i < l; ++i) { 17 if(s[i] == ',') { 18 suc[p] = pre[p + 1] = true; 19 ++p, ++i; 20 } 21 else if(s[i] == '.') { 22 ed[p] = st[p + 1] = true; 23 ++p, ++i; 24 } 25 else if(s[i] == ' ') ++p; 26 else str[p].push_back(s[i]); 27 } 28 for(int i = 1; i < p; ++i) M[str[i]].push_back(i); 29 for(int i = 1; i < p; ++i) { 30 if(pre[i] && SP.find(str[i]) == SP.end()) SP.insert(str[i]), QP.push(str[i]); 31 if(suc[i] && SS.find(str[i]) == SS.end()) SS.insert(str[i]), QS.push(str[i]); 32 } 33 while(!QP.empty() || !QS.empty()) { 34 while(!QP.empty()) { 35 string cur = QP.front(); QP.pop(); 36 vector<int>& pos = M[cur]; 37 for(int i = 0; i < pos.size(); ++i) { 38 int x = pos[i]; 39 if(!st[x]) pre[x] = true; 40 if(x - 1 > 0 && !ed[x - 1] && SS.find(str[x - 1]) == SS.end()) suc[x - 1] = true, SS.insert(str[x - 1]), QS.push(str[x - 1]); 41 } 42 } 43 while(!QS.empty()) { 44 string cur = QS.front(); QS.pop(); 45 vector<int>& pos = M[cur]; 46 for(int i = 0; i < pos.size(); ++i) { 47 int x = pos[i]; 48 if(!ed[x]) suc[x] = true; 49 if(x + 1 < p && !st[x + 1] && SP.find(str[x + 1]) == SP.end()) pre[x + 1] = true, SP.insert(str[x + 1]), QP.push(str[x + 1]); 50 } 51 } 52 } 53 for(int i = 1; i < p; ++i) { 54 cout << str[i]; 55 if(ed[i]) cout << '.'; 56 else if(suc[i]) cout << ','; 57 if(i < p - 1) cout << ' '; 58 else cout << endl; 59 } 60 return 0; 61 }
题意是构造一棵树使得树上度与原图度不相等的节点尽量少。
考虑一个贪心，按度从小到大排序后，对于每个度大于1的点，在上面挂叶子直到度为1，那么这个连通块也看成一个叶子。
如果某个时刻叶子不够了，那么就舍弃度最大的点，把它当做叶子挂上去。
最后如果还有叶子没用完，若剩两个叶子正好拼成一棵树，否则舍弃一个叶子作为根把别的挂上去。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e4 + 10; 4 typedef pair<int, int> pii; 5 int deg[maxn], id[maxn]; 6 vector<pii> ans2; 7 vector<int> one; 8 9 bool cmp(int i, int j) { 10 return deg[i] < deg[j]; 11 } 12 13 int main() { 14 int n, m; 15 scanf("%d %d", &n, &m); 16 int ans1 = n; 17 for(int i = 1; i <= m; ++i) { 18 int u, v; 19 scanf("%d %d", &u, &v); 20 ++u, ++v; 21 deg[u] += 1, deg[v] += 1; 22 } 23 for(int i = 1; i <= n; ++i) id[i] = i; 24 sort(id + 1, id + 1 + n, cmp); 25 int st = 1, ed = n; 26 while(st <= n && deg[id[st]] == 1) { 27 one.push_back(id[st]); 28 ++st; 29 } 30 for(int i = st; i <= ed; ++i) { 31 int x = id[i]; 32 while(deg[x] > 1 && !one.empty()) { 33 int y = one.back(); 34 one.pop_back(); 35 deg[x]--, deg[y]--; 36 ans1--; 37 ans2.emplace_back(pii(x, y)); 38 } 39 while(deg[x] > 1 && ed > i) { 40 int y = id[ed]; 41 deg[x]--, deg[y]--; 42 ans2.emplace_back(pii(x, y)); 43 ed--; 44 } 45 if(deg[x] == 1) one.push_back(x); 46 } 47 if(one.size() > 1) { 48 for(int i = 1; i < one.size(); ++i) 49 ans2.emplace_back(pii(one[0], one[i])); 50 ans1 -= one.size() - 1; 51 if(one.size() == 2) ans1--; 52 } 53 printf("%d\n%d %d\n", ans1, n, int(ans2.size())); 54 for(int i = 0; i < ans2.size(); ++i) printf("%d %d\n", ans2[i].first - 1, ans2[i].second - 1); 55 return 0; 56 }
暴力枚举长度，然后算每个空格的最长链，时限卡的有点紧。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 3e5 + 10; 4 int pre[maxn], cur[maxn]; 5 vector<int> v; 6 7 int main() { 8 int n, wid = -1, ans = 0, sum = 0, M = 0; 9 scanf("%d", &n); 10 for(int i = 1; i <= n; ++i) { 11 char s[111]; 12 scanf("%s", s); 13 int l = strlen(s); 14 v.push_back(l); 15 M = max(M, l); 16 sum += l; 17 } 18 for(int W = M; W <= sum + n - 1; ++W) { 19 int tmp = 0; 20 vector<int> P, C; 21 int pos = 0, fir = 1, ok = 0; 22 for(int i = 0; i < v.size(); ++i) { 23 if(!fir && pos + 1 + v[i] > W) { 24 for(int j = 0; j < P.size(); ++j) pre[P[j]] = 0; 25 for(int j = 0; j < C.size(); ++j) pre[C[j]] = cur[C[j]], cur[C[j]] = 0; 26 P = C, C.clear(); 27 fir = 1; 28 pos = 0; 29 } 30 if(fir) { 31 pos += v[i]; 32 fir = 0; 33 } 34 else { 35 pos += 1; 36 int r = 1; 37 if(pos > 1) r = max(r, pre[pos - 1] + 1); 38 r = max(r, pre[pos] + 1); 39 if(pos < W) r = max(r, pre[pos + 1] + 1); 40 cur[pos] = r, C.push_back(pos); 41 pos += v[i]; 42 tmp = max(tmp, r); 43 } 44 if(pos == W) ok = 1; 45 } 46 if(ok && tmp > ans) ans = tmp, wid = W; 47 for(int j = 0; j < P.size(); ++j) pre[P[j]] = 0; 48 for(int j = 0; j < C.size(); ++j) cur[C[j]] = 0; 49 } 50 printf("%d %d\n", wid, ans); 51 return 0; 52 }
将线路按出发时间排序，倒着dp。
对于每条线路(a, b, s, t, p)，记a点在严格大于s时刻的最优值为ta，b点在严格大于t的最优值为tb。
每个时刻的决策有两种，若选择乘坐，则以p的概率转移到tb，1 - p概率继承ta；若不乘坐则直接继承ta。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<ll, int> pr; 5 const int maxn = 1e6 + 10; 6 map<ll, double> :: iterator ita, itb; 7 map<ll, double> f[maxn]; 8 int a[maxn], b[maxn]; 9 ll s[maxn], t[maxn]; 10 double p[maxn]; 11 vector<pr> v; 12 13 int main() { 14 ll k; 15 int m, n; 16 scanf("%d %d %lld", &m, &n, &k); 17 for(int i = 1; i <= m; ++i) { 18 scanf("%d %d %lld %lld %lf", a + i, b + i, s + i, t + i, p + i); 19 v.emplace_back(pr(s[i], i)); 20 } 21 sort(v.begin(), v.end()); 22 f[1][k + 1] = 1; 23 for(int i = int(v.size()) - 1; i >= 0; --i) { 24 int e = v[i].second, ai = a[e], bi = b[e]; 25 ll si = v[i].first, ti = t[e]; 26 double pi = p[e]; 27 ita = f[ai].upper_bound(si); 28 itb = f[bi].upper_bound(ti); 29 double ta = 0, tb = 0; 30 if(ita != f[ai].end()) ta = (*ita).second; 31 if(itb != f[bi].end()) tb = (*itb).second; 32 f[ai][si] = max(f[ai][si], max(ta, pi * tb + (1 - pi) * ta)); 33 } 34 printf("%.8f\n", (*f[0].begin()).second); 35 return 0; 36 }
注意到取两条对角线是一定可以切到所有线段的，因此答案最大为2，只需考虑1的情况。
将线段转变为环上的区间，相当于找两个端点切开所有区间。
枚举其中一个位置，另一个双指针单调移动。
最后将答案投回矩形上的位置。
注意不能重点，不能取角点。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e6 + 10; 4 typedef pair<int, int> pii; 5 bool vis[maxn]; 6 vector<pii> v; 7 int n, w, h; 8 9 inline int cal(int x, int y) { 10 if(x == 0) return y; 11 if(y == h) return h + x; 12 if(x == w) return 2 * h + w - y; 13 return 2 * (h + w) - x; 14 } 15 16 inline void get(double t, double& x, double& y) { 17 if(t <= h) x = 0, y = t; 18 else if(t <= h + w) x = t - h, y = h; 19 else if(t <= 2 * h + w) x = w, y = 2 * h + w - t; 20 else x = 2 * (h + w) - t, y = 0; 21 } 22 23 int main() { 24 scanf("%d %d %d", &n, &w, &h); 25 for(int i = 0; i < n; ++i) { 26 int X1, Y1, X2, Y2; 27 scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2); 28 v.push_back(pii(cal(X1, Y1), i)); 29 v.push_back(pii(cal(X2, Y2), i)); 30 } 31 sort(v.begin(), v.end()); 32 int sz = int(v.size()), p = 0, cnt = 0, one = 0; 33 for(int i = 0; i < sz; ++i) { 34 if(p == i) vis[v[i].second] = true, ++p, ++cnt; 35 while(!vis[v[p].second]) vis[v[p].second] = true, p = (p + 1) % sz, ++cnt; 36 if(cnt == n) { 37 double ax1, ay1, ax2, ay2; 38 get(v[i].first - 0.5, ax1, ay1); 39 get(v[p].first - 0.5, ax2, ay2); 40 printf("1\n%.8f %.8f %.8f %.8f\n", ax1, ay1, ax2, ay2); 41 one = 1; break; 42 } 43 vis[v[i].second] = false, --cnt; 44 } 45 if(!one) printf("2\n0.5 0 %.8f %.8f\n0 %.8f %.8f %.8f\n", w - 0.5, 1.0 * h, h - 0.5, 1.0 * w, 0.5); 46 return 0; 47 }
考虑统计每个▽，将图上下翻转后再做一次即为全部三角形。
按从右往左从上往下的顺序扫描每一个\方向斜线上的点，考虑这个点作为▽下顶点的贡献。
假设这个点往左上，右上延伸的最大长度分别为UL和UR，那么相当于询问在向上min(UL, UR)的范围内有多少横线长度大于等于到枚举顶点的距离。
这个直观感觉不太好统计，那么反过来考虑每一条横线对于哪些▽下顶点是有效的。
假设在某点处向右的最大距离为R，那么这条横线对于它下方R范围内的顶点都是可以作为三角形▽上边的。
在扫描的过程中顺便维护好UL，UR和R，用一个树状数组维护这个\斜线上横线的贡献，即在扫描到的时候+1，在下方R处加一个删除标记，扫到的时候删掉。
枚举下顶点的时候，只要在树状数组上询问一下min(UL, UR)范围内的有效横线数目。
时限很紧，不仅要比较好的读入还要常数小。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 int f[66666]; 6 inline int lowbit(int s) { 7 return s & (-s); 8 } 9 inline void modify(int i, int x, int n) { 10 while (i <= n) f[i] += x, i += lowbit(i); 11 } 12 inline int query(int i) { 13 int ret = 0; 14 while (i > 0) ret += f[i], i -= lowbit(i); 15 return ret; 16 } 17 vector<int> del[66666]; 18 19 int main() { 20 ios_base :: sync_with_stdio(0); 21 cin.tie(0); 22 int r, c; 23 cin >> r >> c; 24 r = 2 * r - 1, c = 2 * c - 1; 25 vector<string> s(r); 26 getline(cin, s[0]); 27 for(int i = 0; i < r; ++i) { 28 getline(cin, s[i]); 29 while(s[i].length() < c) s[i].push_back(' '); 30 } 31 ll ans = 0; 32 for(int rot = 0; rot < 2; ++rot) { 33 vector< vector<int> > R(r, vector<int>(c, 0)); 34 vector< vector<int> > UL(r, vector<int>(c, 0)); 35 vector< vector<int> > UR(r, vector<int>(c, 0)); 36 for(int j = c - 1; j >= 0; --j) { 37 if(s[0][j] != 'x') continue; 38 int maxi = min((r - 1) / 2, (c - 1 - j) / 2) + 1; 39 for(int ii = 0, jj = j; ii < r && jj < c; ii += 2, jj += 2) { 40 if(jj + 2 < c && s[ii][jj + 2] != ' ') R[ii][jj] = R[ii][jj + 4] + 1; 41 if(ii >= 2 && jj >= 2 && s[ii - 1][jj - 1] != ' ') UL[ii][jj] = UL[ii - 2][jj - 2] + 1; 42 if(ii >= 2 && jj + 2 < c && s[ii - 1][jj + 1] != ' ') UR[ii][jj] = UR[ii - 2][jj + 2] + 1; 43 ans += query(ii / 2 + 1) - query(ii / 2 - min(UL[ii][jj], UR[ii][jj])); 44 if(R[ii][jj]) { 45 modify(ii / 2 + 1, 1, maxi); 46 del[min(ii / 2 + 1 + R[ii][jj], maxi)].push_back(ii / 2 + 1); 47 } 48 for(auto x: del[ii / 2 + 1]) modify(x, -1, maxi); 49 del[ii / 2 + 1].clear(); 50 } 51 } 52 for(int i = 1; i < r; i++) { 53 if(s[i][0] != 'x') continue; 54 int maxj = min((r - 1 - i) / 2, (c - 1) / 2) + 1; 55 for(int ii = i, jj = 0; ii < r && jj < c; ii += 2, jj += 2) { 56 if(jj + 2 < c && s[ii][jj + 2] != ' ') R[ii][jj] = R[ii][jj + 4] + 1; 57 if(ii >= 2 && jj >= 2 && s[ii - 1][jj - 1] != ' ') UL[ii][jj] = UL[ii - 2][jj - 2] + 1; 58 if(ii >= 2 && jj + 2 < c && s[ii - 1][jj + 1] != ' ') UR[ii][jj] = UR[ii - 2][jj + 2] + 1; 59 ans += query(jj / 2 + 1) - query(jj / 2 - min(UL[ii][jj], UR[ii][jj])); 60 if(R[ii][jj]) { 61 modify(jj / 2 + 1, 1, maxj); 62 del[min(jj / 2 + 1 + R[ii][jj], maxj)].push_back(jj / 2 + 1); 63 } 64 for(auto x: del[jj / 2 + 1]) modify(x, -1, maxj); 65 del[jj / 2 + 1].clear(); 66 } 67 } 68 reverse(s.begin(), s.end()); 69 } 70 cout << ans << endl; 71 return 0; 72 }
由于圆半径一致，对于多边形内的每一个点，总是最先被距离自己最近的顶点覆盖到。
也即是说，每个顶点要覆盖到以自己为最近顶点的区域，即维诺图，又称泰森多边形，只要枚举顶点做中垂线即可得到这个凸多边形。
我们只关心这个凸多边形和原多边形交的部分，关键点只有两种情况：凸多边形顶点在原多边形内部；两多边形交点。
暴力求出关键点算距离取最大值即可。
需要抄的板子大概是一个中垂线，半平面交，点多边形位置关系。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef double db; 5 const db eps=1e-6; 6 int sign(db k){ 7 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 8 } 9 int cmp(db k1,db k2){return sign(k1-k2);} 10 int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}// k3 在 [k1,k2] 内 11 struct point{ 12 db x,y; 13 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 14 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 15 point operator * (db k1) const{return (point){x*k1,y*k1};} 16 point operator / (db k1) const{return (point){x/k1,y/k1};} 17 int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;} 18 // 逆时针旋转 19 point turn90(){return (point){-y,x};} 20 bool operator < (const point k1) const{ 21 int a=cmp(x,k1.x); 22 if (a==-1) return 1; else if (a==1) return 0; else return cmp(y,k1.y)==-1; 23 } 24 db abs(){return sqrt(x*x+y*y);} 25 int getP() const{return sign(y)==1||(sign(y)==0&&sign(x)==-1);} 26 }; 27 int inmid(point k1,point k2,point k3){return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);} 28 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;} 29 db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;} 30 // -pi -> pi 31 int compareangle (point k1,point k2){ 32 return k1.getP()<k2.getP()||(k1.getP()==k2.getP()&&sign(cross(k1,k2))>0); 33 } 34 point getLL(point k1,point k2,point k3,point k4){ 35 db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2); 36 } 37 int intersect(db l1,db r1,db l2,db r2){ 38 if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-1&&cmp(r2,l1)!=-1; 39 } 40 int checkSS(point k1,point k2,point k3,point k4){ 41 return intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&& 42 sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<=0&& 43 sign(cross(k1-k3,k2-k3))*sign(cross(k1-k4,k2-k4))<=0; 44 } 45 int onS(point k1,point k2,point q){return inmid(k1,k2,q)&&sign(cross(k1-q,k2-k1))==0;} 46 struct line{ 47 // p[0]->p[1] 48 point p[2]; 49 line(point k1,point k2){p[0]=k1; p[1]=k2;} 50 point& operator [] (int k){return p[k];} 51 int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>0;} 52 point dir(){return p[1]-p[0];} 53 }; 54 point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);} 55 int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;} 56 int sameDir(line k1,line k2){return parallel(k1,k2)&&sign(dot(k1.dir(),k2.dir()))==1;} 57 int operator < (line k1,line k2){ 58 if (sameDir(k1,k2)) return k2.include(k1[0]); 59 return compareangle(k1.dir(),k2.dir()); 60 } 61 int checkpos(line k1,line k2,line k3){return k3.include(getLL(k1,k2));} 62 vector<line> getHL(vector<line> &L){ // 求半平面交 , 半平面是逆时针方向 , 输出按照逆时针 63 sort(L.begin(),L.end()); deque<line> q; 64 for (int i=0;i<(int)L.size();i++){ 65 if (i&&sameDir(L[i],L[i-1])) continue; 66 while (q.size()>1&&!checkpos(q[q.size()-2],q[q.size()-1],L[i])) q.pop_back(); 67 while (q.size()>1&&!checkpos(q[1],q[0],L[i])) q.pop_front(); 68 q.push_back(L[i]); 69 } 70 while (q.size()>2&&!checkpos(q[q.size()-2],q[q.size()-1],q[0])) q.pop_back(); 71 while (q.size()>2&&!checkpos(q[1],q[0],q[q.size()-1])) q.pop_front(); 72 vector<line>ans; for (int i=0;i<q.size();i++) ans.push_back(q[i]); 73 return ans; 74 } 75 int contain(vector<point>A,point q){ // 2 内部 1 边界 0 外部 76 int pd=0; A.push_back(A[0]); 77 for (int i=1;i<A.size();i++){ 78 point u=A[i-1],v=A[i]; 79 if (onS(u,v,q)) return 1; if (cmp(u.y,v.y)>0) swap(u,v); 80 if (cmp(u.y,q.y)>=0||cmp(v.y,q.y)<0) continue; 81 if (sign(cross(u-v,q-v))<0) pd^=1; 82 } 83 return pd<<1; 84 } 85 86 int main() { 87 int n; 88 double ans = 0; 89 scanf("%d", &n); 90 vector<point> p = vector<point>(n); 91 for(int i = 0; i < n; ++i) scanf("%lf %lf", &p[i].x, &p[i].y); 92 for(int i = 0; i < n; ++i) { 93 vector<line> L; 94 L.emplace_back(line{point{-20000, -20000}, point{20000, -20000}}); 95 L.emplace_back(line{point{20000, -20000}, point{20000, 20000}}); 96 L.emplace_back(line{point{20000, 20000}, point{-20000, 20000}}); 97 L.emplace_back(line{point{-20000, 20000}, point{-20000, -20000}}); 98 for(int j = 0; j < n; ++j) { 99 if(i == j) continue; 100 point mid = (p[i] + p[j]) / 2; 101 L.emplace_back(line{mid, (p[j] - mid).turn90() + mid}); 102 } 103 L = getHL(L); 104 int sz = int(L.size()); 105 if(sz > 2) { 106 vector<point> v = vector<point>(sz); 107 for(int j = 0; j < sz; ++j) { 108 v[j] = getLL(L[j], L[(j + 1) % sz]); 109 if(contain(p, v[j])) ans = max(ans, (p[i] - v[j]).abs()); 110 } 111 for(int j = 0; j < sz; ++j) { 112 line l1 = line{v[j], v[(j + 1) % sz]}; 113 for(int k = 0; k < n; ++k) { 114 line l2 = line{p[k], p[(k + 1) % n]}; 115 if(checkSS(v[j], v[(j + 1) % sz], p[k], p[(k + 1) % n])) { 116 point u = getLL(l1, l2); 117 ans = max(ans, (p[i] - u).abs()); 118 } 119 } 120 } 121 } 122 } 123 printf("%.8f\n", ans); 124 return 0; 125 }
考虑分批发放，每次给选中的人一批人各发一个宝石，例如第一步可以看成是给n个人各发一个宝石，第二步则在n个人中选择一个子集，第三步在第二步选中的人中再选择子集……
用f[i][j][k]表示第i批，已经发了j个宝石，目前选中的人集合大小为k的所有方案前r个人的宝石和，g[i][j][k]表示方案数。
转移考虑枚举k个人的子集l，方案数只要乘上C(k, l)，贡献增加是方案数乘min(r, l)。
最后用插板法除个总数就是期望。
第一维空间可以滚动数组，n4敢水敢过。
1 #include <bits/stdc++.h> 2 using namespace std; 3 double c[1005][1005], f[2][505][505], g[2][505][505]; 4 5 int main() { 6 for(int i = 0; i < 1005; ++i) c[i][0] = c[i][i] = 1; 7 for(int i = 2; i < 1005; ++i) 8 for(int j = 1; j < i; ++j) 9 c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; 10 double ans = 0; 11 int n, d, r, o = 0; 12 scanf("%d %d %d", &n, &d, &r); 13 f[0][0][n] = r, g[0][0][n] = 1; 14 for(int i = 2; i <= d + 1; ++i) { 15 o ^= 1; 16 memset(f[o], 0, sizeof(f[o])); 17 memset(g[o], 0, sizeof(g[o])); 18 for(int j = 0; j <= d; ++j) { 19 for(int k = 1; k <= n; ++k) { 20 if(g[o ^ 1][j][k] == 0) continue; 21 for(int l = 1; l <= k; ++l) { 22 if(j + l > d) break; 23 g[o][j + l][l] += g[o ^ 1][j][k] * c[k][l]; 24 f[o][j + l][l] += f[o ^ 1][j][k] * c[k][l] + g[o ^ 1][j][k] * c[k][l] * min(l, r); 25 } 26 } 27 } 28 for(int k = 1; k <= n; ++k) ans += f[o][d][k]; 29 } 30 printf("%.8f\n", ans / c[d + n - 1][d]); 31 return 0; 32 }
枚举格子对判断是否可达，先根据距离和高度差可以求出运动时间，注意判无解的情况，然后可以得到轨迹方程。
然后算这条轨迹在水平面投影的直线，计算投影和每条横线、纵线的交点位置，如果不在4个格子的角落则只要判两边，否则判四周。
最后随便bfs或者floyd一下。
无脑抄板的话只需要一个线段交的样子。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const double g = 9.80665; 4 typedef pair<int, int> pii; 5 vector<pii> G[22][22]; 6 int H[22][22]; 7 8 typedef double db; 9 const db eps=1e-8; 10 int sign(db k){ 11 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 12 } 13 int cmp(db k1,db k2){return sign(k1-k2);} 14 struct point{ 15 db x,y; 16 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 17 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 18 point operator * (db k1) const{return (point){x*k1,y*k1};} 19 point operator / (db k1) const{return (point){x/k1,y/k1};} 20 int operator == (const point &k1) const{return cmp(x,k1.x)==0&&cmp(y,k1.y)==0;} 21 bool operator < (const point k1) const{ 22 int a=cmp(x,k1.x); 23 if (a==-1) return 1; else if (a==1) return 0; else return cmp(y,k1.y)==-1; 24 } 25 db abs(){return sqrt(x*x+y*y);} 26 }; 27 db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;} 28 point getLL(point k1,point k2,point k3,point k4){ 29 db w1=cross(k1-k3,k4-k3),w2=cross(k4-k3,k2-k3); return (k1*w2+k2*w1)/(w1+w2); 30 } 31 int intersect(db l1,db r1,db l2,db r2){ 32 if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2); return cmp(r1,l2)!=-1&&cmp(r2,l1)!=-1; 33 } 34 int checkSS(point k1,point k2,point k3,point k4){ 35 return intersect(k1.x,k2.x,k3.x,k4.x)&&intersect(k1.y,k2.y,k3.y,k4.y)&& 36 sign(cross(k3-k1,k4-k1))*sign(cross(k3-k2,k4-k2))<=0&& 37 sign(cross(k1-k3,k2-k3))*sign(cross(k1-k4,k2-k4))<=0; 38 } 39 40 inline double sq(double x) {return x * x;} 41 inline double cal(double a, double b, double c, double x) { 42 return a * x * x + b * x + c; 43 } 44 int ans[22][22]; 45 int main() { 46 int dx, dy, w, v, lx, ly; 47 scanf("%d %d %d %d %d %d", &dx, &dy, &w, &v, &lx, &ly); 48 for(int i = 1; i <= dy; ++i) 49 for(int j = 1; j <= dx; ++j) 50 scanf("%d", &H[i][j]); 51 for(int i = 1; i <= dy; ++i) { 52 for(int j = 1; j <= dx; ++j) { 53 point p1 = point{(i - 0.5) * w, (j - 0.5) * w}; 54 for(int p = 1; p <= dy; ++p) { 55 for(int q = 1; q <= dx; ++q) { 56 if(i == p && j == q) continue; 57 point p2 = point{(p - 0.5) * w, (q - 0.5) * w}; 58 double h = H[p][q] - H[i][j]; 59 double d = (p1 - p2).abs(); 60 if(sq(v) < g * h || sq(g * h - sq(v)) < sq(g) * (sq(d) + sq(h))) continue; 61 double t = sqrt((sq(v) - g * h + sqrt(sq(g * h - sq(v)) - sq(g) * (sq(d) + sq(h)))) / (sq(g) / 2)); 62 double cost = d / t / v; 63 double a = -0.5 * g / sq(v * cost), b = sqrt(1 - sq(cost)) / cost, c = H[i][j]; 64 int ok = 1; 65 for(int o = 1; o < dy; ++o) { 66 point p3 = point{1.0 * w * o, 0.0}; 67 point p4 = point{1.0 * w * o, 1.0 * w * dx}; 68 if(checkSS(p1, p2, p3, p4)) { 69 point its = getLL(p1, p2, p3, p4); 70 double dis = (its - p3).abs() / w; 71 double ht = cal(a, b, c, (its - p1).abs()); 72 if(abs(int(dis) - dis) < eps) { 73 int x1 = int(dis), x2 = x1 + 1; 74 if(ht < H[o][x1] || ht < H[o + 1][x1]) ok = 0; 75 if(ht < H[o][x2] || ht < H[o + 1][x2]) ok = 0; 76 } 77 else if(abs(int(dis) + 1 - dis) < eps) { 78 int x1 = int(dis) + 1, x2 = x1 + 1; 79 if(ht < H[o][x1] || ht < H[o + 1][x1]) ok = 0; 80 if(ht < H[o][x2] || ht < H[o + 1][x2]) ok = 0; 81 } 82 else { 83 int x = int(dis) + 1; 84 if(ht < H[o][x] || ht < H[o + 1][x]) ok = 0; 85 } 86 } 87 } 88 for(int o = 1; o < dx; ++o) { 89 point p3 = point{0.0, 1.0 * w * o}; 90 point p4 = point{1.0 * w * dy, 1.0 * w * o}; 91 if(checkSS(p1, p2, p3, p4)) { 92 point its = getLL(p1, p2, p3, p4); 93 double dis = (its - p3).abs() / w; 94 double ht = cal(a, b, c, (its - p1).abs()); 95 if(abs(int(dis) - dis) < eps) { 96 int x1 = int(dis), x2 = x1 + 1; 97 if(ht < H[x1][o] || ht < H[x1][o + 1]) ok = 0; 98 if(ht < H[x2][o] || ht < H[x2][o + 1]) ok = 0; 99 } 100 else if(abs(int(dis) + 1 - dis) < eps) { 101 int x1 = int(dis) + 1, x2 = x1 + 1; 102 if(ht < H[x1][o] || ht < H[x1][o + 1]) ok = 0; 103 if(ht < H[x2][o] || ht < H[x2][o + 1]) ok = 0; 104 } 105 else { 106 int x = int(dis) + 1; 107 if(ht < H[x][o] || ht < H[x][o + 1]) ok = 0; 108 } 109 } 110 } 111 if(ok) G[i][j].emplace_back(pii(p, q)); 112 } 113 } 114 } 115 } 116 memset(ans, -1, sizeof(ans)); 117 queue<pii> q; 118 q.push(pii(ly, lx)); 119 ans[ly][lx] = 0; 120 while(!q.empty()) { 121 pii tmp = q.front(); q.pop(); 122 int x = tmp.first, y = tmp.second; 123 for(int i = 0; i < G[x][y].size(); ++i) { 124 pii nxt = G[x][y][i]; 125 int xx = nxt.first, yy = nxt.second; 126 if(ans[xx][yy] == -1) { 127 ans[xx][yy] = ans[x][y] + 1; 128 q.push(nxt); 129 } 130 } 131 } 132 for(int i = 1; i <= dy; ++i) { 133 for(int j = 1; j <= dx; ++j) { 134 if(ans[i][j] == -1) putchar('X'); 135 else printf("%d", ans[i][j]); 136 printf("%c", j == dx ? '\n' : ' '); 137 } 138 } 139 return 0; 140 }
最后两题不看了西西