程序设计基础算法

bool is_prime(int n)
{
    if(n<=1) return false;
    for(int i=2;i<sqrt(n);i++)
    {
        if(n%i==0)return false;
    }
    return true;
}

#include<iostream>
using namespace std;
bool a[100001] = {1, 1}; // i=0,i=1的时候都不是质数 ，所以直接标记
int b[100001]; // 存质数 
int k;
long long n, m;

int main() {
    cin >> n >> m;
    // 首先筛选出 100001 内的质数
    for (int i = 2; i <= 100000; i++) 
    {
        if (a[i] == 0) b[++k] = i;
        for (int j = 1; j <= k; j++) 
        {
            if (i * b[j] > 100000) break;
            a[i * b[j]] = 1;
            if (i % b[j] == 0) break;
        }
    }
    
    // 输出指定范围 [n, m] 内的质数
    for (int i = n; i <= m; i++) 
    {
        if (a[i] == 0) cout << i << " ";
    }
    return 0;
}    

#include<bits/stdc++.h>
// 使用标准命名空间，这样在使用标准库中的类和函数时无需加std::前缀
using namespace std;
// 定义一个整数变量n，用于存储待分解质因数的数
int n;
// 定义一个整数类型的向量a，用于存储分解得到的质因数
vector<int> a;

