Codeforces Round #815 (Div. 2)

Dashboard - Codeforces Round #815 (Div. 2) - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1720

目录

A. Burenka Plays with Fractions

B. Interesting Sum

C. Corners

D1. Xor-Subsequence (easy version)

---

 

A. Burenka Plays with Fractions

题意:给你a/b和c/d,每次最多改动一个字母,问,最少几次两者可以改成一样的.

思路,同分一下对于所有情况进行对比即可.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int temp=__gcd(b,d);
    a=a*d/temp;
    c=c*b/temp;
    if(a==c)
        cout<<"0"<<endl;
    else if(a==0||c==0||a%c==0||c%a==0)
        cout<<"1"<<endl;
    else
        cout<<"2"<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. Interesting Sum

题意,给你一个数组,对于某个区间1<=l<=r<=n求出max(a1,a2,…,al−1,ar+1,ar+2,…,an)−min(a1,a2,…,al−1,ar+1,ar+2,…,an)+max(al,…,ar)−min(al,…,ar).的最大值.

思路:排序后用最大值减去最小值,次大值减去次小值即可.可以保证结果最优

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+10,mod=998244353;
int a[N];
bool cmp(int a,int b)
{
    return a<b;
}
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+1+n,cmp);
    cout<<a[n]+a[n-1]-a[1]-a[2]<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. Corners

思路:每次我们可以选择一个含有至少一个1的L形状(2*2小正方形缺一角)吧这个L里面的数全部置为0,问最多几步可以把这个01矩阵全部转换为0.

思路:当你的任意一个一个小正方形里面包含有两个即以上的0时,你会发现我们可以实现每一步只消去1个1,然后邻近的正方形消去1个1也只需要一步.而当每个小正方形最多只含有1个0时,需要先一步消去两个1然后在每步消去1个1.当不含有0时,则需要一步消去三个1之后才能做到一步消去1个1.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e2+10,mod=998244353;
char ma[N][N];
void solve()
{
    int num=0,n,m,flag=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%s",ma[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(ma[i][j]=='1')
                num++;
    for(int i=1;i<n;i++)
        for(int j=1;j<m;j++)
            if(ma[i][j]+ma[i+1][j]+ma[i][j+1]+ma[i+1][j+1]-4*'0'<=2)
                flag=1;
    if(num==n*m)
        cout<<num-2<<endl;
    else
        if(!flag)
            cout<<num-1<<endl;
        else
            cout<<num<<endl;
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D1. Xor-Subsequence (easy version)

题意:给定一个数组a(下标从0开始).请找出一个最长的子序列,下标为.且这个子序列保证.保证a[i]<=200;求最长的子序列长度.

思路:这个题说实话有点难读懂.针对于可以链接成子序列的两个值的下标我们可以看成i,j,那么式子就变成了:.那么就很好看懂了,只需要枚举i,j然后进行普通的线性dp.因为两者可以链接,那么状态转移方程式为:.但是有一个问题就出现了.复杂度就进而变为了:O(n*n).铁定超时.就思考一下如何优化.

针对于式子在的情况下.可以发现200的最高位为,如果把他们二进制全部化为1的话就是255.异或运算在上述不等式可以让i和j造成的最大差距就是255.也就是说.我们只需要枚举i后面最多255的j即可.那么枚举剪枝复杂度变为O(200*n).

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =3e5+10,mod=998244353;
int f[N],a[N];
void solve()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        f[i]=1,cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=min(n,i+256);j++)
            if(((i-1)^a[j])>((j-1)^a[i]))
                f[j]=max(f[i]+1,f[j]);
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    cout<<ans<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}