题目描述：
给你n个数a[i]，m次询问，每次询问给出一个l, r,问[l, r]中有多少个数a[i]不满足：a[i]可以被该区间所有数整除
思路：
分析一下就可以发现，如果区间内一个数可以被其他所有数整除，那这个数必须等于区间所有数求gcd后的结果
所以我们需要一个数据结构可以维护区间gcd，以及可以维护出区间gcd的数量
这里给出两种方法：
- st表 + 二分，用
st表维护区间gcd,查询数量的时候，我们可以用一个vector数组来存每个数出现位置，用二分来查就行，但是因为数字是1e9，不能用vector数组，所以可以用map<int, vector>或者是写个离散化再用vector数组存 - 线段树维护区间gcd的值和区间gcd数量，就是一个简单的不带修改的普通线段树
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
int l, r;
int tr[MAX];
int lg[MAX];
int gg[MAX][30];
map<int, vector<int>>mp;
int gcd(int a, int b){
if(b) return gcd(b, a % b);
else return a;
}
void init(){
for(int i = 1; i <= n; ++i)gg[i][0] = tr[i];
for(int i = 2; i <= n; ++i){
lg[i] = lg[i / 2] + 1;
}
for(int j = 1; j <= lg[n]; ++j){
for(int i = 1; i + (1 << j) - 1 <= n; ++i){
gg[i][j] = gcd(gg[i][j - 1], gg[i + (1 << (j - 1))][j - 1]);
}
}
}
int getgcd(int l, int r){
int len = lg[r - l + 1];
return gcd(gg[l][len], gg[r - (1 << len) + 1][len]);
}
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
mp[tr[i]].push_back(i);
}
init();
cin >> m;
while(m--){
cin >> l >> r;
int x = getgcd(l, r);
cout << r - l + 1 - (upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l))<<endl;
}
}
int main(){
io;
work();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;
#define MAX 500000 + 50
int n, m, k, op;
int tr[MAX];
int num[MAX];
int gg[MAX];
int gcd(int a, int b){
if(b) return gcd(b, a % b);
else return a;
}
struct ran{
int gg, num;
};
void pushup(int p){
gg[p] = gcd(gg[ls], gg[rs]);
num[p] = (gg[ls] == gg[p] ? num[ls] : 0) + (gg[rs] == gg[p] ? num[rs] : 0);
}
void built(int p, int l, int r){
if(l == r){
gg[p] = tr[l];
num[p] = 1;
return;
}
int mid = (l + r) / 2;
built(ls, l, mid);
built(rs, mid + 1, r);
pushup(p);
}
ran getans(int p, int l, int r, int s, int t){
if(s <= l && r <= t){
return {gg[p], num[p]};
}
ran ans = {0, 0};
int mid = (l + r) / 2;
if(mid >= s){
ans = getans(ls, l, mid, s, t);
}
if(mid < t){
ran a = ans;
ran now = getans(rs, mid + 1, r, s, t);
ans.gg = gcd(ans.gg, now.gg);
ans.num = (a.gg == ans.gg ? a.num : 0) + (now.gg == ans.gg ? now.num : 0);
}
return ans;
}
void work(){
cin >> n;
for(int i = 1; i <= n; ++i)cin >> tr[i];
built(1, 1, n);
cin >> m;
int l, r;
while(m--){
cin >> l >> r;
ran ans = getans(1, 1, n, l, r);
cout << r - l + 1 - ans.num << endl;
}
}
int main(){
io;
work();
return 0;
}
题目描述：
重新给你26字母的先后顺序，按照这个顺序重新定义字典序，给你n个字符串，输出第k小的字符串
思路：
根据给出的26个字母用map映射一下，然后写一个字符串的比较函数sort一下再输出就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ls (p<<1)
#define rs ((p<<1)|1)
typedef long long ll;
typedef pair <bool,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
string s;
map<char, int>mp;
struct ran{
string s;
bool operator < (const ran &x)const{
for(int i = 0; i < s.size() && i < x.s.size(); ++i){
if(mp[s[i]] < mp[x.s[i]])return true;
else if(mp[s[i]] > mp[x.s[i]])return false;
else continue;
}
return s.size() < x.s.size();
}
}tr[MAX];
void work(){
cin >> s;
for(int i = 0; i < s.size(); ++i){
mp[s[i]] = i + 1;
}
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> tr[i].s;
}
sort(tr + 1, tr + 1 + n);
cin >> k;
cout << tr[k].s << endl;
}
int main(){
io;
work();
return 0;
}
题目描述：
给你n * m的图,*是障碍物，.是空地
现在有两个人分别在a，b的位置，二人移动的方向是一样的，都会同时向上、下、左、右四个方向移动，如果向某个方向移动的时候，遇到了障碍物或者遇到了边界，则这个人会原地不动，但是另一个人会正常行走，当然如果同一方向都遇到障碍物那就都不能朝那个东西移动，问二者什么时候可以相遇
思路：
观察一下可以发现n才50，满打满算跑满整个地图也才504的情况，很小，直接跑bfs就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define y1 y114514
#define MAX 300000 + 50
int n, m, k, x;
char tr[55][55];
bool vis[55][55][55][55];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int x1, y1, x2, y2;
struct ran{
int x1, y1, x2, y2, d;
};
bool judge(int x, int y){
if(x < 1 || x > n || y < 1 || y > n)return false;
if(tr[x][y] == '*')return false;
else return true;
}
void bfs(){
queue<ran>q;
ran now, nex;
q.push({x1, y1, x2, y2, 0});
vis[x1][y1][x2][y2] = 1;
while(!q.empty()){
now = q.front();q.pop();
if(now.x1 == now.x2 && now.y114514 == now.y2){
cout << now.d << endl;
return;
}
for(int i = 0; i < 4; ++i){
if(judge(now.x1 + dx[i], now.y114514 + dy[i])){
nex.x1 = now.x1 + dx[i];
nex.y114514 = now.y114514 + dy[i];
}
else {
nex.x1 = now.x1;
nex.y114514 = now.y114514;
}
if(judge(now.x2 + dx[i], now.y2 + dy[i])){
nex.x2 = now.x2 + dx[i];
nex.y2 = now.y2 + dy[i];
}
else{
nex.x2 = now.x2;
nex.y2 = now.y2;
}
if(vis[nex.x1][nex.y114514][nex.x2][nex.y2])continue;
nex.d = now.d + 1;
q.push(nex);
vis[nex.x1][nex.y114514][nex.x2][nex.y2] = 1;
}
}
cout << "no solution\n";
}
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> tr[i][j];
if(tr[i][j] == 'a'){
tr[i][j] = '.';
x1 = i;y1 = j;
}
else if(tr[i][j] == 'b'){
tr[i][j] = '.';
x2 = i;y2 = j;
}
}
}
bfs();
}
int main(){
io;
work();
return 0;
}
题目描述：
给你n个数，选i, j,且满足a[j] >= a[i]，问a[j] % a[i]的最大值
思路：
我们可以先对数组进行排序，排序以后，对于一个数字a[i],我们需要去找一个a[j]，求a[j]%a[i]的最大值，a[j] = k * a[i] + x,x即余数，我们可以通过枚举k，然后二分找到数组中第一个大于等于k*a[i]的位置p，则p-1位置应该是(k-1)*a[i] 到 k * a[i]这a[i]个数中余数最大的那个，对所有的k，我们都计算出余数求一个最大值，这就是对应的a[i]作为除数时能产生的余数，我们对每个i都这样求一遍就可以，复杂度应该是调和级数的，O(nlogn)
注意剪枝，即相同数字找一次就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
int tr[MAX];
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
}
sort(tr + 1, tr + 1 + n);
int ans = 0;
for(int i = 1; i <= n; ++i){
int x = tr[i];
if(tr[i] == tr[i - 1])continue;
if(x == 1)continue;
while(x - tr[i] <= tr[n]){
int p = (int)(lower_bound(tr + i + 1, tr + 1 + n, x) - tr);
ans = max(ans, tr[p - 1] % tr[i]);
x += tr[i];
}
}
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
题目描述：
给你两个数组ar[i], br[i]，Q次询问，每次询问都给出a, b,问ar[1]到ar[a]的数组成的集合与br[1]到br[b]的数组成的集合是否相同
思路：
哈希一下就行，我搞了三种数组，一个数量数组，一个前缀和的数组，一个前缀积的数组，判断的时候三个都相同就相同
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x, y;
ll ar[MAX], br[MAX];
ll sum1[MAX], sum2[MAX];
ll mul1[MAX], mul2[MAX];
ll num1[MAX], num2[MAX];
void work(){
cin >> n;
mul1[0] = mul2[0] = 1;
for(int i = 1; i <= n; ++i)cin >> ar[i];
for(int i = 1; i <= n; ++i)cin >> br[i];
set<ll>se;
for(int i = 1; i <= n; ++i){
sum1[i] = sum1[i - 1];
mul1[i] = mul1[i - 1];
num1[i] = num1[i - 1];
if(!se.count(ar[i])){
++num1[i];
se.insert(ar[i]);
sum1[i] += ar[i];
(mul1[i] *= ar[i]) %= mod7;
}
}
se.clear();
for(int i = 1; i <= n; ++i){
sum2[i] = sum2[i - 1];
mul2[i] = mul2[i - 1];
num2[i] = num2[i - 1];
if(!se.count(br[i])){
++num2[i];
se.insert(br[i]);
sum2[i] += br[i];
(mul2[i] *= br[i]) %= mod7;
}
}
cin >> m;
while (m--) {
cin >> x >> y;
if(num1[x] == num2[y] && sum1[x] == sum2[y] &&
mul1[x] == mul2[y])cout << "Yes\n";
else cout << "No\n";
}
}
int main(){
io;
work();
return 0;
}
题目描述：
你现在在0的位置，需要到达p米的位置
有n个自行车站，你只能在自行车的车站站上下车，每花一块钱最多能骑s米，一米都不可以多骑，如果当前的车不能支持从该站点骑到下一个站点，则他不会骑的
问最少需要在地上走多少米
思路：
动态规划
dp[i][j]表示到i米的位置时，花了j元能骑行的最远距离
状态转移也很好想，就是枚举一下最后一次花k元到达的j
我们假设花了k元,则我们需要知道从什么位置花了k元能走尽可能远的距离到达了j，将这个位置记做id，则dp[i][j] = max(dp[i][j - k] + tr[j] - tr[id];
而求id的方法是二分
注意别忘了加上dp[i][j] = min(dp[i][j], dp[i - 1][j])
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, kk;
ll p, s;
ll tr[MAX];
ll id[MAX][7];
ll dp[MAX][7];
void work(){
scanf("%lld%lld%lld", &n, &p, &s);
for(int i = 1; i <= n; ++i){
scanf("%lld", &tr[i]);
}
scanf("%lld", &kk);
for(int i = 1; i <= n; ++i){
id[i][0] = i;
for(int j = 1; j <= kk; ++j){
ll pos = tr[i] - j * s;
id[i][j] = lower_bound(tr + 1, tr + 1 + n, pos) - tr;
}
}
ll ans = 1e18;
for(int i = 1; i <= n; ++i){
dp[i][0] = 0;
for(int j = 1; j <= kk; ++j){
dp[i][j] = dp[i - 1][j];
for(int k = 0; k <= j; ++k){
dp[i][j] = max(dp[i][j], dp[id[i][k]][j - k] + tr[i] - tr[id[i][k]]);
}
}
}
for(int i = 1; i <= n; ++i){
ans = min(ans, p - dp[i][kk]);
}
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
题目描述：
k = p * q * q * q，p,q都是素数，问小于等于n中有多少个k
思路：
先用欧拉筛筛出1e6内的素数，再枚举每个p，通过二分去计算q的数量
需要注意的是判断p*q*q*q <= n时会爆long long，所以我们可以移项，即判断q*q*q <= n / p
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, m, k, op;
int tot;
ll prim[MAX];
bool vis[1000050];
void init(){
for(int i = 2; i <= 1000000; ++i){
if(!vis[i])prim[++tot] = i;
for(int j = 1; j <= tot && prim[j] * i <= 1000000; ++j){
vis[prim[j] * i] = 1;
if(i % prim[j] == 0)break;
}
}
}
void work(){
init();
cin >> n;
int ans = 0;
for(int i = 1; i <= tot && (ll)pow(prim[i], 4) <= n; ++i){
int l = i + 1, r = tot;
while(l <= r){
int mid = (l + r) / 2;
if(prim[mid] * prim[mid] * prim[mid] > n / prim[i])r = mid - 1;
else l = mid + 1;
}
ans += l - i - 1;
}
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
题目描述：
n个巧克力，m个盒子，这里的巧克力和盒子都只有长和宽，问能不能把n个巧克力放在不同的盒子里面
思路：
我们将n+m个巧克力和盒子放在一起，按照宽从大到小，长从大到小进行排序，然后用一个multiset来维护盒子中没有被用过的宽大于等于当前巧克力的所有的长，遇到巧克力的时候，就去multiset中二分查找他的长，如果找到了就删掉，找不到就输出No,如果遇到了盒子，则把长赛到multiset中
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 500000 + 50
int n, m, k, op;
struct ran{
int x, y;
bool op;
bool operator < (const ran &a)const{
if(x != a.x)return x > a.x;
else if(y != a.y)return y > a.y;
else return op > a.op;
}
}tr[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> tr[i].x;
}
for(int i = 1; i <= n; ++i){
cin >> tr[i].y;
}
for(int i = n + 1; i <= n + m; ++i){
cin >> tr[i].x;
}
for(int i = n + 1; i <= n + m; ++i){
cin >> tr[i].y;
tr[i].op = 1;
}
sort(tr + 1, tr + 1 + n + m);
multiset<int>se;
for(int i = 1; i <= n + m; ++i){
if(tr[i].op == 0){
auto x = se.lower_bound(tr[i].y);
if(x == se.end()){
cout << "No\n";
return;
}
se.erase(x);
}
else{
se.insert(tr[i].y);
}
}
cout << "Yes\n";
}
int main(){
io;
work();
return 0;
}
题目描述：
给你n个点，m条边，问存在多少个点满足以该点为起点可以走到一个环中
思路：
反向建图跑拓扑排序，输出没被塞到队列里面的点的数量即可
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
int in[MAX];
int x, y;
vector<int>G[MAX];
bool vis[MAX];
void work(){
cin >> n >> m;
for(int i = 1; i <= m; ++i){
cin >> x >> y;
G[y].push_back(x);
++in[x];
}
queue<int>q;
int ans = 0;
for(int i = 1; i <= n; ++i){
if(in[i] == 0){
q.push(i);
++ans;
}
}
while(!q.empty()){
int u = q.front();q.pop();
for(auto v : G[u]){
--in[v];
if(in[v] == 0){
q.push(v);
++ans;
}
}
}
cout << n - ans << endl;
}
int main(){
io;
work();
return 0;
}
题目描述：
给出n个数，m次询问，每次询问都给出l, r，假设区间内有k种数，值为a[k],且每种数出现num[k]次，则区间的价值为
∑
i
=
1
k
n
u
m
[
k
]
?
n
u
m
[
k
]
?
a
[
k
]
\sum_{i=1}^{k}{num[k]*num[k] * a[k]}
∑i=1k?num[k]?num[k]?a[k]
求每次查询的区间价值
思路：
莫队板子
简单推一下式子就行
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, op;
int block;
ll ar[MAX];
int get_block(int x){
return x / block;
}
struct ran{
int l, r, id;
bool operator < (const ran &a)const{
int x = get_block(l);
int y = get_block(a.l);
if(x != y)return x < y;
else return r < a.r;
}
}tr[MAX];
ll ans[MAX];
ll num[1000005];
ll cnt;
void add(int id){
cnt += ar[id] * (2 * num[ar[id]] + 1);
++num[ar[id]];
}
void del(int id){
cnt += ar[id] * (1 - 2 * num[ar[id]]);
--num[ar[id]];
}
void work(){
cin >> n >> m;
block = sqrt(n);
for(int i = 1; i <= n; ++i)cin >> ar[i];
for(int i = 1; i <= m; ++i){
cin >> tr[i].l >> tr[i].r;
tr[i].id = i;
}
sort(tr + 1, tr + 1 + m);
int l = 1, r = 0;
for(int i = 1; i <= m; ++i){
int s = tr[i].l, t = tr[i].r;
while(r < t)add(++r);
while(r > t)del(r--);
while(l < s)del(l++);
while(l > s)add(--l);
ans[tr[i].id] = cnt;
}
for(int i = 1; i <= m; ++i){
cout << ans[i] << endl;
}
}
int main(){
io;
work();
return 0;
}
总结
这次比赛有4个abc的题，其中有俩签到题我都做过，就直接写了交了，剩下俩都见过，但是当时没写，正好趁这次比赛补一下
中间写G题的dp的时候写了半天都是wa，换了个姿势就过了，下午对拍研究了一下，发现按照自己的dp的定义来说，应该写一句dp[i][j] = dp[i - 1][j] ，但是比赛的时候没写，所以开始一直wa，后来换个姿势以后就过了
K题确实没想到这么简单，我还在想怎么dfs能少花点时间更新，yj说反向建图跑个拓扑排序就行，一点就通我只能说是
L题赛时看了一眼，知道是个莫队，但是因为我不怎么写数据结构题，没怎么写过莫队，开始就没写，后来9个题的时候就直接下班了，就忘了这个题，刚刚补了一下发现就是sb题
J题巧克力的题确实很妙很妙，虽然我看一眼就知道是排个序然后二分去找找，但是不知道该怎么写，在我和djk写C的时候yj写了一下就过了
C题看的第一眼就想暴力跑bfs，但是刚开始没细想，最后才发现是sb题
A题djk说可以写线段树，但是当时我一看维护区间gcd，直接上st表了，难得遇到一个可以用st表的题，不能浪费了
|