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

Codeforces Round 956 (Div. 2)

时间:2024-10-01 19:24:20浏览次数:7  
标签:temp int 矩阵 Codeforces 956 second Div al first

无法评价,不知道是我傻逼还是题傻逼。

A. Array Divisibility

题意

让你构造一个长度为 \(n\) 的序列,满足对于每一个 \(i\) \((i\in [1,n])\) ,让 \(a_j\) 之和为 \(i\) 的倍数, \(j\) 能被 \(i\) 整除。换句话说,让你构造一个长度为 \(n\) 的序列,满足 \(\sum_{j|i} a_j\) 能被 \(i\) 整除。

思路

这题很容易想到直接输出 \(1...n\) 即可。但是我被骗了。我当时想的是让每一个下标是 \(i\) 的倍数的位置都乘上 \(i\) ,时间复杂度 \(O(nlogn)\) 。而且还 \(\text{WA}\) 了一发,因为还要保证 \(a_i\leq 10^5\) 。赛后才想到 \(j\) 都保证是 \(i\) 的倍数了,那 \(\sum_{j|i}j\) 一定是 \(j\) 的倍数。真的唐完了。。。

代码

看看我的抽象代码

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1,1);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
        {
            if(a[j]%i==0) continue;
            a[j]*=i;
        }
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    cout<<endl;
}

B. Corner Twist

题意

给你一个初始矩阵和目标矩阵,每次操作你可以选择一个子矩阵,然后选择一个子矩阵的对角让这两个位置都加上 \(1\) ,剩下两个不选的位置都加上 \(2\) ,然后每个位置再对 \(3\) 取模。问你能不能从初始矩阵操作完变成目标矩阵。

思路

这题一开始我想的用目标矩阵对应的位置减去初始矩阵对应的位置然后获得了一个新的矩阵,这样就转化为把这个新的矩阵通过上面的操作让里面的数全部变成 \(0\) 。然后我以为这又是什么神秘的找规律结论题,然后我就对着样例开始找规律。一开始我以为只要我新的矩阵是一个中心对称图形就行,然后写了半天发现样例过不了,然后又以为只要他是一个斜对称图形就行,结果发现并不是。就这样我推了半个小时的结论。

最后发现,我只要枚举每个位置,选择的子矩阵大小为 \(2\times2\) 的,让这个位置变成 \(0\) 就行,不用管其他位置怎么样,如果操作到最后这个新的矩阵全部变成了 \(0\) 那么就是可以的,否则就是不行。

代码

void solve()
{
    int n,m;
    cin>>n>>m;
    int sum1=0,sum2=0;
    vector<string> a(n+1),b(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        for(int j=0;j<a[i].size();j++) sum1+=(a[i][j]-'0');
    }
    vector mp(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        for(int j=0;j<b[i].size();j++) sum2+=(b[i][j]-'0'),mp[i][j+1]=(b[i][j]-a[i][j]+3)%3;
    }
    auto change=[&](int i,int j,int op)
    {   
        if(op==1)
        {
            mp[i][j]=0;
            mp[i][j+1]++;
            mp[i][j+1]%=3;
            mp[i+1][j]++;
            mp[i+1][j]%=3;
            mp[i+1][j+1]+=2;
            mp[i+1][j+1]%=3;
        }
        if(op==2)
        {
            mp[i][j]=0;
            mp[i][j+1]+=2;
            mp[i][j+1]%=3;
            mp[i+1][j]+=2;
            mp[i+1][j]%=3;
            mp[i+1][j+1]++;
            mp[i+1][j+1]%=3;
        }
    };
    int flag=0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if(mp[i][j]==1) change(i,j,1);
            else if(mp[i][j]==2)change(i,j,2);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) if(mp[i][j])flag=1;
    }
    if(flag) cout<<"NO\n";
    else cout<<"YES\n"; 
}

C. Have Your Cake and Eat It Too

题意

三个人在分蛋糕,可以分成 \(n\) 块蛋糕,但是每个人对每块蛋糕的美味值不同。 \(\text{Alice}\) 认为第 \(i\) 块蛋糕的美味值为 \(a_i\), \(\text{Bob}\) 认为第 \(i\) 块蛋糕的美味值为 \(b_i\), \(\text{Charlie}\) 认为第 \(i\) 块蛋糕的美味值为 \(c_i\) 。现在让你给每个人分一块连续的蛋糕,还要保证这三个区间不相交,使得每个人获得的蛋糕美味度不低于 \(x\) 。请问是否存在一种合法的分法。

思路

贪心。从前往后遍历,如果这段区间的总和大于了 \(x\) 那就把下一段区间的蛋糕分给另一个人,直到全部分完为止。但是,分了三段区间,还要枚举每个人吃哪一段区间,所以还得分情况讨论六次。你知道我一个一个改有多麻烦吗(出题人真的是私募了)。如果有更好的写法欢迎留言。

