昨天打多校的第二场，状态还算可以，不会像第一场那样浑浑噩噩的敲过去了。可是这次的排名却比第一次要低了。

　　其实昨天比赛很不顺，主要是机房的机器不够，导致我们开局一小时后从三台机减少到只剩一台机。

　　开始的时候，队友ly像开挂一样，瞬间就看懂了1002，20min敲出了代码，抢了个fb。然后就是1009，这题其实很简单，很容易可以看出就是一个二分匹配的题。题目大意是，给出一些1*2的方块，有横向和纵向放置两种，其中只可能出现横向跟纵向重叠的情况，不会横向和横向纵向和纵向重叠。要求求出，最多可以剩下多少方块，是的它们之间两两不重叠。这样子，就可以对有重叠部分的横向和纵向方块添加一条边。然后求出最大匹配，就是最少要删除的方块数目。最后的答案是n+m减去匹配的数目。

　　然后就是队友卡1006了，这时，为了打破窘境（2个小时才做了2题），我去看了一下1007，好水的一道三维几何的题。这题的题意是给出一些空间圆柱，要求求出所有圆柱之间的最短距离。如果有重叠的部分，就输出Lucky。其实可以直接将圆柱看成直线，然后求出空间直线的最短距离即可。1y。

　　在我过了1007以后，队友xdp也接着出了1001。最后整场比赛就就卡在1006了。在不停的给1006出数据以后，最终过了1006，然后才看到1004是简单的线段树，这时的时间已经剩下一个钟不够，最后以5题结束了比赛，线段树没有及时写出来。

　　这次的组队，主要欠缺在于明明已知09是二分，结果搞了很久贪心wa了几次。

　　组队的时候如果看出算法，就应该直接上那个模板，而不应该想虽然敲的简单，却不能肯定对的做法。

 

贴一下代码：

