快速幂
给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
提交代码
c++
#include<iostream> using namespace std; long long qmi(long long a,int b,int p) { long long res=1; while(b)//对b进行二进制化,从低位到高位 { //如果b的二进制表示的第0位为1,则乘上当前的a if(b&1) res = res *a %p; //b右移一位 b>>=1; //更新a,a依次为a^{2^0},a^{2^1},a^{2^2},....,a^{2^logb} a=a*a%p; } return res; } int main() { int n; cin>>n; while(n--) { int a,b,p; long long res=1; cin>>a>>b>>p; res = qmi(a,b,p); cout<<res<<endl; } return 0; }
java
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); String [] strs = reader.readLine().trim().split(" "); int n = Integer.parseInt(strs[0]); int k = Integer.parseInt(strs[1]); strs = reader.readLine().trim().split(" "); int a [] = new int [n + 10]; for (int i = 1; i <= n; ++ i) a[i] = Integer.parseInt(strs[i - 1]); int [] sum = new int [n + 10]; for (int i = 1; i <= n; ++ i) sum[i] = a[i] + sum[i - 1]; while(k -- > 0) { strs = reader.readLine().trim().split(" "); int b1 = Integer.parseInt(strs[0]); int b2 = Integer.parseInt(strs[1]); System.out.println(sum[b2] - sum[b1 - 1]); } } }
滑动窗口
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
提交代码
C++
#include<iostream> using namespace std; const int N = 1000010; int a[N], q[N], hh, tt = -1; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; ++ i) // 这个题要注意的是 q队列里面存放的是位置 { scanf ("%d", &a[i]); // 先求的是最小值 if (i - k + 1 > q[hh]) ++hh; // 如果最小值的位置已经滑出窗口了 然后就 // ++ hh代表这个数已经没了 while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 先确保队列里面有数字 // 然后如果新来的数字要小于 队列里面的最小值 // 那么--tt 就代表当前队列的最小值去掉 q[++ tt] = i; // 把新来的数字放到队列中 if (i + 1 >= k) printf ("%d ", a[q[hh]]); // 当前队列的长度已经满足k了 // 就可以把对首的元素输出出来 } puts(""); int hh = 0, tt = -1; for (int i = 0; i < n; ++ i) { if (i - k + 1 > q[hh]) ++ hh; while (hh <= tt && a[i] >= a[q[tt]]) -- tt; q[++ tt] = i; if (i + 1 >= k) printf("%d ", a[q[hh]]); } return 0; }
Java
import java.io.*; public class Main { final static int N = 1000010; static int [] a = new int [N]; static int [] q = new int [N]; static int hh = 0, tt = -1; public static void main(String[] args) throws IOException { int n, k; BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); String [] str = reader.readLine().split(" "); n = Integer.parseInt(str[0]); k = Integer.parseInt(str[1]); str = reader.readLine().split(" "); for (int i = 0; i < n; ++ i) a[i] = Integer.parseInt(str[i]); // for (int i = 0; i < n; ++ i) // { // if (hh <= tt && i - k + 1 > q[hh]) ++ hh; // while (hh <= tt && a[i] <= a[q[hh]]) -- tt; // q[++ tt] = i; // if (i + 1 >= k) out.write(a[q[hh]]+" "); // } for(int i = 0; i < n; i ++) { if(hh <= tt && i - q[hh] + 1 > k) hh++;//判断队头是否已经滑出窗口 while(hh <= tt && a[q[tt]] >= a[i]) tt--;//出队 q[++tt] = i;//入队 if(i >= k - 1) out.write(a[q[hh]]+" "); } out.write("\n"); hh = 0; tt = -1; // for (int i = 0; i < n; ++ i) // { // if (hh <= tt && i - k + 1 > q[hh]) ++ hh; // while (hh <= tt && a[i] >= a[q[hh]]) -- tt; // q[++ tt] = i; // if (i + 1 >= k) out.write(a[q[hh]]+" "); // } for(int i = 0; i < n; i ++) { if(hh <= tt && i - q[hh] + 1 > k) hh++;//判断队头是否已经滑出窗口 while(hh <= tt && a[q[tt]] <= a[i]) tt--;//出队 q[++tt] = i;//入队 if(i >= k - 1) out.write(a[q[hh]]+" "); } out.flush(); out.close(); } }
