2019 Multi-University Training Contest 5

左手的ㄟ右手 2021-10-23 16:54 239阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th>Solved</th> 
   <th>Pro.ID</th> 
   <th>Title</th> 
   <th>Ratio(Accepted / Submitted)</th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td>1001</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1001&amp;cid=852" rel="nofollow">fraction</a></td> 
   <td>4.17%(7/168)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>已补</td> 
   <td>1002</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1002&amp;cid=852" rel="nofollow">three arrays</a></td> 
   <td>12.69%(76/599)</td> 
   <td>字典树</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1003</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&amp;cid=852" rel="nofollow">geometric problem</a></td> 
   <td>1.59%(1/63)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>已补</td> 
   <td>1004</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&amp;cid=852" rel="nofollow">equation</a></td> 
   <td>20.65%(310/1501)</td> 
   <td>思维</td> 
  </tr> 
  <tr> 
   <td>已补</td> 
   <td>1005</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1005&amp;cid=852" rel="nofollow">permutation 1</a></td> 
   <td>24.77%(407/1643)</td> 
   <td>dfs+思维</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.hdu.edu.cn/images/ac.gif" alt="img"></td> 
   <td>1006</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&amp;cid=852" rel="nofollow">string matching</a></td> 
   <td>23.12%(724/3131)</td> 
   <td>exkmp</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.hdu.edu.cn/images/ac.gif" alt="img"></td> 
   <td>1007</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1007&amp;cid=852" rel="nofollow">permutation 2</a></td> 
   <td>47.19%(688/1458)</td> 
   <td>DP</td> 
  </tr> 
  <tr> 
   <td><img src="http://acm.hdu.edu.cn/images/ac.gif" alt="img"></td> 
   <td>1008</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&amp;cid=852" rel="nofollow">line symmetric</a></td> 
   <td>1.87%(11/588)</td> 
   <td>计算几何</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1009</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&amp;cid=852" rel="nofollow">discrete logarithm problem</a></td> 
   <td>18.42%(7/38)</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>1010</td> 
   <td><a href="http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&amp;cid=852" rel="nofollow">find hidden array</a></td> 
   <td>6.25%(2/32)</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

## 题目 ##

### 1002 ###

将a序列和b序列存放到两个字典树里面，然后每次贪心的匹配a中的0和b中0，或者a中的1和b中的1，如果没有，那就01或者10。最后获得的数字不一定是当前最小的，不过一定是在C中的，所以只需要在最后排个序就行了。

#include <bits/stdc++.h> using namespace std; const int N = 100010; int son[31*N][2],cnt[62*N],tot,n,x; vector<int> res; inline void insert(int head,int x){ int p = head; for(int i=30;i>=0;i--){ int u = x >> i & 1; if(!son[p][u])son[p][u] = ++tot; p = son[p][u]; cnt[p]++; } } inline int getVal(int p1,int p2){ int res = 0; for(int i=30;i>=0;i--){ if(son[p1][0] && son[p2][0] && cnt[son[p1][0]] && cnt[son[p2][0]]){ p1 = son[p1][0]; p2 = son[p2][0]; cnt[p1]--;cnt[p2]--; } else if(son[p1][1] && son[p2][1] && cnt[son[p1][1]] && cnt[son[p2][1]]){ p1 = son[p1][1]; p2 = son[p2][1]; cnt[p1]--;cnt[p2]--; } else if(son[p1][1] && son[p2][0] && cnt[son[p1][1]] && cnt[son[p2][0]]){ p1 = son[p1][1]; p2 = son[p2][0]; cnt[p1]--;cnt[p2]--; res |= (1<<i); } else if(son[p1][0] && son[p2][1] && cnt[son[p1][0]] && cnt[son[p2][1]]){ p1 = son[p1][0]; p2 = son[p2][1]; cnt[p1]--;cnt[p2]--; res |= (1<<i); } } return res; } int main(){ int T;scanf("%d",&T); while(T--){ tot = 1; res.clear(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&x); insert(0,x); } for(int i=1;i<=n;i++){ scanf("%d",&x); insert(1,x); } for(int i=1;i<=n;i++)res.push_back(getVal(0,1)); sort(res.begin(),res.end()); for(int i=0;i<n;i++){ if(i)printf(" "); printf("%d",res[i]); } puts(""); for(int i=0;i<=tot;i++){ son[i][0] = son[i][1] = 0; cnt[i] = 0; } } return 0; }

### 1004 ###

