首页 > 其他分享 >Codeforces Round 988 (Div. 3)

Codeforces Round 988 (Div. 3)

时间：2024-11-18 11:19:43浏览次数：1  
标签：988 return int void Codeforces long solve Div include

Codeforces Round 988 (Div. 3) 总结

A

没啥好说的，用桶存出现次数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=25;
int n;
int a[N],c[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],c[a[i]]++;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans+=c[i]/2;
        c[i]=0;
    }
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

依据题意有 \(n \times m+2=k\)，则 \(n \times m=k-2\)，将 \(k-2\) 分解，检验是否出现在 \(a\) 中即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int k;
int a[N],c[N];
void solve()
{
    cin>>k;
    for(int i=1;i<=k;i++) cin>>a[i],c[i]=0;
    for(int i=1;i<=k;i++) c[a[i]]++;
    int x=k-2;
    for(int i=1;1ll*i*i<=x;i++)
        if(x%i==0&&c[i]&&c[x/i]) 
        {
            cout<<i<<' '<<x/i<<'\n';
            return ;
        }
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C

首先容易想到，奇数相加可行，偶数相加可行，而最小的奇合数为 \(9=4+5\)，所以 \(n \ge 5\) 时有解，\(n=5\) 时为 \(1,3,5,4,2\)。\(n>5\) 只需要将偶数添加到队尾，奇数添加到队头即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N];
void solve()
{
    cin>>n;
    if(n<=4) 
    {
        cout<<-1<<'\n';
        return ;
    }
    int cnt=0;
    for(int i=7;i<=n;i+=2) cout<<i<<' ';
    cout<<"1 3 5 4 2 ";
    for(int i=6;i<=n;i+=2) cout<<i<<' ';
    cout<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

考虑贪心，首先能不捡就不捡，遇到障碍跳不过去时，才返回去捡加速器，要求捡的次数最小，所以回去捡的加速器要先捡大的。

因此枚举障碍 \(i\)，要跳过去必须满足 \(k \ge r_i-l_i+2\)，用大根堆存加速器的信息，如果全部取出来加到 \(k\) 上仍不满足，说明无法完成。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,m,L;
int l[N],r[N];
int x[N],v[N];
priority_queue<int> q;
void solve()
{
    cin>>n>>m>>L;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    for(int i=1;i<=m;i++) cin>>x[i]>>v[i];
    int k=1,id=1,ans=0;
    for(int i=1;i<=n;i++)
    {
        int len=r[i]-l[i]+2;
        while(x[id]<l[i]&&id<=m) q.push(v[id]),id++;
        while(q.size()&&k<len) k+=q.top(),ans++,q.pop();
        if(k<len) 
        {
            cout<<-1<<'\n';
            return ;
        }
    }
    while(q.size()) q.pop();
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

E

交互题，记得用 endl 或者 cout.flush() 清空缓存区。

询问次数最大为 \(n\)，设 \(k_i=f(1,i)\) \((2 \le i \le n)\)。
先考虑无解的情况，显然是 \(k_n=0\) 时不能确定答案。
然后遍历 \(k\)，考虑如果 \(s_i=0\)，则一定有 \(k_i=k_{i-1}\)。所以当 \(k_i>k{i-1}\) 时，\(s_i=1\)。但这样有一个问题，如果 \(s\) 为 \(\mathtt{111\dots000\dots1\dots}\)，那么开头的 \(1\) 也都不会有贡献。所以找到第一个不等于 \(0\) 的 \(k_i\)，说明 \([1,i-1]\) 中有 \(k_i\) 个 \(0\)，所以开头就有 \(i-1-k_i\) 个 \(1\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e4+5;
int n;
int s[N];
int query(int l,int r)
{
    int x;
    cout<<"? "<<l<<" "<<r<<' '<<endl;
    cin>>x;
    return x;
}
int k[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) s[i]=0;
    for(int i=2;i<=n;i++) k[i]=query(1,i);
    if(k[n]==0)
    {
        cout<<"! IMPOSSIBLE "<<endl;
        return ;
    }
    for(int i=2;i<=n;i++) if(k[i]>k[i-1]) s[i]=1;
    for(int i=2;i<=n;i++)
        if(s[i])
        {
            for(int j=1;j<=i-1-k[i];j++) s[j]=1;
            break;
        }
    cout<<"! "; 
    for(int i=1;i<=n;i++) cout<<s[i];
    cout<<' '<<endl;
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

F

二分答案，设攻击了 \(k\) 次。

因为只能是在同一个位置 \(p\) 攻击，所以第 \(i\) 个敌人每次攻击需要受到至少 \(t_i=\lceil\frac{h_i}{k}\rceil\) 的伤害，因此 \(p\) 的范围就是 \([x_i-(m-t[i]),x_i+(m-t[i])]\)，若 \(m < t_i\) 则一定无法击败第 \(i\) 个敌人。

这样就转化成了 \(n\) 个区间的覆盖问题，问是否有一个点被覆盖了至少 \(k\) 次。

离散化加差分轻松搞定，复杂度为 \(O(n\log(n)\log(V))\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5,inf=1e9;
int n,m,k;
int h[N],x[N],t[N];
int tot;
int b[N],c[N];
bool check(int k)
{
    tot=0;
    for(int i=1;i<=n;i++) 
    {
        t[i]=(h[i]+k-1)/k;
        if(t[i]<=m) 
        {
            c[++tot]=x[i]-(m-t[i]);
            c[++tot]=x[i]+(m-t[i])+1;
        }
    }
    sort(c+1,c+tot+1);
    tot=unique(c+1,c+tot+1)-c-1;
    for(int i=1;i<=tot;i++) b[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]<=m)
        {
            int l=lower_bound(c+1,c+tot+1,x[i]-(m-t[i]))-c;
            int r=lower_bound(c+1,c+tot+1,x[i]+(m-t[i])+1)-c;
            b[l]++,b[r]--;
        }
    }
    for(int i=1;i<=tot;i++) b[i]+=b[i-1];
    for(int i=1;i<=tot;i++) if(b[i]>=k) return 1;
    return 0;
}
void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) cin>>x[i];
    int l=1,r=inf,mid,ans=-1;    
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    cout<<ans<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

G

dp 加容斥。

逐步推导，设 \(f_i\) 为从 \(1\) 到 \(i\) 的方案数，按题意模拟就有：

\[ f_1=1 \]

\[ f_i=f_i+f_j (1 \le j < i,\gcd(a_i,a_j)\neq 1) \]

这样做是 \(O(n^2)\) 的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N];
int f[N];
int gcd(int x,int y)
{
    return y ? gcd(y,x%y) : x;
}
vector<int> g[M],h[N];
set<int> v;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    f[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i-1;j++) 
            if(gcd(a[i],a[j])!=1) 
				f[i]=(f[i]+f[j])%mod;
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

