A. Nastya Is Reading a Book
题意: n个区间，每个区间范围不超过100,n不超过100。给一个位置k，1-(k-1)是遍历过的位置，求没有完全遍历完的区间。
k处于区间中时，表示区间没有遍历完。
思路：数据范围小，直接暴力
#include <bits/stdc++.h>
using namespace std;
pair <int, int> p[102];
int main(){
int n, k, ans = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d%d", &p[i].first, &p[i].second);
scanf("%d", &k);
for(int i = 1; i <= n; i++){
if(p[i].second < k){
ans++;
}
}
printf("%d\n", n-ans);
}
B. Nastya Is Playing Computer Games
题意:有n个井盖，每个井盖上有一个小石头。给出n和k，k表示刚开始在第k个井盖上方。有三种操作，左右移动，扔石头到任意一个井盖，下到井盖里拿金币。只有井盖上没有石头才能下井盖。求捡完全部金币的最小步数。
思路：规律题，我们考虑一下当前位置和相邻的任意一个位置，要想拿到这2个井盖的金币一共需要6次。其余的井盖需要(n-2)*3个步骤，还需要考虑这个人是从哪个方向走导致多出来的步数，两个取小即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
scanf("%d%d", &n, &k);
int ans = n * 3 + min(k - 1, n - k);
printf("%d\n", ans);
return 0;
}
C:题意，给了俩个矩阵，你可以无数次对A矩阵的子矩阵进行转置操作，问A是否可以变为B？
思路：考虑一下转置的特性，发现不在同一对角线的元素是无法交换位置的。我们直接对主对角线进行求和判断即可。
#include <bits/stdc++.h>
using namespace std;
int a[505][505], b[505][505];
map <int, int> mp[1010];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &a[i][j]);
mp[i+j-1][a[i][j]]++;
}
}
bool flag = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &b[i][j]);
if(mp[i+j-1][b[i][j]] <= 0){
flag = 0;
break;
}
mp[i+j-1][b[i][j]]--;
}
}
if(flag){
puts("YES");
}else{
puts("NO");
}
}
D:题意：给一个序列和一组交换序列（a,b），当且仅当a在b的前面（不允许有间隔），这两个数才能交换，问最后一个数最多能移动多少个位置。
解法：不会，阅读题解，用数组cnt[x]记录数x后面可以与其交换的数的数目，当这个数目刚好等于这个数和最后一个数的距离时，肯定有办法能把最后一个数换到x的位置，然后需要注意的是要一直更新最后一个数的位置，它的位置就是n-ans（即数列长度-已经移动的次数）。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int p[maxn], cnt[maxn];
vector <int> v[maxn];
int main(){
int n, m, x, y;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%d", &p[i]);
}
for(int i = 1; i <= m; i++){
scanf("%d %d", &x, &y);
v[y].push_back(x);
}
for(int i = 0; i < v[p[n]].size(); i++){
cnt[v[p[n]][i]]++;
}
int ans = 0;
for(int i = n - 1; i >= 1; i--){
if(n - i - ans == cnt[p[i]]){
ans++;
}else{
for(int j = 0; j < v[p[i]].size(); j++){
cnt[v[p[i]][j]]++;
}
}
}
printf("%d\n", ans);
return 0;
}
E. Nastya Hasn’t Written a Legend
题意：有一个数组a和一个数组k，数组a一直保持一个性质：a[i + 1] >= a[i] + k[i]。有两种操作：1，给某个元素加上x，但是加上之后要保持数组a的性质。比如a[i]加上x之后，a[i + 1]<a[i] + k[i],那么a[i + 1]就变成a[i] + k[i]，否则不变。同理，若a[i + 2]小于了现在的a[i + 1] + k[i + 1]，那么a[i + 2]也变成a[i + 1] + k[i + 1]，一直保持这个性质。第二章操作，询问数组a的区间[l, r]的区间和。
题解：https://www.cnblogs.com/pkgunboat/p/10527569.html
题解：来自上面的博主，容易发现，假设更改了x位置之后，恰好到位置y不需要更改元素，那么及其之后的位置肯定就不用更改了。所以，在查找这个位置的时候，我们可以二分查找。找到之后，对区间[x, y]进行操作。我们可以发现，区间[x, y]的数有规律。假设x位置的数是a[x]，那么a[x + 1]是a[x] + k[x], a[x + 2]是a[x] + k[x + 1] + k[x + 2],以此类推。这个区间的和可以分为2部分：[y - x + 1]个a[x]，和关于k的部分。可以发现，k[x]出现了(r - l + 1)次，k[x + 1]出现了(r - l)次，以此类推。那么怎么O（1）获得这个东西呢？我们先预处理k数组的前缀和（假设前缀和数组是b），那么我们再求b的前缀和（假设是数组c），那么c[i]就是出现了i次k[1],i - 1次k[2]，以此类推。那么区间[x, y]中关于k的和就可以得出了：c[y] - c[x - 1] - [y - x + 1] * b[x]。前面c[y] - c[x - 1]可以O(1)算出，而后面的部分比较麻烦。怎么维护后面[y - x + 1] * b[x]这个部分呢？我们发现a[x]正好出现[y - x + 1]次，这样我们可以把a[x] - b[x]用一个懒标记维护，下放标记的时候区间的和为c[y] - c[x - 1] + (r - l + 1) * val (val是a[x] - b[x])。
这个算法的复杂度是nlog(n)，我当时在想分块是不是可以维护，但估计会T。太菜了，完全没有状态了，只能看看题解写写，告辞。
#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
const long long INF = 1e18;
long long a[maxn], b[maxn], c[maxn];
struct node {
int l, r;
long long sum, tag;
}Tree[maxn << 2];
void push_up(int rt) {
Tree[rt].sum = Tree[rt * 2].sum + Tree[rt * 2 + 1].sum;
}
void push_down(int rt) {
if (Tree[rt].tag != -INF) {
Tree[rt * 2].sum = (Tree[rt * 2].r - Tree[rt * 2].l + 1) * Tree[rt].tag + (c[Tree[rt * 2].r] - c[Tree[rt * 2].l - 1]);
Tree[rt * 2].tag = Tree[rt].tag;
}
if (Tree[rt].tag != -INF) {
Tree[rt * 2 + 1].sum = (Tree[rt * 2 + 1].r - Tree[rt * 2 + 1].l + 1) * Tree[rt].tag + (c[Tree[rt * 2 + 1].r] - c[Tree[rt * 2 + 1].l - 1]);
Tree[rt * 2 + 1].tag = Tree[rt].tag;
}
Tree[rt].tag = -INF;
}
void build(int l, int r, int rt) {
Tree[rt].l = l, Tree[rt].r = r;
Tree[rt].tag = -INF;
if (l == r) {
Tree[rt].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt * 2);
build(mid + 1, r, rt * 2 + 1);
push_up(rt);
}
void update(int L, int R, int l, int r, int rt, long long val) {
if (L <= l && r <= R) {
if (val != -INF) {
Tree[rt].sum = (Tree[rt].r - Tree[rt].l + 1) * val + (c[Tree[rt].r] - c[Tree[rt].l - 1]);
Tree[rt].tag = val;
}
return;
}
push_down(rt);
int mid = (l + r) >> 1;
if (L <= mid) update(L, R, l, mid, rt * 2, val);
if (mid < R) update(L, R, mid + 1, r, rt * 2 + 1, val);
push_up(rt);
}
long long query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return Tree[rt].sum;
}
push_down(rt);
int mid = (l + r) >> 1;
long long ans = 0;
if (L <= mid) ans += query(L, R, l, mid, rt * 2);
if (mid < R) ans += query(L, R, mid + 1, r, rt * 2 + 1);
return ans;
}
int main() {
int n, q;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
for (int i = 2; i <= n; i++) {
scanf("%lld", &b[i]);
b[i] += b[i - 1];
}
for (int i = 2; i <= n; i++) {
c[i] = c[i - 1] + b[i];
}
build(1, n, 1);
scanf("%d", &q);
char op[10];
int x, y;
while (q--) {
scanf("%s%d%d", op + 1, &x, &y);
if (op[1] == '+') {
int l = x;
int r = n;
long long temp = query(x, x, 1, n, 1);
while (l < r) {
//int mid = (l + r) >> 1;
int mid = (l + r + 1) >> 1;
long long temp1 = query(mid, mid, 1, n, 1);
if ((temp + y + b[mid] - b[x]) > temp1) {
l = mid;
}
else {
r = mid - 1;
}
}
//printf("************%d %d %d*********\n", x, l, temp + y - b[x]);
update(x, l, 1, n, 1, temp + y - b[x]);
}
else {
printf("%lld\n", query(x, y, 1, n, 1));
}
}
//system("pause");
return 0;
}
京公网安备 11010502036488号