Pinely Round 2 (Div. 1 + Div. 2)
比赛链接
因为第二天早上满课，所以这个比赛没有打，但是补题还是要有的。
A题Channel
A题链接
你是一个博主，有n个订阅者，当你发表了一篇博客时，会被订阅者看到，一开始有a名订阅者在线，随后给你q个指令，“+”代表有一个订阅者上线，“-”代表有一个订阅者下线，你想知道是否全部订阅者都阅读过你的文章，YES表示肯定，MAYBE表示也许，NO表示没有，
A思路：
一开始这个题会错意了，以为减号代表的有可能不是他的订阅者下线，但应该是都是订阅者的信息，接下来就是这个题的思路：如果是YES，那一定是有一段全部是+号，表示有这么一段序列全是加号，并且长度大于n个订阅者。如果是NO呢，就是即使我们下线的全是之前在线的，一开始在线的订阅者加上+号的数量还要小于n，这表明绝不可能出现全部查看的情况，其他情况均是MAYBE。
A代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
int n,a,q;
cin>>n>>a>>q;
int m=a;
int maxn=a;
int ans=0;
for(int i=1;i<=q;i++){
char b;
cin>>b;
if(b=='+'){
m++;
maxn=max(maxn,m);
ans++;
}
else{
m--;
}
}
if(maxn>=n){
cout<<"YES"<<endl;
}
else{
if(a+ans>=n){
cout<<"MAYBE"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
int main(){
int t;
cin>>t;
// cout<<t<<endl;
while(t--){
solve();
}
return 0;
}
B. Split Sort
题目链接
给定一个序列a，你可以进行操作：选择一个数 x ，将所有 比 x 小的数按照序列中的顺序放到 x 前面 ， 将所有大于等于 x 的数 按照序列中的顺序放到 x 后面。求整个序列满足单增的最小操作数。
B思路：
一开始我以为只需要找到一个位置他的前一个数比当前数的位置大，那这个点就是需要交换的，但这样想是错的，倒不是思路错，只是无法满足是最小操作数，看样例发现，当我们改变一个数的位置的时候，有些数的位置也会改变，事实上这个题的操作于逆序对有关，操作数为整个序列中 i 和 i + 1 位置的逆序对数量。
B代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
return a.first<b.first;
}
void solve(){
int n;
cin>>n;
int ans1=0;
std::vector<PII> v(n+1);
for(int i=1;i<=n;i++){
int x;
cin>>x;
v[i].first=x;
v[i].second=i;
if(x<v[i-1].first){
ans1++;
}
}
sort(v.begin(),v.end(),cmp);
int ans=0;
if(n==1){
cout<<0<<endl;
}
else{
for(int i=2;i<=n;i++){
if(v[i].second<v[i-1].second){
ans++;
}
}
cout<<ans<<" "<<ans1<<endl;
}
}
int main(){
int t;
cin>>t;
// cout<<t<<endl;
while(t--){
solve();
}
return 0;
}
C. MEX Repetition
题目链接
给定一个长度为n，大小在[0,n]的没有相同元素的序列，总共进行k轮操作，每轮操作将按照顺序从i=1~n，使得ai=MEX(a1,a2,a3,...)。其中MEX函数代表了所有数当中没有出现的最小非负整数。例如：MEX(1,1,2)=0,MEX(0,1,2)=3。求k轮操作后序列变成了什么样子，
C思路：
一开始我竟然没有读懂这个题是在说什么，果然中午没睡觉太困啦影响脑子转动，睡醒一觉醒来发现这个题还是比较简单的，但是如果只是简单的模拟的话其实是会超时的，我们不妨将这n+1个数字按照他规定的方式进行展开，这样说可能不太明显，画个图就比较易懂了。
C代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
return a.first<b.first;
}
void solve(){
int n,k;
cin>>n>>k;
std::vector<int> v;
std::map<int, int> mp;
for(int i=1;i<=n;i++){
int x;
cin>>x;
mp[x]=1;
v.push_back(x);
}
for(int i=0;i<=n;i++){
if(mp[i]!=1){
v.push_back(i);
}
}
//y因为是0-n有n+1个数字
n+=1;
int t=k%n;//看看是取到了哪个位置
int st=n-t;
for(int i=1;i<n;i++){
cout<<v[st%n]<<" ";
st++;
}
cout<<endl;
}
int main(){
int t;
cin>>t;
// cout<<t<<endl;
while(t--){
solve();
}
return 0;
}
D. Two-Colored Dominoes
原题链接
有一个n * m 的网格。其中有若干个1 * 2的多米诺骨牌横着放或者竖着放在其中，你需要将其一格涂成黑色，一格涂成白色。需要满足一行当中白色的格子等于黑色的格子，一列当中白色的格子等于黑色的格子。问能否涂成每行和每列黑白颜色数目相等的样子，可以输出画法，不可以输出-1；
D思路：
这个题也并不是很难，你想如果横着放是不是影响到的就是两列，竖着放影响到的就是两行，基于这个的基础上，我们可以对这些按照一黑一白和一白一黑插着放，这样就保证了颜色相等，所以我们只需要统计一下对应行列中横竖放着的个数就可以。
D代码：
#include<bits/stdc++.h>
using namespace std;
const int N=510;
typedef long long ll;
typedef pair<int,int> PII;
bool cmp(PII a,PII b){
return a.first<b.first;
}
char a[N][N];
void solve()
{
int n , m;
cin>>n>>m;
vector<int>row[m] , column[n];
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < m ; j ++){
cin>>a[i][j];
if(a[i][j] == 'L'){
row[j].push_back(i);
}
if(a[i][j] == 'U'){
column[i].push_back(j);
}
}
}
for(int i = 0; i < m ; i++){
if(row[i].size() % 2 == 1){
cout<<"-1\n";
return;
}
else{
int t = row[i].size();
int flag = 1;
for(int j = 0 ; j < t ; j ++){
int r = row[i][j];
if(flag == 1){
a[r][i] = 'W';
a[r][i + 1] = 'B';
flag *= -1;
}
else{
a[r][i] = 'B';
a[r][i + 1] = 'W';
flag *= -1;
}
}
}
}
for(int i = 0 ; i < n ; i ++){
if(column[i].size() % 2 == 1){
cout<<"-1\n";
return;
}
else{
int t = column[i].size();
int flag = 1;
for(int j = 0 ; j < t ; j ++){
int c = column[i][j];
if(flag == 1){
a[i][c] = 'W';
a[i + 1][c] = 'B';
flag*=-1;
}
else{
a[i][c] = 'B';
a[i + 1][c] = 'W';
flag*= -1;
}
}
}
}
for(int i = 0 ; i < n ; i++){
for(int j = 0; j < m ; j ++){
cout<<a[i][j];
}
cout<<endl;
}
}
int main(){
int t;
cin>>t;
// cout<<t<<endl;
while(t--){
solve();
}
return 0;
}