考虑优化，不难发现我们其实并不在意具体的 \(\gcd(a_i,a_j)\) 是啥，只要求不为 \(1\)，将 \(a_i\) 质因数分解，\(a_i\) 与 \(a_j\) 是通过相同的质因数产生联系的。每次分解 \(a_i\)，找前面的位置进行转移。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353,M=1e6+5;
int n;
int a[N],f[N];
vector<int> g[M],h[N];
set<int> v;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int x=a[1];
    for(int j=2;1ll*j*j<=n;j++)
    {
        if(x%j==0) 
        {
            g[j].push_back(1);
            while(x%j==0) x/=j;
        }
    }
    if(x>1) g[x].push_back(1);
    f[1]=1;
    for(int i=2;i<=n;i++)
    {
        int x=a[i];
        for(int j=2;1ll*j*j<=x;j++)
        {
            if(x%j==0) 
            {
                for(int k:g[j]) 
                {
                    if(v.count(k)==0) f[i]=(f[i]+f[k])%mod;
                    v.insert(k);
                }
                g[j].push_back(i);
                while(x%j==0) x/=j;
            }
        }
        if(x>1) 
        {
            for(int k:g[x]) 
            {
                if(v.count(k)==0) f[i]=(f[i]+f[k])%mod;
                v.insert(k);
            }
            g[x].push_back(i);
        }
        v.clear();
    }
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

但这样还是过不了。因为这最坏还是 \(O(n^2)\) 的，随便就能卡掉。

然后不妨按质因数划分集合，设 \(b_x\) 为质因数为 \(x\) 的数产生的贡献。这样每次 \(a_i\) 分解出 \(x\) \(f_i\) 只需要加上 \(b_x\) 就行了。但是仅仅如此的话连样例都过不了。

考虑这样一组数据 \(\mathtt{6,6}\)。\(i=1\)，\(f_1=1\)，更新 \(b\)，有 \(b_2=1,b_3=1\)。\(i=2\)，\(f_2=b_2+b_3=2\)，但实际上是 \(f_2=1\)。

这里就是 \(2\) 和 \(3\) 重复算了，因为这里显然还要减去 \(6\) 出现的次数 \(1\)。

如何避免这样情况呢？用容斥原理。

将 \(a_i\) 质因数分解后，每个质因数只取一次相乘得到 \(y\)，取 \(y\) 的所有约数放在动态数组 g[a[i]] 中。比如 g[12]={2,3,6}，g[6]={2,3,6}，这时候可以计算上面例子，\(i=1\)，有 \(b_2=b_3=b_6=1\)，\(i=2\)，有 \(f_2=b_2+b_3-b_6=1\)。

