Codeforces Round #771 (Div. 2)
B题最后被hack了.....不过最后还是加了17。。。不掉就行，下场要上粉！！！
A. Reverse
题目要求最小的字典序序列，比较显然的想法就是第一个元素找1，第二个元素找2....依次类推。
点击查看代码
#include<bits/stdc++.h>
#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<bits/stdc++.h>
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<l) flag=false;
if(x%2==0&&x<r) flag=false;
(x%2)?l=x:r=x;
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
C. Inversion Graph
C题一眼看过去就是知道是优化连边的题,对于逆序对，我的第一想法就是用树状数组求逆序对的方法。就是倒序，然后按权值大小，累计，每一个x，1 - x-1内的个数就是它对应的逆序数的个数。那么在这个题中就是x要与1 - x-1内的所有数连边。暴力的连边不可行，我们考虑怎么优化，我们最终的目的是让1 - x-1与x形成一个连通块，那么我们可以保留最小的那个数，将其他数都删去，这样，能连上这个连通块的其他的数时，一定也能连上这个连通块内的最小的数字。
点击查看代码
#include<bits/stdc++.h>
#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_queue<int>q;
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())<a[i])
{
b[++num]=-q.top();
q.pop();
}
if(num)
{
for(int j=2;j<=num;++j) f[b[j]]=b[1];
f[a[i]]=b[1];
q.push(-b[1]);
}
else q.push(-a[i]);
}
int cnt=0;
for(int i=1;i<=n;++i)
{
int t=getf(i);
if(vis[t]) continue;
vis[t]=1;cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
这个题当然也有其他的方法，我是采用优先队列去模拟这个过程。其实我们完全可以用单调栈去模拟这个过程，我们维护一个栈底到栈顶单调递增的栈，一旦出现一个元素将其他元素顶出栈时，我们考虑保留当中最大的元素，将所有的元素与最大的元素连边即可。
点击查看代码
#include<bits/stdc++.h>
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]<st[top])
{
ts=max(ts,st[top]);
f[st[top]]=ts;
top--;
}
f[a[i]]=ts;
st[++top]=ts;
}
int cnt=0;
for(int i=1;i<=n;++i)
{
int t=getf(i);
if(vis[t]) continue;
vis[t]=1;
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
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<pair<int,int> >q;
struct wy{int x,y,c;}b[N*N];
inline bool check(int x,int y)
{
if(x>=1&&x<n&&y>=1&&y<m) {="" int="" mx="max(max(c[x][y],c[x][y+1]),max(c[x+1][y],c[x+1][y+1]));" if(!mx)="" return="" false;="" if(c[x][y]&&c[x][y]!="mx)" if(c[x][y+1]&&c[x][y+1]!="mx)" if(c[x+1][y]&&c[x+1][y]!="mx)" if(c[x+1][y+1]&&c[x+1][y+1]!="mx)" true;="" }="" inline="" void="" clear(int="" x,int="" y)="" c[x][y]="c[x][y+1]=0;" c[x+1][y]="c[x+1][y+1]=0;" bool="" duan()="" for(int="" i="1;i<=n;++i)" j="1;j<=m;++j)" if(c[i][j])="" main()="" freopen("1.in","r",stdin);="" scanf("%d%d",&n,&m);="" scanf("%d",&c[i][j]);="" if(check(i,j))="" q.push({i,j});="" while(q.size())="" x="q.front().first,y=q.front().second;" q.pop();="" if(check(x,y))="" b[++num].x="x;" b[num].y="y;" b[num].c="max(max(c[x][y],c[x][y+1]),max(c[x+1][y],c[x+1][y+1]));" clear(x,y);="" q.push({x+i,y+j});="" if(!duan())="" {puts("-1");return="" 0;}="" printf("%d\n",num);="">=1;--i) printf("%d %d %d\n",b[i].x,b[i].y,b[i].c);
return 0;
}
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int N=1010;
int n,m,c[N][N],num;
queue<pair<int,int> >q;
struct wy{int x,y,c;}b[N*N];
inline bool check(int x,int y)
{
if(x>=1&&x<n&&y>=1&&y<m)
{
int mx=max(max(c[x][y],c[x][y+1]),max(c[x+1][y],c[x+1][y+1]));
if(!mx) return false;
if(c[x][y]&&c[x][y]!=mx) return false;
if(c[x][y+1]&&c[x][y+1]!=mx) return false;
if(c[x+1][y]&&c[x+1][y]!=mx) return false;
if(c[x+1][y+1]&&c[x+1][y+1]!=mx) return false;
return true;
}
return false;
}
inline void clear(int x,int y)
{
c[x][y]=c[x][y+1]=0;
c[x+1][y]=c[x+1][y+1]=0;
}
inline bool duan()
{
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) if(c[i][j]) return false;
return true;
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
scanf("%d",&c[i][j]);
if(check(i,j)) q.push({i,j});
}
while(q.size())
{
int x=q.front().first,y=q.front().second;
q.pop();
if(check(x,y))
{
b[++num].x=x;
b[num].y=y;
b[num].c=max(max(c[x][y],c[x][y+1]),max(c[x+1][y],c[x+1][y+1]));
clear(x,y);
for(int i=-1;i<=1;++i)
for(int j=-1;j<=1;++j) q.push({x+i,y+j});
}
}
if(!duan()) {puts("-1");return 0;}
printf("%d\n",num);
for(int i=num;i>=1;--i) printf("%d %d %d\n",b[i].x,b[i].y,b[i].c);
return 0;
}