把n个等式按照 \\(-b\\over a\\) 从小到大排序，然后可以发现把n条线\\(x=\{-b\\over a\}\\)画到坐标轴上面可以把x分为n+1个区域，针对每个区域，可以将每个等式的绝对值去掉，然后加到一起变成一个等式，直接解出来看x在不在这个范围即可

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 100010; ll n; int t; ll C; ll gcd(ll a,ll b){ return b == 0 ? a : gcd(b,a%b); } struct node{ int a,b; bool operator <(const node y){ return (-b) * y.a < -y.b * a; } }a[N]; ll aa[N],bb[N],tot; int main(){ scanf("%d",&t); while(t--){ tot = 0; scanf("%lld%lld",&n,&C); ll A = 0,B = 0; for(ll i=1;i<=n;i++){ scanf("%lld%lld",&a[i].a,&a[i].b); A += a[i].a; B += a[i].b; } sort(a+1,a+n+1); ll resa = 0, resb = 0; bool flag = false; for(ll i=n;i>=0;i--){ if(A == 0){ if(B == C){ flag = true; break; } else { continue; } } resa = C-B; resb = A; if(resb < 0){ resa = - resa; resb = - resb; } ll g = gcd(resa > 0 ? resa : -resa,resb); if(g > 1){ resa/=g; resb/=g; } if(i >= 1){ A -= 2 * a[i].a; B -= 2 * a[i].b; } if(i >= 1 && resa * a[i].a < (-a[i].b * resb))continue; if(i < n && resa * a[i+1].a >= (-a[i+1].b * resb))continue; aa[++tot] = resa; bb[tot] = resb; } if(flag)puts("-1"); else{ printf("%lld",tot); for(ll i = tot; i>= 1;i--){ printf(" %lld/%lld",aa[i],bb[i]); } puts(""); } } return 0; }

### 1005 ###

企图用组合数学，一直wa找不着北，场后先找到前两个数字然后再dfs还是wa，看题解明白了，但是并不知道自己错在哪里

#include <bits/stdc++.h> using namespace std; const int N = 50; int n,k; int d[N],u[N]; //d中存在n个数字，他们表示着相对大小，实际大小由整个数组的low和hi决定。 //low表示现在填过的数字中最大的和最小的数字是多少。 int dfs(int x,int low,int hi){ if(x == n){ k --; if(k == 0){ for(int i=0;i<n;i++){ if(i)printf(" "); printf("%d",d[i] - low + 1); } puts(""); return 1; } return 0; } for(int i = hi - n + 1;i <= low + n -1;i++){ if(u[i])continue; u[i] = 1; d[x] = i; if(dfs(x+1,min(low,i),max(hi,i)) == 1){ u[i] = 0; return 1; } u[i] = 0; } return 0; } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%d%d",&n,&k); d[0] = n; u[n] = 1; dfs(1,n,n); u[n] = 0; } return 0; }

### 1006 ###

开场SA+LCP获得一T（看SA看晕了），回过头来发现就是个exkmp，直接上板子

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6+10; char s[N]; int nxt[N]; void pre_EKMP(char x[],int m){ nxt[0] = m; int j = 0; while(j+1 < m && x[j] == x[j+1])j++; nxt[1] = j; int k = 1; for(int i=2;i<m;i++){ int p = nxt[k] + k - 1; int l = nxt[i-k]; if(i + l < p + 1)nxt[i] = l; else{ j = max(0,p-i+1); while(i + j < m && x[i+j] == x[j])j++; nxt[i] = j; k = i; } } } int main(){ int T;scanf("%d",&T); while(T--){ scanf("%s",s); int len = strlen(s); pre_EKMP(s,len); ll res = 0; for(int i=1;i<len;i++){ if(nxt[i] == len - i){ res += nxt[i]; } else res += nxt[i] + 1; } printf("%lld\n",res); } return 0; }

### 1007 ###

