srm 503 250pts

注意到答案只能是-1或1或2，判一下就行了。

#include <bits/stdc++.h> using namespace std; class ToastXToast { public: int bake(vector<int>a1,vector<int>a2) { sort(a1.begin(),a1.end()); sort(a2.begin(),a2.end()); if(a1[0]>a2[0])return -1; if(a1.back()>a2.back())return -1; if(a1.back()<a2[0])return 1; return 2; } };

srm 503 500pts

考虑每个v点的贡献，将所有v点和c点按到当前v点的距离排序，按距离枚举所有的点，如果枚举到一个c点那么之后的所有点都没有用了，所以计算当前c点后退出。

枚举的每个点的贡献为 距离*概率，距离随便算，只考虑概率就行了。
设当前点之前共有x个点。
如果当前枚举的是一个v点那么概率为 1(x+1)(x+2)
否则概率为 1x+1

讯享网#include <bits/stdc++.h> using namespace std; #define ld long double #define ll long long int n,m; struct poi { int x,y,pos; poi(){} poi(int x,int y,int pos):x(x),y(y),pos(pos){} }now,c[52],v[52]; double bir[110],ans; ll sq(int x){ 
  
    
  return (ll)x*x;} ll dis(poi p1,poi p2) { 
  
    
  return sq(p1.x-p2.x)+sq(p1.y-p2.y);} int cmp(poi p1,poi p2) { 
  
    
  return dis(p1,now)<dis(p2,now);} int cmp1(poi p1,poi p2) { 
  
    
  return p1.pos<p2.pos;} class KingdomXCitiesandVillages { public: double determineLength(vector<int>cx,vector<int>cy,vector<int>vx,vector<int>vy) { n=cx.size();m=vx.size(); for(int i=0;i<n;i++) c[i+1]=poi(cx[i],cy[i],i+1); for(int i=0;i<m;i++) v[i+1]=poi(vx[i],vy[i],i+1); for(int i=1;i<=m;i++) { now=v[i]; sort(c+1,c+1+n,cmp); sort(v+1,v+1+m,cmp); for(int j=2;j<=m+1;j++) { if(j==m+1||dis(v[1],c[1])<=dis(v[1],v[j])) { ans+=sqrt((ld)dis(v[1],c[1]))/(j-1); break; } ans+=sqrt((ld)dis(v[1],v[j]))/(j-1)/j; } sort(v+1,v+1+m,cmp1); } return ans; } }tmp;

srm 503 1000pts

看jry博客时被吓得不轻，不过写完觉得还好吧，并没有太多细节。思路还是挺神的。。。

讯享网

然后把b块单独拎出来：

那么可以用5个变量存一块，其中 h4 可以用其他四个变量表示。
因此状态总数是 O(hw3) 级别的。

特殊情况是最上面没有封顶的块，注意到这样的块只有一个，然后分这两种转移：

记录两个布尔变量 r1,r2 表示当前块是不是最上面一块以及当前块在左面还是在右面。
对于最下面的情况，由于第一步一定是从最下边的一个点发出一条边，因此可以枚举蓝线部分：

