Codeforces Round #813 (Div. 2) A - E2

本文主要是介绍Codeforces Round #813 (Div. 2) A - E2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A：一组长度为n 的排列，问交换多少次，能让前m个数变成[1,m]中的数

输出前 m 个数中有多少个比 m 大的就可以了

//-------------------------代码----------------------------
 
//#define int ll
const int N = 1e5+10;
int n,m;
 
void solve()
{
    cin>>n>>m;
    int ans = 0;
    set<int> q;
    fo(i,1,n) {
        int x;cin>>x;
        if(i <= m) {
            if(x > m) {
                ans ++ ;
            }
        }
    }
    cout<<ans<<endl;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}
 
/*样例区
 
 
*/
 
//------------------------------------------------------------

B：一组长度为n的数，让所有数的位置和值的lcm之和最大

位置大的和值大的lcm如果不是本身一般就是最大的。

知识：x和x+1互质。所以只要 将n 个数两两互换就可以了

需要注意，如果有奇数个数，第一个数只能是1，偶数个数，第一个数只能是2

//-------------------------代码----------------------------
 
//#define int ll
const int N = 1e5+10;
int n,m;
int a[N];
void solve()
{
    cin>>n;
    for(int i = n;i>=1;i-=2) {
        a[i] = i - 1;a[i-1] = i;
    }
    if(n % 2 == 1) a[1] = 1;
    else a[1] = 2;
    fo(i,1,n) cout<<a[i]<<' ';cout<<endl;
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
    int t;cin>>t;while(t -- )
    solve();
    return 0;
}
 
/*样例区
 
 
*/
 
//------------------------------------------------------------

C：n个数，问删除多少种数，可以使序列递增

从前往后遍历，如果当前数出现两次以上，并且不相邻，就要删掉所有数的种数

如果当前数比后面的数大，也要删掉所有数的种数

取一个删去种数的最大值就好了

前k 个数有多少种数怎么算？将所有数放到set里会自动去重，算set的大小就可以了

//-------------------------代码----------------------------
 
//#define int ll
const int N = 1e5+10;
int n,m;
int a[N];
void solve()
{
    cin>>n;
    int mx = 0;
    map<int,int> mp; 
    set<int> q;
    fo(i,1,n) {
        cin>>a[i];
        mp[a[i]] ++ ;
        if(i >= 2 && mp[a[i]] >= 2 && a[i-1] != a[i]) mx = max(int(q.size()),mx);
        if(i >= 2 && a[i] < a[i-1]) mx = max((int)q.size(),mx);
        q.insert(a[i]);
    }
    cout<<mx<<endl;
    
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}
 
/*样例区
 
 
*/
 
//------------------------------------------------------------

E1：(easy版） lcm的性质：必定是最大的数的倍数，数据范围一眼做法 

题意：多组询问。lcm(i,j,k) >= i + j + k，问l 到 r 之间有多少满足条件的。l ,r <= 2e5。t <= 10

有一个性质：l 和 r 都是 1e5级别的，搜索三元组爆搜 要 n ^3,稍微优化：n^2 很难到 nlogn或者 n根号n。这里一眼可以确定要筛出某些数，在筛出来的数里搜了。

[l,r] 区间内三元组的数目是 组合数C_n³，就等于 len * (len - 1) * (len - 2) / 6

对于lcm(i,j,k) >= i + j + k，并不好直接判断，将大于等于号改成小于号：lcm(i,j,k) < i + j + k 。然后从最共的三元组数量找出满足条件的三元组数量即可

假设i，j，k中最大的数是 k ，那 lcm = 2 * k 或者 k 才满足条件 ：比i + j + k 小。如果是 3k 的话 肯定要比 i + j + k 大

如果 lcm == k 。那肯定满足条件，三元组总数 - 1

如果 lcm == 2 * k 。那肯定是 k % i != 0 && k % j != 0。如果 满足 2 * k < i + j + k 也满足条件，三元组总数 - 1

只要枚举 所有 的2 * k ，并且找出它的因子 i ，j ，剪枝即可

ps：

1.lcm == 2 * k，如果 第二大的数 比 最大的数 的一半还小，那肯定不满足条件，可以减少对第一个数的搜索

2.找出每个数的因子是 o(n根号n)

//-------------------------代码----------------------------

//#define int ll
const int N = 4e5+10;
int n,m;
V<int> g[N];
void solve()
{
//    cin>>n>>m;
    int l,r;cin>>l>>r;
    int len = r - l + 1;;
    ll res = 1ll * len * (len - 1) * (len - 2) / 6;
    for(int i = l + 2;i<=r;i++) {
        V<int> v;
        for(auto x:g[2*i]) {
            if(x < l) continue;
            if(i % x && x * 2 <= i) continue;//如果不是 i 的因子，说明它是 2 * i 的因子 ，要满足 lcm(i,j,k) < i + j + k 那它的大小至少要是 i 的一半， 
            if(x >= i) break;
            for(auto y : g[2*i]) {
                if(y < l) continue;
                if(y >= x) break;
                if(i % x || i % y ) res -= 2 * i < x + y + i;//如果lcm = 2 * k，就要判断 
                else res -- ; //lcm = k，直接减 
            }
        }
    }
}
void main_init() {
    fo(i,1,200000) {
        for(int j = i;j<=400000;j+=i) {
            g[j].pb(i);
        }
    }
}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

E2：hard版（t <= 1e5）树状数组+离线算法

我们把所有的循环 l 和 r 以及它是第几个询问，装进结构体

枚举[1,i] 以 r 为关键词，所有的 l 都是已经被计算过的

当枚举到当前询问的 r 的时候，l 就是一个特征值，不同的l 答案不一样

所以我们把所有的 i j k 的权值放入到最小的数 i 里，

ans[id] -= sum - query( l - 1)

//-------------------------代码----------------------------

#define int ll
const int N = 4e5+10;
int n,m;

V<int> v[N];
V<pii> q[N];
int tr[N];
void add(int x,int v) {
    for(int i = x;i<N;i+=lowbit(i)) tr[i] += v;
}
int ans[N];
ll qq(int x) {
    ll res = 0;for(int i = x;i;i-=lowbit(i)) res += tr[i];return res;
}

void solve()
{
//    cin>>n>>m;
    int t;cin>>t;fo(i,1,t) {
        int l,r;cin>>l>>r;
        q[r].pb({l,i});int len = r - l + 1;
        ans[i] = len * (len - 1) * (len - 2) / 6 ;
    }
    
    int sum = 0;
    for(int i = 1;i<=200000;i++) {
        for(auto x:v[i * 2]) {
            if(x >= i) break;
            if((i % x) && x * 2 <= i) continue;
            for(int y:v[i * 2]) {
                if(y >= x) break;
                if(i % x || i % y) {
                    if(x + y + i > 2 * i) {
                        sum ++ ;
                        add(y,1);
                    }
                } else {
                    sum ++ ;add(y,1);
                }
            }
        }
        for(auto it : q[i]) {
            int l = it.first,id = it.second;
            ans[id] -= sum - qq(l-1);
        }
    }
    fo(i,1,t) {
        cout<<ans[i]<<'\n';
    }
}
void main_init() {
    for(int i = 1;i<=2e5;i++) {
        for(int j = i * 2;j<=4e5;j+= i) {
            v[j].pb(i);
        }
    }
}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

这篇关于Codeforces Round #813 (Div. 2) A - E2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！