题意#

$N$ 个数，每个数介于 $1$ 和 $M_i$ 之间（可以为 $1$ 或 $M_i$）。对于每一个 $M_i$ 选择一个数这个数在 $1$ 到 $M_i$ 之间，且选择的数不能重复。问一共有多少选择方案。

题解#

从小到大排序后，假设当前你对前i个进行了选择，这 $i$ 个选择的范围在 $1$ 到 $M_i$ 之间，对于第 $M_{i+1}$ 个数它之中一定有 $i$ 个数已经被选择过了，因为已经从小到大排过序了。所以对于每个 $M_i$,它对答案的贡献是使答案乘上 $M_i - i - 1$ 的结果。所以当 $M_i < i - 1$ 时是无解的。

代码#

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9 + 7;
void sl(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1 ;i <= n ;i++){
        cin >> a[i];
    }
    sort(a.begin() + 1,a.end());
    int sum = 1;
    for(int i = 1 ;i <= n ;i++){
        if(a[i] < i){
            sum = 0;
            break;
        }
        sum = sum * (a[i] - i + 1) % mod;
    }
    cout << sum << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) sl();
    return 0;
}

题意#

$A B$ 两地的距离 $s$，初始两人在 $A$ 地，人的步行速度 $a$ 和车的速度 $b$，车一次只能载一人求两人同时到达 $B$ 的所花费的最少时间。保证车速大于人的速度。

题解#

假设先开车带一个人行驶了 $x$ 距离，然后折返回去接第二个人，一路开到 $B$ 点，且保证两人同时到达，由此可列出方程：

根据 $x$ 可求出最后时间为：$x / b + (s - x) / a$

代码#

#include<bits/stdc++.h>

using namespace std;

#define int long long

void sl(){
    double s,a,b;
    cin >> s >> a >> b;
    double x = (b + a) * s / (b + 3 * a);
    double t = x / b + (s - x) / a;
    cout << fixed << setprecision(6) << t << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) sl();
    return 0;
}

题意#

$Q$ 次询问，每次询问给一个 $l$ 和 $r$，求出

后的结果。

题解#

首先观察数据范围，发现询问次数在 $10^4$ 次，每次的询问范围在 $10^{12}$。因此可以判断该题应该是一道 $O(1)$ 的结论题。

首先观察 $7 \mod 9$，$70 \mod 9$，$700 \mod 9$ 等等，发现结果都是 $7$。因此可以大胆假设对于任意整数 $x$，有 $x \mod 9 = (x \times 10^y) \mod 9$（其中 $y$ 为 $0$ 到正无穷之间的整数）。

而对于 $l$ 到 $r$ 拼接起来形成的巨大数，可以看做 $l \times 10^{y_l} + (l + 1) \times 10^{y_{l + 1}} + \ldots + r \times 10^{y_r}$。根据之前的假设，将 $10$ 的上标全部置为 $0$ 在 $x\mod 9$ 意义下的结果是一样的，所以原式变为 $l + (l + 1) + \ldots + r = \frac{(r - l + 1) \times (l + r)}{2}$。

因为我们最后需要对答案取模，为了防止取模后奇偶性发生改变，我们需要对 $(r - l + 1)$ 或者 $(l + r)$ 单独除 $2$

代码#

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 9;

void sl(){
    int l,r;
    cin >> l >> r;
    int sum;
    if((l + r) % 2 == 0){
        sum = (((l + r) / 2 % mod) * ((r - l + 1) % mod)) % mod;
    }else{
        sum = (((l + r) % mod) * ((r - l + 1) / 2 % mod)) % mod;
    }
    cout << sum << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) sl();
    return 0;
}

题意#

给一个长度为 $n$ 的数列，我们需要找出该数列的一个连续子串，使得该子串平均数最大化，并且子串长度 $\ge m$。

题解#

我们使用二分答案来解决这个问题。对于当前二分出的平均值，我们要确定它的合法性，可以通过以下步骤实现：

1. 将所有数先减去平均值。
2. 这时我们相当于是要找到一段区间，使得它的和大于 $0$
3. 对减后的数组进行前缀和计算。
4. 假设我们当前找到了 pre[i]，只需要判断 pre[1] 到 pre[i - m] 之间的最小值是否小于 pre[i]，就可以判断出是否存在这样的区间。

代码#

#include<bits/stdc++.h>

using namespace std;

