首页 > 其他分享 >Codeforces Round #956 (Div. 2)题解

Codeforces Round #956 (Div. 2)题解

时间:2024-07-11 12:58:23浏览次数:11  
标签:typedef int 题解 long 956 solve tp Div define

A. Array Divisibility

需要让满足$ k\mid j $ 的所有\(a_j\)的和整除k,只需要让每个\(a_j\)整除k就可以了,可以让\(a_j=j\)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5+5,M=20,mod=998244353,P=131;
 
 
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cout<<i<<" ";
    cout<<endl;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Corner Twist

可以知道,大矩形的操作可以由小矩形合成,两次副对角+1的操作可以合成为主对角+1的操作

于是使用最小的,副对角为1的矩形操作,从上到下,从左到右,最后判断相等就可以了

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int N = 505,M=20,mod=998244353,P=131;
int mp1[N][N];
int mp2[N][N];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&mp1[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&mp2[i][j]);
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            while(mp1[i][j]!=mp2[i][j]){
                mp1[i][j]=(mp1[i][j]+1)%3;
                mp1[i+1][j]=(mp1[i+1][j]+2)%3;
                mp1[i+1][j+1]=(mp1[i+1][j+1]+1)%3;
                mp1[i][j+1]=(mp1[i][j+1]+2)%3;
            }
        }
    }
    int flag=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp1[i][j]!=mp2[i][j])flag=0;
        }
    }
    if(flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
//    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. Have Your Cake and Eat It Too

双指针枚举中间的一段,然后前缀和判断左右两边能不能用就行了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int N = 505,M=20,mod=998244353,P=131;

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+2),b(n+2),c(n+2);
    vector<int> qza(n+2),qzb(n+2),qzc(n+2);
    vector<int> hza(n+2),hzb(n+2),hzc(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
    int sum=0;
    for(int i=1;i<=n;i++)sum+=a[i];
    int tp=(sum+2)/3;
    for(int i=1;i<=n;i++){
        qza[i]=qza[i-1]+a[i];
        qzb[i]=qzb[i-1]+b[i];
        qzc[i]=qzc[i-1]+c[i];
    }
    for(int i=n;i>=1;i--){
        hza[i]=hza[i+1]+a[i];
        hzb[i]=hzb[i+1]+b[i];
        hzc[i]=hzc[i+1]+c[i];
    }


    int l=1,s=0;
    for(int r=1;r<=n;r++){
        s+=a[r];
        while(s-a[l]>=tp)s-=a[l++];
        if(qzb[l-1]>=tp&&hzc[r+1]>=tp){
            cout<<l<<" "<<r<<" "<<1<<" "<<l-1<<" "<<r+1<<" "<<n<<endl;
            return ;
        }
        if(qzc[l-1]>=tp&&hzb[r+1]>=tp){
            cout<<l<<" "<<r<<" "<<r+1<<" "<<n<<" "<<1<<" "<<l-1<<endl;
            return ;
        }
    }

    l=1,s=0;
    for(int r=1;r<=n;r++){
        s+=b[r];
        while(s-b[l]>=tp)s-=b[l++];
        if(qza[l-1]>=tp&&hzc[r+1]>=tp){
            cout<<1<<" "<<l-1<<" "<<l<<" "<<r<<" "<<r+1<<" "<<n<<endl;
            return ;
        }
        if(qzc[l-1]>=tp&&hza[r+1]>=tp){
            cout<<r+1<<" "<<n<<" "<<l<<" "<<r<<" "<<1<<" "<<l-1<<endl;
            return ;
        }
    }

    l=1,s=0;
    for(int r=1;r<=n;r++){
        s+=c[r];
        while(s-c[l]>=tp)s-=c[l++];
        if(qza[l-1]>=tp&&hzb[r+1]>=tp){
            cout<<1<<" "<<l-1<<" "<<r+1<<" "<<n<<" "<<l<<" "<<r<<endl;
            return ;
        }
        if(qzb[l-1]>=tp&&hza[r+1]>=tp){
            cout<<r+1<<" "<<n<<" "<<1<<" "<<l-1<<" "<<l<<" "<<r<<endl;
            return ;
        }
    }

    cout<<-1<<endl;
    return ;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

D. Swap Dilemma

可以知道,更大的操作可以由更小的操作合成,所以只需要交换两个相邻数就可以了,那么我们不妨把两个数组都交换成升序,如果这样做,因为其中一个交换时另外一个必须同时交换,并且同一对位置交换两次就抵消,所以就是看两者的交换次数是不是同奇偶,交换次数计算逆序对就行了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+5,M=20,mod=998244353,P=131;
int tmp[N];
int merge_sort(vector<int> &a,int l,int r){
    if(l>=r)return 0;
    int mid=l+r>>1,res=0;
    res+=merge_sort(a,l,mid);
    res+=merge_sort(a,mid+1,r);
    int i=l,j=mid+1,cnt=l;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j])tmp[cnt++]=a[i++];
        else {
            res+=mid-i+1;
            tmp[cnt++]=a[j++];
        }
    }
    while(i<=mid)tmp[cnt++]=a[i++];
    while(j<=r)tmp[cnt++]=a[j++];
    for(i=l;i<=r;i++)a[i]=tmp[i];
    return res;
}
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int ra=merge_sort(a,1,n);
    int rb=merge_sort(b,1,n);
    int flag=1;
    for(int i=1;i<=n;i++)
        if(a[i]!=b[i])flag=0;
    if(abs(ra-rb)%2==0&&flag)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