// 主函数，程序的入口点
signed main(){
    // 从标准输入读取一个整数n
    cin>>n;

    // 从2开始到根号n进行遍历，寻找n的质因数
    // 因为如果一个数n有大于根号n的因数，那么必然有小于根号n的因数与之对应
    for(int i = 2; i <= sqrt(n); i++)
    {
        // 当n能被i整除时，将i添加到向量a中，并将n除以i
        // 持续进行这个操作，直到n不能再被i整除为止
        while(n % i == 0)
        {
            // 将质因数i添加到向量a中
            a.push_back(i);
            // n除以i，继续对商进行质因数分解
            n /= i;
        }
    }

    // 如果经过上述循环后，n仍然大于1，说明n本身是一个质数
    // 因为如果n能被完全分解为小于等于根号n的质因数，那么最后n会变为1
    if(n > 1) a.push_back(n);

    // 遍历向量a，输出所有的质因数
    for(auto &it : a) cout << it << " ";

    // 程序正常结束，返回0
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int x,n;
#define int long long

const int p = 233333;

// 快速幂函数，用于计算x的n次幂对p取模的结果
int qmi(int x, int n)
{
    // 初始化结果为1对p取模，防止出现负数情况
    int res = 1 % p;
    // 当指数n不为0时，继续循环
    while (n)
    {
        // 如果n的二进制表示的最低位为1，说明当前位需要参与计算
        if (n & 1)
            res *= x % p;
        // 将指数n右移一位，相当于除以2
        n /= 2;
        // 更新底数x为x的平方对p取模的结果
        x = (int)x * x % p;
    }
    // 返回最终结果
    return res;
}
	
signed main(){
	cin>>x>>n;
	cout<<qmi(x,n);
	return 0;
}

#include<bits/stdc++.h>
//输入格式:
//输入一行字符串，保证字符串中只包含字符LQ
//输出格式:
//输出一个整数，为输入字符串中最长平衡串的长度。
using namespace std;
const int N = 1005;
int prefix[N];

int main(){
    string s;cin>>s;
    for(int i=0;i<s.length();i++)
    {
        prefix[i] = prefix[i-1] + (s[i]=='L'?1:-1);
    }

    int ans=0;
    for(int i=0;i<s.size();i++)
        for(int j=i;j<s.size();j++)
            if(prefix[j]-prefix[i-1]==0) ans = max(ans,j-i+1);

    cout<<ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll X = 1e9+7; 
const ll N = 100005;
ll a[6][N];
ll prefix[6][N];

int main(){
    int n,m;
    // 从标准输入读取 n 和 m 的值
    cin>>n>>m;
    // 读取第一行的 5 个值，存储在 a[1][1] 到 a[1][5] 中
    for(int i=1;i<=5;i++)
    {
        cin>>a[1][i];
    }
    // 计算每个数的 1 到 5 次幂，并计算前缀和
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=n;j++)
        {
            // 计算 a[1][j] 的 i 次幂，并存储在 a[i][j] 中
            a[i][j] = pow(a[1][j],i);
            // 计算前缀和，prefix[i][j] 表示前 j 个数的 i 次幂的和
            prefix[i][j] = prefix[i][j-1] + a[i][j];
        }
    }
    // 处理 m 次查询
    while(m--)
    {
        int l,r,k;
        // 从标准输入读取查询的区间 [l, r] 和次幂 k
        cin>>l>>r>>k;
        // 计算区间 [l, r] 内所有数的 k 次幂的和，并对 X 取模后输出
        cout<<(prefix[k][r]-prefix[k][l-1])%X<<endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)    cin >> a[i];
    for (int i = 1; i <= n; ++i)    s[i] = s[i - 1] + a[i];
    
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

#include<iostream>
using namespace std;

// 定义全局变量 n、m、q
// n 表示矩阵的行数，m 表示矩阵的列数，q 表示查询的次数
int n,m,q;
// 定义二维数组 sum 用于存储二维前缀和
// 大小为 1010x1010，足够处理一定规模的数据
long long int sum[1010][1010];

int main(){
    // 从标准输入读取矩阵的行数 n、列数 m 和查询的次数 q
    cin>>n>>m>>q;

    // 嵌套循环遍历矩阵的每一个元素
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            // 定义变量 a 用于临时存储当前输入的矩阵元素值
            int a;
            // 从标准输入读取当前位置的矩阵元素值
            cin>>a;
            // 计算二维前缀和并存储到 sum[i][j] 中
            // sum[i-1][j] 表示上方区域的前缀和
            // sum[i][j-1] 表示左方区域的前缀和
            // sum[i-1][j-1] 表示左上角区域的前缀和，由于在前面两项中被重复计算，所以要减去
            // a 是当前位置的元素值
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a;  
        }
    }

    // 处理 q 次查询
    while(q--){
        // 定义四个变量 x1、y1、x2、y2 用于表示查询的子矩阵的左上角和右下角坐标
        int x1,y1,x2,y2;
        // 从标准输入读取查询子矩阵的左上角 (x1, y1) 和右下角 (x2, y2) 坐标
        cin>>x1>>y1>>x2>>y2;
        // 计算并输出查询子矩阵的元素和
        // sum[x2][y2] 表示从矩阵左上角到 (x2, y2) 的所有元素和
        // sum[x2][y1-1] 表示从矩阵左上角到 (x2, y1 - 1) 的所有元素和，要减去它
        // sum[x1-1][y2] 表示从矩阵左上角到 (x1 - 1, y2) 的所有元素和，要减去它
        // sum[x1-1][y1-1] 由于在前面两项中被多减了一次，所以要加回来
        cout<<sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1]<<endl;
    }
    // 程序正常结束，返回 0
    return 0;
}

#include <iostream>
using namespace std;

// 定义常量 N 作为二维数组的最大边长
const int N = 1010;
// n 为矩阵的行数，m 为矩阵的列数，q 为查询的次数
int n, m, q;
// 数组 a 存储原始矩阵元素，数组 s 存储二维前缀和
int a[N][N], s[N][N];

