BestCoder #86

今年暑假最后一次BC了，结果B题少加了个判断终测WA了，很不爽......

求出所有数的和$sum$，如果$q>sum$那么肯定记多了。

时间复杂度$O(n)$。

以上是引用官方题解...

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;//#pragma comment(linker, "/STACK:1024000000,1024000000")#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;const double PI = 3.1415926536;
const double eps = 1e-6;
const int MAXN = 100000 + 5;int T, N, M;
int V[MAXN];
LL Q, SUM;int main() {
#ifndef ONLINE_JUDGEFIN;// FOUT;
#endif // ONLINE_JUDGEscanf ("%d", &T);while (T--) {scanf ("%d %d", &N, &M);SUM = 0LL;for (int i = 1; i <= N; i++) {scanf ("%d", &V[i]);SUM += V[i];}for (int i = 1; i <= M; i++) {scanf ("%I64d", &Q);if (Q > SUM) {putchar ('1');continue;} else {putchar ('0');}}putchar ('\n');}return 0;
}

1002 NanoApe Loves Sequence[hdu 5805]

求出前$i$个数里相邻差值的最大值f_if​i​​，$i$到$n$里相邻差值的最大值g_ig​i​​，那么ans=\sum_{i=1}^n \max(|A_{i-1}-A_{i+1}|,f_{i-1},g_{i+1})ans=∑​i=1​n​​max(∣A​i−1​​−A​i+1​​∣,f​i−1​​,g​i+1​​)。

时间复杂度$O(n)$。

以上是引用官方题解...

我的做法是求出N个数相邻的最大值，然后将删除第一个节点和删除最后一个节点和删除中间节点分开来算。

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;//#pragma comment(linker, "/STACK:1024000000,1024000000")#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;const double PI = 3.1415926536;
const double eps = 1e-6;
const int MAXN = 100000 + 5;int T, N, M;
int A[MAXN];
PII F[MAXN];
int main() {
#ifndef ONLINE_JUDGEFIN;
#endif // ONLINE_JUDGEscanf ("%d", &T);while (T--) {scanf ("%d", &N);for (int i = 1; i <= N; i++) {scanf ("%d", &A[i]);}LL res = 0LL;for (int i = 1; i <= N - 1; i++) {F[i].fst = abs (A[i + 1] - A[i]);F[i].snd = i;}sort (F + 1, F + N);reverse (F + 1, F + N);/// delete 1if (F[1].snd == 1) res += F[2].fst;else res += F[1].fst;/// delete Nif (F[1].snd == N - 1) res += F[2].fst;else res += F[1].fst;/// delete 2 ~ N-1for (int i = 2, w; i <= N - 1; i++) {w = abs (A[i + 1] - A[i - 1]);int p = 1;while (F[p].snd == i || F[p].snd == i - 1) p++;if(p == N) res += w;    /// 竟然在这里没有加判断， Too Young Too Simple!...else res += max (w, F[p].fst);}printf("%I64d\n", res);}return 0;
}

1002 NanoApe Loves Sequence[hdu 5806]

将不小于$m$的数看作$1$，剩下的数看作$0$，那么只要区间内$1$的个数不小于$k$则可行，枚举左端点，右端点可以通过two-pointer求出。

时间复杂度$O(n)$。

看了题解之后恍然大悟的感觉...

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;//#pragma comment(linker, "/STACK:1024000000,1024000000")#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
#define lson            l, mid, rt << 1
#define rson            mid + 1, r, rt << 1 | 1typedef __int64  LL;
//typedef long long LL;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;const int MAXN = 200000 + 5;int T, N, M, K;
int pre[MAXN];int main() {
#ifndef ONLINE_JUDGEFIN;
#endif // ONLINE_JUDGEscanf ("%d", &T);while (T--) {scanf ("%d %d %d", &N, &M, &K);pre[0] = 0;for (int i = 1, temp; i <= N; i++) {scanf ("%d", &temp);pre[i] = pre[i - 1] + (int) (temp >= M);}LL res = 0LL;int L, R, v, p = 1;for (int i = 1; i <= N; i++) {L = i, R = K + L - 1;if (R > N) break;v = pre[L - 1] + K;while (p <= N && pre[p] < v) p++;if (pre[p] < v) break;res += N - p + 1;}printf ("%I64d\n", res);}return 0;
}