Dashboard - Pinely Round 2 (Div. 1 + Div. 2) - Codeforces
A.题意是一共有n个用户，当前有a个用户在线，然后有m个用户上/下线通知，问是否有一时刻所有用户都在线。
简单的模拟，按照+-统计最大的和n的关系，和上线用户数量的关系判断下就行。
当时代码有点小乱。
查看代码
#pragma GCC optimize(2)
#include<iostream>
using namespace std;
typedef long long ll;
void solve()
{
int n,q,m;
cin>>n>>q>>m;
int add=0,sub=0,tmp=q,suc=q;
for(int i=0;i<m;i++)
{
char c;
cin>>c;
if(c=='+')add++,tmp++;
else sub++,tmp--;
suc=max(suc,tmp);
}
if(suc==n)
{
cout<<"YES\n";
return;
}
if(suc<n&&q+add<n)
{
cout<<"NO\n";
}
else cout<<"MAYBE\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}B。题意是给你一个(1-n)的某个排列，每次可以选择一个数，让小于它的数按照原来的相对位置排到它前面，大于它的按照原来的相对位置排在它后面，然后问最少多少次操作把序列变成1-n
最坏可能是n-1次(毕竟最后一个不用动嘛)。
我们想一种情况，如果x+1在x后面的话，我们动x+1的时候就把x,x+1有序化了，相当于少操作一次。
我们存一下每个数的下标，判断下它加1在不在后面即可
然后
查看代码
#pragma GCC optimize(2)
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll a[100005],b[100005],n;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]=i;
}
int ans=n-1;
for(int i=1;i<n;i++)
if(b[a[i]+1]>b[a[i]]&&a[i]<n)ans--;
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}C.给一个大小为n的数组，里面是0-n缺了一个数。然后每次操作都把a[i]换成mex{a1....an}，问k次操作后数组变成什么样。
既然是0-n这n+1个数缺少的那个数，那么每次操作都会让第一个数变成缺的数，然后第二个等于原来的第一个，第三个等于原来的第二个。。。。直到最后一个变成原来的倒数第二个。
那么再执行n-1次，缺的那个数到了最后一位，再执行一次，发现回到了原来的数组。即n+1次循环。
我们先将k%(n+1)，统计下缺的数和剩下的k，那么n-k+1这一位的数会在k轮操作后消失，它后面的加上此时缺的数再加上它前面的构成k轮后的数列。
查看代码
#pragma GCC optimize(2)
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
int a[100005],b[100005],n,k;
void solve()
{
cin>>n>>k;
for(int i=0;i<=n;i++)b[i]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[a[i]]=1;
}
k%=(n+1);
if(k==0)
{
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
cout<<"\n";
return;
}
int mex=0;
for(int i=0;i<=n;i++)
{
if(b[i]==0)
{
mex=i;
break;
}
}
int ft=n-k+1;
vector<int>ans;
for(int i=ft+1;i<=n;i++)
{
ans.push_back(a[i]);
}
ans.push_back(mex);
for(int i=1;i<ft;i++)ans.push_back(a[i]);
for(auto x:ans)
cout<<x<<' ';
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}D.题意是给一个n*m的格子，然后有两种特殊的占两块的格子，横着的LR,竖着的U,D，现在要求在两块的格子上涂黑白两种颜色，同一块L,R颜色相异，同一块U,D颜色相异，问是否能让每一行每一列的两种颜色格子相等。
想了差不多一个小时，想过DP,DSU，最后是按照之前看的PYY大佬的E. Tick, Tock[带权并查集] - qbning - 博客园 (cnblogs.com)想到的思路，尽管用的不是并查集，但也是过了。
L,R横着放，对于一行的黑白两色的个数平衡不会影响，那么我们来找U,D的数目，如果这一行U,D的数目为奇数，那么肯定不行。如果为偶数，那么
。。。太困了，明天再补，先把代码放这吧。
查看代码
#pragma GCC optimize(2)
#include<iostream>
using namespace std;
typedef long long ll;
char mp[505][505];
int f[505][505],g[505][505];
void solve()
{
int n,m,fail=0;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='U'||mp[i][j]=='D')cnt++;
f[i][j]=0;
g[i][j]=0;
}
if(cnt%2)
fail=1;
}
for(int i=1;i<=m;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
if(mp[j][i]=='L'||mp[j][i]=='R')cnt++;
if(cnt%2)
fail=1;
}
if(fail)
{
cout<<-1<<"\n";
return;
}
for(int i=1;i<=n;i++)
{
int la=0;
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='U')
{
if(f[i][f[i][j]]==j)continue;
if(la)
{
f[i][j]=la;
f[i][la]=j;
f[i+1][j]=la;
f[i+1][la]=j;
la=0;
}
else la=j;
}
}
if(la)
{
cout<<-1<<'\n';
return;
}
}
for(int i=1;i<=m;i++)
{
int la=0;
for(int j=1;j<=n;j++)
{
if(mp[j][i]=='L')
{
if(g[g[j][i]][i]==j)continue;
if(la)
{
g[j][i]=la;
g[la][i]=j;
g[j][i+1]=la;
g[la][i+1]=la;
la=0;
}
else la=j;
}
}
if(la)
{
cout<<-1<<'\n';
return;
}
}
char ans[505][505];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mp[i][j]=='.')
{
ans[i][j]='.';
}
else if(mp[i][j]=='L')
{
ans[i][j]='W';
ans[g[i][j]][j]='B';
}
else if(mp[i][j]=='U')
{
ans[i][j]='W';
ans[i][f[i][j]]='B';
}
else if(mp[i][j]=='R')
{
ans[g[i][j]][j]=ans[i][j-1];
if(ans[i][j-1]=='W')
ans[i][j]='B';
else
ans[i][j]='W';
}
else if(mp[i][j]=='D')
{
ans[i][f[i][j]]=ans[i-1][j];
if(ans[i-1][j]=='B')
ans[i][j]='W';
else ans[i][j]='B';
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<ans[i][j];
cout<<'\n';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)solve();
return 0;
}