代码

int tot;
pair<int,int> check(vector<int> &x,vector<int> &y,vector<int> &z)
{
    int n=x.size()-1;
    int l,r,num=(tot-1)/3+1,flag=0;
    for(l=1;l<=n;l++) if(x[l]>=num) {flag++;break;}
    for(r=l+1;r<=n;r++) if(y[r]-y[l]>=num) {flag++;break;}
    if(z[n]-z[r]>=num) flag++;
    if(flag==3) return {l,r};
    else return {0ll,0ll};
}
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1),c(n+1);
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1];
    for(int i=1;i<=n;i++) cin>>c[i],c[i]+=c[i-1];
    tot=a[n]; 
    int al=0,ar=0,bl=0,br=0,cl=0,cr=0;
    auto temp=check(a,b,c);
    if(temp.first) al=1,ar=temp.first,bl=temp.first+1,br=temp.second,cl=temp.second+1,cr=n;
    temp=check(a,c,b);
    if(temp.first) al=1,ar=temp.first,cl=temp.first+1,cr=temp.second,bl=temp.second+1,br=n;
    temp=check(b,a,c);
    if(temp.first) bl=1,br=temp.first,al=temp.first+1,ar=temp.second,cl=temp.second+1,cr=n;
    temp=check(b,c,a);
    if(temp.first) bl=1,br=temp.first,cl=temp.first+1,cr=temp.second,al=temp.second+1,ar=n;
    temp=check(c,a,b);
    if(temp.first) cl=1,cr=temp.first,al=temp.first+1,ar=temp.second,bl=temp.second+1,br=n;
    temp=check(c,b,a);
    if(temp.first) cl=1,cr=temp.first,bl=temp.first+1,br=temp.second,al=temp.second+1,ar=n;
    if(al) cout<<al<<' '<<ar<<' '<<bl<<' '<<br<<' '<<cl<<' '<<cr<<endl;
    else cout<<-1<<endl;
}

D. Swap Dilemma

题意

给你两个数组 \(a,b\) ,你每次可以选择一个 \(l,r,p,q\) ,满足 \(r-l+1=q-p+1\)。然后交换 \(a_l,a_r\) , 和 \(a_p,a_q\) 。 问你经过若干次操作之后能不能使得两个序列相等。

思路

这个题我想了一个小时都没想出来怎么做。因为我不知道要满足 \(r-l+1=q-p+1\) 这个条件该怎么交换。
但是首先要保证两个序列里的元素要一模一样才行。
之后我想到了 \(i\) 和 \(a_i,b_i\) 连边构成两张图,然后考虑环个数的奇偶性,如果两个图环的奇偶性相同那么就是 YES。证明如下:

  • 如果交换的两个点在同一个环上,那么这个环会分裂成两个环。
  • 如果交换的点不在同一个环上,就等价于把这两个环合并成一个环。

所以只要经行交换操作,就会换改变环的个数。但是这个约束条件还是给我卡的死死的,到结束还是不知道怎么处理选取等距离的点。
看到别的题解说只需要选择两个相同的数交换即可,这使我恍然大悟,就像冒泡排序一样,\(a\) 序列中如果两个数想交换位置,只需要一直选择相邻的两个数,然后 \(b\) 序列里面任意选两个相邻的数左右横跳。这样就能把题目中的约束条件给消除了。


老老老老老师,我还有一种方法!

因为 \(a_i,b_i\) 中每个数都不相同,所以只要我们交换两个相邻的位置,那么这个序列里面逆序对的个数一定会加 \(1\) 或者减 \(1\) 。假设 \(b\) 序列反复横跳, \(a\) 序列可以任意交换两个位置的数使得 \(a\) 长得更像 \(b\) ,如果 \(a,b\) 初始的逆序对奇偶性不同那么无论如何都无法使得两个序列相等。所以判断一下 \(a,b\) 的逆序对奇偶性是否相等就可以了。

代码

方法一:

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1),X,Y;
    for(int i=1;i<=n;i++) cin>>a[i],X.push_back(a[i]);
    for(int i=1;i<=n;i++) cin>>b[i],Y.push_back(b[i]);
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    if(X!=Y) return cout<<"NO\n",void();
    vector<int> e1[n+1],e2[n+1];
    for(int i=1;i<=n;i++) e1[lower_bound(X.begin(),X.end(),a[i])-X.begin()+1].push_back(i);
    for(int i=1;i<=n;i++) e2[lower_bound(Y.begin(),Y.end(),b[i])-Y.begin()+1].push_back(i);
    int num1=0,num2=0;
    vector<int> vis1(n+1),vis2(n+1);
    for(int i=1;i<=n;i++)
    {
        if(!vis1[i])
        {
            for(int j=i;;j=e1[j][0]) if(vis1[j]) break;else vis1[j]=1;
            num1++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis2[i])
        {
            for(int j=i;;j=e2[j][0]) if(vis2[j]) break;else vis2[j]=1;
            num2++;
        }
    }
    if(num1%2==num2%2) cout<<"YES\n";
    else cout<<"NO\n";
}

