2. 宣读数字【算法赛】
思维题，注意到完全平方数的约数是奇数个，其余都是偶数个。
#include <bits/stdc++.h>using namespace std;#define LL long long#define pb push_back#define x first#define y second #define int long long #define endl '\n'const LL maxn = 4e05+7;const LL N = 5e05+10;const LL mod = 988244353;const int inf = 0x3f3f3f3f;const LL llinf = 5e18;typedef pair<int,int>pl;priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆priority_queue<LL> ma;//大根堆LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;}LL lcm(LL a , LL b){return a / gcd(a , b) * b;}int n , m;vector<int>a(N , 0);void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}}LL qpow(LL a , LL b)//快速幂{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;}std::vector<int> minp, primes;void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}}void solve() {cin >> n;if((int)sqrt(n) * (int)sqrt(n) == n){cout <<"L\n";}else{cout <<"Q\n";}} signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;sieve(N); cin>>t;while(t--){solve();}return 0;}3. 最大质因子个数【算法赛】
贪心：用尽可能多的质数来构造这个数。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 988244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
std::vector<int> minp, primes;
void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}void solve()
{int n;cin >> n;int cnt = 0;int tmp = 1;for(auto it : primes){if(n / it >= tmp){cnt++;tmp *= it; }else{break;}}cout << cnt << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;sieve(N); cin>>t;while(t--){solve();}return 0;
}
4. 物流选址【算法赛】
注意到无论怎么改变，这两个数的差值不会变，因此考虑到差值的每个约数能否满足题意，记录最小值即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 988244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
void solve()
{int n , m;cin >> n >> m;int k = m - n;if(k == 0 || m % n == 0){cout << 0 << endl;}else if(k == 1 || n >= k){cout << -1 << endl;}else{int ans = llinf;for(int i = 2 ; i * i <= k ; i ++){//可能的倍数if(k % i == 0){if(n % i == m % i){int tmpn = n + i - (n % i);int tmpm = m + i - (m % i);if(tmpm % tmpn == 0){ans = min(ans , i - n % i);}}if(n % (k / i) == m % (k / i)){int tmpn = n + (k / i) - (n % (k / i));int tmpm = m + (k / i) - (m % (k / i));if(tmpm % tmpn == 0){ans = min(ans , k / i - m % (k / i));}}}}int i = k;int tmpn = n + i - (n % i);int tmpm = m + i - (m % i);if(tmpm % tmpn == 0){ans = min(ans , i - n % i);} if(ans == llinf){cout << -1 << endl;}else{cout << ans << endl;}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
5. 小蓝的MEX问题【算法赛】
计数问题,对于每次询问，大于k的数全部可以选或者不选,而小于k的数至少选一个，然后可以预处理出所有的MEX取值情况，最后输出即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
void solve()
{int n , m;cin >> n >> m;vector<int>cnt(n + 5 ,0);for(int i = 0 ; i < n ; i ++){cin >> a[i];cnt[a[i]] ++;} int MEX = 0;while(cnt[MEX] > 0){MEX++;}int pre = 1;vector<int>ans(n + 5 , 0);int tot = n;for(int i = 0 ; i <= MEX ; i ++){tot -= cnt[i];//这些随便选if(i == 0){ans[i] = qpow(2 , tot);ans[i]--;ans[i] += mod;ans[i] %= mod;}else{ans[i] = pre * qpow(2 , tot);ans[i] %= mod;}pre *= ((qpow(2 , cnt[i]) - 1 + mod) % mod);pre %= mod;}for(int i = 0 ; i < m ; i ++){int x;cin >> x;cout << ans[x] << endl;}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}
6. 平摊购买费用【算法赛】
首先发现排序后没影响，因此先排个序，然后发现若要使得 l - f 最小，必然选取的是前y个数和后m-y个数。
构建关于y的函数，发现这是一个有波谷的函数，因此考虑三分求波谷即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 988244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
void solve()
{int n , m;cin >> n >> m;int a[n + 5];set<int>st;vector<int>pre(n + 5 , 0);for(int i = 1 ; i <= n ; i ++)cin >> a[i] , st.insert(a[i]);sort(a + 1, a + n + 1);for(int i = 1 ; i <= n ; i ++){pre[i] = pre[i - 1] + a[i];}map<int,int>mp;int idx = 1;for(auto it :st){mp[it] = idx++;}map<int,int>pm;for(int i = 1 ; i <= n ; i ++){int id = mp[a[i]];if(!pm.count(id)){pm[id] = i;}}//先找比x大的位置for(int i = 0 ; i < m ; i ++){int x , c;cin >> x >> c;auto it = st.lower_bound(x);if(it == st.end()){cout << pre[c] << endl;}else{int tmp = *it;//取前几个跟最后几个int ans = pre[c];auto check =[&] (int t){return pre[c - t] + t * x - (pre[n] - pre[n - t] - t * x); };int l = 0 , r = c;while(l < r){int mid = (r - l) / 3;if(r - l < 3){for(int j = l ; j <= r ; j ++){ans = min(ans , check(j));}break;}int m1 = l + mid;int m2 = m1 + mid;if(check(m1) > check(m2)){l = m1;}else{r = m2;}}cout << ans << endl;}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}
4. 电力之城【算法赛】
观察到一次只会使得电能增加1/2，而最终总的电能是可以确定的，因此变成了一个NIM问题，每次能拿一个或两个石头，求最终谁拿走了最后的石头。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
void solve()
{int n;cin >> n;string s;cin >> s;int cnt = 0;for(int i = 1 ; i < n ;i ++){cnt += (s[i] == s[i - 1]);} if(cnt % 3 == 0){cout << "qiao\n";}else{cout <<"lan\n";}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;cin>>t;while(t--){solve();}return 0;
}
5. 价值共性度【算法赛】
此题类似于昆明邀请赛的E题，需要知道这么一个事实：一个长度为n的数列，前缀GCD的数量不会超过logn个，因此我们只需要维护以某个数结尾，向前能够组成多少个GCD即可，并且记录这些GCD的最左侧位置，然后暴力求答案即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 1e6+10;
const LL mod = 988244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){for(int i = 0 ; i <= n ; i ++){a[i] = 0;}
}
LL qpow(LL a , LL b)//快速幂
{LL sum=1;while(b){if(b&1){sum=sum*a%mod;}a=a*a%mod;b>>=1;}return sum;
}
std::vector<int> minp, primes;
void sieve(int n) {minp.assign(n + 1, 0);primes.clear();for (int i = 2; i <= n; i++) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto p : primes) {if (i * p > n) {break;}minp[i * p] = p;if (p == minp[i]) {break;}}}
}void solve()
{set< pair<int,int> >st;//前缀gcdset< pair<int,int> >pre;int n , k;cin >> n >> k;for(int i = 1 ; i <= n ; i ++){cin >> a[i];}vector<int>S(n + 5 , 0);for(int i = 1 ; i <= n ; i ++){S[i] = S[i - 1] + a[i];}int ans = 0;for(int i = 1 ; i <= n ; i ++){st.empty();set< pair<int,int> >tmp;tmp.insert({a[i] , i});for(auto it : pre){tmp.insert({gcd(a[i] , it.first) , it.second});}pre.clear();map<int,int>mp;for(auto it : tmp){if(mp.count(it.first)){continue;}else{mp[it.first] = 1;if(i - it.second + 1 >= k){ans = max(ans , it.first * (S[i] - S[it.second - 1]));}st.insert(it);}}swap(st , pre);}cout << ans << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}
6. 小蓝的逆序对问题【算法赛】
（不是正解..但卡过去了）
如此复杂度，想到用根号分治来解决问题，考虑交换两数后的逆序对该如何变化，然后想办法维护每个区间的信息
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 2e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
const int B = 800;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){return b > 0 ? gcd(b , a % b) : a;
}LL lcm(LL a , LL b){return a / gcd(a , b) * b;
}
int n , m;
vector<int>num(N , 0);
long long sum = 0;
void merge(int s1, int e1, int s2, int e2){vector<int> temp;int p1 = s1;int p2 = s2;while(p1 <= e1&&p2 <= e2){if(num[p1] <= num[p2]){temp.push_back(num[p1++]);}else{sum += (e1-p1+1);temp.push_back(num[p2++]);}}while(p1 <= e1){temp.push_back(num[p1++]);}while(p2 <= e2){temp.push_back(num[p2++]);}for(int i = 0;i < (int)temp.size();i++){num[s1+i] = temp[i];}
}
void mergesort(int str, int end){if(str < end){int mid = (str + end)/2;mergesort(str,mid);mergesort(mid+1,end);merge(str,mid,mid+1,end);}
}
struct BIT{//Binary indexed Tree(树状数组)int n;vector<int> t;BIT(int n) : n(n) , t(n + 1 , 0){}int lowbit(int x){return x & -x;}void modify(int k, int v) {while (k <= n) {t[k] += v;k += lowbit(k);}}void modify(int l, int r, int v) {modify(l, v), modify(r + 1, -v); // 将区间加差分为两个前缀加}int query(int k) {int ret = 0;while(k) {ret += t[k];k -= lowbit(k);}return ret;}int query(int l , int r){return query(r) - query(l - 1);}
};
int ans[500][N];
void solve()
{int n , k;cin >> n >> k;vector<int>idx(n + 5 , 0);memset(ans , -1 , sizeof ans);int tot = 505;vector<BIT>bit;for(int i = 0 ; i < tot ; i ++){BIT tmp(N);bit.pb(tmp);}for(int i = 1 ; i <= n ; i ++){cin >> num[i];idx[i] = (i - 1) / B;}int a[n + 5];for(int i = 1 ; i <= n ; i ++){a[i] = num[i];}unordered_map<int,int>mp;set<int>st;for(int i = 1 ; i <= n ; i ++){st.insert(num[i]);}int id = 1;for(auto it : st){mp[it] = id++;}for(int i = 1 ; i <= n ; i ++){int id = idx[i];int tp = mp[a[i]];bit[id].modify(tp + 1, 1);}mergesort(1,n);
// cout << bit[0].query(4) << endl;for(int i = 0 ; i < k; i ++){int l , r;cin >> l >> r;long long tmp = sum;int ll = idx[l] , rr = idx[r];// cout << ll << " " << rr << endl;if(ll == rr){for(int i = l ; i <= r ; i ++){if(a[r] < a[i]){tmp--;}if(a[l] > a[i]){tmp--;}if(a[l] < a[i]){tmp++;}if(a[r] > a[i]){tmp++;}}}else{for(int i = ll ; i <= rr ; i ++){if(i == ll){for(int j = l ; j <= (ll + 1) * B ; j ++){if(a[r] < a[j]){tmp--;}if(a[l] > a[j]){tmp--;}if(a[l] < a[j]){tmp++;}if(a[r] > a[j]){tmp++;}}}else if(i == rr){for(int j = rr * B + 1 ; j <= r ; j ++){if(a[r] < a[j]){tmp--;}if(a[l] > a[j]){tmp--;}if(a[l] < a[j]){tmp++;}if(a[r] > a[j]){tmp++;}} }else{int id1 = mp[a[r]];if(ans[i][id1] != -1){tmp += ans[i][id1];}else{ans[i][id1] = bit[i].query(id1);tmp += ans[i][id1]; }if(ans[i][id1 + 1] != -1){tmp -= B - ans[i][id1 + 1];//比a[r]大的 }else{ans[i][id1 + 1] = bit[i].query(id1 + 1);tmp -= B - ans[i][id1 + 1];//比a[r]大的 }int id2 = mp[a[l]];if(ans[i][id2] != -1){tmp -= ans[i][id2];}else{ans[i][id2] = bit[i].query(id2);tmp -= ans[i][id2]; }if(ans[i][id2 + 1] != -1){tmp += B - ans[i][id2 + 1];//比a[r]大的 }else{ans[i][id2 + 1] = bit[i].query(id2 + 1);tmp += B - ans[i][id2 + 1];//比a[r]大的 }}//cout << tmp << endl;}}if(a[l] > a[r]) tmp++;if(a[l] < a[r]) tmp--;cout << tmp << endl;}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout.precision(10);int t=1;//cin>>t;while(t--){solve();}return 0;
}
