Bayan 2015 Contest Warm Up
http://codeforces.com/contest/475
A - Bayan Bus
B - Strongly Connected City
C - Kamal-ol-molk's Painting
A. Bayan Bus
题意：输入人数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 ll long long
#define usll unsigned ll
#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 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 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
const double pi=acos(-1.0);
const double eps=1e-; string s[];
int k; int main(){
int i,j;
s[]="+------------------------+";
s[]="|#.#.#.#.#.#.#.#.#.#.#.|D|)";
s[]="|#.#.#.#.#.#.#.#.#.#.#.|.|";
s[]="|#.......................|";
s[]="|#.#.#.#.#.#.#.#.#.#.#.|.|)";
s[]="+------------------------+";
int len=s[].length();
RD(k);
while(k--){
bool flag=;
FOR(i,,len-){
FOR(j,,){
if(s[j][i]=='#'){
flag=;
s[j][i]='O';
break;
}
}
if(flag)break;
}
}
FOR(i,,){
cout<<s[i]<<endl;
}
return ;
}
B. Strongly Connected City
题意：城市由一堆单行线组成，给出一堆单行线的方向，判断是否每个交点能到达每个交点。
题解：从每个点出发暴力dfs啊！每个点出发最多每个点走一次，O(n^2)！
//#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 ll long long
#define usll unsigned ll
#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 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 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
const double pi=acos(-1.0);
const double eps=1e-; string s[];
int n,m; bool f[][];
int cnt; void dfs(int x,int y){
if(x< || x>=n || y< || y>=m || f[x][y])return;
//printf("(%d,%d) ",x,y);
f[x][y]=;
cnt++;
if(s[][x]=='>')dfs(x,y+);
else dfs(x,y-);
if(s[][y]=='v')dfs(x+,y);
else dfs(x-,y);
} bool farm(){
int i,j;
REP(i,n){
REP(j,m){
mz(f);
cnt=;
dfs(i,j);
if(cnt!=m*n)return ;
}
}
return ;
} int main(){
int i,j;
RD2(n,m);
cin>>s[]>>s[];
//cout<<s[0]<<'!'<<s[1]<<'!';
if(farm())puts("YES");
else puts("NO");
return ;
}
C. Kamal-ol-molk's Painting
题意：给出一个图，其中“X”是刷的，“.”是不能刷的。刷子是个矩形，刷的时候要从某个地方下笔，只能往右或者往下移动。问是否能用刷子刷出这个图，不能则输出-1，能则输出最小的刷子的面积。
题解：先找到最左上的X，当做起点。然后找两个轨迹：
优先往右其次往下，可以得到刷子右上角的轨迹。
优先往下其次往右，能得到刷子左下角的轨迹。
但这些轨迹的初始和结尾部分不是轨迹，真正是轨迹的只有中间部分。从哪里开始是轨迹，由刷子的形状决定。
有两种情况，一种是右上角的轨迹开始向下走的那一格，当做右上角的初始位置，左下角的初始位置暂定为起点，然后我们就开始两个轨迹同步动。
若两个轨迹的移动方向不同，则说明左下角的初始位置选得不对，将左下角轨迹的下标++，直到两种轨迹相同。（若++使得刷子面积变小，则说明到结尾处了，则不++，使其结束）
最后时刻，得到的左下角坐标和右上角坐标，就真正决定了刷子形状，检查一下轨迹中是否都符合这个形状，符合而且刷的格子数等于X的数量的话，就得到一种解。
上面说的这种是先找右上角起始位置，另一种是先找左下角的起始位置，为左下角的轨迹开始往右走的那一格。而右上角的初始位置暂定为起点。与上面说的类似，弄着弄着就得到另一种解。
上面这两种情况也可能只有一种有解或者都没解。
最后有解的话输出面积小的那个面积，没解则输出-1。
（总体来说特别难搞，我是结束之后再交才A的……）
代码：
//#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 ll long long
#define usll unsigned ll
#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 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 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
const double pi=acos(-1.0);
const double eps=1e-; pair<int,int> operator -(pair<int,int>x,pair<int,int>y) {
return mp(x.first-y.first,x.second-y.second);
} int n,m;
char a[][]; int cnt;
bool b[][]; inline bool in(const int &x,const int &y) {
return x>= && x<n && y>= && y<m;
} inline bool can(const int &x,const int &y) {
return (in(x,y)&&a[x][y]=='X');
} inline int mj(pair<int,int>x , pair<int,int>y) {
return (abs(x.first-y.first)+) * (abs(x.second-y.second)+);
} vector<pair<int,int> > v[];///右上角，左下角，右上角，左下角
int sz[]; int farm() {
if(cnt==)return ;
int i,j;
// REP(i,n){
// REP(j,m){
// printf("%c",a[i][j]);
// }
// puts("");
// }
REP(i,n) {
REP(j,m) {
if(a[i][j]=='X')break;
}
if(a[i][j]=='X')break;
}
int sx=i,sy=j;
int x=sx,y=sy;
//printf("%d,%d\n",sx,sy);
v[].clear();
while() {
v[].pb(mp(x,y));
int c1=can(x+,y),c2=can(x,y+),c3=can(x+,y+);
//printf("(%d,%d) %d,%d,%d %c\n",x,y,c1,c2,c3,a[x+1][y]);
if(c1&&c2&&!c3)return -;
if(!c1 && !c2)break;
if(c2)y++;
else if(c1)x++;
}
x=sx;
y=sy;
v[].clear();
while() {
//printf("[%d,%d]\n",x,y);
v[].pb(mp(x,y));
int c1=can(x+,y),c2=can(x,y+),c3=can(x+,y+);
if(c1&&c2&&!c3)return -;
if(!c1 && !c2)break;
if(c1)x++;
else if(c2)y++;
}
if(v[].back()!=v[].back())return -;
int ex=v[].back().first,ey=v[].back().second; x=ex;
y=ey;
v[].clear();
while() {
//printf("[%d,%d]\n",x,y);
v[].pb(mp(x,y));
int c1=can(x-,y),c2=can(x,y-),c3=can(x-,y-);
if(c1&&c2&&!c3)return -;
if(!c1 && !c2)break;
if(c1)x--;
else if(c2)y--;
} x=ex;
y=ey;
v[].clear();
while() {
//printf("[%d,%d]\n",x,y);
v[].pb(mp(x,y));
int c1=can(x-,y),c2=can(x,y-),c3=can(x-,y-);
if(c1&&c2&&!c3)return -;
if(!c1 && !c2)break;
if(c2)y--;
else if(c1)x--;
}
//printf("WOW!\n");
if(v[].size()!=v[].size() || v[].size()!=v[].size())return -;
REP(i,)sz[i]=v[i].size();
int t=sz[]-;
REP(i,sz[]) {
if(v[][i]!=v[][t-i])return -;
}
t=sz[]-;
REP(i,sz[]) {
if(v[][i]!=v[][t-i])return -;
} //printf("WA!"); t=;
while(t<sz[]) {
if(t+<sz[] && v[][t+].first!=v[][t].first)break;
t++;
}
int st=t;
int t2=;
pair<int,int>cha=v[][t]-v[][t2];
while(t<sz[] && t2<sz[] && v[][t]-v[][t2] == cha) {
while(t2<sz[] && t<sz[]) {
if(t2+<sz[] && t+<sz[] && (v[][t2+]-v[][t2]!=v[][t+]-v[][t])
&& mj(v[][t],v[][t2+]) > mj(v[][t],v[][t2]))
t2++;
else break;
}
cha=v[][t]-v[][t2];
//printf("%d,%d %d,%d\n",v[0][t].first,v[0][t].second,v[1][t2].first,v[1][t2].second);
t++;
t2++;
} mz(b);
bool fail=;
int cnt2=;
t--,t2--;
while(t>=st) {
if(cha!=v[][t]-v[][t2]){
//printf("cha!%d,%d %d,%d\n",v[0][t].first,v[0][t].second,v[1][t2].first,v[1][t2].second);
fail=;break;}
int rx=v[][t2].first , lx=v[][t].first;
int ry=v[][t].second , ly=v[][t2].second;
FOR(i,lx,rx) {
FOR(j,ly,ry) {
if(a[i][j]!='X') {
fail=;
break;
}
if(b[i][j])continue;
b[i][j]=;
cnt2++;
}
if(fail)break;
}
if(fail)break;
t--;
t2--;
}
vector<int>re;
//printf("%d %d %d\n",fail,cnt2,cnt);
if(!fail && cnt2==cnt) {
//printf("!1\n");
re.pb((abs(cha.first)+)*(abs(cha.second)+));
}
///上面那段复制过来改的！要错很可能是这里错
t=;
while(t<sz[]) {
if(t+<sz[] && v[][t+].second!=v[][t].second)break;
t++;
}
st=t;
t2=;
cha=v[][t2]-v[][t];
while(t<sz[] && t2<sz[] && v[][t2]-v[][t] == cha) {
while(t<sz[] && t2<sz[]) {
if(t2+<sz[] && t+<sz[] && (v[][t+]-v[][t]!=v[][t2+]-v[][t2])
&& mj(v[][t2+],v[][t]) > mj(v[][t2],v[][t]))
t2++;
else break;
}
//printf("[%d,%d] [%d,%d]\n",v[0][t2].first,v[0][t2].second,v[1][t].first,v[1][t].second);
cha=v[][t2]-v[][t];
t++;
t2++;
}
mz(b);
cnt2=;
fail=;
t--,t2--;
while(t>=st){
if(v[][t2]-v[][t] != cha){fail=;break;}
int rx=v[][t].first , lx=v[][t2].first;
int ry=v[][t2].second , ly=v[][t].second;
FOR(i,lx,rx) {
FOR(j,ly,ry) {
if(a[i][j]!='X') {
fail=;
break;
}
if(b[i][j])continue;
b[i][j]=;
cnt2++;
}
if(fail)break;
}
if(fail)break;
t--;
t2--;
} if(!fail && cnt2==cnt) {
// printf("!2\n");
re.pb((abs(cha.first)+)*(abs(cha.second)+));
}
sort(re.begin(),re.end());
if(re.size()!=)return re[];
else return -;
} int main() {
int i,j;
cnt=;
RD2(n,m);
REP(i,n) {
REP(j,m) {
scanf(" %c",&a[i][j]);
if(a[i][j]=='X')cnt++;
}
}
printf("%d\n",farm());
return ;
}
![P1941 [NOIP2014 提高组] 飞扬的小鸟 题解](https://www.kunjuke.com/file/css/thumb/8.jpg/280-180.jpg)
![P1880 [NOI1995] 石子合并 题解](https://www.kunjuke.com/file/css/thumb/4.jpg/280-180.jpg)
![P5020 [NOIP2018 提高组] 货币系统 题解](https://www.kunjuke.com/file/css/thumb/6.jpg/280-180.jpg)