也就是说在每次更新 \(f_i\) 时对于 g[a[i]] 中的每个元素 \(x\)，如果 \(x\) 的质因数个数为奇数，说明要加上贡献，否则减去贡献。同样 \(b_x\) 的更新也需要取 g[a[i]] 中的每个元素 \(x\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=2e5+5,M=1e6+5,mod=998244353;
int n;
int a[N],b[M],f[N];
vector<int> g[M],h[M];
void divide1(int x,int id)
{
    for(int i=2;1ll*i*i<=x;i++)
    {
        if(x%i==0) 
        {
            h[id].push_back(i);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) h[id].push_back(x);
}
void divide2(int x,int id)
{
    x=1;
    for(auto t:h[id]) x*=t;
    for(int i=2;1ll*i*i<=x;i++)
    {
        if(x%i==0)
        {
            g[id].push_back(i);
            if(x!=i) g[id].push_back(x/i);
        }
    }
    if(x>1) g[id].push_back(x);
}
void solve()
{
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++) cin>>a[i],mx=max(mx,a[i]);
    for(int i=2;i<=mx;i++) divide1(i,i),divide2(i,i);
    f[1]=1;
    for(int i=1;i<=n;i++)
    {
        for(auto x:g[a[i]])
        {
            if(h[x].size()&1) f[i]=(f[i]+b[x])%mod;
            else f[i]=(f[i]+mod-b[x])%mod;
        }
        for(auto x:g[a[i]]) b[x]=(b[x]+f[i])%mod;
    }
    cout<<f[n]<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

标签：988,return,int,void,Codeforces,long,solve,Div,include
From： https://www.cnblogs.com/zhouruoheng/p/18551781

相关文章

  • Solution - Codeforces 1957E Carousel of Combinations
    首先这个\(C(i,j)\bmodj\)的形式就非常怪，于是首先肯定要先研究一下这个值。先考虑如何求\(C(i,j)\)。可以考虑先选出要用的\(j\)个数，再乘上其排列成环的方案数，那么有\(C(i,j)=\binom{i}{j}\times(j-1)!\)。那么就是来考虑\(\binom{i}{j}\times(j-1)!\bmod......
  • 【星航计划】2024.11 Div. 3 题解
    2024--星航计划--十一月份--基础算法A.分段每一段连续的\(1\)之间是独立的，我们只需要关心一段连续的1的结果。可以证明对于一段连续的\(1\)，最优策略是将其划分成多个单独的\(1\)以及可能余下的连续两个\(1\)。对于\(k\)个连续的\(1\)，如果\(k\)是奇数，......
  • Codeforces Round 987 (Div. 2) - 比赛总结
    Preface我是若只。A.PenchickandModernMonument先吃三发罚时。最优策略应当是把所有数都调成众数，然而我一开始就忙着往后面做，胡乱猜了个结论就WA了，又猜了一个又WA了，再猜了一个再WA了。点击查看代码constintN=105;intn,a[N];intmain(){ intT;read(T);......
  • Codeforces Round 986 (Div. 2)
    CodeforcesRound986(Div.2)总结A按题意模拟即可，因为\(n,a,b\)很小，可以多循环几遍来判断。只循环十遍的吃罚时qwq。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<queue&......
  • Refact.ai Match 1 (Codeforces Round 985)
    Refact.aiMatch1(CodeforcesRound985)总结A集合中的元素为\(l\lex\ler\)，有\(k\)个\(x\)的倍数在其中才可删，可以求出最大可删的元素，直接计算。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#inclu......
  • 第九章DIV+CSS布局
    9.1DIV+CSS概述9.1.1认识DIVdiv标签在Web标准网页中属于块级元素9.1.2DIV的宽高设置9.1.2.1宽高属性9.1.2.2div标签内直接设置宽高9.1.2.3div使用选择器设置宽高<!DOCTYPEhtml><html> <head> <metacharset="utf-8"/> <title></title> <styletype......
  • Codeforces Round 987 (Div. 2)
    好不容易的一次CF阳间赛，这次题目普遍较长。A-PenchickandModernMonument题目大意将一个非递增的序列通过操作某些数（可增大可减小），最终使得序列变成一个非递减的序列，求出最少要操作多少次？解题思路这个题也是想了不断时间，而且还提交错误一次，原因就是调试的代码没......
  • Codeforces Round 987 (Div. 2)
    训练记录CodeforcesRound987(Div.2)4/6前四题都是简单思维题A.PenchickandModernMonument这个题目最贪心的做法是找到出现最多的数，保留种数字不变，其他按照题目要求改大小就行//Problem:A.PenchickandModernMonument//Contest:Codeforces-CodeforcesRound......
  • CF987 Div2 F 题解
    阶段1考虑我们每次随机删除两个然后询问，若中位数为\(\frac{n}{2},\frac{n}{2}+1\)称被删除的两个为基准数，用\(v_1,v_2\)代表。每次询问得到解的概率约为\(\frac{1}{2}\)。发现基准数一定一个\(<\frac{n}{2}\)一个\(>\frac{n}{2}+1\)，且对于一次四个数的询问\(x......
  • C. Penchick and BBQ Buns （python解）-codeforces
    C.PenchickandBBQBuns（python解）-codeforces原题链接：点击传送问题分析：我们需要为给定数量的BBQ包子分配填料，满足以下条件：每种填料必须至少使用两次，或者不使用。任何两个相同填料的包子之间的距离必须是一个完全平方数。思路:为了满足条件，我们可以利用完全平方数的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99