A .AvtoBus
题意：
给你一个数由4 6组成最多/少由几个数组成
题解：
4x+6y=num
4(x+y)+2y=num;
当x或y>=1时 num>=4,且为偶数。
num只能由46组成
且最多的数最多只能有一个6因为偶数个6可以由三个4组成
最少的同理
Example
input
4
4
7
24
998244353998244352
output
1 1
-1
4 6
166374058999707392 249561088499561088
看样例数据范围1e18记得开longlong
//
// Created by YikN on 2022/5/13.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2 * 1e5 + 100;
const int mod = 1e9 + 7;
int y[N], l[N];
int st[N];
long long f[N];
int n, m;
int main() {
int T;
cin >> T;
while (T--) {
ll x;
cin >> x;
if (x & 1 || x < 4)printf("-1\n");
else {
ll liu = 0, si = 0;
while ((x - liu * 6) % 4 != 0) {
liu++;
}
ll ma = liu + (x - liu * 6) / 4;
while ((x - si * 4) % 6 != 0) {
si++;
}
ll mi = si + (x - si * 4) / 6;
printf("%lld %lld\n", mi, ma);
}
}
return 0;
}
B. Stone Age Problem
题意：
给你一组数
和m个操作
有两种操作
1.全变某个数，然后输出总和。
2.变单个数，然后输出总和。
数据范围：2*1e5
题解
根据数据范围可以得出我们只需要记录每次的单独操作即可，全部变之后清除这些操作
Example
input
5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1
output
19
50
51
42
5
//
// Created by YikN on 2022/5/13.
//
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2 * 1e5 + 100;
const int mod = 1e9 + 7;
long long f[N];
ll n, m;
ll a[N];
ll s[N];
map<long long, long long> mp;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
}
ll sum = -1, zo = s[n];
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
ll idx, num, cao = 0;
scanf("%lld%lld", &idx, &num);
if (!mp.count(idx)) {
if (sum == -1)cao = num - a[idx];
else cao = num - sum;
} else {
cao = num - mp[idx];
}
zo += cao;
mp[idx] = num;
printf("%lld\n", zo);
} else {
mp.clear();
ll fl;
scanf("%lld", &fl);
sum = fl;
zo = fl * n;
printf("%lld\n", fl * n);
}
}
return 0;
}
C. Rooks Defenders
给你n*n的棋盘有三种操作
1.添加棋子
2.删除棋子
3.查询子矩阵是否被攻击过
主要是查询子矩阵是否被攻击过n*n的范围有点大我们可以通过前缀的方式来看
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2 * 1e5 + 100;
const int mod = 1e9 + 7;
ll x[N], y[N];
ll sumx[N], sumy[N];
int n, m;
ll lowbit(ll x) { return x & -x; }
void add(ll sum[], int x, int c) {
for (int i = x; i <= n; i += lowbit(i))sum[i] += c;
}
ll query(ll sum[], int x) {
ll res = 0;
for (int i = x; i; i -= lowbit(i)) res += sum[i];
return res;
}
int main() {
scanf("%d%d", &n, &m);
int k, a, b, c;
int x1, x2, y1, y2;
for (int i = 1; i <= m; i++) {
scanf("%d", &k);
if (k == 1) {
scanf("%d%d", &a, &b);
x[a]++, y[b]++;
if (x[a] == 1)add(sumx, a, 1);
if (y[b] == 1)add(sumy, b, 1);
}
if (k == 2) {
scanf("%d%d", &a, &b);
if (x[a] >= 1)x[a]--;
if (y[b] >= 1) y[b]--;
if (!x[a])add(sumx, a, -1);
if (!y[b])add(sumy, b, -1);
}
if (k == 3) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (query(sumx, x2) - query(sumx, x1 - 1) == x2 - x1 + 1) {
puts("Yes");
} else if (query(sumy, y2) - query(sumy, y1 - 1) == y2 - y1 + 1) {
puts("Yes");
} else puts("No");
}
}
return 0;
}
