A:最小的k个数一定是1到k
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
void solve(){
cin>>n>>k;
int s=0;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+k);
for(int i=1;i<=k;i++)
{
s+=(a[i]>k);
}
cout<<s<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
int cnt=0;
cin>>t;
while(t--) solve();
return 0;
}
B:
相邻的两个数互质,所以lcm=x*(x-1)
所以直接交换相邻两个数即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
void solve(){
cin>>n;
if(n%2==0){
for(int i=1;i<=n;i+=2){
cout<<i+1<<" "<<i<<" ";
}
}
else{
cout<<1<<" ";
for(int i=2;i<=n;i+=2){
cout<<i+1<<" "<<i<<" ";
}
}
cout<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
int cnt=0;
cin>>t;
while(t--) solve();
return 0;
}
C:
固定的如果a[i]<a[i+1]一定要改变,这会导致两个情况,且前缀都会变成0
后面的a[i]变成0,导致原本 a[i-1]<=a[i] 变成a[i-1]>0
或者 a[i]变成0 导致原本a[i]>a[i+1] 变成0<=a[i+1]
所以拿个set存已经变成0的数,
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
map<int,int> mp;
for(int i=1;i<=n;i++)
{
mp[a[i]]=i;
}
int mx=1;
set<int> st;
for(int i=1;i<n;i++)
{
if((a[i]>a[i+1]&&!st.count(a[i])) ||
(st.count(a[i+1])&&!st.count(a[i])))
{
if(mp[a[i]]>=mx)
{
while(mx<=mp[a[i]])
{
// cout<<a[mx]<<"\n";
st.insert(a[mx]);
mx++;
}
}
}
}
cout<<st.size()<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
int cnt=0;
cin>>t;
while(t--) solve();
return 0;
}
D:手玩一下,最大值的最短路径只有两个情况
第一种直接就是相邻两个点的最小值,或者通过一个最小点来到达,构成三元环
最大化最小值二分,然后统计前缀和后缀小于当前答案的最小点,这些点都要改变
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
void solve()
{
//inf inf 84
//d(1,2)=d(1,3)+d(2,3)=84+84
//最大值一定是在相邻两个点之间
//或者经过一个最小的点做中间点
//min(2*{a1-an},min(l,r);
cin>>n>>k;
int now=0;
multiset<int> st;
for(int i=1;i<=n;i++)
{
cin>>a[i];
st.insert(a[i]);
}
//枚举相邻点,改变比当前边小的点
//min(a[l],a[r])>=2*a[x]
auto check=[&](int x)
{
vector<int> l(n+10),r(n+10);
for(int i=1;i<=n;i++){
if(a[i]*2<x) l[i]++;
l[i]+=l[i-1];
}
for(int i=n;i>=1;i--){
if(a[i]*2<x) r[i]++;
r[i]+=r[i+1];
}
int mn=inf;
for(int i=1;i<n;i++)
{
int cnt=0;
if(a[i]<x) cnt++;
if(a[i+1]<x) cnt++;
cnt+=l[i-1]+r[i+2];
mn=min(mn,cnt);
}
return mn<=k;
};
int l=0,r=1e9;
while(l<r){
int mid=l+r+1>>1;
if(check(mid)) l=mid;
else r=mid-1;
}
cout<<l<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
E:
考虑容斥原理
答案等于l到r选三个点-lcm(i,j,k)<=2k- lcm(i,j,k)<=k
为啥只能是k的倍数,因为k是最大的,且lcm一定是k的倍数
lcm(i,j,k)=k,说明i,j是k的因子
lcm(i,j,k)<=2*k只有两种情况 (3,4,6) (6,10,15)两种情况
对于E1直接枚举即可
且由于lcm(i,j,k)<=2k- lcm(i,j,k)<=k 没有交集,所以直接减掉即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
int C(int x){
return x*(x-1)/2*(x-2)/3;
}
void solve()
{
int l,r;
//lcm(i,j,k)<3k
//lcm(i,j,k)=k lcm(i,j,k)=2*k
//lcm(i,j)=2*k
cin>>l>>r;
int res=C(r-l+1);
int ans=0;
for(int i=l+2;i<=r;i++){
int cnt=0;
for(int j=1;j<=i/j;j++)
{
if(i%j==0)
{
if(j>=l) ++cnt;
if(j!=1&&j*j!=i&&i/j>=l) ++cnt;//不算自己
}
}
ans+=(cnt-1)*cnt>>1;
if(i%6==0&&(i>>1)>=l) ++ans;
if(i%15==0&&(i<<1)/5>=l) ++ans;
}
cout<<res-ans<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
E2
对于E2,数最多200000
所以考虑直接离线每个询问
考虑lcm(i,j,k)=k
考虑直接素数筛?类似方法直接找每个数的因子,
对于 1 2 3 4 6 12
举例子,对于r=12 ,如果当前l是2,那么可以选择3 4 6
r=12当前l是4 可以选择 6
当然自身不算,所以预处理每个数的因子的贡献,按顺序加即可
对于lcm(i,j,k)=2*k
lcm(i,j,k)<=2*k只有两种情况 (3,4,6) (6,10,15)两种情况
比如(3,4,6,)贡献是啥呢
r/6 -(l-1)/3
等于r能构造的6个倍数,减掉这个(1,l-1)中不能用的3的倍数就是答案了
因为对于范围里面的6的倍数都会有一个l里面的3的倍数符合条件
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,M=2*N,mod=1e9+7;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
using node=tuple<int,int,int>;
const long long inf=1e18;
int n,m,k;
int a[N];
vector<int> g[N];
struct qu{
int l,r,id;
bool operator <(qu x) const{
return r^x.r?r<x.r:l<x.l;
}
}q[N];
struct ptt{
int lt,rt,val;
}p[5000010];
int tr[N];
int lowbit(int x){
return x&-x;
}
void add(int x,int y){
for(int i=x;i<=200000;i+=lowbit(i))
tr[i]+=y;
}
int sum(int x){
long long res=0;
if(x<=0) return 0;
for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
return res;
}
void solve()
{
}
int ans[N];
int C(int x){
return x*(x-1)*(x-2)/6;
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
int cnt=0;
cin>>t;
int n=200000;
for(int i=1;i<=n;i++)
for(int j=(i<<1);j<=n;j+=i)
g[j].push_back(i);//预处理因数
for(int i=1;i<=n;i++)
for(int j=0;j<(int)g[i].size()-1;j++)
p[++cnt].lt=g[i][j],p[cnt].rt=i,p[cnt].val=g[i].size()-j-1;
for(int i=1;i<=t;i++)
cin>>q[i].l>>q[i].r,q[i].id=i;
sort(q+1,q+t+1);
int now=1;
for(int i=1;i<=t;i++){
while(now<=cnt&&p[now].rt<=q[i].r)
add(p[now].lt,p[now].val),now++;
ans[q[i].id]=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l)*(q[i].r-q[i].l-1)/6-
max(0ll,q[i].r/6-(q[i].l-1)/3)
-max(0ll,q[i].r/15-(q[i].l-1)/6)
-sum(q[i].r)+sum(q[i].l-1);
//3 4 6
}
for(int i=1;i<=t;i++)
cout<<ans[i]<<'\n';
}