NCPC2016-白红宇

NCPC2016

阅读量：6041 次

发布时间：2019-06-20

本文共 11337 字，大约阅读时间需要 37 分钟。

题目链接：https://vjudge.net/contest/259564#overview

A题：离线并查集。先把所有的线条全部画上去，然后我们dfs跑一遍，把所有的连通块求出来。然后从后往前一步一步的去掉每一笔，我们判断是否会出现两个连通块合并到一起，或者多出一个联通块。这个我们通过并查集就可以实现。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define INF 0x3f3f3f3f 8 #define lson l, mid, pos<<1 9 #define rson mid+1, r, pos<<|1 10 using namespace std; 11 int n,m,q,ans; 12 int dir[4][2]={ { 1,0},{ 0,1},{-1,0},{ 0,-1}}; 13 int fa[1100000], cnt[1010][1010]; 14 bool is_fa[1100000], vis[1010][1010]; 15 stack
            
              ansans; 16 struct line{ 17 int xx1, xx2, yy1, yy2; 18 }ql[10010]; 19 int find_set(int x){ 20 if (x==fa[x]) 21 return x; 22 else 23 return fa[x]=find_set(fa[x]); 24 } 25 void dfs(int x, int y, int fapos){ 26 if (x<=0||y<=0||x>m||y>n) 27 return ; 28 if (cnt[x][y]!=INF) 29 return ; 30 if (!vis[x][y]) 31 return ; 32 vis[x][y]=false; 33 fa[x*1000+y]=fapos; 34 int tx, ty; 35 for (int i=0;i<4;++i){ 36 tx=x+dir[i][0]; ty=y+dir[i][1]; 37 dfs(tx,ty,fapos); 38 } 39 return ; 40 } 41 void init(){ 42 for (int i=1;i<=m;++i){ 43 for (int j=1;j<=n;++j){ 44 if (vis[i][j]){ 45 fa[i*1000+j]=i*1000+j; 46 } 47 if (vis[i][j]&&cnt[i][j]==INF){ 48 is_fa[i*1000+j]=true; 49 dfs(i,j,i*1000+j); ans++; 50 } 51 } 52 } 53 } 54 55 void mergefa(int faa, int fab){ 56 fa[faa]=fab; 57 is_fa[faa]=false; 58 ans--; 59 return ; 60 } 61 62 void release(int x, int y){ 63 int tx, ty, ma, mb; 64 for (int i=0;i<4;++i){ 65 tx=x+dir[i][0]; ty=y+dir[i][1]; 66 if (tx>0&&ty>0&&tx<=m&&ty<=n){ 67 if (cnt[tx][ty]==INF){ 68 ma=find_set(x*1000+y); mb=find_set(tx*1000+ty); 69 if (ma!=mb){ 70 //printf("%d\t%dwith\t%d\t%d\n",ma/1000,ma%1000,mb/1000,mb%1000); 71 mergefa(ma,mb); 72 } 73 } 74 } 75 } 76 return ; 77 } 78 79 int main(){ 80 //freopen("in.txt","r",stdin); 81 while(~scanf("%d%d%d",&n,&m,&q)){ 82 ans=0; 83 memset(cnt,INF,sizeof(cnt)); 84 memset(vis,true,sizeof(vis)); 85 memset(is_fa,false,sizeof(is_fa)); 86 for (int i=1;i<=q;++i){ 87 scanf("%d%d%d%d",&ql[i].yy1,&ql[i].xx1,&ql[i].yy2,&ql[i].xx2); 88 for (int j=ql[i].xx1;j<=ql[i].xx2;++j){ 89 for (int k=ql[i].yy1;k<=ql[i].yy2;++k){ 90 cnt[j][k]=min(cnt[j][k],i); 91 } 92 } 93 } 94 init(); 95 ansans.push(ans); 96 while(q>1){ 97 for (int i=ql[q].xx1;i<=ql[q].xx2;i++){ 98 for (int j=ql[q].yy1;j<=ql[q].yy2;++j){ 99 if (cnt[i][j]==q){100 cnt[i][j]=INF; fa[i*1000+j]=i*1000+j; is_fa[i*1000+j]=true; ans++;101 release(i,j);102 }103 }104 }105 ansans.push(ans);106 q--;107 }108 while(!ansans.empty()){109 printf("%d\n",ansans.top());110 ansans.pop();111 }112 }113 return 0;114 }

View Code

B题：

C题：暴力+LCS。

D题：简单贪心。比附近的价格低就买，比附近的价格高就卖，最后注意平价的情况，不买即可。代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5  6 using namespace std; 7 typedef long long LL; 8 const int maxn=400; 9 const int INF=2147000000;10 LL p[maxn];11 int d,n;12 LL mo,sh;13 int main(){14     scanf("%d",&d);15     LL a,num=0;16     for(int i=1;i<=d;i++){17         scanf("%lld",&a);18         if(a!=p[num]){19             num++;20             p[num]=a;21         }22     }23     d=num;24     p[0]=INF,p[d+1]=-INF;25     mo=100,sh=0;26     for(int i=1;i<=d;i++){27         if(p[i]
          
           
            =p[i]){28 LL num=mo/p[i];29 if(num>100000){30 sh+=100000;31 mo-=p[i]*100000;32 }else{33 sh+=num;34 mo-=p[i]*num;35 }36 }37 if(p[i]>p[i-1]&&p[i]>p[i+1]&&sh){38 mo+=p[i]*sh;39 sh=0;40 }41 }42 43 printf("%lld\n",mo);44 return 0;45 }

View Code

E题：指数循环定理。A^B mod C = A^{B mod φ(C) + φ(C)} mod C (B > φ(C))，所以我们就能得到递推式子 exponial(n) % m = n^φ(m)* n^{exponial(n-1) % φ(m)} % m，一次递推即可，递推到 m = 1 即可，这个递推是O(logm)的复杂度，时间复杂度差不多就够了。代码如下：

1 #include 
      
        2 using namespace std; 3  4 typedef long long LL; 5  6 int phi(int n) { 7     int m = sqrt(n+0.5); 8     int ans = n; 9     for(int i = 2; i <= m; ++i) if(n%i == 0){10         ans = ans / i * (i-1);11         while(n%i == 0) n /= i;12     }13     if(n > 1) ans = ans / n * (n-1);14     return ans;15 }16 17 LL qpow(LL a, LL b, LL m) {18     LL ans = 1;19     while(b) {20         if(b&1) ans = ans * a % m;21         a = a * a % m;22         b >>= 1;23     }24     return ans;25 }26 27 int solve(int n, int m) {28     if(m == 1) return 0;29     if(n == 1) return 1%m;30     if(n == 2) return 2%m;31     if(n == 3) return 9%m;32     if(n == 4) return 262144%m;33 34     int p = phi(m);35     LL ans = qpow(n, p, m)*qpow(n, solve(n-1, p), m) % m;36     return ans;37 }38 39 int main() {40     int n, m;41     scanf("%d%d", &n, &m);42     printf("%d\n", solve(n, m));43     return 0;44 }

View Code

F题：递推，或者三分都行。我们推导出来一个式子，从而递推一下，细节不表。代码如下：

1 #include 
      
        2 using namespace std; 3  4 typedef long long LL; 5  6 int main() { 7     double n, p, ans, last; 8     scanf("%lf%lf", &n, &p); 9     last = ans = p/(n+1);10     for(int k = 2; ; ++k) {11         last = ans;12         ans = ans/(k-1)*k/(n+k)*(n+k-p);13         if(ans < last) break;14     }15     printf("%.10f\n", last);16     return 0;17 }

View Code

G题：小模拟，细节不述，代码如下：

1 #include 
      
        2 using namespace std; 3 const int maxn = 10010; 4 int up(int x) 5 { 6     if (x >= 21) return 2; 7     if (x >= 16) return 3; 8     if (x >= 11) return 4; 9     if (x >= 1) return 5;10     return 0x3f3f3f3f;11 }12 13 int main()14 {15     char s[maxn];16     scanf("%s", s);17 18     int tmp = 0;19     int rak = 25, star = 0;20     for (int i = 0; s[i]; i++)21     {22         if (s[i] == 'W')23         {24             ++tmp, ++star;25             if (tmp >= 3 && rak > 5) star++;26         }27         else28         {29             if ((rak > 0 && rak < 20) || (rak == 20 && star)) star--;30             tmp = 0;31         }32 33         if (star > up(rak))34         {35             star -= up(rak);36             rak--;37         }38 39         if (star < 0)40         {41             rak++;42             star = up(rak)-1;43         }44     }45 46     if (rak < 1) printf("Legend\n");47         else printf("%d\n", rak);48 49     return 0;50 }

View Code

H题：

I 题：

J题：签到

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6  7 int n1,n2; 8 int main(){ 9     scanf("%d%d",&n1,&n2);10     int a1 = n1-n2;11     int a2 = 360-abs(a1);12     if(a1 > 0) {13         if(a1 >= 180) printf("%d\n", a2);14         else printf("-%d", abs(a1));15     }16     else {17         if(abs(a1) > 180) printf("-%d\n", a2);18         else printf("%d", abs(a1));19     }20 return 0;21 }

View Code

K题：几何，这个题和刘汝佳蓝书上的一道例题几乎一模一样。题号是 UVa11796。我们这样考虑，运动是相对的，因此我们可以认为（假设两只狗分别为甲、乙）甲静止不动，乙自己沿着直线走，这就是一个点到线段的醉小距离问题。现在我们就可以模拟整个过程了，我们利用相对运动的思路来解决这题，首先分段，每次只讨论甲乙都在进行直线运动的时候进行计算，当其中一个到达拐点的时候，我们接下来又是另一组相对运动，这都是直线运动。直线运动就可以利用相对运动的思路来看，把其中一个看作静止，另一个看作直线运动即可。怎么实现呢？我们先计算出甲的相对位移 X_i和乙的相对位移 X_j ,然后他们之间的相对位移就是 X_i - X_j 。这就是甲静止，乙的位移是 X_i - X_j的情况。这就好处理了，代码如下：

1 #include 
      
         2 using namespace std;  3   4 typedef long long LL;  5   6 const double eps = 1e-10;  7 const double pi = acos(-1);  8   9 struct Point { 10     double x, y; 11     Point(double x=0, double y=0):x(x),y(y) { } 12     void input() { scanf("%lf%lf", &x, &y); } 13 }; 14  15 typedef Point Vector; 16 //向量的加法：向量 + 向量 = 向量 17 Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); } 18 //生成向量：点-点 = 向量 19 Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); } 20 //向量的数乘：向量 * 数 = 向量 21 Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); } 22 //向量的数除；向量 / 数 = 向量 23 Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); } 24 bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } 25 //三态函数 26 int dcmp(double x) { if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1 ; } 27 //判断点\向量是否相等 28 bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; } 29 //向量的点积： 30 double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; } 31 //向量的大小： 32 double Length(Vector A) { return sqrt(Dot(A, A)); } 33 //向量的极角（范围：-pi~pi）： 34 double PolarAngle(Vector A) { return atan2(A.y, A.x); } 35 //两个向量的夹角（范围：0~pi）： 36 double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); } 37 //向量的叉积： 38 double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; } 39 //给出三个点算出三角形有向面积的2倍（可能为负）： 40 double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); } 41 //向量逆时针旋转rad度（弧度制）： 42 Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad)); } 43 //向量的单位法线（确保不是零向量）： 44 Vector Normal(Vector A) { double L = Length(A); return Vector(-A.y/L, A.x/L); } 45 //求两直线的交点（确保两直线不平行或重合，cross(v,w)!=0）： 46 Point GetLineIntersection(Point P, Vector v, Point Q, Vector w) { 47     Vector u = P-Q; 48     double t = Cross(w,u) / Cross(v,w); 49     return P+v*t; 50 } 51 //点到直线的距离： 52 double DistanceToLine(Point P, Point A, Point B) { 53     Vector v1 = B - A, v2 = P - A; 54     return fabs(Cross(v1,v2)) / Length(v1); 55 } 56 //点到线段的距离： 57 double DistanceToSegment(Point P, Point A, Point B) { 58     if(A == B) return Length(P-A); 59     Vector v1 = B-A, v2 = P-A, v3 = P-B; 60     if(dcmp(Dot(v1, v2)) < 0) return Length(v2); 61     else if(dcmp(Dot(v1, v3)) > 0) return Length(v3); 62     else return fabs(Cross(v1, v2)) / Length(v1); 63 } 64 //点在直线上的投影： 65 Point GetLineProjection(Point P, Point A, Point B) { 66     Vector v = B-A; 67     return A + v*(Dot(v, P-A) / Dot(v, v)); 68 } 69 //线段相交的判定（1）： 70 bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2) { 71     double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1), 72            c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1); 73     return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0; 74 } 75 //判断点是否在直线上（包含在端点上，若要排除端点，则将 <= 改为 < 即可）： 76 bool OnSegment1(Point p, Point a1, Point a2) { 77     return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) <= 0; 78 } 79 bool OnSegment2(Point p, Point a1, Point a2) { 80     return dcmp(Cross(a1-p, a2-p)) == 0 && dcmp(Dot(a1-p, a2-p)) <  0; 81 } 82 //求多边形的面积： 83 double PolygonArea(Point *p, int n) { 84     double area = 0; 85     for(int i = 1; i < n-1; ++i) 86         area += Cross(p[i]-p[0], p[i+1]-p[0]); 87     return fabs(area)/2; 88 } 89  90 const int maxn = 100000 + 100; 91 int A, B, T; 92 Point P[maxn], Q[maxn]; 93 double Min; 94  95 void update(Point P, Point A, Point B) { 96     Min = min(Min, DistanceToSegment(P, A, B)); 97 } 98  99 int main() {100     scanf("%d", &A);101     for(int i = 0; i < A; i++) P[i].input();102     scanf("%d", &B);103     for(int i = 0; i < B; i++) Q[i].input();104 105     int Sa = 0, Sb = 0;106     Point Pa = P[0], Pb = Q[0];107     Min = 1e9;108     while(Sa < A-1 && Sb < B-1) {109         double La = Length(P[Sa+1] - Pa);110         double Lb = Length(Q[Sb+1] - Pb);111         double T = min(La, Lb);112         Vector Va = (P[Sa+1] - Pa) / La * T;113         Vector Vb = (Q[Sb+1] - Pb) / Lb * T;114         update(Pa, Pb, Pb+Vb-Va);115         Pa = Pa + Va;116         Pb = Pb + Vb;117         if(Pa == P[Sa+1]) Sa++;118         if(Pb == Q[Sb+1]) Sb++;119     }120     printf("%.10f\n", Min);121     return 0;122 }

View Code

转载于:https://www.cnblogs.com/DynastySun/p/9754208.html

你可能感兴趣的文章