#define int long long
void sl(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 1 ;i <= n ;i ++){
        cin >> a[i];
        a[i] *= 10000;
    }
    auto check=[&](int x){
        vector<int> b = a,pre(n + 1);
        int mn = 0;
        for(int i = 1 ;i <= n ;i++){
            b[i] -= x;
            pre[i] = pre[i - 1] + b[i];
            if(i >= m){
                mn = min(mn,pre[i - m]);
                if(pre[i] > mn) return 1;
            }
        }
        return 0;
    };
    int l = 0,r = 30000000;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    cout << l / 10 << '\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) sl();
    return 0;
}

题意#

有 $q$ 组询问，每次询问 $a,b$ 在 $[l,r]$ 之间的最大公约数，如果不存在输出 $-1$

题解#

首先考虑 $a, b$ 的最大公约数 $\gcd(a, b)$ 与 $a, b$ 其他公约数之间的关系，可以发现 $a, b$ 的所有公约数均是最大公约数的因数。因此我们先处理出最大公约数的所有因数，然后对于每次询问的 $l, r$ 进行二分查找即可。

代码#

#include <bits/stdc++.h>

using namespace std;
#define int long long

void sl( ){
    int a,b,q;
    cin >> a >> b >> q;
    int gd = __gcd(a,b);
    set<int> p;
    for(int i = 1 ;i * i <= gd ;i ++){
        if(gd % i == 0){
            p.insert(i);
            p.insert(gd / i);
        }
    }
    while(q--){
        int l,r;
        cin >> l >> r;
        if(gd < l){
            cout << "-1\n";
            continue;
        }
        if(gd <= r){
            cout << gd << '\n';
            continue;
        }
        auto it = p.upper_bound(r);
        it--;
        if(*it < l) cout << "-1\n";
        else cout << *it << '\n';
    }
}

signed main( ){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    //	cin>>t;
    while(t--) sl();
    return 0;
}

题意#

给你 $m_1$ 与 $m_2$，并且给你 $n$ 个数，假设第 $i$ 个数为 $S_i$，找到最小的 $k$ 使得，$S_i ^ {k} \mod m_1^{m_2} = 0$，如果不存在这样的 $k$，输出 $-1$

题解#

首先我们需要知道两个结论：

1. $x \mod y = 0$，将 $x$ 和 $y$ 质因数分解后，$s1$ 为 $x$ 的质因数集，$s2$ 为 $y$ 的质因数集，那么 $s2$ 为 $s1$ 的一个子集。
2. 假设 $z$ 是 $x$ 的一个质因数，$x$ 可以分解出 $num_z$ 个 $z$，而 $x^y$ 可以分解出 $num_z \times y$ 个 $z$。

之后我们在回来看题目，要保证 $S_i^k \mod m_1^{m_2} = 0$，可以先对 $m_1$ 进行质因数分解，并且对于每一个 $S_i$ 同样进行质因数分解。如果 $S_i$ 可以通过幂次操作使得取模结果为 0，那么 $m_1$ 的每一个质因数也需要在 $S_i$ 中出现，并且操作之后的每一个质因数的数量也要大于 $m_1$ 的每一个质因数的数量乘上 $m_2$

代码#

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 3e4 + 10;

vector<int> prime;
bool is[N];

void init(){
	for(int i = 2 ;i < N ;i ++){
		if(!is[i]){
			prime.push_back(i);
	    	for(int j = i * i ;j < N ;j += i){
				is[j] = 1;
			}
		}
	}
}

void sl( ){
	int m1,m2,n;
	cin >> n >> m1 >> m2;
	vector<int> a(n + 1);
	map<int,int> mp;
	int idx = 0;
	while(m1 > 1){
		while(m1 % prime[idx] == 0){
			mp[prime[idx]] ++;
			m1 /= prime[idx];
		}
		idx++;
	}
	for(auto it : mp){
		auto[u,v] = it;
		mp[u] *= m2;
	}
	int f = 0,num = -1;
	for(int i = 1 ;i <= n ;i ++){
		cin >> a[i];
	}
	for(int i = 1 ;i <= n ;i++){
		int flag = 1,mn = 0;
		for(auto x : mp){
			if(a[i] % x.first != 0){
				flag = 0;
				break;
			}
			int ans = 0;
			while(a[i] % x.first == 0){
				a[i] /= x.first;
				ans++;
			}
			mn = max(mn,(x.second - 1) / ans + 1);
		}
		if(flag == 0) continue;
		if(num == -1){
			num = mn;
		}else{
			num = min(num,mn);
		}
	}
	cout << num << '\n';
}


signed main( ){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	init();
	int t = 1;
//	cin>>t;
	while(t--) sl();
	return 0;
}