Codeforces Round #771 (Div. 2)思路分享
Codeforces Round #771 (Div. 2)
B题最后被hack了.....不过最后还是加了17。。。不掉就行，下场要上粉！！！
A. Reverse
题目要求最小的字典序序列，比较显然的想法就是第一个元素找1，第二个元素找2....依次类推。
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
int n,T,a[510],b[510];
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
if(i!=a[i])
{
int o;
for(int j=i+1;j<=n;++j)
{
if(i==a[j])
{
o=j;
break;
}
}
for(int j=i;j<=o;++j) b[j]=a[i+o-j];
for(int j=i;j<=o;++j) a[j]=b[j];
break;
}
}
for(int i=1;i<=n;++i) printf("%d ",a[i]);
puts("");
}
return 0;
}
B. Odd Swap Sort
比赛的时候就被这个题卡了许久，到最后还是打了个\(O(n^2)\)的复杂度上去，数据1e5,我......脑子抽抽了估计...
发现只奇偶的才能换，也就是说相同的奇偶性是不能交换的，换句话说也就是相同奇偶性的数他们的相对位置是不变的。那么我们只需要分别对于奇数和偶数观察他们是否是有序的即可。
点击查看代码
#include
using namespace std;
const int N=1e5+10;
int T,n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
bool flag=true;
int l=0,r=0;
for(int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
if(x%2==1&&x C. Inversion Graph
C题一眼看过去就是知道是优化连边的题,对于逆序对，我的第一想法就是用树状数组求逆序对的方法。就是倒序，然后按权值大小，累计，每一个x，1 - x-1内的个数就是它对应的逆序数的个数。那么在这个题中就是x要与1 - x-1内的所有数连边。暴力的连边不可行，我们考虑怎么优化，我们最终的目的是让1 - x-1与x形成一个连通块，那么我们可以保留最小的那个数，将其他数都删去，这样，能连上这个连通块的其他的数时，一定也能连上这个连通块内的最小的数字。
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
const int N=1e5+10;
int n,T,a[N],f[N],vis[N],b[N],num;
priority_queueq;
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) f[i]=i,vis[i]=0;
while(q.size()) q.pop();
for(int i=n;i>=1;--i)
{
num=0;
while(q.size()&&(-q.top()) 这个题当然也有其他的方法，我是采用优先队列去模拟这个过程。其实我们完全可以用单调栈去模拟这个过程，我们维护一个栈底到栈顶单调递增的栈，一旦出现一个元素将其他元素顶出栈时，我们考虑保留当中最大的元素，将所有的元素与最大的元素连边即可。
点击查看代码
#include
using namespace std;
const int N=1e5+10;
int T,n,a[N],st[N],top,f[N],vis[N];
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),f[i]=i,vis[i]=0;
top=0;
for(int i=1;i<=n;++i)
{
int ts=a[i];
while(top&&a[i] D. Big Brush
这个题算是最后逆风翻盘了吧...记得之前在洛谷做过一个类似的题，这种覆盖性问题的解法就是倒着解....我们先找最后一个四个一起的小矩形，之后这些小矩形可以变成任意颜色，一直扩展即可。
点击查看代码
#include
#define ll long long
#define db double
using namespace std;
const int N=1010;
int n,m,c[N][N],num;
queue >q;
struct wy{int x,y,c;}b[N*N];
inline bool check(int x,int y)
{
if(x>=1&&x=1&&y=1;--i) printf("%d %d %d\n",b[i].x,b[i].y,b[i].c);
return 0;
}
E. Colorful Operations
关于这种线段树的延迟操作，其实之前也是写过类似的题目的.....就是没想到这个题可以这样写。
先把问题简化，如果只有单点修改的话，那我们可以新增一个变量color[],表示某个颜色总的变化量。对于操作一：我们输出a[x]+color[c[x]].对于操作二,color[x]+=v;对于操作一：我们可以a[x]+=color[c[x]];c[x]=k;a[x]-=color[c[x]];这样的话，我们全部操作即可在O(1)操作内完成。
至于变成区间修改的话，大体的想想，因为操作1的原因，整个序列大概率是一段一段连续的数字。那我们可以维护一个区间是否颜色相同，相同的话在上面做修改。不同的话，继续往下找。虽然某个操作的复杂度可能很大，但均摊下去应该不大。.....（具体证明还没有想明白...先这样咕掉...）
点击查看代码
#include
#define ls p<<1
#define rs p<<1|1
#define ll long long
using namespace std;
const int N=1e6+10;
int n,q;
char c[100];
ll color[N];
struct Tree
{
int col;
bool sa;
ll la;
#define sa(p) t[p].sa
#define la(p) t[p].la
#define col(p) t[p].col
}t[N<<2];
inline void build(int p,int l,int r)
{
sa(p)=1;col(p)=1;
if(l==r) return;
int mid=l+r>>1;
build(ls,l,mid);
build(rs,mid+1,r);
}
inline void push(int p)
{
if(la(p))
{
la(ls)+=la(p);
la(rs)+=la(p);
la(p)=0;
}
if(sa(p)&&col(p))
{
sa(ls)=1;sa(rs)=1;
col(ls)=col(p);
col(rs)=col(p);
}
}
inline ll ask(int p,int l,int r,int x)
{
if(l==r) return la(p)+color[col(p)];
push(p);
int mid=l+r>>1;
if(x<=mid) return ask(ls,l,mid,x);
else return ask(rs,mid+1,r,x);
}
inline void alter(int p,int l,int r,int L,int R,int c)
{
if(l<=L&&r>=R&&sa(p))
{
sa(p)=1;
la(p)+=color[col(p)]-color[c];
col(p)=c;
return;
}
push(p);
int mid=L+R>>1;
if(l<=mid) alter(ls,l,r,L,mid,c);
if(r>mid) alter(rs,l,r,mid+1,R,c);
if(sa(ls)&&sa(rs)&&col(ls)==col(rs)) sa(p)=1,col(p)=col(ls);
else sa(p)=0;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d",&n,&q);
build(1,1,n);
for(int i=1;i<=q;++i)
{
scanf("%s",c+1);
if(c[1]=='C')
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
alter(1,l,r,1,n,c);
}
else if(c[1]=='A')
{
int c,x;
scanf("%d%d",&c,&x);
color[c]+=x;
}
else
{
int x;scanf("%d",&x);
printf("%lld\n",ask(1,1,n,x));
}
}
return 0;
}
Powered by .NET 6 on Kubernetes 作者：逆天峰 出处：https://www.cnblogs.com/gcfer//