题目链接 题目大意: 有两种车分别有4个轮子和6个轮子,现在只知道若干个车的轮子总数,想知道最少和最多有几辆车;
输入: 第一行,整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行 整数 𝑛,表示 𝑛个轮子 (1≤𝑛≤10e18)
输出: 每个样例一行,分别输出最少和最多有几辆车,如果没有则输出-1;
Examples input 4 4 7 24 998244353998244352 output 1 1 -1 4 6 166374058999707392 249561088499561088
题目解析: 容易知道,如果n为奇数,则题目无解; n为偶数,如果n=2则无解,其他必然有解; 最少的情况,全部用6轮,剩下的有2个轮子和4个轮子的情况;如果剩2个轮子,则总数+1(将1个6改成4就好);如果剩4个轮子,则总数+1; 最多的情况,全部用4轮,如果剩2个轮子,则总数不变(将1个4改成6就好);
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
lld n;
cin >> n;
if (n < 4 || n % 2) {
cout << -1 << endl;
}
else {
lld ansMin = (n / 6) + (n % 6 != 0);
lld ansMax = (n / 4);
cout << ansMin << " " << ansMax << endl;
}
}
}
}
ac;
题目链接 题目大意: 给出n个整数的数组a,现在有两个操作: 1、将第i个数字替换为x;(x为输入的整数) 2、将整个数组替换为x;(x为输入的整数) 现在想知道经历q次操作,每次操作完数组的和;
输入: 第一行,整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5) 第二行n个整数 𝑎1,…,𝑎𝑛 (1≤𝑎𝑖≤1e9) 接下来q行,每行第一个数字是t,表示操作1或者操作2; 如果t=1,则接下来输入数字i和x (1≤𝑖≤𝑛, 1≤𝑥≤1e9) 如果t=2,则接下来输入数字x (1≤𝑥≤1e9)
输出: 每个操作一行,输出操作后的数字和;
Examples 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
题目解析: 朴素的做法,对于数组a,操作1则修改a[i],时间复杂度O(1); 操作2则全量修改数组a,时间复杂度O(N); 计算数字和的复杂度,也是O(N),总的复杂度是(NQ);
对于操作2,全量修改没必要,用变量记住当前整个数组已经修改即可,数字和也不需要累计,直接x和n的乘积即可; 但是这个变量要如何兼容操作1? 不用兼容,单独用一个map来记录操作1,当遇到操作2的时候再把map清空;正常往map里面添加一个值的时候,我们就可以实时算出来这个值带来的总和diff,O(1)就可以维护这个数组和; 将这个思路流程化,那么就是记录一个当前和sum; 然后生成一个map,记录每个位置对应的值; 当遇到操作1,则访问当前map,拿到当前值(如果map没有就是操作2的值),生成新的值记录到map,并更新diff到sum; 遇到操作2,则清空map并更新sum; 总的复杂度是O(NlogN);
class Solution {
static const int N = 201010;
lld a[N];
public:
void solve() {
lld n, q;
cin >> n >> q;
map<lld, lld> h;
lld cur = 0, sum = 0;
for (int i = 1; i <= n; ++i) {
lld x;
cin >> x;
h[i] = x;
sum += x;
}
while (q--) {
int k;
cin >> k;
if (k == 1) {
int i, x;
cin >> i >> x;
if (h[i]) {
sum += x - h[i];
h[i] = x;
}
else {
sum += x - cur;
h[i] = x;
}
}
else {
int x;
cin >> x;
cur = x;
sum = cur * n;
h.clear();
}
cout << sum << endl;
}
}
}
ac;
题目链接 题目大意: 有一个n x n的国际象棋棋盘,现在有3个操作: 操作1,往棋盘(x,y)上面放一个车,车可以攻击同一行或者同一列; 操作2,移除棋盘(x,y)上面的车; 操作3,询问区域(𝑥1,𝑦1)到(𝑥2,𝑦2)内所有位置,是否都可以被车攻击到; 现在有q个操作,想知道每次操作3 之后的结果;
输入: 第一行,整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5) 接下来q行,每行第一个数字是t,表示操作1、2、3; 如果t=1或者2,则接下来输入数字x和y; (1 ≤ 𝑥,𝑦 ≤ 𝑛) 如果t=3,则接下来输入数字x1、y1、x2和y2; (1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛, 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑛)
输出: 每个操作3一行,输出YES或者NO;
Examples input 8 10 1 2 4 3 6 2 7 2 1 3 2 3 6 2 7 2 1 4 3 3 2 6 4 8 2 4 3 3 2 6 4 8 1 4 8 3 2 6 4 8
output No Yes Yes No Yes
题目解析: 我们用row[N]和column[N]来表示行和列,那么添加(x, y)就可以拆分为row[x]和column[y]的变动; 操作1和操作2比较简单,直接操作数组即可; 操作3,朴素的想法是遍历所有行、列,看看是否满足,所有行或者所有列都被车覆盖;这样的复杂度复杂度是O(N); 分析这个遍历过程,当我们想知道row[x1]到row[x2]这个区间,是否全部为1,其实可以转化为前n项和之差:只要sum[x2] - sum[x1] = x2 - x1,就满足条件; 于是问题转化为,如何快速维护sum[i]?(row前i个元素的和) 这里偷个懒,用树状数组来支持。(就不展开介绍怎么用树状数组了,可以自己百度,有非常详细介绍)
class TreeArray {
static const int N = 201001;
int tree[N];
int low_bit(int x)
{
return x&-x;
}
public:
void tree_add(int x,int v, int n)
{
while(x<=n)
{
tree[x] += v;
x+=low_bit(x);
}
}
int tree_sum(int x)
{
int sum=0;
while(x)
{
sum += tree[x];
x-=low_bit(x);
}
return sum;
}
};
class Solution {
static const int N = 201001;
TreeArray rowArr, columnArr;
int rowCnt[N], columnCnt[N];
public:
void solve() {
int n, q;
cin >> n >> q;
while (q--) {
int k;
cin >> k;
if (k == 1) {
int x, y;
scanf("%d%d", &x, &y);
int add = 1;
rowCnt[x] += add;
if (rowCnt[x] == 1) {
rowArr.tree_add(x, add, n);
}
columnCnt[y] += add;
if (columnCnt[y] == 1) {
columnArr.tree_add(y, add, n);
}
}
else if (k == 2) {
int x, y;
scanf("%d%d", &x, &y);
int add = -1;
rowCnt[x] += add;
if (rowCnt[x] == 0) {
rowArr.tree_add(x, add, n);
}
columnCnt[y] += add;
if (columnCnt[y] == 0) {
columnArr.tree_add(y, add, n);
}
}
else {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int rowSum = rowArr.tree_sum(x2) - rowArr.tree_sum(x1 - 1);
int columnSum = columnArr.tree_sum(y2) - columnArr.tree_sum(y1 - 1);
if (rowSum == (x2 - x1 + 1) || columnSum == (y2 - y1 + 1)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}
}
}
ac;
题目链接 题目大意: 有一个n个节点的有向图,每个节点有一个数字a[i]; 现在可以选择某个节点,从这个节点开始沿着有向边走,记录每个访问到的节点,并将这个访问顺序记录下来; 现在想知道,如果需要访问k个节点,访问顺序中的节点数字最大值的最小值是多少;
输入: 整数 𝑛, 𝑚 and 𝑘 (1≤𝑛≤2⋅1e5, 0≤𝑚≤2⋅1e5, 1≤𝑘≤10e18) 接下来n个整数 𝑎𝑖 (1≤𝑎𝑖≤1e9) 接下来是m条行,每行有整数 𝑢 and 𝑣 ,表示u到v的边(1≤𝑢≠𝑣≤𝑛) 题目保证没有指向自己的边,也没有多重边;
输出: 输出k个节点,节点数字最大值的最小值是多少; 如果无法访问到k个节点,则输出-1;
Examples input 6 7 4 1 10 2 3 4 5 1 2 1 3 3 4 4 5 5 6 6 2 2 5
output 4
题目解析: 先用朴素的思维来分析,假如我们需要访问1个节点,那么就是寻找节点的最小值; 如果是需要访问2个节点,那么问题就变得复杂,因为节点2->3的解是比 节点1->4的解更优;那么节点的最小值就失去了意义; 如果是想遍历整个图,并且在遍历过程中去保留这个最大值的最小,无疑是非常复杂的;
那么换一种思想,假如我用二分来处理这个最大值,得到mid,如果a[i]<=mid认为a[i]可以访问,如果a[i]>mid则认为节点不可方案; 题目变成在有向图中,询问遍历步数最多是否能到k;
先不考虑环的情况,在一个有向图中要去判断遍历步数最多情况,可以枚举所有起点出发的情况,然后通过深度优先搜索来记录遍历过程中的步数; 当出现环的时候,我们可以把步数设置为一个很大的值,这样也可以统一逻辑处理。
那么,问题又变成如何在有向图中判断环的存在? 当我们在深度优先遍历的过程中,假如当前点是u,下一个节点是v,此时有两种情况,v是已经访问过,v还没访问过; 如果v没有访问过,那么就访问v即可; 如果v已经访问过,此时又有两种情况,如果v已经访问过,但是还在当前的递归栈中,则证明v已经可以和u构成环;(step[u]=inf,inf表示一个很大值) 如果是v已经访问过,但是和当前递归栈中没有关系,怎么v只是普通访问过的节点;(此时step[u]=max(step[u], step[v]+1);
class Solution {
static const lld N = 201001;
static const lld inf = 0x7fff7fff3fff7fff;
lld a[N];
int vis[N]; // 0表示没访问,1表示访问中,2表示访问后
lld step[N], n;
vector<lld> g[N];
void dfs(lld u, lld cur, lld mid) {
vis[u] = 1;
step[u] = 1;
for (lld i = 0; i < g[u].size(); ++i) {
lld v = g[u][i];
if (a[v] > mid) {
continue;
}
if (!vis[v]) {
dfs(v, cur + 1, mid);
step[u] = max(step[u], step[v] + 1);
}
else {
if (vis[v] == 1) {
step[u] = inf;
}
else {
step[u] = max(step[u], step[v] + 1);
}
}
}
vis[u] = 2;
}
bool check(lld mid, lld k) {
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
dfs(0, 0, mid);
for (lld i = 1; i <= n; ++i) {
if (a[i] > mid) {
continue;;
}
if (step[i] >= k) {
return true;
}
}
return false;
}
public:
void solve() {
lld m, k;
cin >> n >> m >> k;
lld l = 0, r = 0x7fffffff;
for (lld i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
r = max(r, a[i]);
}
for (lld i = 0; i < m; ++i) {
lld u, v;
scanf("%lld%lld", &u, &v);
g[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
g[0].push_back(i);
}
lld ans = -1;
while (l <= r) {
lld mid = (l + r) / 2;
if (check(mid, k)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}
}
ac;
题目链接 题目大意: 有n个格子排成一行,每个格子有一个灯,灯有两个方向:L和R,分别表示朝左和朝右; 当一个灯朝左时,它能照亮其左边的格子;(不包括灯所在格子) 当一个灯朝右时,它能照亮其右边的格子;(不包括灯所在格子) 现在允许选择某个格子,交换该格子和右边格子的灯,灯的朝向不变;(不能选择最右边的格子) 现在想知道,是否能够让每个格子都能被灯照亮;
输入: 第一行,整数𝑡 表示t个样例𝑡 (1≤𝑡≤10000) 每个样例2行,第一行整数 𝑛 (2≤𝑛≤100000) 第二行n个字符'L' 和 'R'
输出: 每个样例一行,如果无解输出-1,如果不需要交换输出0,如果需要交换则输出交换第x个格子;(1 <= x < n)
Examples input 6 2 LL 2 LR 2 RL 2 RR 7 LLRLLLR 7 RRLRRRL output -1 1 0 -1 3 6
题目解析: 样例给了一个比较关键的数据,当字符串出现RL,题目就必然存在解; 基于此我们继续分析,当字符串只有L或者只有R时,必然无解; 当字符串存在L和R时,必然有解:因为总是能找到L和R相交的位置,如果是R和L,则无需交换;如果是L和R,则进行交换;
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string str;
cin >> str;
int index = -1;
for (int i = 0; i + 1 < n; ++i) {
if (str[i] != str[i + 1]) {
index = str[i] == 'R' ? 0 : (i + 1);
break;
}
}
cout << index << endl;
}
}
}
ac;