inline int read(){ int x = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if (ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x<<1) + (x<<3) + (ch^48); ch = getchar(); } return x * f; }
时间: 2023-10-24 08:04:38 浏览: 75
这段代码是一个用于读取输入的函数。它使用了一个循环来读取输入字符,并将其转换为整数。
首先,它初始化了一个整数变量x和一个整数变量f为1,表示正数。
然后,它调用getchar()函数来读取输入字符,并将其存储在字符变量ch中。
接下来,它进入一个while循环,判断ch是否小于'0'或大于'9'。如果是,则检查ch是否是'-',如果是,则将f设置为-1,表示负数。然后,再次调用getchar()函数来继续读取下一个字符。
然后,它进入另一个while循环,判断ch是否大于等于'0'且小于等于'9'。如果是,则将x左移一位(相当于乘以2),再加上x左移三位(相当于乘以8),再加上ch异或48的结果(将字符转换为对应的数字)。然后,再次调用getchar()函数来继续读取下一个字符。
最后,函数返回x乘以f,即最终得到的整数值。
这个函数可以用于读取整数型的输入,忽略掉输入中的非数字字符,并且可以处理负数输入。
相关问题
满足这是一道 ST 表经典题——静态区间最大值 请注意最大数据时限只有 0.8s,数据强度不低,请务必保证你的每次查询复杂度为 � ( 1 ) O(1)。若使用更高时间复杂度算法不保证能通过。 如果您认为您的代码时间复杂度正确但是 TLE,可以尝试使用快速读入: inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } 函数返回值为读入的第一个整数。 快速读入作用仅为加快读入,并非强制使用。#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n[200005], m,a,b,c,d; int correct(int c1, int c2) { int j = 0; for (int i = c1; i <= c2; i++) j = max(n[i], j); return j; } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } int main() { int i = 1; cin >> a >> b; for(i;i<=a;i++) n[i] = read(); while (b--) { cin >> c >> d; cout << correct(c, d) << endl;; } return 0; }怎么修改
要将上述代码修改为满足题目要求的时间复杂度O(1),可以使用ST表(Sparse Table)数据结构。以下是修改后的代码:
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 200005;
const int MAXLOG = 20;
int n[MAXN], m, a, b, c, d;
int st[MAXN][MAXLOG];
void initST()
{
for (int i = 1; i <= a; i++)
st[i][0] = n[i];
for (int j = 1; (1 << j) <= a; j++)
{
for (int i = 1; i + (1 << j) - 1 <= a; i++)
{
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r)
{
int k = 0;
while ((1 << (k + 1)) <= r - l + 1)
k++;
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
int main()
{
int i = 1;
cin >> a >> b;
for (i; i <= a; i++)
n[i] = read();
initST();
while (b--)
{
cin >> c >> d;
cout << query(c, d) << endl;
}
return 0;
}
```
在这个修改后的代码中,我们使用ST表数据结构来存储每个区间的最大值。在预处理阶段,我们计算出每个长度为2^j的区间的最大值,并存储在`st`数组中。然后,当需要查询c到d范围内的最大值时,我们根据区间长度选择合适的j值,并使用`st[l][k]`和`st[r - (1 << k) + 1][k]`来获取结果。这样,每次查询的时间复杂度都是O(1),满足题目要求。
另外,我们还使用了快速读入来加快输入速度,以适应题目给定的时间限制。
解释这段代码#include <bits/stdc++.h> using namespace std; #define int long long #define INF32_MAX 2147483647 #define endl '\n' inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } const int N = 1e6; signed main() { return 0; }
这段代码是C++语言的一段模板代码,主要目的是用于快速输入输出,同时定义了一些常量和变量。
首先,`#include <bits/stdc++.h>` 是一个特殊的头文件,它包含了所有标准C++库的头文件。这样就不需要手动添加每个头文件,可以方便地使用所有库函数。
然后,`using namespace std;` 表示使用标准命名空间 `std` 中的所有函数和变量,可以省略一些冗长的前缀。
接下来,`#define int long long` 定义了一个宏,将 `int` 类型重定义为 `long long` 类型。这样定义是为了避免整型溢出的问题,因为 `long long` 类型的取值范围比 `int` 类型更大。
`#define INF32_MAX 2147483647` 定义了一个常量 `INF32_MAX`,它的值为 `2^31 - 1`,即 `INT_MAX`,表示整型变量的最大值。
`#define endl '\n'` 定义了一个常量 `endl`,将其定义为换行符 `\n`,用于在输出时换行。
`inline int read()` 是一个快速的读入函数,可以快速读入一个整数。具体实现是通过每次读入一个字符,然后将字符转换为整数,最后返回整数。
`const int N = 1e6;` 定义了一个常量 `N`,表示数组的最大长度为 `1e6`。
最后,`signed main() { return 0; }` 是程序的入口函数,它返回一个整数值表示程序的执行状态。在这个例子中,程序只是一个空函数,返回值为0,表示程序正常结束。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)