T1
思路
看到样例和数据范围就明白了些什么。(b - a)/2 + 1。但是需要(特判!!!!)
代码
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll read() {
ll x = 0, f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
ll a,b;
int main() {
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
while(cin>>a>>b) {
if(b <= 1) {
puts("0");
continue;
}
if(b <= 2) {
puts("1");
continue;
}
int now = 0;
if(a == b || a == b - 1) {
puts("2");
continue;
}
if(a > 1) now = 1;
cout<<(b-a)/2 + now<<endl;
}
return 0;
}
T2
0分思路
一开始的思路是先处理一下前缀和，然后二分长度。然后预处理出每一个点和其之前的b个点的权值和。然后去check当前长度是否能满足sum[i] - sum[l] - a[i] <= p a[i] 为预处理出的数组。然后还需要用一个st表来维护一下a数组的区间最值。然后MLE了、、、
100分思路
这个题的正解是用双指针 + 单调队列。和上面一样先预处理出a数组和sum数组。然后用双指针尽可能扩大区间长度，并且用单调队列维护处a数组的最大值。
代码
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 2000000 + 100;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
ll sum[N],a[N];
int q[N],head = 1,tail;
int ans = -1;
int main() {
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int n = read(); ll p = read(); int d = read();
for(int i = 1;i <= n;++i) sum[i] = sum[i - 1] + read();
for(int i = 1; i<= n;++i) a[i] = sum[i] - sum[max(0,i - d)];
int ans = 0;
int l = 0;
for(int r = 1;r <= n;++r) {
while(a[q[tail]] <= a[r] && tail >= head) tail--;
q[++tail] = r;
while(sum[r] - sum[l] - a[q[head]] > p && l < r) {
l++;
while(tail >= head && q[head] < l + d) head++;
}
if(sum[r] - sum[l] - a[q[head]] <= p) ans = max(ans,r - l);
}
cout<<ans;
return 0;
}
T3
思路
(n_3)过1000
代码
#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
typedef long long ll;
map<int,int>ma;
ll read() {
ll x = 0, f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int a[N][N],b[N],tmp[N];
int n,k,now;
void lisan() {
for(int i = 1;i <= n; ++i) tmp[i] = b[i];
sort(tmp + 1,tmp + n + 1);
ma[tmp[1]] = ++now;
for(int i = 2;i <= n;++i) {
if(tmp[i] != tmp[i - 1])
ma[tmp[i]] = ++now;
}
for(int i = 1;i <= n;++i) b[i] = ma[b[i]];
}
void BF1() {
for(int i = 1;i <= n;++i) b[i] = read();
lisan();
for(int i = 1;i <= now;++i)
for(int j = 1;j < i; ++j)
a[i][j] = 1;
tmp[++n] = 0x7fffffff;
for(int i = 1;i <= k;++i) {
int l = read(),r = read();
l = ma[tmp[upper_bound(tmp + 1,tmp + n + 1,l) - tmp]];
r = ma[tmp[upper_bound(tmp + 1,tmp + n + 1,r) - tmp - 1]];
for(int j = l;j <= r;++j) {
for(int k = l;k < j;++k) {
a[k][j] ^= 1;
a[j][k] ^= 1;
}
}
}
ll ans = 0;
for(int i = 1;i <= now;++i) {
for(int j = 1;j < i;++j) {
for(int k = 1;k < j;++k) {
if(a[i][j] == a[j][k] && a[i][j] == a[k][i]) ans ++;
}
}
}
cout<<ans;
}
int main() {
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
n = read() ,k = read();
if(k == 0) {
puts("0");
return 0;
}
BF1();
return 0;
}
总结
预计得分:100 + 100 + 30 = 230
实际得分:80 + 0 + 70 = 150
T1还有一些特殊情况需要特判没考虑到，T2空间算错了，瞬间少了120分。然后T3能过70真的神奇
一言
你太善良了，这个世界会把你啃得尸骨无存。 ——生活大爆炸