Codeforces Round #Pi (Div. 2) （ABCD） codeforce

A 解析：

水题，就是求每个数之间的距离的最大值和最小值。

mycode

#include #include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10; int n; int x[N]; int main() { while(scanf("%d", &n) != EOF) { for(int i = 1; i <= n; i++) { scanf("%d", &x[i]); } int minv, maxv; minv = abs(x[2] - x[1]); maxv = abs(x[n] - x[1]); printf("%d %d\n", minv, maxv); for(int i = 2; i <= n - 1; i++) { minv = min(abs(x[i] - x[i-1]), abs(x[i+1] - x[i])); maxv = max(abs(x[n] - x[i]), abs(x[i] - x[1])); printf("%d %d\n", minv, maxv); }minv = abs(x[n] - x[n-1]); maxv = abs(x[n] - x[1]); printf("%d %d\n", minv, maxv); } return 0; }

B 题意

【Codeforces Round #Pi (Div. 2) （ABCD）】给你一个日志文件系统
+ 进入的编号
- 出去的编号
问最多人的时候是几个人。

解析：

用数组模拟，每个id的出入情况。

mycode

#include #include #include #include #include using namespace std; const int N = 1e6 + 10; int n; char oper[5]; int r; int A[N]; int main() { while(scanf("%d", &n) != EOF) { memset(A, 0, sizeof(A)); int cur = 0, maxv = 0; for(int i = 0; i < n; i++) { scanf("%s%d", oper, &r); if(oper[0] == '-') { if(!A[r]) { maxv++; maxv = max(maxv, cur); }else { A[r]--, cur--; } }else { if(!A[r]) { cur++; maxv = max(maxv, cur); A[r]++; } } } printf("%d\n", maxv); } return 0; }

C 题意：

给出一个序列的公比，问再这个序列中，存在着多少个a,a?k,a?k?k 这样的等比序列。

解析：

简单的dp问题，dp1[i]表示从前到后第i个位置 A[i]/k 有多少个，
dp2[i]表示从后到前第i个 A[i]?k 有多少个。
那么最后的总和就是∑dp1[i]?dp2[i]

mycode

#include #include #include #include using namespace std; typedef long long ll; const int N = 2e5 + 10; ll dp[N], dp2[N]; map mp; ll n, k; ll a[N]; int main() { while(scanf("%lld%lld", &n, &k) != EOF) { memset(dp, 0, sizeof(dp)); memset(dp2, 0, sizeof(dp2)); mp.clear(); for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); if(a[i] % k == 0) { dp[i] = mp[a[i]/k]; } mp[a[i]]++; } mp.clear(); for(int i = n; i >= 1; i--) { dp2[i] = mp[a[i]*k]; mp[a[i]]++; } ll ans = 0; for(int i = 1; i <= n; i++) { ans += dp[i] * dp2[i]; } printf("%lld\n", ans); } return 0; }

D 题意：

A和B在 1?n 的平面上面玩一个战船游戏，这个游戏先由A放置战船再由B来击落战船，现在由B来执行击落战船m次，最早哪次和之前给出的条件矛盾。

解析：

二分最小的不符合条件的答案。

mycode

#include #include #include #include #define pb push_back using namespace std; const int N = 2e5 + 10; int n, m, K, a; int x[N]; bool check(int q) { vector xx; for(int i = 0; i < q; i++) xx.pb(x[i]); xx.pb(0); xx.pb(n+1); sort(xx.begin(), xx.end()); int cnt = 0; for(int i = 1; i < xx.size(); i++) { int len = xx[i] - xx[i-1]; cnt += len / (a + 1); } return cnt >= K; }int main() { while(scanf("%d%d%d", &n, &K, &a) != EOF) { scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%d", &x[i]); } int L = 0, R = m; while(L < R) { int M = (L + R + 1) >> 1; if(check(M)) L = M; else R = M - 1; } if(L == m) printf("%d\n", -1); else printf("%d\n", L+1); } return 0; }