<span>Codeforces 1272 A-E</span>
Codeforces 1272 A-E
A Three Friends
直接枚举所有情况，共\(3\times 3\times 3=27\)种。
code
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
int main(){
//ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>q;
while(q--){
int a,b,c;
cin>>a>>b>>c;
int ans=abs(a-b)+abs(b-c)+abs(a-c);
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
for(int k=-1;k<=1;k++){
int x=a+i,y=b+j,z=c+k;
ans=min(ans,abs(x-y)+abs(y-z)+abs(x-z));
}
}
}
cout<<ans<<endl;
}
return 0;
}
B Snow Walking Robot
因为是无限大的网格，所以最简单的构造方法是走一个矩形框
注意要特判向任意方向走一步再走回起点的情况，样例中有。
code
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
char s[maxn];
int main(){
ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>q;
while(q--){
cin>>s+1;
int n=strlen(s+1);
int L=0,R=0,U=0,D=0;
for(int i=1;i<=n;i++){
if(s[i]=='L') ++L;
else if(s[i]=='R') ++R;
else if(s[i]=='U') ++U;
else ++D;
}
L=R=min(L,R);
U=D=min(U,D);
if(L&&U==0){
cout<<2<<endl;
cout<<"RL"<<endl;
}else if(U&&L==0){
cout<<2<<endl;
cout<<"DU"<<endl;
}else if(U==0||L==0){
cout<<0<<endl;
}else{
cout<<L*2+U*2<<endl;
for(int i=1;i<=L;i++){
cout<<'R';
}
for(int i=1;i<=D;i++){
cout<<'D';
}
for(int i=1;i<=L;i++){
cout<<'L';
}
for(int i=1;i<=D;i++){
cout<<'U';
}
cout<<endl;
}
}
return 0;
}
C Yet Another Broken Keyboard
在字符串s中所有不能打出的字母的位置作为隔板，隔出来的每个子串(设\(len\)为子串的长度)对答案的贡献即为\(len \times (len+1) /2\)。
code
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n,k;
char s[maxn],t[30];
int main(){
ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>n>>k;
cin>>s+1;
for(int i=1;i<=k;i++){
char c;
cin>>c;
t[c-'a']=1;
}
ll ans=0,cnt=0;
for(int i=1;i<=n;i++){
if(!t[s[i]-'a']){
ans+=cnt*(cnt+1)/2;
cnt=0;
}else ++cnt;
}
ans+=cnt*(cnt+1)/2;
cout<<ans<<endl;
return 0;
}
D Remove One Element
\(O(n)\)预处理出\(l[i]\)为\(i\)作为终点的最长严格递增子段，\(r[i]\)为\(i\)作为起始点的最长严格递增子段。
- 不删除一个元素，\(ans=max\{l[i]\},(1<=i<=n)\)。
- 删除一个元素，\(ans=max\{l[i-1]+r[i+1]\},(1<i<n\&\&a[i-1]<a[i+1])\)
code
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
int l[maxn],r[maxn];
int main(){
ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>a[i-1]) l[i]=l[i-1]+1;
else l[i]=1;
ans=max(ans,l[i]);
}
r[n]=1;
for(int i=n-1;i>=1;i--){
if(a[i]<a[i+1]) r[i]=r[i+1]+1;
else r[i]=1;
}
for(int i=2;i<n;i++){
if(a[i+1]>a[i-1]) ans=max(ans,l[i-1]+r[i+1]);
}
cout<<ans<<endl;
return 0;
}
E Nearest Opposite Parity
能发现若\(d[i+-a[i]]\)的值已确定，那么\(d[i]=min(d[i],d[i+-a[i]]+1)\)。
跟据这个性质我们以反边建图，所有边的边权都为1，以所有能一步到达奇偶性不同的点的点作为源点来跑最短路就行了(因为所有边权都为1，所以直接bfs也行)。
code
#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
vector<int>g[maxn];
int dis[maxn];
struct ppo{
int v,c;
bool operator <(const ppo &r) const{
return c>r.c;
}
};
int main(){
ios::sync_with_stdio(false);
//freopen("in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dis[i]=inf;
if(i-a[i]>=1){
if(a[i-a[i]]%2!=a[i]%2) dis[i]=1;
g[i-a[i]].pb(i);
}
if(i+a[i]<=n){
if(a[i+a[i]]%2!=a[i]%2) dis[i]=1;
g[i+a[i]].pb(i);
}
}
priority_queue<ppo>q;
for(int i=1;i<=n;i++){
if(dis[i]==1) q.push(ppo{i,dis[i]});
}
while(!q.empty()){
int u=q.top().v;q.pop();
for(int x:g[u]){
if(dis[u]+1<dis[x]){
dis[x]=dis[u]+1;
q.push(ppo{x,dis[x]});
}
}
}
for(int i=1;i<=n;i++){
if(dis[i]==inf) cout<<-1<<" ";
else cout<<dis[i]<<" ";
}
return 0;
}
腾讯公司福利 469人发布