「ABC 197A」Rotate
Link.
略。
#include<bits/stdc++.h>
using namespace std;
int main(){
char a,b,c;cin>>a>>b>>c;cout<<b<<c<<a;
return 0;
}
「ABC 197B」Visibility
Link.
扫。
#include<bits/stdc++.h>
using namespace std;
int main(){
int h,w,x,y;cin>>h>>w>>x>>y;vector<string> a(h);--x,--y;
for(string &i:a)cin>>i;
int ans=0;
for(int i=x;~i;--i)if(a[i][y]=='.')++ans;/*,printf("(%d %d)
",i+1,y+1);*/else break;
for(int i=x;i<h;++i)if(a[i][y]=='.')++ans;/*,printf("(%d %d)
",i+1,y+1);*/else break;
for(int i=y;~i;--i)if(a[x][i]=='.')++ans;/*,printf("(%d %d)
",x+1,i+1);*/else break;
for(int i=y;i<w;++i)if(a[x][i]=='.')++ans;/*,printf("(%d %d)
",x+1,i+1);*/else break;
cout<<ans-3;
return 0;
}
「ABC 197C」ORXOR
Link.
二进制枚举暴力算。
#include<bits/stdc++.h>
using namespace std;
long long n,a[30],b[30];
int main(){
scanf("%lld",&n);for(long long i=1;i<=n;++i){scanf("%lld",&a[i]);}
long long up=(1<<n),ans=1e18;
for(long long i=0;i<=up;++i){
long long ct=1;
b[ct]=a[1];
for(long long j=2;j<=n;++j)if(((i>>(j-1))&1)^((i>>(j-2))&1))b[++ct]=a[j];else b[ct]|=a[j];
long long tmp=0;
for(long long j=1;j<=ct;++j)tmp^=b[j];
ans=min(ans,tmp);
}
printf("%lld
",ans);
return 0;
}
「ABC 197D」Opposite
Link.
数学题，不会，而且读不太懂题。
// Oops, something went wrong.
「ABC 197E」Traveler
Link.
这个题看起来就很 关路灯。
对于每一种颜色（这里的颜色是指我们已经收集完了上一种颜色，正在收集的颜色），我们不可能走过而不拾。
于是收完一种颜色后，我们一定是这种颜色的的最左 / 右边。
然后就可以 DP 了；设 (f_{i,0 ext{ or }1}) 为拾 (i)-th 颜色，在左 / 右，转移显然。
/*
Denote f[i][0/1] for the minimum time, that we finish collecting the i-th color and we're at the left/right (0/1) endpoint.
f[i][0]=min( f[las][0]+Dist( R[las],L[i] ),f[las][1]+Dist( L[las],L[i] ) )+R[i]-L[i];
f[i][1]=min( f[las][0]+Dist( R[las],R[i] ),f[las][1]+Dist( L[las],R[i] ) )+R[i]-L[i];
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=1e18;
int n;
LL f[200010][2],L[200010],R[200010];
int main()
{
scanf("%d",&n);
for( int i=1;i<=n;++i ) L[i]=INF,R[i]=-INF;
for( int i=1;i<=n;++i )
{
LL pos;
int color;
scanf( "%lld %d",&pos,&color );
L[color]=min( pos,L[color] );
R[color]=max( pos,R[color] );
}
#define Dist( x,y ) ( LL( abs( ( x )-( y ) ) ) )
for( int i=1,las=0;i<=n+1;++i )
{
if( L[i]!=INF )
{
f[i][0]=min( f[las][0]+Dist( R[las],L[i] ),f[las][1]+Dist( L[las],L[i] ) )+R[i]-L[i];
f[i][1]=min( f[las][0]+Dist( R[las],R[i] ),f[las][1]+Dist( L[las],R[i] ) )+R[i]-L[i];
las=i;
}
}
printf( "%lld
",f[n+1][1] );
return 0;
}
「ABC 197F」Construct a Palindrome
Link.
相当于是从 (1) 和 (n) 同时走，每次走字母一样的边，直接双向 BFS 即可。
#include<bits/stdc++.h>
using namespace std;
#define turn(c) ((c)-'a')
#define fs first
#define sc second
const int INF=1e9;
vector<int> suf[1010][26];
int n,m,ans=INF,vis[1010][1010];
struct node
{
int fs,sc,val;
node(int A=0,int B=0,int C=0){fs=A,sc=B,val=C;}
};
queue<node> q;
int main()
{
// freopen("in.in","r",stdin);
// freopen("my.out","w",stdout);
scanf("%d %d",&n,&m);
vis[1][n]=1;
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d %d",&x,&y);
char c=getchar();
while(c<'a' || c>'z') c=getchar();
suf[x][turn(c)].emplace_back(y);
suf[y][turn(c)].emplace_back(x);
}
q.emplace(node(1,n,0));
while(!q.empty())
{
int one=q.front().fs,ano=q.front().sc,lav=q.front().val;
q.pop();
if(lav==ans) return printf("%d
",ans<<1),0;
for(int i=0;i<26;++i)
{
for(int exone:suf[one][i])
{
for(int exano:suf[ano][i])
{
if(exone==ano || exano==one) return printf("%d
",lav<<1|1),0;
if(exone==exano) ans=lav+1;
if(!vis[exone][exano])
{
vis[exone][exano]=1;
q.emplace(node(exone,exano,lav+1));
}
}
}
}
}
printf("-1
");
return 0;
}