1. f1 score
首先了解f1 score的计算方法， 我记得是学信息检索知道的， 然后简单处理就行。 由于我写的比较麻烦， 中间处理过程引入了一些除数为0的情况，导致错了很多次。其实是很简单的。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e3 + 10; 7 8 char c1x[5], c2x[5]; 9 void solve() { 10 int n; 11 int a, b, c, d; 12 a = b = c = d = 0; 13 scanf("%d", &n); 14 char c1, c2; 15 for (int i = 0; i < n; i++) { 16 scanf("%s%s", c1x, c2x); 17 c1 = c1x[0];c2 = c2x[0]; 18 //cout << c1 << " " << c2 << endl; 19 if(c1 == '+') { 20 if(c2 == '+') a++; 21 else b++; 22 } else { 23 if(c2 == '+') c++; 24 else d++; 25 } 26 } 27 //if(a + b == 0 || a + c == 0) { 28 // printf("0.00%% "); 29 // return; 30 //} 31 //double x1 = a + b == 0 ? 0 : 1.0 * a / (a + b); 32 //double x2 = a + c == 0 ? 0 : 1.0 * a / (a + c); 33 //double res = (x1 + x2 == 0) ? 0 : 100.0 * 2 * (x1 * x2) / ((x1 + x2)); 34 double res = 100.0 * 2 * a / (2.0 * a + b + c); 35 printf("%.2f%% ", res); 36 } 37 38 int main() { 39 //freopen("test.in", "r", stdin); 40 41 solve(); 42 return 0; 43 }
2. 数组重排2
没有做出来。当时的考虑是：最差情况下需要移动 n-1次，而不是n次。每次移动之后不知道怎么考虑。想了好久没有想出来。
后来看答案，就是从末尾向前找，从n开始，连续的能得到几个，剩下的都是需要移动的。感觉很巧妙。关键在于理解不需要移动的，最多有多少个。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 8 int n; 9 int a[maxn]; 10 void solve() { 11 cin >> n; 12 for (int i = 0; i < n; i++) 13 cin >> a[i]; 14 int t = n; 15 for (int i = n - 1; i >= 0; i--) { 16 if(a[i] == t) { 17 t--; 18 } 19 } 20 cout << t << endl; 21 } 22 23 int main() { 24 freopen("test.in", "r", stdin); 25 //freopen("test.out", "w", stdout); 26 ios::sync_with_stdio(0); 27 cin.tie(0); cout.tie(0); 28 solve(); 29 return 0; 30 }
3. 逆序对
很经典的问题， mergesort或者树状数组。我写的不熟练，花费了一些时间。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 int f[maxn]; 8 int n; 9 int lb(int x) { 10 return x & -x; 11 } 12 void update(int x) { 13 while(x <= n) { 14 f[x]++; 15 x += lb(x); 16 } 17 } 18 int ask(int x) { 19 int r = 0; 20 while(x > 0) { 21 r += f[x]; 22 x -= lb(x); 23 } 24 return r; 25 } 26 int a[maxn]; 27 void solve() { 28 cin >> n; 29 for (int i = 0; i < n; i++) cin >> a[i]; 30 ll res = 0; 31 for (int i = n - 1; i >= 0; i--) { 32 res += ask(a[i]); 33 update(a[i]); 34 } 35 cout << res << endl; 36 } 37 38 int main() { 39 freopen("test.in", "r", stdin); 40 //freopen("test.out", "w", stdout); 41 ios::sync_with_stdio(0); 42 cin.tie(0); cout.tie(0); 43 solve(); 44 return 0; 45 }
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 int a[maxn], b[maxn]; 8 int n; 9 ll res; 10 void mg(int left, int mid, int right) { 11 int x = left, y = mid; 12 for (int i = left; i <= right; i++) { 13 if(y > right || ( x < mid && a[x] <= a[y])) { 14 b[i] = a[x]; 15 x++; 16 } else { 17 res += (mid - x); 18 //cout << x << " " << y <<endl; 19 // cout << left << " " << mid << " " << right <<endl; 20 //cout << res << endl; 21 b[i] = a[y]; y++; 22 } 23 } 24 memcpy(a + left, b + left, sizeof(int) * (right - left + 1)); 25 } 26 void mgsort(int left, int right) { 27 if(left >= right) return; 28 int mid = (left + right) / 2; 29 mgsort(left, mid); 30 mgsort(mid + 1, right); 31 mg(left, mid + 1, right); 32 } 33 void solve() { 34 cin >> n; 35 for (int i = 0; i < n; i++) cin >> a[i]; 36 mgsort(0, n - 1); 37 cout << res << endl; 38 } 39 40 int main() { 41 freopen("test.in", "r", stdin); 42 //freopen("test.out", "w", stdout); 43 ios::sync_with_stdio(0); 44 cin.tie(0); cout.tie(0); 45 solve(); 46 return 0; 47 }
4. 逃离迷宫3
不知道怎么怎么做，感觉很麻烦。
分析起来比较复杂，暂时先放弃了。