学长过的，是我不会的DP

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 998244353; ll dp[100005][2]; int main() { dp[3][0] = 1LL; dp[3][1] = 0LL; dp[4][0] = 1LL; dp[4][1] = 1LL; for(int i = 5; i <= 100000; i++) { dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod; dp[i][1] = dp[i - 2][0]; } int T; scanf("%d", &T); while(T--) { int n, x, y; scanf("%d%d%d", &n, &x, &y); if(x + 1 == y && n > 3) { if(y == n || x == 1) puts("1"); else puts("0"); continue; } ll ans = 0; int l, r; if(x == 1) l = 1; else l = x + 1; if(y == n) r = n; else r = y - 1; r -= l - 1; //cout << r << endl; if(r <= 3) ans = 1LL; else ans = (dp[r][0] + dp[r][1]) % mod; printf("%lld\n", ans); } return 0; }

### 1008 ###

学长过的，我什么都不会

#include <bits/stdc++.h> using namespace std; const double eps = 1e-8; int cmp(double x) { if (fabs(x) < eps) return 0; if (x > 0) return 1; return -1; } const double pi = acos(-1.0); inline double sqr(double x) { return x * x; } struct point { double x, y; point() {} point(double a, double b) : x(a), y(b) {} void input() { scanf("%lf%lf", &x, &y); } friend point operator + (const point &a, const point &b) { return point(a.x + b.x, a.y + b.y); } friend point operator - (const point &a, const point &b) { return point(a.x - b.x, a.y - b.y); } friend bool operator == (const point &a, const point &b) { return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0; } friend point operator * (const point &a, const double &b) { return point(a.x * b, a.y * b); } friend point operator * (const double &a, const point &b) { return point(a * b.x, a * b.y); } friend point operator / (const point &a, const double &b) { return point(a.x / b, a.y / b); } double norm(){ return sqrt(sqr(x) + sqr(y)); } }; double det(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } double dot(const point &a, const point &b) { return a.x * b.x + a.y * b.y; } double dist(const point &a, const point &b) { return (a - b).norm(); } point rotate_point(const point &p, double A){ double tx = p.x, ty = p.y; return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A)); } struct line { point a, b; line() {} line(point x, point y) : a(x), b(y) {} }; line point_make_line(const point a, const point b) { return line(a, b); } double dis_point_segment(const point p, const point s, const point t) { if(cmp(dot(p - s, t - s)) < 0) return (p - s).norm(); if(cmp(dot(p - t, s - t)) < 0) return (p - t).norm(); return fabs(det(s - p, t - p) / dist(s, t)); } void PointProjLine(const point p, const point s, const point t, point &cp){ double r = dot((t - s), (p - s)) / dot(t - s, t - s); cp = s + r * (t - s); } bool PointOnSegment(point p, point s, point t){ return cmp(det(p - s, t - s)) == 0 && cmp(dot(p - s, p - t)) <= 0; } bool parallel(line a, line b){ return !cmp(det(a.a - a.b, b.a - b.b)); } bool line_make_point(line a, line b, point &res){ if(parallel(a, b)) return false; double s1 = det(a.a - b.a, b.b - b.a); double s2 = det(a.b - b.a, b.b - b.a); res = (s1 * a.b - s2 * a.a) / (s1 - s2); return true; } line move_d(line a, const double &len){ point d = a.b - a.a; d = d / d.norm(); d = rotate_point(d, pi / 2); return line(a.a + d * len, a.b + d * len); } bool SegmentSamePoints(line i, line j){ return max(i.a.x, i.b.x) >= min(j.a.x, j.b.x) && max(j.a.x, j.b.x) >= min(i.a.x, i.b.x) && max(i.a.y, i.b.y) >= min(j.a.y, j.b.y) && max(j.a.y, j.b.y) >= min(i.a.y, i.b.y) && cmp(det(j.a - i.a, i.b - i.a) * det(j.b - i.a, i.b - i.a)) <= 0 && cmp(det(i.a - j.a, j.b - j.a) * det(i.b - j.a, j.b - j.a)) <= 0; } int T; int n; point a[1005]; int main(){ scanf("%d", &T); while(T--){ scanf("%d", &n); for(int i = 0; i < n; i++){ a[i].input(); } if(n < 5){ puts("Y"); continue; } bool ans = false; // 关于某条边的中垂线对称 for(int i = 0; i < n; i++){ point fir = a[i]; point sec = a[(i + 1) % n]; point mid_p = (fir + sec) / 2; point ss1 = sec - fir; point mid_q = rotate_point(ss1, pi / 2) * (2500.0) + mid_p; point mid_r = rotate_point(ss1, -pi / 2) * (2500.0) + mid_p; int cnt = 0; for(int j = 1; j <= (n + 1) / 2 - 1; j++){ fir = a[(i + 1 + j) % n]; sec = a[(i - j + n) % n]; if(!(fir == sec) && cmp(dis_point_segment(fir, mid_q, mid_r)) == 0 && cmp(dis_point_segment(sec, mid_q, mid_r)) == 0){ cnt = 20; break; } point mid_c = (fir + sec) / 2; if(cmp(dis_point_segment(mid_c, mid_q, mid_r)) != 0){ cnt++; } point cp1, cp2; PointProjLine(fir, mid_q, mid_r, cp1); PointProjLine(sec, mid_q, mid_r, cp2); if(!(cp1 == cp2)){ cnt++; } if(n % 2 == 0 && j == (n + 1) / 2 - 1){ point ss1 = a[(i + j) % n] - mid_q; point ss2 = a[(i + j + 1) % n] - mid_q; point ss3 = a[(i + j + 2) % n] - mid_q; point ss4 = a[(i + j + 3) % n] - mid_q; point ss5 = mid_r - mid_q; int bb1 = cmp(det(ss5, ss2)); int bb2 = cmp(det(ss5, ss1)); int bb3 = cmp(det(ss5, ss3)); int bb4 = cmp(det(ss5, ss4)); int bb5 = bb1 * bb2; int bb6 = bb4 * bb3; if(bb5 > 0 || bb6 > 0){ ; } else{ cnt += 20; } } if(cnt > 1){ break; } } if(cnt <= 1){ ans = true; break; } } if(ans){ puts("Y"); continue; } // 偶数点时：关于对边连线对称 if(n % 2 == 0){ for(int i = 0; i < n / 2; i++){ point fir = a[i]; point sec = a[i + n / 2]; point ss1 = sec - fir; point mid_q = ss1 * 2500.0 + fir; point mid_r = ss1 * (-2500.0) + fir; int cnt = 0; for(int j = 1; j < n / 2; j++){ fir = a[(i + j) % n]; sec = a[(i - j + n) % n]; if(!(fir == sec) && cmp(dis_point_segment(fir, mid_q, mid_r)) == 0 && cmp(dis_point_segment(sec, mid_q, mid_r)) == 0){ cnt = 20; break; } point mid_c = (fir + sec) / 2; if(cmp(dis_point_segment(mid_c, mid_q, mid_r)) != 0){ cnt++; continue; } point cp1, cp2; PointProjLine(fir, mid_q, mid_r, cp1); PointProjLine(sec, mid_q, mid_r, cp2); if(!(cp1 == cp2)){ cnt++; } if(cnt > 1){ break; } } if(cnt <= 1){ ans = true; break; } } if(ans){ puts("Y"); continue; } } // 奇数点时：检查能不能调整正对的两个点。 else{ for(int i = 0; i < n; i++){ point fir = a[(i + 1) % n]; point sec = a[(i - 1 + n) % n]; point mid_p = (fir + sec) / 2; point ss1 = mid_p - a[i]; point mid_q = ss1 * 2500.0 + a[i]; point mid_r = ss1 * (-2500.0) + a[i]; int cnt = 0; for(int j = 1; j <= n / 2; j++){ // printf("%d\n", j); fir = a[(i + j) % n]; sec = a[(i - j + n) % n]; if(!(fir == sec) && cmp(dis_point_segment(fir, mid_q, mid_r)) == 0 && cmp(dis_point_segment(sec, mid_q, mid_r)) == 0){ cnt = 20; break; } point mid_c = (fir + sec) / 2; if(cmp(dis_point_segment(mid_c, mid_q, mid_r)) != 0){ // printf("%d: mid wrong\n", j); cnt++; } point cp1, cp2; PointProjLine(fir, mid_q, mid_r, cp1); PointProjLine(sec, mid_q, mid_r, cp2); if(!(cp1 == cp2)){ // printf("%d: cp wrong\n", j); cnt++; } point ss1 = a[(i + j - 1 + n) % n] - mid_q; point ss2 = a[(i + j) % n] - mid_q; point ss3 = a[(i + j + 1) % n] - mid_q; point ss4 = a[(i + j + 2) % n] - mid_q; point ss5 = mid_r - mid_q; int bb1 = cmp(det(ss5, ss2)); int bb2 = cmp(det(ss5, ss1)); int bb3 = cmp(det(ss5, ss3)); int bb4 = cmp(det(ss5, ss4)); int bb5 = bb1 * bb2; int bb6 = bb4 * bb3; if(bb5 > 0 || bb6 > 0){ ; } else{ cnt += 20; } if(cnt > 1){ break; } } if(cnt <= 1){ // printf("%d\n", i); ans = true; break; } } if(ans){ puts("Y"); continue; } } // 偶数时：还要检查是不是正对面的点是偏的 if(n % 2 == 0){ for(int i = 0; i < n; i++){ point fir = a[(i + 1) % n]; point sec = a[(i - 1 + n) % n]; point mid_p = (fir + sec) / 2; point ss1 = mid_p - a[i]; point mid_q = ss1 * 2500.0 + a[i]; point mid_r = ss1 * (-2500.0) + a[i]; int cnt = 0; for(int j = 1; j <= n / 2; j++){ fir = a[(i + j) % n]; sec = a[(i - j + n) % n]; if(!(fir == sec) && cmp(dis_point_segment(fir, mid_q, mid_r)) == 0 && cmp(dis_point_segment(sec, mid_q, mid_r)) == 0){ cnt = 20; break; } point mid_c = (fir + sec) / 2; if(cmp(dis_point_segment(mid_c, mid_q, mid_r)) != 0){ cnt++; continue; } point cp1, cp2; PointProjLine(fir, mid_q, mid_r, cp1); PointProjLine(sec, mid_q, mid_r, cp2); if(!(cp1 == cp2)){ cnt++; } if(cnt > 1){ break; } } if(cnt <= 1){ ans = true; break; } } if(ans){ puts("Y"); continue; } } if(ans){ puts("Y"); } else{ puts("N"); } } return 0; }

转载于:https://www.cnblogs.com/1625--H/p/11305662.html