Codeforces Round #816 (Div. 2)

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

目录

A. Crossmarket(签到)

B. Beautiful Array

C. Monoblock

D. 2+ doors

---

A. Crossmarket(签到)

思路:观察样例即可,注意1,1时要特判

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,m;
    cin>>n>>m;
    if(n==1&&m==1)
    {
        cout<<0<<endl;
        return ;
    }
    cout<<2*(n-1+m-1)-max(n-1,m-1)+1<<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. Beautiful Array

题意:给你n,k,b,s四个数,分别意思为,有一个长度为n的数组,s为每个元素没有除k后求和值,b为每个元素除k之后求和的值.问你是否可以构造出一个数组.

思路:由题意可知,当b*k时(最值情况,所有元素整除k),b*k时一定<=s的当>s时就肯定不成立.当b*k=s的时候,直接在最后一位放上一个b即可,其余元素化为0,而当b*k

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
void solve()
{
    int n,k,b,s;
    cin>>n>>k>>b>>s;
    if(b*k>s)
    {
        cout<<"-1"<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
        a[i]=0;
    for(int i=1;i<=n-1;i++)
    {
        if(s/k>b)
        {
            a[i]=k-1;
            s-=k-1;
        }
    }
    a[n]=s;
    if(a[n]/k!=b)
    {
        cout<<"-1"<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<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. Monoblock

题意:g(l,r)的含义是数组内的子段l到r内有多少个连续区间(例如[1,1,3,3,2,1]有4个连续的区间(区间内元素相同)),g(l,r)的值即为可以被分成的连续相等区间个数.我们每次可以对原数组中某一个元素进行修改,求出每一次修改后盖数组的所有子段的g(l,r)的值的和.

思路:我们先把原数组当做每一个元素都不一样的情况,这样包含第一个元素的子段贡献为:1+2+...+n.而第二个的为:1+2+...+n-1.最后一个元素的贡献为1,那么就可以求出当原数组每个数字都不一样的情况下的贡献.

那么在进行观察,发现当连续的两个元素原本不同,变为两者不同的时候(设两者的下标为idx和idx+1),那么这对于整个数组贡献的影响是减少idx*(n-idx),这个的含义就是前idx个元素的后面从第idx+1开始所有的子段贡献都会-1,那么根据这个规律直接每次进行计算即可.(注意下面要判断对两边的影响).

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
int a[100005];
void solve()
{
    a[0]=-1;
    int f,f1,idx,x,n,m,ans=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        ans+=(1+(n-i+1))*(n-i+1)/2;
    }
    for(int i=1;i<n;i++)
    {
        if(a[i]==a[i+1])
            ans-=i*(n-i);
    }
    while(m--)
    {
        cin>>idx>>x;
        if(idx!=1)
        {
            f=(a[idx]==a[idx-1]);
            f1=(x==a[idx-1]);
            if(f1!=f&&f==1)
                ans+=(idx-1)*(n-idx+1);
            else if(f1!=f&&f1==1)
                ans-=(idx-1)*(n-idx+1);
        }
        if(idx!=n)
        {
            f=(a[idx]==a[idx+1]);
            f1=(x==a[idx+1]);
            if(f1!=f&&f==1)
                ans+=idx*(n-idx);
            else if(f1!=f&&f1==1)
                ans-=idx*(n-idx);
        }
        a[idx]=x;
        cout<<ans<<endl;
    }
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}

D. 2+ doors

题意:你有n个数字的数组,你有m个约束条件,每个条件包含三个数字,x,y,z,表示 .构造出一个数组,要求它比其他合法数组字典序都要小.

思路:我们先确定每个数字的0位,当一个数字的所有关系中某一位都是0,那么肯定填0.如果某个位置既可以填写1又可以填写0,那么我们就在这个关系所连接的最前面的数字填写0,后面的数字为了满足前面这个数字填写的0,就都要填写1.(所以我们构造是从前往后构造,这样可以先把要填写0的部分确定,后面满足前面填写1就会达到字典序最小的情况).思路如此,操作看代码(有注释)

#include<bits/stdc++.h>
using namespace std;
const int N =2e5+10,mod=998244353;
struct node
{
    int to,val;
};
vector<node>g[N];
int a[N];
void solve()
{
    int n,m,x,y,val;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>val;
        g[x].push_back({y,val});
        g[y].push_back({x,val});
    }
//记录每个元素的关系
    for(int i=1;i<=n;i++)
    {
        if(g[i].size()==0)
            continue;
        a[i]=(1<<30)-1;
        for(int j=0;j<g[i].size();j++)
            a[i]&=g[i][j].val;//这里这样操作可以确定那些位置要填写0,那些位置必须填写1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=29;j++)
        {
            if((a[i]>>j)&1)
            {
                int f=0;
                for(int k=0;k<g[i].size();k++)
                {
                    int v=g[i][k].to;
                    if(!((a[v]>>j)&1)||v==i)
                        f=1;
//如果该数位的前置关系填写了0,那么此位肯定要填写1
                }
                if(f==0)
                    a[i]-=(1<<j);
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    return ;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    solve();
    return 0;
}