E. I Love Balls

因为挑选到特殊球可以继续往下挑选,一直到挑选到普通球为止,那么我们不妨先计算普通球的贡献,再以插空的方式计算特殊球的贡献。可以知道每个普通球对先手者的贡献是\(\frac{\lceil\frac{n-k}{2}\rceil}{n-k}\cdot a[i]\), 每个普通球对后手者的贡献是\(\frac{\lfloor\frac{n-k}{2}\rfloor}{n-k}\cdot a[i]\),然后再插空计算贡献,有\(n-k+1\)个空,所以每个特殊球对先手者的贡献是\(\frac{\lceil\frac{n-k+1}{2}\rceil}{n-k+1}\cdot a[i]\),每个特殊球对后手者的贡献是\(\frac{\lceil\frac{n-k+1}{2}\rceil}{n-k+1}\cdot a[i]\) 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5+5,M=20,mod=1e9+7,P=131;
int qmi(int a,int k){
    int res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans1=0,ans2=0;
    for(int i=k+1;i<=n;i++){
        ans1=(ans1+(n-k+1)/2*a[i]%mod*qmi(n-k,mod-2)%mod)%mod;
        ans2=(ans2+(n-k)/2*a[i]%mod*qmi(n-k,mod-2)%mod)%mod;
    }
    for(int i=1;i<=k;i++){
        ans1=(ans1+(n-k+2)/2*a[i]%mod*qmi(n-k+1,mod-2)%mod)%mod;
        ans2=(ans2+(n-k+1)/2*a[i]%mod*qmi(n-k+1,mod-2)%mod)%mod;
    }
    cout<<ans1<<" "<<ans2<<endl;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

标签:typedef,int,题解,long,956,solve,tp,Div,define
From: https://www.cnblogs.com/lxllxs/p/18295926

相关文章

  • CF1051F题解
    TheShortestStatement算法:树链剖分,最小生成树,最短路。先讲一下题意:有一个\(n\)点\(m\)边的无向连通图,\(q\)次询问,每次询问\(a\)到\(b\)的最短路长度。数据范围\(1\len,m\le10^5,m-n\le20\)。首先发现给了一个很奇怪的限制:\(m-n\le20\),考虑他有什么用。我们在......
  • 【完结】LeetCode 热题 HOT 100分类+题解+代码详尽指南
    目录LeetCode热题100前言LeetcodeTop100题目和答案-哈希LeetcodeTop100题目和答案-双指针篇LeetcodeTop100题目和答案-滑动窗口篇LeetcodeTop100题目和答案-子串篇LeetcodeTop100题目和答案-普通数组篇LeetcodeTop100题目和答案-矩阵篇LeetcodeTop100题目和......
  • CentOS 乱码问题解决
    首先要区别3个概:编码集、字符集、字体是完全不同的东西,我们要解决的是字符集问题。当一个系统初始化完毕后,会生成一个/usr/lib/locale/locale-archive文件,这个是字符集二进制文件,是系统不同语言运行的核心,通过命令locale-a可以看到当前文件中支持的语言locale命令可以......
  • [题解] [ABC221H] Count Multiset - DP
    [ABC221H]CountMultiset题面翻译输入两个正整数\(N,M\),并存在一个集合,问你一个长度为\(k\)的合法集合存在多少个?你需要回答\(k\)的值为\(1\)到\(N\)的每种情况。一个合法的集合定义指长度为\(k\),元素和为\(N\),每一个数字在集合中出现的次数都小于等于\(M\)的集......
  • CF506D题解
    Mr.Kitayuta'sColorfulGraph算法:根号分治。题目大意先说一下:给一个\(n\)点\(m\)边的无向图,边有颜色。\(q\)组询问,每次给出\(u,v\),求有多少种颜色\(c\),使得存在一条\(u\)到\(v\)的路径,这个路径中每条边的颜色都为\(c\)。先考虑一个朴素的暴力,暴力对每个颜色加边,......
  • UVA12683 Odd and Even Zeroes 题解
    题目简述定义\(\operatorname{count}(num)\)表示\(num\)末尾\(0\)的个数。给出\(n\)(\(n\leq10^{18}\)),求\(\sum\limits_{i=0}^{n}[2\mid\operatorname{count}(i!)]\)。题目分析对于一个\(i\),以下记成\(n\)。\(n!\)末尾\(0\)的个数取决于\(1\simn\)......
  • [ARC080F] Prime Flip 题解
    Description有无限枚硬币,其中有\(n\)枚硬币\(x_{1\ldotsn}\)。初始时正面朝上,其余均为背面朝上,每次可以选择一段区间\([l,r]\),将区间内所有硬币翻转,其中\(r-l+1\)为一个奇质数。问最少多少次能将所有硬币全部翻为背面朝上。\(1\leqn\leq100,1\leqx_1\leqx_2\leq\ld......
  • CF369D Valera and Fools 题解
    传送门LuoguCodeforces题意简述有\(n\)个傻子智者站成一排,每人手中有\(k\)发子弹,每次每人会向除自己外编号最小的人开枪,第\(i\)个人开枪的命中率为\(p_i\%\),剩余最多一人时结束,问有多少种可能的局面。解法说明从题目要求中可以发现,每次一定是编号最小的人向编号第二......
  • 优化爬虫体验:揭秘IP重复率过高问题解决方案
    在当今信息爆炸的时代,网络中蕴藏着大量宝贵的数据,而爬虫技术成为我们提取这些数据的重要工具。然而,随着爬虫的广泛使用,IP重复率高的问题也随之而来。本篇博文将揭秘解决这一问题的关键方法——使用IP代理。一、IP高重复问题带来的挑战&nbsp;被封禁风险:当一个IP在短时间内频......
  • 优化爬虫体验:揭秘IP重复率过高问题解决方案
    在当今信息爆炸的时代,网络中蕴藏着大量宝贵的数据,而爬虫技术成为我们提取这些数据的重要工具。然而,随着爬虫的广泛使用,IP重复率高的问题也随之而来。本篇博文将揭秘解决这一问题的关键方法——使用IP代理。一、IP高重复问题带来的挑战&nbsp;被封禁风险:当一个IP在短时间内频......