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<s时,我们只需要在前面每一位依次分配一个k-1直到b减去之前所有的值再除k等于s为止即可.
#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;
}