hdu 4619：（二分匹配的题，用了HK算法，不过因为边数比较少，可以直接用匈牙利算法。）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 9 using namespace std;10 const int N = 1111;11 vector
             
               rel[N];12 13 bool overlap(int a, int b, int c, int d) {14 if (c == a && d + 1 == b) return true;15 if (c == a && d == b) return true;16 if (c == a + 1 && d + 1 == b) return true;17 if (c == a + 1 && d == b) return true;18 return false;19 }20 21 int mx[N], my[N], rx[N], ry[N];22 int hx[N], hy[N], vx[N], vy[N];23 queue
              
                Q;24 25 bool HKbfs(int n) {26 bool ret = false;27 while (!Q.empty()) Q.pop();28 memset(rx, 0, sizeof(rx));29 memset(ry, 0, sizeof(ry));30 for (int i = 0; i < n; i++) {31 if (mx[i] == -1) Q.push(i);32 }33 while (!Q.empty()) {34 int cur = Q.front();35 Q.pop();36 for (int i = 0; i < rel[cur].size(); i++) {37 int t = rel[cur][i];38 if (!ry[t]) {39 ry[t] = rx[cur] + 1;40 if (~my[t]) {41 rx[my[t]] = ry[t] + 1;42 Q.push(my[t]);43 } else {44 ret = true;45 }46 }47 }48 }49 return ret;50 }51 52 bool HKdfs(int cur) {53 for (int i = 0; i < rel[cur].size(); i++) {54 int t = rel[cur][i];55 if (ry[t] == rx[cur] + 1) {56 ry[t] = 0;57 if (my[t] == -1 || HKdfs(my[t])) {58 my[t] = cur;59 mx[cur] = t;60 return true;61 }62 }63 }64 return false;65 }66 67 int HK(int n) {68 int cnt = 0;69 memset(mx, -1, sizeof(mx));70 memset(my, -1, sizeof(my));71 while (HKbfs(n)) {72 for (int i = 0; i < n; i++) if (mx[i] == -1 && HKdfs(i)) cnt++;73 }74 return cnt;75 }76 77 int main() {78 int n, m;79 while (cin >> n >> m && (n || m)) {80 for (int i = 0; i < n; i++) cin >> hx[i] >> hy[i];81 for (int i = 0; i < m; i++) cin >> vx[i] >> vy[i];82 for (int i = 0; i < n; i++) {83 rel[i].clear();84 for (int j = 0; j < m; j++) {85 if (overlap(hx[i], hy[i], vx[j], vy[j])) {86 //cout << i << ' ' << j << endl;87 rel[i].push_back(j);88 }89 }90 }91 cout << n + m - HK(n) << endl;92 }93 return 0;94 }
              
             
            
           
          
         
        
       
      

 

hdu 4617：（三维几何）

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 9 using namespace std;10 11 const double EPS = 1e-8;12 const int N = 33;13 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}14 struct Point {15 double x, y, z;16 Point() {}17 Point(double x, double y, double z) : x(x), y(y), z(z) {}18 Point operator + (Point a) { return Point(x + a.x, y + a.y, z + a.z);}19 Point operator - (Point a) { return Point(x - a.x, y - a.y, z - a.z);}20 Point operator * (double p) { return Point(x * p, y * p, z * p);}21 Point operator / (double p) { return Point(x / p, y / p, z / p);}22 } pt[N][3];23 24 inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y + a.z * b.z;}25 inline Point cross(Point a, Point b) { return Point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);}26 inline double veclen(Point x) { return sqrt(dot(x, x));}27 inline double ptdis(Point a, Point b) { return veclen(a - b);}28 inline Point vecunit(Point x) { return x / veclen(x);}29 30 bool lldis(Point p1, Point u, Point p2, Point v, double &s) {31 double b = dot(u, u) * dot(v, v) - dot(u, v) * dot(u, v);32 if (sgn(b) == 0) return false;33 double a = dot(u, v) * dot(v, p1 - p2) - dot(v, v) * dot(u, p1 - p2);34 s = a / b;35 return true;36 }37 38 double p2l(Point p, Point a, Point b) {39 Point v1 = b - a, v2 = p - a;40 return veclen(cross(v1, v2)) / veclen(v1);41 }42 43 Point p[N], nor[N];44 double r[N];45 46 int main() {47 int T, n;48 cin >> T;49 while (T-- && cin >> n) {50 for (int i = 0; i < n; i++) {51 for (int j = 0; j < 3; j++) cin >> pt[i][j].x >> pt[i][j].y >> pt[i][j].z;52 p[i] = pt[i][0];53 r[i] = veclen(pt[i][0] - pt[i][1]);54 nor[i] = cross(pt[i][1] - pt[i][0], pt[i][2] - pt[i][0]);55 }56 double ans = 1e10;57 bool touch = false;58 for (int i = 0; i < n && !touch; i++) {59 for (int j = i + 1; j < n && !touch; j++) {60 double s, t, dis;61 if (lldis(p[i], nor[i], p[j], nor[j], s)) {62 lldis(p[j], nor[j], p[i], nor[i], t);63 Point a = p[i] + nor[i] * s;64 Point b = p[j] + nor[j] * t;65 dis = ptdis(a, b);66 } else dis = p2l(p[i], p[j], p[j] + nor[j]);67 //cout << i << ' ' << j << ' ' << dis << endl;68 if (dis <= r[i] + r[j]) touch = true;69 ans = min(ans, dis - r[i] - r[j]);70 }71 }72 if (touch) puts("Lucky");73 else printf("%.2f\n", ans);74 }75 return 0;76 }
            
           
          
         
        
       
      

 

hdu 4611：（模拟，队友xdp过的）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6  7 #define ll long long 8  9 ll gcd(ll a,ll b){10     return b?gcd(b,a%b):a;11 }12 ll lcm(ll a,ll b){13     return a/gcd(a,b)*b;14 }15 ll myabs(ll key){16     if(key<0) return -key;17     return key;18 }19 20 int main(){21 //    freopen("in","r",stdin);22     int t;23     cin>>t;24     while(t--){25         ll l=0,r=0,rlcm=0,rsum=0;26         ll n,a,b;27         cin>>n>>a>>b;28 //        cout<
          
           <
           
            =Max){39 rsum+=Max*dif;40 c-=Max;41 }42 else{43 rsum+=c*dif;44 c=0;45 }46 l+=Max;47 r+=Max;48 l%=a;49 r%=b;50 // cout<
            
             <<' '<
             
              <
             
            
           
          
         
        
       
      

 

hdu 4616：（树dp，队友ly过的）

1 #pragma comment(linker,"/STACK:102400000,102400000")  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 typedef long long LL; 10 11 const int N = 50005; 12 using namespace std; 13 int n,c; 14 LL dp[N][5][5]; 15 int tot,pre[N]; 16 struct edge{ 17 int v,next; 18 }e[N<<1]; 19 LL val[N]; 20 int trap[N]; 21 22 void init(){ 23 tot=0; 24 memset(pre,-1,sizeof(pre)); 25 memset(dp,-1,sizeof(dp)); 26 } 27 28 void add(int u,int v){ 29 edge E={v,pre[u]}; 30 e[tot]=E,pre[u]=tot++; 31 } 32 33 void input(){ 34 scanf("%d%d",&n,&c); 35 int u,v; 36 for(int i=0;i
             
              c) continue; 85 if(dp[u][j][0]==dp[v][j-trap[u]][0]+val[u]){ 86 if(dp[u][j][1]!=-1) dp[v][j+trap[v]][2]=max(dp[v][j+trap[v]][2],dp[u][j][1]+val[v]); 87 // if(v==7&&j+trap[v]==2) printf("dp[%d][%d][1]=%lld val[%d]=%lld\n",u,j,dp[u][j][1],v,val[v]); 88 89 } 90 else if(dp[u][j][0]!=-1){ 91 // if(v==7&&j+trap[v]==2) printf("dp[%d][%d][0]=%lld val[%d]=%lld\n",u,j,dp[u][j][0],v,val[v]); 92 dp[v][j+trap[v]][2]=max(dp[v][j+trap[v]][2],dp[u][j][0]+val[v]); 93 } 94 // if(v==7&&j+trap[v]==2) printf("dp[%d][%d][2]=%lld val[%d]=%lld\n",u,j,dp[u][j][2],v,val[v]); 95 if(dp[u][j][2]!=-1) dp[v][j+trap[v]][2]=max(dp[v][j+trap[v]][2],dp[u][j][2]+val[v]); 96 } 97 dfs2(v,u); 98 } 99 }100 101 void get(){102 puts("~~~~~~~~~~~~~~~~~~~~~~");103 for(int i=3;i<=3;i++){104 for(int j=0;j<=c;j++){105 for(int k=0;k<3;k++){106 if(dp[i][j][k]!=-1) printf("dp[%d][%d][%d]=%lld\n",i,j,k,dp[i][j][k]);107 }108 }109 }110 }111 112 int main(){113 // freopen("in","r",stdin);114 int T;115 scanf("%d",&T);116 while(T--){117 init();118 input();119 res=-1;120 dfs1(0,-1);121 dp[0][trap[0]][2]=0;122 dfs2(0,-1);123 // get();124 cout << res << endl;125 }126 return 0;127 }
             
            
           
          
         
        
       
      

 

hdu 4614：（线段树，跟POJ的hotel那题相似，是比较经典的模型）

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 9 using namespace std; 10 11 const int N = 55555; 12 13 #define lson l, m, rt << 1 14 #define rson m + 1, r, rt << 1 | 1 15 #define root 0, n - 1, 1 16 17 int ml[N << 2], mr[N << 2], sum[N << 2], late[N << 2]; 18 int n; 19 20 void up(int rt) { 21 int ls = rt << 1, rs = rt << 1 | 1; 22 sum[rt] = sum[ls] + sum[rs]; 23 if (ml[ls] == -1) ml[rt] = ml[rs]; 24 else ml[rt] = ml[ls]; 25 if (mr[rs] == -1) mr[rt] = mr[ls]; 26 else mr[rt] = mr[rs]; 27 } 28 29 void down(int rt, int l, int r) { 30 int ls = rt << 1, rs = rt << 1 | 1; 31 int len = r - l + 1; 32 int lr = len >> 1, ll = len - lr; 33 if (~late[rt]) { 34 sum[ls] = late[rt] * ll; 35 sum[rs] = late[rt] * lr; 36 if (late[rt]) { 37 ml[ls] = ml[rs] = mr[ls] = mr[rs] = -1; 38 } else { 39 ml[ls] = l, mr[ls] = l + ll - 1; 40 ml[rs] = r - lr + 1, mr[rs] = r; 41 } 42 late[ls] = late[rs] = late[rt]; 43 late[rt] = -1; 44 } 45 } 46 47 void build(int l, int r, int rt) { 48 late[rt] = -1; 49 if (l == r) { 50 ml[rt] = mr[rt] = l; 51 sum[rt] = 0; 52 return ; 53 } 54 int m = l + r >> 1; 55 build(lson); 56 build(rson); 57 up(rt); 58 } 59 60 int clean(int L, int R, int l, int r, int rt) { 61 int ret = 0; 62 if (L <= l && r <= R) { 63 // cout << l << ' ' << r << " sum " << sum[rt] << endl; 64 ret = sum[rt]; 65 late[rt] = 0; 66 sum[rt] = 0; 67 ml[rt] = l, mr[rt] = r; 68 return ret; 69 } 70 int m = l + r >> 1; 71 down(rt, l, r); 72 if (L <= m) ret += clean(L, R, lson); 73 if (m < R) ret += clean(L, R, rson); 74 up(rt); 75 return ret; 76 } 77 78 typedef pair
             
               PII; 79 PII insert(int L, int R, int l, int r, int rt) { 80 PII ret = PII(-1, -1); 81 if (L <= l && r <= R) { 82 late[rt] = 1; 83 sum[rt] = r - l + 1; 84 ret = PII(ml[rt], mr[rt]); 85 ml[rt] = mr[rt] = -1; 86 return ret; 87 } 88 int m = l + r >> 1; 89 down(rt, l, r); 90 if (L <= m) ret = insert(L, R, lson); 91 if (m < R) { 92 PII tmp = insert(L, R, rson); 93 if (ret.first == -1) ret.first = tmp.first; 94 if (tmp.second != -1) ret.second = tmp.second; 95 } 96 up(rt); 97 return ret; 98 } 99 100 int getsum(int L, int R, int l, int r, int rt) {101 if (L <= l && r <= R) return r - l + 1 - sum[rt];102 down(rt, l, r);103 int m = l + r >> 1;104 int sum = 0;105 if (L <= m) sum += getsum(L, R, lson);106 if (m < R) sum += getsum(L, R, rson);107 up(rt);108 return sum;109 }110 111 int dc(int l, int r, int cnt) {112 int mk = -1, m, p = l;113 while (l <= r) {114 m = l + r >> 1;115 //cout << m << "= =" << getsum(p, m, root) << '~' << cnt << endl;116 if (getsum(p, m, root) >= cnt) mk = m, r = m - 1;117 else l = m + 1;118 }119 return mk;120 }121 122 int main() {123 int T, m;124 int op, x, y;125 PII tmp;126 cin >> T;127 while (T-- && cin >> n >> m) {128 build(root);129 while (m--) {130 scanf("%d%d%d", &op, &x, &y);131 if (op == 1) {132 int cnt = getsum(x, n - 1, root);133 y = min(y, cnt);134 int pos = dc(x, n - 1, y);135 //cout << x << '=' << pos << endl;136 if (~pos) {137 PII tmp = insert(x, pos, root);138 //cout << tmp.first << '~' << tmp.second << endl;139 if (~tmp.first) printf("%d %d\n", tmp.first, tmp.second);140 else puts("Can not put any one.");141 } else {142 puts("Can not put any one.");143 }144 } else {145 printf("%d\n", clean(x, y, root));146 }147 }148 puts("");149 }150 return 0;151 }
             
            
           
          
         
        
       
      

 

hdu 4612：（好像是强连通分量吧，图论，队友ly过的）

1 #pragma comment(linker,"/STACK:102400000,102400000")  2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 const int N = 200005; 11 const int E = 1000005; 12 using namespace std; 13 int n,m; 14 int tot,pre[N]; 15 struct edge{ 16 int u,v,next; 17 }e[E<<1]; 18 int dfn[N],low[N],id[N],st[N]; 19 int scc,num,top; 20 bool vis[N]; 21 22 void init(){ 23 tot=0; 24 memset(pre,-1,sizeof(pre)); 25 } 26 27 void add(int u,int v){ 28 edge E={u,v,pre[u]}; 29 e[tot]=E,pre[u]=tot++; 30 } 31 32 void input(){ 33 int u,v; 34 while(m--){ 35 scanf("%d%d",&u,&v); 36 add(u,v),add(v,u); 37 } 38 } 39 40 void dfs(int u,int fa){ 41 dfn[u]=low[u]=++num; 42 vis[u]=1,st[++top]=u; 43 int flag=1; 44 for(int i=pre[u];i!=-1;i=e[i].next){ 45 int v=e[i].v; 46 if(v==fa&&flag){ 47 flag=0; 48 continue; 49 } 50 if(!dfn[v]){ 51 dfs(v,u); 52 low[u]=min(low[u],low[v]); 53 } 54 else if(vis[v]) low[u]=min(low[u],dfn[v]); 55 } 56 if(low[u]==dfn[u]){ 57 scc++; 58 while(1){ 59 int v=st[top--]; 60 id[v]=scc,vis[v]=0; 61 if(v==u) break; 62 } 63 } 64 } 65 66 void tarjan(){ 67 memset(dfn,0,sizeof(dfn)); 68 memset(vis,0,sizeof(vis)); 69 scc=num=top=0; 70 for(int i=1;i<=n;i++){ 71 if(!dfn[i]) dfs(i,-1); 72 // printf("id[%d]=%d\n",i,id[i]); 73 } 74 } 75 76 void build(){ 77 int nn=tot; 78 init(); 79 for(int i=0;i
             

q; 88 memset(vis,0,sizeof(vis)); 89 dis[s]=0,vis[s]=1,t=s; 90 q.push(s); 91 int res=0; 92 while(!q.empty()){ 93 int u=q.front(); 94 q.pop(); 95 if(res

0){114 if(n==0&&m==0) break;115 init();116 input();117 tarjan();118 build();119 int u,v;120 int res=bfs(1,u);121 res=bfs(u,v);122 printf("%d\n",scc-1-res);123 }124 return 0;125 }