# ECNU 2018 程序能力实训第一次机考（下午场）

xiaoxiao2021-02-28  2

https://acm.ecnu.edu.cn/contest/64/

A.闪卡销售

### Output

#include <bits/stdc++.h> using namespace std; const int maxn = 1200; struct info{ int x; int price; info(int a = 0 , int b = 0):x(a),price(b){}; bool operator < (const info& rhs){ return rhs.price < price; } }; int num[maxn]; vector<info> vec; int main() { int n = 0 , m = 0; cin >> n >> m; int x = 0, y = 0; for (int i = 1 ; i <= n ;++i) cin >> num[i]; for (int i = 0 ; i < m ; ++i) { cin >> x >> y; vec.push_back(info(x,y)); } sort(vec.begin(),vec.end()); int ans = 0; int sz = vec.size(); for (int i = 0 ; i < sz ; ++i) { x = vec[i].x; y = vec[i].price; if(num[x]) { ans += y*num[x]; num[x] = 0; } } cout << ans << endl; return 0; }

B. DNA 排序题

### Output

#include <bits/stdc++.h> using namespace std; const int maxn = 200000; struct Dna{ string info; int occur; bool operator < (const Dna& rhs){ if(occur == rhs.occur) return info < rhs.info; return occur < rhs.occur; } }; Dna seq[maxn]; int cnt = 1; int main() { int n = 0; cin >> n; string str; map<string,int> mps; for (int i = 0 ; i < n ; ++i){ cin >> str; int t = mps[str]; if(t != 0) seq[t].occur++; else { mps[str] = cnt; seq[cnt].info = str; seq[cnt++].occur = 1; } } sort(seq+1,seq+cnt); for (int i = 1 ; i < cnt ; ++i) cout << seq[i].info << endl; return 0; }

C. 字符串替换

### Output

D. 移动游戏

U: (x,y)(x,y+1)D: (x,y)(x,y1)L: (x,y)(x1,y)R: (x,y)(x+1,y)

### Input

30%: 100a,b100, 保证只会出现 U, D 或只会出现 L, R, 1q100;70%: |a|,|b|200,1q105;100%: |a|,|b|109,1q105.

### Output

#include <bits/stdc++.h> const int maxn = 200; using namespace std; int sz = 0; typedef long long long_int; struct Vector{ long_int x , y; Vector(long_int _x = 0 , long_int _y = 0):x(_x),y(_y){} /* Vector operator * (const int& k){ return Vector(x*k,y*k); } */ Vector operator + (const Vector & rhs){ return Vector(x+rhs.x,y+rhs.y); } Vector operator - (const Vector & rhs){ return Vector(x-rhs.x,y-rhs.y); } Vector operator = (const Vector& rhs){ x = rhs.x; y = rhs.y; } bool operator == (const Vector& rhs) const{ return (x == rhs.x) && (y == rhs.y); } bool buildby (const Vector& rhs)const { if(x == 0 && y == 0) return true; if(rhs.x == 0 && rhs.y == 0) return false; if(x * rhs.x < 0) return false; if(y * rhs.y < 0) return false; if(rhs.x == 0 && x != 0) return false; if(x == 0 && rhs.x != 0) return false; if(rhs.y == 0 && y != 0) return false; if(y == 0 && rhs.y != 0) return false; if(x == 0) return (y % rhs.y == 0); else if (y == 0) return (x % rhs.x == 0); else { if(y % rhs.y != 0 || x % rhs.x != 0) return false; int k1 = y / rhs.y; int k2 = x / rhs.x; return k1 == k2; } } void putLocation(){ cout << x <<' ' << y << endl; } }; Vector arr[maxn]; const Vector Up(0,1); const Vector Down(0,-1); const Vector Left(-1,0); const Vector Right(1,0); Vector EndSequence; string str; int querys; bool solve_Equation(Vector target){ for (int i = 0 ; i <= sz ; ++i){ Vector new_Vec = target - arr[i]; if(new_Vec.buildby(EndSequence)) return true; } return false; } int main() { arr[0] = Vector(0,0); cin >> str; cin >> querys; sz = str.size(); for (int i = 1 ; i <= sz ; ++i) { switch(str[i-1]) { case 'U' : arr[i] = arr[i-1] + Up; break; case 'D' : arr[i] = arr[i-1] + Down;break; case 'L' : arr[i] = arr[i-1] + Left;break; case 'R' : arr[i] = arr[i-1] + Right;break; } } EndSequence = arr[sz]; Vector target; long_int cx = 0, cy = 0; for (int i = 0 ; i < querys ; ++i) { cin >> cx >> cy; target = Vector(cx,cy); if(solve_Equation(target)){ cout << "Yes" << endl; } else { cout << "No" << endl; } } return 0; }

E. 字串变换

### Output

#include <bits/stdc++.h> using namespace std; typedef long long long_int; const long_int maxss = 20000100; const int maxn = 100050; char s[120]; int n = 0; struct data{ int length; vector<char> alpha; vector<int> occur; }; data seq[maxn]; int sum[maxn]; int max_num[maxn]; int total_len = 0; long_int try_aver(int index , int aver){ long_int res = 0; for (int i = 0 ; i < n ; ++i) res += abs(seq[i].occur[index] - aver); return res; } int solve(){ int ans = 0; total_len = seq[0].length; long_int tmp = 0; for (int i = 0 ; i < total_len ; ++i) { tmp = maxss; long_int tmp1 = 0 , tmp2 = 0; int l = 1 , r = 100; while(l <= r) { int mid = (l+r) >> 1; tmp1 = try_aver(i,mid); tmp2 = try_aver(i,mid+1); if(tmp1 < tmp2) { r = mid - 1; tmp = min(tmp,tmp1); } else { l = mid + 1; tmp = min(tmp,tmp2); } } ans += tmp; } return ans; } int main() { cin >> n; for (int i = 0 ; i < n ; ++i){ scanf("%s",s); // puts(s); int cnt = 0; char t = 0; int len = strlen(s); for (int j = 0 ; j < len ; ++j) { if(t != s[j]) { if(t != 0) { seq[i].alpha.push_back(t); seq[i].occur.push_back(cnt); sum[seq[i].length] += cnt; seq[i].length++; } t = s[j]; cnt = 1; } else cnt++; } if(t != 0) { seq[i].alpha.push_back(t); seq[i].occur.push_back(cnt); sum[seq[i].length] += cnt; max_num[seq[i].length] = max(cnt,max_num[seq[i].length]); seq[i].length++; if(seq[i].length != seq[0].length){ cout << -1 << endl; return 0; } for (int j = 0 ; j < seq[j].length ; ++j) { if(seq[i].alpha[j] != seq[0].alpha[j]) { cout << -1 << endl; return 0; } } } } // above are inputs; cout << solve() << endl; return 0; }