方法二:


标签:temp,int,矩阵,Codeforces,956,second,Div,al,first
From: https://www.cnblogs.com/Lao-Die/p/18443117

相关文章

  • Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)
    题意给定一个无向图,含有\(n\)个点和\(m\)条边。题解点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constexpri64inf=1e18;voidsolve(){intn,m,h;cin>>n>>m>>h;vector<vector<......
  • Codeforces Round 974 (Div. 3) - D题
    这道题题意就是你有k个工作,每个工作都有一个时间区间左边界l和右边界r,妈妈和哥哥要来看你,时长为d,题目要求求出1.哥哥看你的这段时间工作时间段重叠最多是多少?2.妈妈看你的这段时间工作时间段重叠最少是多少?这道题如果硬做的话可能就是线段树了(蒟蒻暂时没有想到其他的做法),但如果......
  • Codeforces Round 973 (Div. 2) - D题二分
    首先这道题的一个坑点就是求max(a[1],a[2],...,a[n])和求min(a[1],a[2],...,a[n])是完全独立的,不会相互影响(可能是我读题能力太差,一直卡在这点了。。。)这道题二分是一种很好想的方法,题中提到max和min,我们就可以想到只要让最大值最小,让最小值最大就可以达到我的目的了,二分的......
  • Codeforces Round 976 (Div. 2)
    VP的这一场,真的唐完了。。。A.FindMinimumOperations题意给你一个\(n\)和\(k\),每次操作可以让\(n\)减去一个\(k\)的\(x\)次方,即\(n-k^x\)。问你最少操作几次能够让\(n\)变成\(0\)。思路我们先考虑如果\(k\)是\(2\)的情况,那么题目就转化成了\(n\)的......
  • Codeforces Round 958 (Div. 2)
    手速前三题,D题想到树形dp但是没做出来。A.SplittheMultiset题意给你一个多集,一开始这个多集里只有一个数字。每次操作可以选择删掉多集里的一个数,然后添加\(k\)个数,并且使得这\(k\)个数的和等于删掉的数。问你最少需要操作多少次多集里的数的个数等于等于\(n\)。思路......
  • codeforces round 975 E(div.2)(lambda表达式实现dfs,min_element函数,一定要优化重复的
    解题历程:看到题目要求要用最少的消除次数让所有叶子深度相同,通过观察,那么就只需要将所有深度都尝试一遍就行了,可是我当时没多想就用dfs记录所有节点的深度,单独将所有叶子和该叶子的深度存起来,记录最大的深度,从最大深度尝试到深度0,对于深度小于当前尝试深度的叶子,用dfs的方式将与......
  • 9564 Work Scheduling 结构体排序 优先队列 最小堆 贪心
    解决思路 排序:首先将所有工作按照截止时间 D_i 进行排序。 优先队列:使用一个最小堆来存储当前选择的工作的利润。 选择工作:遍历所有工作,如果当前工作的截止时间大于堆的大小,则将该工作加入堆中;否则,如果当前工作的利润大于堆顶的利润,则替换堆顶的工作。#include......
  • Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
    目录写在前面A签到B数学,模拟C二进制,拆位D暴力,并查集E概率DPF写在最后写在前面补题地址:https://codeforces.com/gym/104128。上大分失败呃呃呃呃有点过载了妈的我现在应该去打会儿游戏。A签到等价于求\(n\)在\(k\)进制下各位之和,写一个类似快速幂的东西。///*By......
  • Codeforces Round 975 (Div. 2)
    C.CardsPartition(C)对于每个确定的size,有便捷的方法判断该值是否合法:组数最小为\(a_{max}\),若\(k\)张牌可以填出\(a_{max}\)组牌堆则合法;将余下的牌当成新的一组,若\(k\)张牌可以凑出一整组则合法;其余情况不合法。由于check过程为\(O(1)\),可从大到小暴力枚举size,时间......
  • Codeforces Round 976 (Div. 2)
    传送门A.输出\(n\)在\(k\)进制下各数位之和B.一个位置被反转当且仅当有奇数个因子,有奇数个因子的数一定是完全平方数。二分\(n\)即可C.枚举二进制下每一位,发现\(b,c,d\)再这一位最多有八种可能,对于每一种情况都能得到在这一位\(a\)的值,分类讨论就行了。D.E.\(......