#include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long  #define seed  ull p[21]; struct node { int h,h1,h2,h3,h4,r1,r2; ull val; void get() {val=h+h1*p[1]+h2*p[2]+h3*p[3]+h4*p[4]+r1*p[5]+r2*p[6];} friend bool operator < (const node &r1,const node &r2) { 
  
    
  return r1.val<r2.val;} }; map<node,ll>ma; int a[2][210],b[21],w,H[2]; ll ans; ll cal(int h,int h1,int h2,int h3,int h4,int r1,int r2) { node tmp=(node){h,h1,h2,h3,h4,r1,r2}; tmp.get(); if(ma.count(tmp))return ma[tmp]; ll ret=1ll<<60; if(r2==0) { int t1=0,t2=0; for(int i=h1+2;i<=H[0];i+=2) if(a[0][i])t1=1; for(int i=h3+2;i<=H[1];i+=2) if(a[1][i])t2=1; if(!t1&&!t2)ret=0; else { for(int i=h2+1;i<=h3;i++) { int t=h1+(i-h2)*2; ret=min(ret,cal(h1,h2,i,t,t,0,1)+cal(0,t,i,h3,0,0,0)+b[t-i]); } for(int i=h2+1;i<=h1;i++) { int t=h3+(i-h2)*2; ret=min(ret,cal(h3,h2,i,t,t,1,1)+cal(0,h1,i,t,0,0,0)+b[t-i]); } } } else { int t1=0; for(int i=h+2;i<h4;i+=2) if(a[r1][i])t1=1; if(!t1)ret=0; else { int x=h2+h4-h3; for(int i=h+2;i<h4;i+=2) { int t=h1+(i-h)/2; ret=min(ret,cal(h,h1,t,i,i,r1,r2)+cal(i,t,h2,h3,h4,r1,r2)+b[i-t]); } for(int i=x;i<h2;i++) { int t=h3+i-h2; ret=min(ret,cal(h,h1,i,t,h4,r1,r2)+b[t-i]); } x=h2+h-h1; for(int i=h+2;i<h4;i+=2) { int t=h3-(h4-i)/2; ret=min(ret,cal(h,h1,h2,t,i,r1,r2)+cal(i,i,t,h3,h4,r1,r2)+b[t-i]); } for(int i=h2+1;i<=x;i++) { int t=i-h2+h1; ret=min(ret,cal(h,t,i,h3,h4,r1,r2)+b[i-t]); } } } ma[tmp]=ret; return ret; } void init() { p[0]=1; for(int i=1;i<=15;i++) p[i]=p[i-1]*seed; } class KingdomXEmergencyStaircase { public: ll determineCost(string s1,string s2,vector<int>vec) { init(); w=vec.size(); H[0]=s1.size()*2+w;H[1]=s2.size()*2+w; for(int i=0;i<s1.size();i++) a[0][(i+1)*2]=s1[i]=='Y' ? 1:0; for(int i=0;i<s2.size();i++) a[1][(i+1)*2]=s2[i]=='Y' ? 1:0; for(int i=0;i<w;i++)b[i+1]=vec[i]; ans=1ll<<60; ll t=cal(0,w,0,0,0,0,0); for(int i=0;i<=w;i+=2) { if(i==w) ans=min(ans,t+b[w]); else { int t1=(w-i)/2; ans=min(ans,cal(i,i,i+t1,w,w,0,1)+t+b[w]+b[t1]); } if(a[0][i])break; } t=cal(0,0,0,w,0,0,0); for(int i=0;i<=w;i+=2) { if(i==w) ans=min(ans,t+b[w]); else { int t1=(w-i)/2; ans=min(ans,cal(i,i,i+t1,w,w,1,1)+t+b[w]+b[t1]); } if(a[1][i])break; } return ans; } }tmp;

srm 504 250pts

按题意模拟一下就行了，记录一下变了几次色。

讯享网#include <bits/stdc++.h> using namespace std; int a[]; class MathContest { public: int countBlack(string s,int tim) { int len=s.size(),now=0,pos=0,ans=0,head=1,tail=0; for(int i=0;i<len;i++) a[++tail]=s[i]=='B' ? 1:0; for(int i=2;i<=tim;i++) { for(int j=1;j<=len;j++) a[++tail]=a[j]; } while(tail>=head) { int t; if(pos)t=a[tail--]^now; else t=a[head++]^now; if(t==0)pos^=1; else now^=1; ans+=t; } return ans; } }tmp;

srm 504 500pts

第一行一定不变，枚举 1 到 n−1 行，模拟一下算出下一行每一个点的颜色。分没有颜色，黑，白，三种。如果有颜色，看和给出的颜色是否相符，相符答案乘2，否则答案为0。

#include <bits/stdc++.h> using namespace std; #define mod  #define ll long long int val[61]; int qpow(int x,int y) { int ret=1; while(y) { if(y&1)ret=(ll)ret*x%mod; x=(ll)x*x%mod;y>>=1; } return ret; } class AlgridTwo { public: int makeProgram(vector<string>s) { int n=s.size(),m=s[0].size(),ans=0; for(int i=0;i<n-1;i++) { memset(val,-1,sizeof(val)); for(int j=0;j<m-1;j++) { if(s[i][j]=='W'&&s[i][j+1]=='B') val[j]=val[j+1]=0; if(s[i][j]=='B'&&s[i][j+1]=='W') val[j]=val[j+1]=1; if(s[i][j]=='B'&&s[i][j+1]=='B') swap(val[j],val[j+1]); } for(int j=0;j<m;j++) if(val[j]!=-1) { if((s[i+1][j]=='B')!=val[j])return 0; ans++; } } return qpow(2,ans); } }cls;