题目编号1136
A
暴力咯。。
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 105;
int n, m;
struct A{
int l, r;
}a[N];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%d%d", &a[i].l, &a[i].r);
}
scanf("%d", &m);
for(int i = 1; i <= n; ++i){
if(a[i].r >= m){
printf("%d
", n - i + 1);
return 0;
}
}
return 0;
}
B
先往少的一边跳
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 105;
int n, k;
int main(){
scanf("%d%d", &n, &k);
printf("%d", n + 1 + n - 1 + min(k - 1, n - k) + n);
return 0;
}
C
同一斜行上点不变
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 505;
const int M = 5e5 + 5;
int n, m;
int a[N][N], b[N][N];
int lsh[M], lsize;
long long cnt[2][N << 1];
long long c2[2][N << 1];
//bool flag;
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
scanf("%d", &a[i][j]);
lsh[++lsize] = a[i][j];
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
scanf("%d", &b[i][j]);
lsh[++lsize] = b[i][j];
}
}
sort(lsh + 1, lsh + lsize + 1);
lsize = unique(lsh + 1, lsh + lsize + 1) - lsh - 1;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
/*if((i == 1 && j == 1) || (i == n && j == m)){
if(a[i][j] != b[i][j]){
printf("NO
");
return 0;
}
}*/
cnt[0][i + j - 1] += lower_bound(lsh + 1, lsh + lsize + 1, a[i][j]) - lsh;
cnt[1][i + j - 1] += lower_bound(lsh + 1, lsh + lsize + 1, b[i][j]) - lsh;
c2[0][i + j - 1] ^= lower_bound(lsh + 1, lsh + lsize + 1, a[i][j]) - lsh;
c2[1][i + j - 1] ^= lower_bound(lsh + 1, lsh + lsize + 1, b[i][j]) - lsh;
}
}
for(int i = 1; i <= n + m - 1; ++i){
if(cnt[0][i] != cnt[1][i] || c2[0][i] != c2[1][i]){
printf("NO
");
return 0;
}
}
printf("YES
");
return 0;
}
D
计算出度 记录能到达最后的位置
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>
using namespace std;
const int N = 3e5 + 5;
struct Edge{
int v, next;
}edge[N << 1];
int head[N], esize;
inline void addedge(int x, int y){
edge[++esize] = (Edge){y, head[x]};
head[x] = esize;
}
int n, m, ans;
int a[N];
int d[N];
inline void ins(int x){
for(int i = head[x], vv; ~i; i = edge[i].next){
vv = edge[i].v;
++d[vv];
}
}
int main(){
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);
}
for(int i = 1, x, y; i <= m; ++i){
scanf("%d%d", &x, &y);
addedge(y, x);
//++d[x];
}
ans = 0;
ins(a[n]);
for(int i = n - 1; i >= 1; --i){
// printf("%d
", d[a[i]]);
if(d[a[i]] == n - i){
--n;
++ans;
}
else{
ins(a[i]);
}
}
printf("%d", ans);
return 0;
}
E
分块暴力维护
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
const int M = 500;
int n, m;
long long a[N], b[N], sb[N];
struct Bl{
long long fir[M], sum[M], atag[M];
int size, cnt, bel[N];
int l[N], r[N];
void build(){
size = sqrt(n);
cnt = (n - 1) / size + 1;
for(int i = 1; i <= cnt; ++i){
l[i] = r[i - 1] + 1, r[i] = min(n, l[i] + size - 1);
for(int j = l[i]; j <= r[i]; ++j){
sum[i] += a[j];
bel[j] = i;
atag[i] += sb[j - 1] - sb[l[i] - 1];
}
fir[i] = a[l[i]];
}
}
void update(int x){
a[l[x]] = fir[x]; sum[x] = a[l[x]];
for(int i = l[x] + 1; i <= r[x]; ++i){
a[i] = max(a[i], a[i - 1] + b[i - 1]);
sum[x] += a[i];
}
}
void ins(int x, int y){
int pos = bel[x];
update(pos);
a[x] += y;
if(x == l[pos]) fir[pos] += y;
update(pos);
int end = cnt; //ע��������ܲ�������!!
for(int i = pos + 1; i <= cnt; ++i)
if(fir[i] > a[x] + sb[l[i] - 1] - sb[x - 1]){end = i - 1; break;}
for(int i = pos + 1; i < end; ++i){
fir[i] = a[x] + sb[l[i] - 1] - sb[x - 1];
sum[i] = 1ll * (r[i] - l[i] + 1) * fir[i] + atag[i];
}
if(end != pos){
fir[end] = a[x] + sb[l[end] - 1] - sb[x - 1];
update(end);
}
}
long long qry(int x, int y){
long long res = 0;
int px = bel[x], py = bel[y];
if(px == py){
update(px);
for(int i = x; i <= y; ++i) res += a[i];
return res;
}
update(px);
for(int i = x; i <= r[px]; ++i) res += a[i];
update(py);
for(int i = l[py]; i <= y; ++i) res += a[i];
for(int i = px + 1; i < py; ++i){
res += sum[i];
}
return res;
}
}bl;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; ++i){
scanf("%lld", &a[i]);
}
for(int i = 1; i < n; ++i){
scanf("%lld", &b[i]);
sb[i] = sb[i - 1] + b[i];
}
bl.build();
scanf("%d", &m);
char opt[10];
for(int i = 1, x, y; i <= m; ++i){
scanf("%s%d%d", opt, &x, &y);
if(opt[0] == '+'){
bl.ins(x, y);
}
else {
printf("%lld
", bl.qry(x, y));
}
}
return 0;
}