int main()
{
    cin >> n >> m >> q;

    // 读取矩阵 a 的元素
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    // 计算二维前缀和数组 s
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];

    // 处理 q 次查询
    while (q -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
int diff[N];//差分数组  

void CF(int l,int r,int x)
{
    diff[l] += x;
    diff[r+1] -= x;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;cin>>n>>m;

    int a[n+1]={0};
    for(int i=1;i<=n;i++) cin>>a[i];

    //对原数组进行差分构造差分数组 
    for(int i=1;i<=n;i++) diff[i] = a[i] - a[i-1];

    //对原数组x-y区间进行运算之后存在差分数组当中 
    while(m--)
    {
        int x,y,z;cin>>x>>y>>z;
        CF(x,y,z);
    }

    //对差分数组求前缀和得到经过操作q次之后的数组结果
    for(int i=1;i<=n;i++)
    {
        diff[i] += diff[i-1];
        cout<<diff[i]<<" ";
    }
    return 0;
}

#include <iostream>
using namespace std;

// 定义数组最大长度
const int N = 100010;
// n 为数组长度，m 为操作次数
int n, m;
// 数组 a 存储原始数组及最终结果，数组 b 存储差分数组
int a[N], b[N];

// 对差分数组进行区间修改操作
// l 为区间左端点，r 为区间右端点，c 为要增加的值
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;

    // 输入原始数组 a 的元素
    for (int i = 1; i <= n; ++i)    cin >> a[i];
    // 根据原始数组初始化差分数组 b
    for (int i = 1; i <= n; ++i)    insert(i, i, a[i]);

    // 处理 m 次区间修改操作
    while (m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }

    // 通过差分数组还原得到修改后的数组 a
    for (int i = 1; i <= n; ++i)    a[i] = a[i - 1] + b[i];
    // 输出修改后的数组 a 的元素
    for (int i = 1; i <= n; ++i)    cout << a[i] << ' ';

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

// 定义数组 a 存储原矩阵，数组 s 存储差分数组，n 为行数，m 为列数，q 为操作次数
int a[1005][1005], s[1005][1005], n, m, q;

// 对差分数组进行区间修改
void insert_num(int x1, int y1, int x2, int y2, int c) {
    s[x1][y1] += c;
    s[x2 + 1][y1] -= c;
    s[x1][y2 + 1] -= c;
    s[x2 + 1][y2 + 1] += c;
}

int main() {
    // 输入矩阵的行数、列数和操作次数
    cin >> n >> m >> q;
    // 输入矩阵元素并初始化差分数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            insert_num(i, j, i, j, a[i][j]);
        }
    }
    // 处理 q 次区间修改操作
    while (q--) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert_num(x1, y1, x2, y2, c);
    }
    // 从差分数组还原出修改后的矩阵并输出
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            cout << s[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
 
int a[N];
int n,m;
int x;

bool check(int mid)
{
	if(a[mid]<x) return true;
	else return false;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	while(m--)
	{
		cin>>x;
		
		int l=0,r = n+1;
		while(l+1<r)
		{
			int mid = (l+r)/2;
			if(check(mid)) l = mid;
			else r = mid;
		}
		if(a[r]==x) cout<<r<<" ";
		else cout<<"-1"<<" ";
	}
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2*1e5 + 10;
int a[N];
int main(){
	int n,c;cin>>n>>c;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	int ans=0;
	sort(a+1,a+n+1);
	int A = 1,B = 1;
	while(A<=n && B<=n)
	{
		if(a[A]-a[B] >= c)
		{
			if(a[A]-a[B]==c) ans++;
			B++;
		} 
		else A++;
	}
	cout<<ans;
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];

int n,need,mx;

#define int long long
bool check(int mid)
{
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
		sum += max(0LL,a[i]-mid);
	}
	if(sum>=need) return true;
	else return false;
}
signed main(){
	cin>>n>>need;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mx = max(mx,a[i]);
	}
	
	int l = 0, r = mx;
	
	while(l+1<r)
	{
		int mid = (l+r)/2;
		if(check(mid))
		{
			l = mid;
		}
		else r = mid;
	}
	cout<<l;
	
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int n,k,mx;
int res;//记录查找到的答案 
bool check(int x)
{
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
		sum += a[i]/x;//n个圆木可以切割成的总段数 
		if(sum>=k) return true; //满足条件的blue放在左边 
	}
	return false;
}
int main(){
	cin>>n>>k;
	
	mx = 0;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		mx = max(mx,a[i]);
	}
	
	int l = 0,r = mx+1;
	
	while(l+1<r)
	{
		int mid = (l+r)/2;
		if(check(mid))
		{
			l = mid;
		}
		else r = mid;
	}
	
	cout<<l;//输出分界线坐标满足条件的最优解 
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+9;
char s[N]; 

