Educational Codeforces Round 123 (Rated for Div. 2)（ABCDE）
A. Doors and Keys
题意：给定长度为6的字符串，问是否可以通关，其中
R
，
G
，
B
R，G，B
R，G，B为门，
r
，
g
，
b
r，g，b
r，g，b为钥匙。要获得对应钥匙才能开相应的门。
思路：直接用
m
a
p
<
c
h
a
r
,
i
n
t
>
map<char,int>
map<char,int>记录每个字符的位置，然后对应比较就行了。
#include<bits/stdc++.h>
using namespace std;
char s[10];
void solve(){
map<char,int>mp;
scanf("%s",s+1);
for(int i=1;i<=6;i++) mp[s[i]]=i;
if(mp['r']<mp['R']&&mp['g']<mp['G']&&mp['b']<mp['B']) puts("YES");
else puts("NO");
}
int main(){
int t;scanf("%d",&t);
while(t--) solve();
}
B. Anti-Fibonacci Permutation
题意：给一个数字n，要求输出n个长度为n的排列，保证每个序列中不存在
p
i
?
2
+
i
?
1
!
=
p
i
p_{i-2}+_{i-1}!=p_{i}
pi?2?+i?1?!=pi?
思路：我们将长度为n的序列倒过来，形式为
n
，
n
?
1
，
n
?
2...3
，
2
，
1
n，n-1，n-2...3，2，1
n，n?1，n?2...3，2，1,然后移动n次1的位置，每次去与前一位交换。就形成了n个符合题意的排列。
#include<bits/stdc++.h>
using namespace std;
int n,a[55];
void solve(){
scanf("%d",&n);
for(int i=n,j=1;i>=1;i--,j++) a[j]=i;
for(int i=n;i>=1;i--){
for(int j=1;j<=n;j++){
printf("%d%c",a[j],(j==n)?'\n':' ');
}
swap(a[i],a[i-1]);
}
}
int main(){
int t;scanf("%d",&t);
while(t--) solve();
}
C. Increase Subarray Sums
题意：给定长度为n的一个序列a，和一个值k，输出序列a中依次有x[0,n]个不同位置数+k,序列的最大子数组
思路：我们单独看每个x，发现其实就是找到一个最大子数组，然后根据子数组的长度len，来增加k的个数。
如果子数组长度小于x，那么我们选择的子数组其中所有位置都会加k
如果子数组长度大于x，那么我们选择的子数组其中只有len个位置会加k
同时我们预处理下选择不长度的子数组的初始最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5005;
ll n,x,pre[N],dp[N];
vector<ll>ans;
void solve(){
ans.clear();
scanf("%lld%lld",&n,&x);
for(ll i=1;i<=n;i++){
ll xx;scanf("%lld",&xx);
pre[i]=pre[i-1]+xx;
dp[i]=-1e18;
}
for(ll l=1;l<=n;l++){
for(ll r=l;r<=n;r++){
ll len=r-l+1;
dp[len]=max(dp[len],pre[r]-pre[l-1]);
}
}
dp[0]=0;
for(ll i=0;i<=n;i++){
ll mx=0;
for(ll j=0;j<=n;j++){
if(i>j) mx=max(mx,dp[j]+j*x);
else mx=max(mx,dp[j]+i*x);
}
ans.push_back(mx);
}
for(auto it:ans) printf("%lld ",it);
puts("");
}
int main(){
int t;scanf("%d",&t);
while(t--) solve();
}
D. Cross Coloring
题意：初始有一个n*m的全白矩阵，有k种颜色，q次操作后可以得到矩阵种类数。每次操作输入
x
i
,
y
i
x_{i},y_{i}
xi?,yi?，会将第
x
i
x_{i}
xi?行，第
y
i
y_{i}
yi?列涂上颜色，有颜色则直接覆盖。存在一个位置两个矩阵颜色不同则为不同矩阵
思路：发现有时候靠前的操作会被全部覆盖掉，所以我们从后往前统计，cnt记录有效操作数，每次如果行或列其中一个没有出现过，那么它将是一个有效操作,cnt++。答案为
k
c
n
t
k^cnt
kcnt
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
const ll mod=998244353;
ll n,m,k,q,x[N],y[N];
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void solve(){
scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
for(ll i=1;i<=q;i++) scanf("%lld%lld",&x[i],&y[i]);
ll cnt=0;
set<ll>row,col;
for(ll i=q;i>=1;i--){
bool flag=false;
if(!row.count(x[i])&&col.size()<m) flag=true;
if(!col.count(y[i])&&row.size()<n) flag=true;
if(flag) cnt++;
row.insert(x[i]);
col.insert(y[i]);
}
printf("%lld\n",ksm(k,cnt));
}
int main(){
int t;scanf("%d",&t);
while(t--) solve();
}
//题意：
//一个机器人在一个n*n的网格中，只能向右(R)或向下(D)走
//再保证不能走出网格，且完成所有初始指令，指令可以增加，如D可以增加为DD、DDD，R可以增加为RR、RRR。
//问最终最多可以经过多少格子
//思路：
//先记录出现了多少的D指令和R指令，如果只有其中一种指令，那么答案就是n
//否则，我们可以根据chax=n-nuD-1、chay=n-nuR-1,得到最多向下或向右再多拓展多少格
//我们记录不能到达点数。（具体看代码注释）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n;
char s[N];
void solve(){
scanf("%lld",&n);
scanf("%s",s+1);
ll nuD=0,nuR=0,len=strlen(s+1),sum=0;
for(ll i=1;i<=len;i++){
if(s[i]=='D') nuD++;
else nuR++;
}
if(nuD==0||nuR==0){printf("%lld\n",n);return;}
ll chax=n-nuD-1,x=1;
ll chay=n-nuR-1,y=1;
for(ll i=1;i<=len;i++){
if(s[i]=='D'){
if(y==1) sum+=n-1;//此时还在第1列，因为s[i]=='D',所以当前行的后面n-1列肯定无法经过 sum+=n-1
else sum+=n-y-chay;//已经离开第1列，说明出现过'R'，指令，可以向右拓展经过chay格，加上向右至少移动了y格，剩下的均无法到达
x++;//至少移动行数++
}
else{//同上理
if(x==1) sum+=n-1;
else sum+=n-x-chax;
y++;
}
}
printf("%lld\n",n*n-sum);
}
int main(){
int t;scanf("%d",&t);
while(t--) solve();
}