A
描述:给出一串数,可以互换任意两个数的位置一次,求最大的数和最小的数的最大距离.
分析:找到最大的数和最小的数的位置,求右边的数到左端点的距离和左边的数到右端点的距离.
#include <bits/stdc++.h>
using namespace std; const int maxn=+,INF=0x7fffffff;
int n,M1,M2,m1,m2;
int a[maxn]; int main(){
scanf("%d",&n);
M1=INF,M2=-INF;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]<M1) M1=a[i], m1=i;
if(a[i]>M2) M2=a[i], m2=i;
}
if(m1>m2) swap(m1,m2);
int ans=max(n-m1,m2-);
printf("%d\n",ans);
}
B(模拟)
描述:酒杯落在一起,长得和数字三角形一样,每分钟倒一杯酒,满了会向两边流且流得一样多,问t分钟后有多少酒杯满了.
分析:模拟,一次性倒t杯酒(我sb地一杯一杯倒...TLE了好久).
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,t;
double a[maxn*maxn]; int main(){
scanf("%d%d",&n,&t);
a[]=t;
int ans=;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++){
int x=(i-)*i/+j;
if(a[x]>=){
ans++;
a[(i*i+i)/+j]+=(a[x]-)/;
a[(i*i+i)/+j+]+=(a[x]-)/;
}
}
printf("%d\n",ans);
return ;
}
C(尺取法)
描述:给出一个由a,b组成的字符串,最多能改变k个字符,问最多有多少相同的字符串连在一起.
分析:尺取法.注意k=0的情况.
#include <bits/stdc++.h>
using namespace std; const int maxn=+;
int n,k;
int a[maxn]; void solve(){
int l=,r=,rem=k,ans=;
while(l<=n&&r<=n){
if(a[r]==){
while(rem==&&l<r)
if(a[l++]==) rem++;
if(rem) rem--;
else { l++; r++; continue; }
}
ans=max(ans,r-l+);
r++;
}
l=; r=; rem=k;
while(l<=n&&r<=n){
if(a[r]==){
while(rem==&&l<r)
if(a[l++]==) rem++;
if(rem) rem--;
else { l++; r++; continue; }
}
ans=max(ans,r-l+);
r++;
}
printf("%d\n",ans);
}
void init(){
scanf("%d%d\n",&n,&k);
for(int i=;i<=n;i++){
char c; c=getchar();
if(c=='b') a[i]=;
}
}
int main(){
init();
solve();
return ;
}
D(最短路+宽搜)
描述:一个迷宫,每个点可以通向四个方向中的一部分,只有两两相通的点才能走,也可以花费时间把所有点通向的方向顺时针旋转90度.求起点到终点花费的最短时间.
分析:一共就4张图,分别预处理出来.在一个点,要么就在原来的图上继续跑,要么走到顺时针旋转90度之后的图上去.(不看题解的我TLE).
#include <bits/stdc++.h>
using namespace std; const int maxn=+; int n,m,ans,xs,ys,xt,yt,cnt;
int head[maxn*maxn*];
bool vis[maxn*maxn*];
bool t[maxn][maxn][];
struct edge{
int to,next;
edge(int to=,int next=):to(to),next(next){}
}g[maxn*maxn**];
struct node{
int x,step;
node(int x=,int step=):x(x),step(step){}
};
inline int idx(int x,int y,int z){ return z*n*m+(x-)*m+y; }
bool tag(int id){
for(int i=;i<;i++)
if(idx(xt,yt,i)==id) return true;
return false;
}
void add_edge(int u,int v){
g[++cnt]=edge(v,head[u]); head[u]=cnt;
g[++cnt]=edge(u,head[v]); head[v]=cnt;
}
void add_edge2(int u,int v){
g[++cnt]=edge(v,head[u]); head[u]=cnt;
}
void bfs(){
queue <node> q;
q.push(node(idx(xs,ys,),));
while(!q.empty()){
node t=q.front(); q.pop();
int x=t.x,step=t.step;
if(tag(x)){
ans=step;
return;
}
for(int i=head[x];i;i=g[i].next){
int y=g[i].to;
if(vis[y]) continue;
vis[y]=true;
q.push(node(y,step+));
}
}
}
void init(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
char c; while(c=getchar(), c=='\n');
if(c=='+') t[i][j][]=t[i][j][]=t[i][j][]=t[i][j][]=true;
else if(c=='-') t[i][j][]=t[i][j][]=true;
else if(c=='|') t[i][j][]=t[i][j][]=true;
else if(c=='^') t[i][j][]=true;
else if(c=='>') t[i][j][]=true;
else if(c=='v') t[i][j][]=true;
else if(c=='<') t[i][j][]=true;
else if(c=='U') t[i][j][]=t[i][j][]=t[i][j][]=true;
else if(c=='R') t[i][j][]=t[i][j][]=t[i][j][]=true;
else if(c=='D') t[i][j][]=t[i][j][]=t[i][j][]=true;
else if(c=='L') t[i][j][]=t[i][j][]=t[i][j][]=true;
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
int x,y;
x=i; y=j+;//R
if(x<=n&&y<=m){
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
}
x=i+; y=j;//D
if(x<=n&&y<=m){
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
if(t[i][j][]&&t[x][y][]) add_edge(idx(i,j,),idx(x,y,));
}
for(int k=;k<;k++) add_edge2(idx(i,j,k),idx(i,j,(k+)%));
}
scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
ans=-;
}
int main(){
init();
bfs();
printf("%d\n",ans);
return ;
}
E
并没有看...