int main(){
    cin>>s+1;
    int n = strlen(s+1);
    int l = 1;
    int r = n;
    bool flag = true;
    while(l<r && flag)
    {
        if(s[l]!=s[r]) flag = false;
        l++;
        r--;
    }
    cout<<(flag?"Y":"N");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

map<char, int> mp;

int main() {
    int n;
    cin >> n;
    string s;
    for (int i = 1; i <= n; i++) {
        char s_;
        cin >> s_;
        s += s_;
    }

    int ans = 0;
    for (int r = 0, l = 0; r < s.size(); r++) {
        mp[s[r]]++;
        while (mp[s[r]] >= 2) {
            mp[s[l]]--;
            l++;
        }
        ans = max(ans, r - l + 1);
    }
    cout << ans;
    return 0;
}

#include <iostream>
using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

int main()
{
    cin >> n >> m >> x;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];

    for (int i = 0, j = m - 1; i < n; ++i)
    {
        while (a[i] + b[j] > x) -- j;
        if (a[i] + b[j] == x)
        {
            cout << i << ' ' << j << endl;
            break;
        }
    }
    return 0;
}

#include <iostream>
using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];

    int i = 0;
    for (int j = 0; j < m; ++j)
        if (i < n && a[i] == b[j])
            ++i;

    if (i == n)
        puts("Yes");
    else
        puts("No");

    return 0;
}

int ntoten(string s, int n) {
    int ans = 0;
    for (int i = 0; i < s.size(); i++) {
        ans = ans * n + s[i] - '0';
    }
    return ans;
}

int ntoten(int a[], int num, int n) {
    int ans = 0;
    for (int i = 0; i < num; i++) {
        ans = ans * n + a[i];
    }
}

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 15;
int x[N], y[N];
int n, bx, m, by;

LL ntoten(int a[], int num, int n) {
    LL res = 0;
    for (int i = 0; i < num; i++) {
        res = res * n + a[i];
    }
    return res;
}

int main() {
    cin >> n >> bx;
    for (int i = 0; i < n; i++) cin >> x[i];
    cin >> m >> by;
    for (int i = 0; i < m; i++) cin >> y[i];

    LL xs = ntoten(x, n, bx), ys = ntoten(y, m, by);
    if (xs < ys) cout << '<';
    else if (xs > ys) cout << '>';
    else cout << '=';
    return 0;
}

void tenton(int nums, int n) {
    stack<int> s;
    while (nums) {
        s.push(nums % n);
        nums /= n;
    }
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
}

int a[N];
void tenton(int nums, int n) {
    int cnt = 0;
    while (nums) {
        a[cnt++] = nums % n;
        nums /= n;
    }
    reverse(a, a + cnt);
    for (int i = 0; i < cnt; i++) cout << a[i];
}

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;
using ll = long long;
int a[N];
char ch[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};

void solve() {
    int N, M;
    cin >> N >> M;
    string s;
    cin >> s;

    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s[i] >= '0' && s[i] <= '9') a[i] = s[i] - '0';
        else a[i] = s[i] - 'A' + 10;
    }

    ll x = 0;
    for (int i = 0; i < len; i++) {
        x = x * N + a[i];
    }

    string ans;
    while (x) {
        ans += ch[x % M];
        x /= M;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int arr[N];
int arr1[N];//记录转置之后的数组 
int main(){
	int n,m,t;cin>>n>>m>>t;
	for(int i=0;i<n*m;i++) cin>>arr[i];
	
	int op,n1=n,m1=m,a,b;
	while(t--)
	{
		cin>>op>>a>>b;
		//重塑不改变一维数组的序列
		if(op==1)
		{
			n1 = a;
			m1 = b;
		}
		
		//转置 注意二维转一维的公式
		else if(op==2)
		{
			for(int i=1;i<n*m;i++)
			{
				arr1[(i%m1)*n1+i/m1] = arr[i]; 
			}
			for(int i=1;i<n*m;i++)
			{
				arr[i] = arr1[i];//把转置之后的数组arr1赋值回arr 
			}
			
			//记得行列交换方便op==3查询不出错
			int temp = n1;
			n1 = m1;
			m1 = temp; 
		}
		
		//查询 
		else cout<<arr[a*m1+b]<<endl;
	}
  return 0;
}