Codeforces Round #354 (Div. 2)
Problems
| # | Name | ||
|---|---|---|---|
| A |
standard input/output
1 s, 256 MB |
|
|
| B |
standard input/output
1 s, 256 MB |
|
|
| C |
standard input/output
1 s, 256 MB |
|
|
| D |
standard input/output
3 s, 256 MB |
|
|
| E |
standard input/output
1 s, 256 MB |
|
题意：允许你交换一次任意两个数位置，要使最大的数和最小的数的距离最大，输出最大值
题解：
大水题，就先找到最小的和最大的，把其中一个交换到尽头。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int main() {
int i;
int x;
int q,w,n;
RD(n);
REP(i,n){
RD(x);
if(x==n)q=i;
if(x==)w=i;
}
if(q>w)swap(q,w);
WN(max(n-q-, w));
return ;
}
题意：摆了一个高脚杯金字塔，每秒钟往最上面倒一整杯，一杯满了会往两边溢出流到下面两个杯子，求n层高的金字塔，倒水k分钟后，有多少杯是满的。
题解：
直接把k分钟的全倒进最上面的杯子，然后模拟流下去就行。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int n,t; int farm(){
double a[][];
int i,j;
REP(i,)REP(j,)a[i][j]=0.0;
a[][] = t;
int cnt=;
FOR(i,,n){
FOR(j,,i){
if(a[i][j]>1.0){
double t = (a[i][j] - 1.0)/2.0;
a[i+][j] += t;
a[i+][j+] += t;
a[i][j]=1.0;
}
if(a[i][j]>=1.0)cnt++;
}
}
// FOR(i,1,n){
// FOR(j,1,i){
// printf("%f ",a[i][j]);
// }
// puts("");
// }
return cnt;
} int main() {
int i;
RD2(n,t);
WN(farm());
return ;
}
题意：给出一个由a和b两个字母组成的字符串，最多修改其中k个，使得其中最长的连续同一字母子串最长，求最长的长度。
题解：
用双端队列，以a为本体扫一遍，再以b为本体扫一遍。以a为本体的时候，扫到b的话，就加到双端队列里，如果双端队列里超过k个，就从左端弹出，保持里面剩k个。记录全a子序列的区间左端，弹出的时候更新 区间左端L = 弹出的元素的位置+1。时刻更新ans = max(ans , R-L+1)，R为当前扫到的位置。
只用扫两遍，O(n)。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int n,k;
char s[MAXN]; int gank(char c){
deque<int> d;
int l=;
int cnt=;
int re=;
int i;
REP(i,n){
if(s[i]==c){
d.push_back(i);
if(cnt==k){
l = d.front() + ;
d.pop_front();
}else cnt++;
}
re = max(re, i-l+);
}
return re;
} int farm(){
return max(gank('a'), gank('b'));
} int main() {
int i;
RD2(n,k);
scanf(" %s",s);
WN(farm());
return ;
}
题意：给出一个n*m的地图，英雄从(xt,yt)出发，要到达敌人所在地(xm,ym)。地图每个格子有设定：
^>v<代表向箭头方向有门，其他方向没门；
URDL代表某个方向没门，其他方向都有门，例如U，代表上面没门，其他3个方向各有一个门。
-|代表左右有门、上下有门。
+代表4个门，*代表没有门。
每分钟，英雄可以进行一项操作：
A.将所有方块顺时针转90度。
B.移动到相邻方块，要求自己方块到它的方向有门，它的方块到自己的方向也有门。
给出地图、英雄位置、敌人位置，求英雄到达敌人的最少分钟数，或者不能到达输出-1。
题解：
走迷宫，典型的广搜题。广搜每个节点有5种扩展：旋转90度、往4个方向走。注意记录某个点是否走过，需要save[x][y][z]，x,y为该点坐标，z为旋转的次数，z<=3。
比较难写的是判断某个点能否向某个方向走一步，可以写到一个函数里can(x,y,z,j)，(x,y)为当前坐标，z为当前旋转了几次(0~3)，j为方向，我设定方向0123代表上右下左。
方块旋转、门的位置可以预处理，记到一个数组里，例如rot['<'][2] = '>'，代表<符号旋转2次得到>符号。
例如door['-'] = "0101"，代表-符号的门开在右、左。
这块写好了就无敌了。
我就写错了一个符号，卧槽，就一直wa6，比赛结束以后发现一个-写成了|，改了就过了。这种题要认真点写啊。
（可恶，刚才看官方题解，哇，直接预处理出4种方向的地图，a[x][y][z]，就是简单的三维地图bfs了，卧槽，我怎么没想到）
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ;
const int gx[] = {-,,,};
const int gy[] = {,,,-};
int n,m;
char s[MAXN][MAXN];
int xt,yt,xm,ym; int save[MAXN][MAXN][];
char rota[][];
char door[][];
void init() {
int i,j;
MF1(save);
REP(i,) {
rota['+'][i]='+';
rota['*'][i]='*';
}
for(i=; i<; i+=) {
rota['-'][+i]='-';
rota['|'][+i]='|';
rota['-'][+i]='|';
rota['|'][+i]='-';
}
char q[] = "^>v<";
char w[] = "URDL";
REP(i,) {
REP(j,) {
int l=(i+j)%;
rota[q[i]][j] = q[l];
rota[w[i]][j] = w[l];
}
}
REP(i,) {
door['+'][i]='';
door['*'][i]='';
door['|'][i]=door['-'][i]='';
}
door['|'][]=door['|'][] = '';
door['-'][]=door['-'][] ='';
REP(i,)REP(j,) {
door[q[i]][j]='';
door[w[i]][j]='';
}
REP(i,) {
door[q[i]][i]='';
door[w[i]][i]='';
}
} char rot(char x, int n) {
return rota[x][n%];
} bool cango(char now , char next, int j) {
int k = (j+)%;
// door[now][4]='\0';
// door[next][4]='\0';
// printf("%c,%c,%s,%s,%d,%d,%c,%c\n",now,next,door[now],door[next],j,k,door[now][j],door[next][k]);
if (door[now][j]=='' && door[next][k]=='')return true;
else return false;
} bool can(int x,int y,int z,int j) {
int xx=x+gx[j];
int yy=y+gy[j];
if(xx< || xx>=n || yy< || yy>=m)return false;
char now = s[x][y];
char next = s[xx][yy];
// printf("%c,%c %d->",now,next,z);
now = rot(now, z);
next = rot(next,z);
// printf("%c,%c\n",now,next);
if(cango(now,next,j))return true;
else return false;
} struct Node {
int x,y,z;
int step;
Node() {}
Node(int _x,int _y,int _z,int _s) {
x=_x;
y=_y;
z=_z;
step=_s;
}
}; int farm() {
deque<Node> d;
int i,j;
d.clear();
d.push_back(Node(xt,yt,,));
save[xt][yt][]=;
while(!d.empty()) {
Node now = d.front();
int x=now.x, y=now.y, z=now.z, step=now.step;
d.pop_front();
// if(x==19 && z==1)printf("%d,%d,%d,%d\n",x,y,z,step);
if(x==xm && y==ym)return step; int k = (z+)%;
if(save[x][y][k]==- || save[x][y][k]>step+) {
d.push_back(Node(x, y, k, step+));
save[x][y][k]=step+;
} REP(i,) {
int xx=x+gx[i];
int yy=y+gy[i];
// printf("%d,%d,%d,%d,%d,[%d,%d,%d],%d\n",x,y,z,i,can(x,y,z,i),xx,yy,z,save[xx][yy][z]);
if(can(x,y,z,i)&&(save[xx][yy][z]==- || save[xx][yy][z]>step+)) {
d.push_back(Node(xx,yy,z,step+));
save[xx][yy][z]=step+;
}
}
}
return -;
} int main() {
int i;
init();
RD2(n,m);
REP(i,n)scanf(" %s",s[i]);
RD2(xt,yt);
RD2(xm,ym);
xt--;
yt--;
xm--;
ym--;
WN(farm());
return ;
}
E比赛时没空看，结束后看了，大概是说一个那样的式子，两个玩家交替操作，要是能使式子P(x) =B(x)Q(x)，就算人类胜。其中B(x)是任意一种那样的式子，Q(x)=x-k，k为给出的数。给出当前局面，到人类动，问人类是否有必胜策略。好像有100多人过pre，最后只有五十多个ac，好像有点难，我还是先不看了。
不懂能不能抢到百度之星t恤啊！