A. Reverse
思路:找到当前序列中$a_i!=i$的最小的a[i],以该位置为左边界,第一个$a_i!=i$的位置为右边界.$reverse$一遍即可.
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
int cnt=INF;
vector<int>a(n+1);
int id1=0;
int id2=0;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
if(a[i]!=i)
{
int l=i+1;
while(a[l]!=i)l++;
// if(i==1)cout<<l<<endl;
// cout<<*(a.begin()+i)<<' '<<*(a.begin()+l)<<endl;
reverse(a.begin()+i,a.begin()+l+1);
break;
}
}
// reverse(a.begin()+1,a.begin()+3);
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
B. Odd Swap Sort
思路:
分别独立的判断,奇数子列和偶数子列是否都分别满足非降序.
证明:
充分性:即只要存在 奇数列和偶数列分别独立非降序必有解.
因为如果某一个偶数比奇数大且偶数在奇数之前那么他们之间一定全是偶数,因此是可以直接换的.
必要性:就是说如果 存在这样的 子列, $odd1 >odd2< odd3$ 或者$odd1< odd2 >odd3$ 即奇数的非降序
显然是无法操作完成的 偶数的情况同理
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
int odd=1,even=0;//记录前一个奇数
bool flag=true;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(!flag)continue;
if(x%2!=0)//奇数
{
if(x>=odd)
{
odd=x;
}else flag=false;
}else
{
if(x>=even)even=x;
else flag=false;
}
}
if(flag)cout<<"Yes"<<endl;
else cout<<"NO"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Inversion Graph
思路:线段树维护区间最大最小值.
题目要求对于任意一个数而言,可以将所有其右侧小于它的数连在一起.
因此从右往左贪心的考虑:
每次从还未考虑过的区间$[1,R]$中找到最大值的位置。
然后从已经考虑过的区间$[R+1,n]$中寻找最小值,并判断未考虑的区间中最大值是否比最小值要小。
1.如果未考虑区间的最大值比 考虑过的区间的最小值还小 说明当前最大值和其右侧的数,无法和之前合并的区间合并,此时区间数++
2.如果未考虑区间的最大值比 考虑过区间的最小值大,说明可以和之前的区间合并.答案不加.
每次判断结束后指针移动到当前区间最大值的前一个位置即可。
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
bool vis[N];
int w[N],n;
struct node{
int l,r;
int x,pos1;//最大值以及最大值所在位置
int y,pos2;//最小值以及最小值所在位置
}tr[N*4];
void pushup(int u)//同时维护区间最大值和区间最小值
{
if(tr[u<<1].x>tr[u<<1|1].x)tr[u].x=tr[u<<1].x,tr[u].pos1=tr[u<<1].pos1;
else tr[u].x=tr[u<<1|1].x,tr[u].pos1=tr[u<<1|1].pos1;
if(tr[u<<1].y<tr[u<<1|1].y)tr[u].y=tr[u<<1].y,tr[u].pos2=tr[u<<1].pos2;
else tr[u].y=tr[u<<1|1].y,tr[u].pos2=tr[u<<1|1].pos2;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)tr[u]={l,r,w[r],r,w[r],r};
else
{
int mid=tr[u].l+tr[u].r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
PII query1(int u,int l,int r)//查询区间最大值
{
if(tr[u].l>=l&&tr[u].r<=r)
{
PII t={tr[u].x,tr[u].pos1};
return t;
}else
{
int mid=tr[u].l+tr[u].r>>1;
PII res1={-INF,-1},res2={-INF,-1};//初始化
if(l<=mid)res1=query1(u<<1,l,r);
if(r>mid)res2=query1(u<<1|1,l,r);
if(res1.first>res2.first)return res1;
else return res2;
}
}
PII query2(int u,int l,int r)//查询区间最小值
{
if(tr[u].l>=l&&tr[u].r<=r)
{
PII t={tr[u].y,tr[u].pos2};
return t;
}else
{
int mid=tr[u].l+tr[u].r>>1;
PII res1={INF,-1},res2={INF,-1};//初始化
if(l<=mid)res1=query2(u<<1,l,r);
if(r>mid)res2=query2(u<<1|1,l,r);
if(res1.first<res2.first)return res1;
else return res2;
}
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>w[i];
build(1,1,n);
/* for(int i=1;i<=15;i++)
if(tr[i].l!=0)
{
cout<<i<<endl;
cout<<tr[i].l<<' '<<tr[i].r<<endl;
cout<<tr[i].x<<' '<<tr[i].pos1<<endl;
cout<<tr[i].y<<' '<<tr[i].pos2<<endl;
cout<<endl;
}*/
int R=n,L=1;
int ans=0;
while(R>=1)
{
PII res1,res2;
res1=query1(1,1,R);
if(R+1<=n)res2=query2(1,R+1,n);//右侧所有区间的最小值
else res2={INF,0};
if(res1.first>res2.first)R=res1.second-1;//可以和右边某个区间合并
else ans++,R=res1.second-1;//无法和右边任意区间合并
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(n*\log n)$
单调栈做法.
思路:对于逆序对$P(i,j)$,从左往右一次入栈,每次进栈的元素如果比之前的元素要小说明可以合并.
每次合并的时候取出所有$>a_i$的数并取$t=max{a_i,t1,t2,t3,....}$这些栈中比$a_i$大的合并成一个集合.
由于每次出现不等关系均会及时合并,因此栈中存的元素从栈顶到栈底是一个降序排列.即出现大于栈顶的元素,直接放入栈顶即可。
AC Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
stack<int>q;
for(int i=1;i<=n;i++)
{
if(q.empty()){q.push(a[i]);continue;}
if(q.top()<a[i])q.push(a[i]);
else
{
int t=q.top();
while(!q.empty()&&q.top()>a[i])q.pop();
q.push(t);
}
}
cout<<q.size()<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
时间复杂度$O(n)$
思路:
首先找到,标程中所说的$special square$.
为什么需要这个?因为一次只能染色四个格子,无论如何操作,最后一次操作的四个格子颜色必定相同.
然后统计出所有的这样的格子,将其放入bfs队列并标记.随后bfs是否能将全部格子染色即可.
最后注意,我们需要反向的输出$BFS$过程,所得到的方案.这是因为染色的过程实际上是操作的逆过程.
在输出完由$BFS$得到的操作后,最后按任意顺序输出,最初的$special square$,的染色操作即可。
注意:本题输出较大会卡常,需要将endl 替换成 ‘\n’
#define endl '\n'
AC Code:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llINF=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int g[1010][1010];
bool vis[1010][1010];
struct node{
int x,y;
int col;
};
queue<PII>q;
vector<node>ans;
int n,m;
void check(int x,int y,int res)//检测周围四种情况
{
if(res==1)
{
if(x+1<=n&&y+1<=m)
{
vector<PII>a;
if(!vis[x][y+1])a.push_back({x,y+1});
if(!vis[x+1][y])a.push_back({x+1,y});
if(!vis[x+1][y+1])a.push_back({x+1,y+1});
if(a.size()==0)return;//a是空的 全被染色了
int col=g[a[0].first][a[0].second];
for(auto c:a)
if(col!=g[c.first][c.second])return;
for(auto c:a)vis[c.first][c.second]=true,q.push(c);//染成*
ans.push_back({x,y,col});
}
}
if(res==2)
{
if(x+1<=n&&y-1>=1)
{
vector<PII>a;
if(!vis[x][y-1])a.push_back({x,y-1});
if(!vis[x+1][y])a.push_back({x+1,y});
if(!vis[x+1][y-1])a.push_back({x+1,y-1});
if(a.size()==0)return;//a是空的 全被染色了
int col=g[a[0].first][a[0].second];
for(auto c:a)
if(col!=g[c.first][c.second])return;
for(auto c:a)vis[c.first][c.second]=true,q.push(c);//染成*
ans.push_back({x,y-1,col});
}
}
if(res==3)
{
if(x-1>=1&&y+1<=m)
{
vector<PII>a;
if(!vis[x-1][y])a.push_back({x-1,y});
if(!vis[x-1][y+1])a.push_back({x-1,y+1});
if(!vis[x][y+1])a.push_back({x,y+1});
if(a.size()==0)return;//a是空的 全被染色了
int col=g[a[0].first][a[0].second];
for(auto c:a)
if(col!=g[c.first][c.second])return;
for(auto c:a)vis[c.first][c.second]=true,q.push(c);//染成*
ans.push_back({x-1,y,col});
}
}
if(res==4)
{
if(x-1>=1&&y-1>=1)
{
vector<PII>a;
if(!vis[x][y-1])a.push_back({x,y-1});
if(!vis[x-1][y])a.push_back({x-1,y});
if(!vis[x-1][y-1])a.push_back({x-1,y-1});
if(a.size()==0)return;//a是空的 全被染色了
int col=g[a[0].first][a[0].second];
for(auto c:a)
if(col!=g[c.first][c.second])return;
for(auto c:a)vis[c.first][c.second]=true,q.push(c);//染成*
ans.push_back({x-1,y-1,col});
}
}
}
void bfs()
{
while(!q.empty())
{
auto t=q.front();
q.pop();
int x=t.first,y=t.second;
for(int i=1;i<=4;i++)check(x,y,i);
}//染色
}
void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cin>>g[i][j];
bool ok=false;
vector<node>res;
for(int i=1;i+1<=n;i++)
for(int j=1;j+1<=m;j++)
if(g[i][j]==g[i+1][j]&&g[i][j]==g[i][j+1]&&g[i][j]==g[i+1][j+1])
{
ok=true;
q.push({i,j});
q.push({i+1,j});
q.push({i,j+1});
q.push({i+1,j+1});
int col=g[i][j];
res.push_back({i,j,col});
vis[i][j]=true,vis[i+1][j]=true,vis[i][j+1]=true,vis[i+1][j+1]=true;
}
if(!ok)cout<<"-1"<<endl;
else
{
bfs();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!vis[i][j])
{
cout<<"-1"<<endl;
return;
}
cout<<res.size()+ans.size()<<endl;
for(int i=ans.size()-1;i>=0;i--)cout<<ans[i].x<<' '<<ans[i].y<<' '<<ans[i].col<<endl;
for(auto c:res)cout<<c.x<<' '<<c.y<<' '<<c.col<<endl;
}
}
/*4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4
4 4
* * * *
* * * *
* * * 4
* * 4 4*/
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
3
6 6 6
这个数据不知道为啥过不去
本来输入三个6就应该停止,但得输入9个数
迷茫
最后两组样例一起写时候才会出现
看代码修改了下
前面错的原因是 如果出现错误直接提前终止 导致数据还没读完就输出了 这一没读完的数据就读到下一组了…
B代码过不去。。。