Screamers in the Storm
题意：
狼向右走，在到最右部后会跳至最左面，然后接着向右走，周遭往复。
羊向下走，到头后和狼同理。
场地规则： 地上本是秃地，记作“ . ”
三回合后会长草，草地记作“#”，
羊会吃草，吃掉三回合后草会重新长，
狼会吃羊，羊死后会标记为“ * ”
如果羊 5 回合没吃草会被饿死，狼则为 10 回合，
死后都会被记作“ *”
标记为“ * ”的砖块不会再长草。
输出T回合后的场地。
思路：
感觉题目里有很多细节没有解释清楚：
每一轮的顺序是先进行狼和羊的行走，再看狼羊草能不能互相吃掉，再看草会不会长出来。
如果这一轮里羊把草吃掉，那么这一轮的草是不会生长的。
对于最后答案的输出，优先级为狼/羊>草
如果起初这个格子有狼/羊的话，草也是正常生长的。
大体思路就是先将狼跟羊的位置跟没有吃到东西的回合数用结构体存起来。
每一轮，先进行狼跟羊的移动，再看三者之间能不能吃掉，再看草的生长问题。
代码：
int n,m,t; char s[110][110]; int c[110][110]; int sheep[110][110],wolf[110][110]; struct node{ int x,y,val;///val表示有几回合没有吃到东西了 }; vector<node>sheeps,wolfs; bool vis_sheep[maxn],vis_wolf[maxn]; int main(){ t=read;n=read,m=read; rep(i,1,n) cin>>s[i]+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(s[i][j]=='S') sheeps.push_back({i,j,0}),s[i][j]='.'; else if(s[i][j]=='W') wolfs.push_back({i,j,0}),s[i][j]='.'; for(int i=0;i<sheeps.size();i++) vis_sheep[i]=1; for(int i=0;i<wolfs.size();i++) vis_wolf[i]=1; //cout<<sheeps.size()<<" "<<wolfs.size()<<endl; while(t--){ for(int i=0;i<sheeps.size();i++)//羊的移动 if(vis_sheep[i]){ //这个羊还活着 int nx=sheeps[i].x+1,ny=sheeps[i].y; if(nx==n+1) nx=1; sheeps[i].x=nx;sheeps[i].y=ny; //cout<<i<<" "<<nx<<" "<<ny<<endl; } for(int i=0;i<wolfs.size();i++)//狼的移动 if(vis_wolf[i]){ int nx=wolfs[i].x,ny=wolfs[i].y+1; if(ny==m+1) ny=1; wolfs[i].x=nx;wolfs[i].y=ny; // cout<<i<<" "<<nx<<" "<<ny<<endl; } // puts("+++++++++++++++++"); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int flag_sheep=-1,flag_wolf=-1; for(int k=0;k<sheeps.size();k++) if(vis_sheep[k]&&i==sheeps[k].x&&j==sheeps[k].y) flag_sheep=k; for(int k=0;k<wolfs.size();k++) if(vis_wolf[k]&&i==wolfs[k].x&&j==wolfs[k].y) flag_wolf=k; if(flag_wolf!=-1&&flag_sheep!=-1){ //狼吃羊 vis_sheep[flag_sheep]=0;//羊死了 s[i][j]='*';//草地变成尸体 wolfs[flag_wolf].val=0; } else if(flag_wolf!=-1&&flag_sheep==-1){ wolfs[flag_wolf].val++; if(wolfs[flag_wolf].val==10){ vis_wolf[flag_wolf]=0; s[i][j]='*'; } } else if(flag_wolf==-1&&flag_sheep!=-1){ if(s[i][j]=='#'){ s[i][j]='.';c[i][j]=-1;//羊吃草 sheeps[flag_sheep].val=0; } else{ sheeps[flag_sheep].val++; if(sheeps[flag_sheep].val==5){ vis_sheep[flag_sheep]=0; s[i][j]='*'; } } } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ c[i][j]=min(3,c[i][j]+1); if(c[i][j]==3){ if(s[i][j]!='*') s[i][j]='#';//这个地方长草 } } // for(int i=1;i<=3;i++) cout<<s[i][1]<<" "<<c[i][1]<<endl; // puts("++++++++++++++"); } for(int i=0;i<sheeps.size();i++) if(vis_sheep[i]){ int x=sheeps[i].x,y=sheeps[i].y; // cout<<i<<" "<<x<<" "<<y<<endl; s[x][y]='S'; } for(int i=0;i<wolfs.size();i++) if(vis_wolf[i]){ int x=wolfs[i].x,y=wolfs[i].y; s[x][y]='W'; //cout<<i<<" "<<x<<" "<<y<<endl; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(c[i][j]==3){ if(s[i][j]=='.') s[i][j]='#'; } for(int i=1;i<=n;i++){ cout<<(s[i]+1)<<endl; } return 0; }
Beer Coasters
题意：
求圆跟矩形的面积交
思路：
套了多边形和圆面积交的板子，注意矩形的保存要按照端点顺时针或逆时针来进行。
代码：
// `计算几何模板` const double eps = 1e-6; const double pi = acos(-1.0); const int maxp = 1010; //`Compares a double to zero` int sgn(double x){ if(fabs(x) < eps)return 0; if(x < 0)return -1; else return 1; } //square of a double inline double sqr(double x){return x*x;} struct Point{ double x,y; Point(){} Point(double _x,double _y){ x = _x; y = _y; } void input(){ scanf("%lf%lf",&x,&y); } void output(){ printf("%.2f %.2f\n",x,y); } bool operator == (Point b)const{ return sgn(x-b.x) == 0 && sgn(y-b.y) == 0; } bool operator < (Point b)const{ return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x; } Point operator -(const Point &b)const{ return Point(x-b.x,y-b.y); } //叉积 double operator ^(const Point &b)const{ return x*b.y - y*b.x; } //点积 double operator *(const Point &b)const{ return x*b.x + y*b.y; } //返回长度 double len(){ return hypot(x,y);//库函数 } //返回长度的平方 double len2(){ return x*x + y*y; } //返回两点的距离 double distance(Point p){ return hypot(x-p.x,y-p.y); } Point operator +(const Point &b)const{ return Point(x+b.x,y+b.y); } Point operator *(const double &k)const{ return Point(x*k,y*k); } Point operator /(const double &k)const{ return Point(x/k,y/k); } //`计算pa 和 pb 的夹角` //`就是求这个点看a,b 所成的夹角` //`测试 LightOJ1203` double rad(Point a,Point b){ Point p = *this; return fabs(atan2( fabs((a-p)^(b-p)),(a-p)*(b-p) )); } //`化为长度为r的向量` Point trunc(double r){ double l = len(); if(!sgn(l))return *this; r /= l; return Point(x*r,y*r); } //`逆时针旋转90度` Point rotleft(){ return Point(-y,x); } //`顺时针旋转90度` Point rotright(){ return Point(y,-x); } //`绕着p点逆时针旋转angle` Point rotate(Point p,double angle){ Point v = (*this) - p; double c = cos(angle), s = sin(angle); return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c); } }; struct Line{ Point s,e; Line(){} Line(Point _s,Point _e){ s = _s; e = _e; } bool operator ==(Line v){ return (s == v.s)&&(e == v.e); } //`根据一个点和倾斜角angle确定直线,0<=angle<pi` Line(Point p,double angle){ s = p; if(sgn(angle-pi/2) == 0){ e = (s + Point(0,1)); } else{ e = (s + Point(1,tan(angle))); } } //ax+by+c=0 Line(double a,double b,double c){ if(sgn(a) == 0){ s = Point(0,-c/b); e = Point(1,-c/b); } else if(sgn(b) == 0){ s = Point(-c/a,0); e = Point(-c/a,1); } else{ s = Point(0,-c/b); e = Point(1,(-c-a)/b); } } void input(){ s.input(); e.input(); } void adjust(){ if(e < s)swap(s,e); } //求线段长度 double length(){ return s.distance(e); } //`返回直线倾斜角 0<=angle<pi` double angle(){ double k = atan2(e.y-s.y,e.x-s.x); if(sgn(k) < 0)k += pi; if(sgn(k-pi) == 0)k -= pi; return k; } //`点和直线关系` //`1 在左侧` //`2 在右侧` //`3 在直线上` int relation(Point p){ int c = sgn((p-s)^(e-s)); if(c < 0)return 1; else if(c > 0)return 2; else return 3; } // 点在线段上的判断 bool pointonseg(Point p){ return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0; } //`两向量平行(对应直线平行或重合)` bool parallel(Line v){ return sgn((e-s)^(v.e-v.s)) == 0; } //`两线段相交判断` //`2 规范相交` //`1 非规范相交` //`0 不相交` int segcrossseg(Line v){ int d1 = sgn((e-s)^(v.s-s)); int d2 = sgn((e-s)^(v.e-s)); int d3 = sgn((v.e-v.s)^(s-v.s)); int d4 = sgn((v.e-v.s)^(e-v.s)); if( (d1^d2)==-2 && (d3^d4)==-2 )return 2; return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) || (d2==0 && sgn((v.e-s)*(v.e-e))<=0) || (d3==0 && sgn((s-v.s)*(s-v.e))<=0) || (d4==0 && sgn((e-v.s)*(e-v.e))<=0); } //`直线和线段相交判断` //`-*this line -v seg` //`2 规范相交` //`1 非规范相交` //`0 不相交` int linecrossseg(Line v){ int d1 = sgn((e-s)^(v.s-s)); int d2 = sgn((e-s)^(v.e-s)); if((d1^d2)==-2) return 2; return (d1==0||d2==0); } //`两直线关系` //`0 平行` //`1 重合` //`2 相交` int linecrossline(Line v){ if((*this).parallel(v)) return v.relation(s)==3; return 2; } //`求两直线的交点` //`要保证两直线不平行或重合` Point crosspoint(Line v){ double a1 = (v.e-v.s)^(s-v.s); double a2 = (v.e-v.s)^(e-v.s); return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)); } //点到直线的距离 double dispointtoline(Point p){ return fabs((p-s)^(e-s))/length(); } //点到线段的距离 double dispointtoseg(Point p){ if(sgn((p-s)*(e-s))<0 || sgn((p-e)*(s-e))<0) return min(p.distance(s),p.distance(e)); return dispointtoline(p); } //`返回线段到线段的距离` //`前提是两线段不相交，相交距离就是0了` double dissegtoseg(Line v){ return min(min(dispointtoseg(v.s),dispointtoseg(v.e)),min(v.dispointtoseg(s),v.dispointtoseg(e))); } //`返回点p在直线上的投影` Point lineprog(Point p){ return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) ); } //`返回点p关于直线的对称点` Point symmetrypoint(Point p){ Point q = lineprog(p); return Point(2*q.x-p.x,2*q.y-p.y); } }; //圆 struct circle{ Point p;//圆心 double r;//半径 circle(){} circle(Point _p,double _r){ p = _p; r = _r; } circle(double x,double y,double _r){ p = Point(x,y); r = _r; } bool operator == (circle v){ return (p==v.p) && sgn(r-v.r)==0; } bool operator < (circle v)const{ return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0)); } //面积 double area(){ return pi*r*r; } //周长 double circumference(){ return 2*pi*r; } //`点和圆的关系` //`0 圆外` //`1 圆上` //`2 圆内` int relation(Point b){ double dst = b.distance(p); if(sgn(dst-r) < 0)return 2; else if(sgn(dst-r)==0)return 1; return 0; } //`直线和圆的关系` //`比较的是圆心到直线的距离和半径的关系` int relationline(Line v){ double dst = v.dispointtoline(p); if(sgn(dst-r) < 0)return 2; else if(sgn(dst-r) == 0)return 1; return 0; } //`求直线和圆的交点，返回交点个数` int pointcrossline(Line v,Point &p1,Point &p2){ if(!(*this).relationline(v))return 0; Point a = v.lineprog(p); double d = v.dispointtoline(p); d = sqrt(r*r-d*d); if(sgn(d) == 0){ p1 = a; p2 = a; return 1; } p1 = a + (v.e-v.s).trunc(d); p2 = a - (v.e-v.s).trunc(d); return 2; } //`求圆和三角形pab的相交面积` //`测试：POJ3675 HDU3982 HDU2892` double areatriangle(Point a,Point b){ if(sgn((p-a)^(p-b)) == 0)return 0.0; Point q[5]; int len = 0; q[len++] = a; Line l(a,b); Point p1,p2; if(pointcrossline(l,q[1],q[2])==2){ if(sgn((a-q[1])*(b-q[1]))<0)q[len++] = q[1]; if(sgn((a-q[2])*(b-q[2]))<0)q[len++] = q[2]; } q[len++] = b; if(len == 4 && sgn((q[0]-q[1])*(q[2]-q[1]))>0)swap(q[1],q[2]); double res = 0; for(int i = 0;i < len-1;i++){ if(relation(q[i])==0||relation(q[i+1])==0){ double arg = p.rad(q[i],q[i+1]); res += r*r*arg/2.0; } else{ res += fabs((q[i]-p)^(q[i+1]-p))/2.0; } } return res; } }; struct polygon{ int n; Point p[maxp]; Line l[maxp]; void input(int _n){ n = _n; for(int i = 0;i < n;i++) p[i].input(); } void add(Point q){ p[n++] = q; } void getline(){ for(int i = 0;i < n;i++){ l[i] = Line(p[i],p[(i+1)%n]); } } struct cmp{ Point p; cmp(const Point &p0){p = p0;} bool operator()(const Point &aa,const Point &bb){ Point a = aa, b = bb; int d = sgn((a-p)^(b-p)); if(d == 0){ return sgn(a.distance(p)-b.distance(p)) < 0; } return d > 0; } }; //`多边形和圆交的面积` //`测试：POJ3675 HDU3982 HDU2892` double areacircle(circle c){ double ans = 0; for(int i = 0;i<=n-1;i++){ int j = (i+1)%n; if(sgn( (p[j]-c.p)^(p[i]-c.p) ) >= 0) ans += c.areatriangle(p[i],p[j]); else ans -= c.areatriangle(p[i],p[j]); } return fabs(ans); } }; //`AB X AC` double cross(Point A,Point B,Point C){ return (B-A)^(C-A); } //`AB*AC` double dot(Point A,Point B,Point C){ return (B-A)*(C-A); } int main(){ double x,y,r; cin>>x>>y>>r; circle c={x,y,r}; double x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; polygon tp; tp.n=4; tp.p[0]={x1,y1}; tp.p[1]={x1,y2}; tp.p[2]={x2,y2}; tp.p[3]={x2,y1}; printf("%.4f\n",tp.areacircle(c)); return 0; }
Beer Can Game
题意：
给定两个字符串，字符串仅包含数字和小写字母。可以进行如下操作：
插入：可以向一个字符串中插入一个字符。
兑换：如果某一位是数字 x，那么这 x 可以兑换为任意 x 个小写字母（必须兑换！）
删除：可以选定某一位并删除该位置上的小写字母。
输出最小的操作次数，可以使得这两个字符串相等。思路：
首先可以先将第二种操作预处理出来，由于可以变成任意的字母，不妨假设一个通用匹配符是′ ∗ ′ '*'
每次将数字x换成x个′ ∗ ′ '*'
那么问题就转化成了编辑距离的经典问题，注意预处理完第二种操作后就只两种操作的转移了。
代码：
const int maxn=2e4+3,mod=1e9+7; int dp[20007][2007]; char a[maxn],b[maxn]; int idx=0; int main(){ string x,y; cin>>x>>y; a[0]='*';b[0]='*'; int lena=0,lenb=0; for(int i=0;i<x.size();i++) if(x[i]>='0'&&x[i]<='9'){ int t=x[i]-'0'; for(int j=1;j<=t;j++) a[++lena]='*'; idx++; } else a[++lena]=x[i]; for(int i=0;i<y.size();i++) if(y[i]>='0'&&y[i]<='9'){ int t=y[i]-'0'; for(int j=1;j<=t;j++) b[++lenb]='*'; idx++; } else b[++lenb]=y[i]; for(int i=1;i<=lenb;i++) dp[0][i]=i; for(int i=1;i<=lena;i++) dp[i][0]=i; for(int i=1;i<=lena;i++){ for(int j=1;j<=lenb;j++){ dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1); if(a[i]==b[j]||a[i]=='*'||b[j]=='*') dp[i][j]=min(dp[i][j],dp[i-1][j-1]); // else dp[i][j]=min(dp[i][j],dp[i-1][j-1]+1); } } cout<<dp[lena][lenb]+idx<<endl; return 0; }
Beer Flood System
题意：
给定一个图，要求在保证从源点可以到达任意点，从任意点可以到达汇点的情况下，最多
能删掉几条多余的边。
其中，源点是图中入度为零的点，汇点是图中出度为零的点。
思路：
很思维的一个题。
把图中每个点分成两部分，出点和入点，每条边连接一个出点一个入点，
用入点集和出点集构造二分图，借助匈牙利算法求出二分图最大匹配。
在这个基础上判断原图，源点是否能到达其他任意点，其他任意点是否能到达汇点，
也就是使除源点和汇点外的每个点入度和出度都不为零，不满足的把相应的边加上。
代码：
const int maxn=2010,mod=1e9+7; vector<int>g[maxn]; int n,m,mat[maxn]; bool vis[maxn]; bool dfs(int u){ for(int t:g[u]){ if(vis[t]) continue; vis[t]=1; if(!mat[t]||dfs(mat[t])){ mat[t]=u;return 1; } } return 0; } PII p[5100]; int din[2100],dout[2100]; int main(){ n=read;m=read; rep(i,1,m){ int u=read,v=read; g[u].push_back(v); p[i]={u,v}; } int ans=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans++; } map<int,int>mp; rep(i,1,m){ int u=p[i].first,v=p[i].second; if(mat[v]==u){ dout[u]++;din[v]++; mp[i]=1; } } rep(i,1,m){ int u=p[i].first,v=p[i].second; if(!mp[i]){ if(!din[v]||!dout[u]) ans++,din[v]++,dout[u]++; } } cout<<m-ans<<endl; return 0; }
![P3146 [USACO16OPEN]248 G](https://ucc.alicdn.com/pic/developer-ecology/2873cb7d2a1b4850893a317fb9c77273.png?x-oss-process=image/resize,h_160,m_lfit)
