2016年江西理工大学C语言程序设计竞赛（高级组）

2023-08-10 08:06:04

问题 A: jxust

解法：争议的问题（是输入整行还是输入字符串），这里倾向输入字符串，然后判断是否含有jxust就行

#include<bits/stdc++.h>

using namespace std;

string s;

int num;

//jxust

int t;

class P

{

public:

    int cmd(string s)

    {

        num=;

        for(int i=; i<s.length()-; i++)

        {

            if(s[i]=='j'&&s[i+]=='x'&&s[i+]=='u'&&s[i+]=='s'&&s[i+]=='t')

            {

                num++;

            }

        }

        return num;

    }

};

int main()

{

    P sovle;

    cin>>t;

    while(t--)

    {

       num=;

       cin>>s;

       cout<<sovle.cmd(s)<<endl;

    }

    return ;

}

问题 B: 开房

解法：贪心，不过首先判断是不是可以花完，题目可以知道价格都是100的倍数，那么除以100判断就好

#include<bits/stdc++.h>

using namespace std;

string s;

int num;

int t;

class P

{

public:

};

int main()

{

    int t;

    int n;

    int sum=;

    cin>>t;

    while(t--)

    {

        sum=;

        cin>>n;

        if(n%)

        {

            cout<<"-1"<<endl;

            continue;

        }

        sum+=(n/);

        n%=;

        sum+=(n/);

        n%=;

        sum+=(n/);

        n%=;

        sum+=(n/);

        cout<<sum<<endl;

    }

    return ;

}

问题 C: 回文

解法：dp，i表示左边的位置，j表示右边的位置，转移方程s[i] == s[j]？dp[i][j] = dp[i+1][j-1]：dp[i][j] = min({dp[i+1][j-1]+2, dp[i+1][j]+1, dp[i][j-1]+1})

include<bits/stdc++.h>

using namespace std;

int dp[][];

int t;

string s;

class P

{

public:

};

int main()

{

    cin>>t;

    while(t--)

    {

        cin>>s;

        for(int i=s.length()-; i>=; i--)

        {

            for(int j=i+; j<s.length(); j++)

            {

                if(s[i] == s[j])

                {

                    dp[i][j] = dp[i+][j-];

                }

                else

                {

                    dp[i][j] = min({dp[i+][j-]+, dp[i+][j]+, dp[i][j-]+});

                }

            }

        }

        cout<<dp[][s.length()-]<<endl;

    }

    return ;

}

问题 D: 豆豆的字符串

解法：KMP

#include<bits/stdc++.h>

using namespace std;

char a[];

char a1[];

char s[];

int Next[];

char pos;

void cmd(int M)

{

    int i=,j=-;

    Next[i] = -;

    while(i<M)

    {

        if(j==-||s[i]==s[j])Next[++i] = ++j;

        else j=Next[j];

    }

}

int kmp(int pos,int n,int m)

{

    int i = pos, j = ,ans = ;

    while(i<n)

    {

        if(a1[i]==s[j]||j==-)i++,j++;

        else j=Next[j];

        if(j==m)

        {

            ans++;

            j=Next[j-];

            i--;

        }

    }

    return ans;

}

int main()

{

    int n,m;

    char x;

    int c=;

    int cot=;

    scanf("%s",a);

    for(int i=; i<strlen(a); i++)

    {

        if(a[i]>=''&&a[i]<='')

        {

            c=(a[i]-'')+c*;

            continue;

        }

        else

        {

            for(int j=; j<=c; j++)

            {

                a1[cot++]=a[i];

            }

            c=;

        }

    }

   // cout<<a1<<endl;

    scanf("%s",s);

    cmd(strlen(s));

    cout<<kmp(,strlen(a1),strlen(s))<<endl;

    return ;

}

问题 F: 兽兽大神

解法：先用几何模版算法符合要求的方框，再用并查集求个数

#include <bits/stdc++.h>

using namespace std;

struct Point

{

    double x, y;

    Point(double x = , double y = ) : x(x), y(y) {}

};

typedef Point Vector;

Vector operator + (Vector A, Vector B)

{

    return Vector(A.x + B.x, A.y + B.y);

}

Vector operator - (Vector A, Vector B)

{

    return Vector(A.x - B.x, A.y - B.y);

}

Vector operator * (Vector A, double p)

{

    return Vector(A.x*p, A.x*p);

}

Vector operator / (Vector A, double p)

{

    return Vector(A.x/p, A.x/p);

}

bool operator < (const Point& a, const Point b)

{

    return a.x < b.x || (a.x == b.x && a.y < b.y);

}

const double EPS = 1e-;

int dcmp(double x)

{

    if(fabs(x) < EPS) return ;

    else return x <  ? - : ;

}

bool operator == (const Point& a, const Point& b)

{

    return dcmp(a.x-b.x) ==  && dcmp(a.y-b.y);

}

//向量a的极角

double Angle(const Vector& v)

{

    return atan2(v.y, v.x);

}

//向量点积

double Dot(Vector A, Vector B)

{

    return A.x*B.x + A.y*B.y;

}

//向量长度\share\CodeBlocks\templates\wizard\console\cpp

double Length(Vector A)

{

    return sqrt(Dot(A, A));

}

//向量夹角

double Angle(Vector A, Vector B)

{

    return acos(Dot(A, B) / Length(A) / Length(B));

}

//向量叉积

double Cross(Vector A, Vector B)

{

    return A.x*B.y - A.y*B.x;

}

//三角形有向面积的二倍

double Area2(Point A, Point B, Point C)

{

    return Cross(B-A, C-A);

}

//向量逆时针旋转rad度(弧度)

Vector Rotate(Vector A, double rad)

{

    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));

}

//计算向量A的单位法向量。左转90°，把长度归一。调用前确保A不是零向量。

Vector Normal(Vector A)

{

    double L = Length(A);

    return Vector(-A.y/L, A.x/L);

}

/************************************************************************

使用复数类实现点及向量的简单操作

#include <complex>

typedef complex<double> Point;

typedef Point Vector;

double Dot(Vector A, Vector B) { return real(conj(A)*B)}

double Cross(Vector A, Vector B) { return imag(conj(A)*B);}

Vector Rotate(Vector A, double rad) { return A*exp(Point(0, rad)); }

*************************************************************************/

/****************************************************************************

* 用直线上的一点p0和方向向量v表示一条指向。直线上的所有点P满足P = P0+t*v;

* 如果知道直线上的两个点则方向向量为B-A, 所以参数方程为A+(B-A)*t;

* 当t 无限制时， 该参数方程表示直线。

* 当t > 0时， 该参数方程表示射线。

* 当 0 < t < 1时， 该参数方程表示线段。

*****************************************************************************/

//直线交点,须确保两直线有唯一交点。

Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)

{

    Vector u = P - Q;

    double t = Cross(w, u)/Cross(v, w);

    return P+v*t;

}

//点到直线距离

double DistanceToLine(Point P, Point A, Point B)

{

    Vector v1 = B - A, v2 = P - A;

    return fabs(Cross(v1, v2) / Length(v1)); //不取绝对值，得到的是有向距离

}

//点到线段的距离

double DistanceToSegmentS(Point P, Point A, Point B)

{

    if(A == B) return Length(P-A);

    Vector v1 = B-A, v2 = P-A, v3 = P-B;

    if(dcmp(Dot(v1, v2)) < ) return Length(v2);

    else if(dcmp(Dot(v1, v3)) > ) return Length(v3);

    else return fabs(Cross(v1, v2)) / Length(v1);

}

//点在直线上的投影

Point GetLineProjection(Point P, Point A, Point B)

{

    Vector v = B - A;

    return A+v*(Dot(v, P-A)/Dot(v, v));

}

//线段相交判定，交点不在一条线段的端点

bool SegmentProperIntersection(Point a1, Point a2, Point b1, Point b2)

{

    double c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);

    double c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);

    return dcmp(c1)*dcmp(c2) <  && dcmp(c3)*dcmp(c4) < ;

}

//判断点是否在点段上，不包含端点

bool OnSegment(Point P, Point a1, Point a2)

{

    return dcmp(Cross(a1-P, a2-P) ==  && dcmp((Dot(a1-P, a2-P)) < ));

}

//计算凸多边形面积

double ConvexPolygonArea(Point *p, int n)

{

    double area = ;

    for(int i = ; i < n-; i++)

        area += Cross(p[i] - p[], p[i+] - p[]);

    return area/;

}

//计算多边形的有向面积

double PolygonArea(Point *p, int n)

{

    double area = ;

    for(int i = ; i < n-; i++)

        area += Cross(p[i] - p[], p[i+] - p[]);

    return area/;

}

/***********************************************************************

* Morley定理：三角形每个内角的三等分线，相交成的三角形是等边三角形。

* 欧拉定理：设平面图的定点数，边数和面数分别为V,E,F。则V+F-E = 2;

************************************************************************/

struct Circle

{

    Point c;

    double r;

    Circle(Point c, double r) : c(c), r(r) {}

    //通过圆心角确定圆上坐标

    Point point(double a)

    {

        return Point(c.x + cos(a)*r, c.y + sin(a)*r);

    }

};

struct Line

{

    Point p;

    Vector v;

    double ang;

    Line() {}

    Line(Point p, Vector v) : p(p), v(v) {}

    bool operator < (const Line& L) const

    {

        return ang < L.ang;

    }

};

//直线和圆的交点，返回交点个数，结果存在sol中。

//该代码没有清空sol。

int getLineCircleIntersecion(Line L, Circle C, double& t1, double& t2, vector<Point>& sol)

{

    double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;

    double e = a*a + c*c, f = *(a*b + c*d), g = b*b + d*d - C.r*C.r;

    double delta = f*f - *e*g;

    if(dcmp(delta) < ) return ; //相离

    if(dcmp(delta) == )          //相切

    {

        t1 = t2 = -f / (*e);

        sol.push_back(C.point(t1));

        return ;

    }

    //相交

    t1 = (-f - sqrt(delta)) / (*e);

    sol.push_back(C.point(t1));

    t2 = (-f + sqrt(delta)) / (*e);

    sol.push_back(C.point(t2));

    return ;

}

//两圆相交

int getCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol)

{

    double d = Length(C1.c - C2.c);

    if(dcmp(d) == )

    {

        if(dcmp(C1.r - C2.r == )) return -;    //两圆完全重合

        return ;                                //同心圆，半径不一样

    }

    if(dcmp(C1.r + C2.r - d) < ) return ;

    if(dcmp(fabs(C1.r - C2.r) == )) return -;

    double a = Angle(C2.c - C1.c);               //向量C1C2的极角

    double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (*C1.r*d));

    //C1C2到C1P1的角

    Point p1 = C1.point(a-da), p2 = C1.point(a+da);

    sol.push_back(p1);

    if(p1 == p2) return ;

    sol.push_back(p2);

    return ;

}

const double PI = acos(-);

//过定点做圆的切线

//过点p做圆C的切线，返回切线个数。v[i]表示第i条切线

int getTangents(Point p, Circle C, Vector* v)

{

    Vector u = C.c - p;

    double dist = Length(u);

    if(dist < C.r) return ;

    else if(dcmp(dist - C.r) == )

    {

        v[] = Rotate(u, PI/);

        return ;

    }

    else

    {

        double ang = asin(C.r / dist);

        v[] = Rotate(u, -ang);

        v[] = Rotate(u, +ang);

        return ;

    }

}

//两圆的公切线

//返回切线的个数，-1表示有无数条公切线。

//a[i], b[i] 表示第i条切线在圆A，圆B上的切点

int getTangents(Circle A, Circle B, Point *a, Point *b)

{

    int cnt = ;

    if(A.r < B.r)

    {

        swap(A, B);

        swap(a, b);

    }

    int d2 = (A.c.x - B.c.x)*(A.c.x - B.c.x) + (A.c.y - B.c.y)*(A.c.y - B.c.y);

    int rdiff = A.r - B.r;

    int rsum = A.r + B.r;

    if(d2 < rdiff*rdiff) return ;   //内含

    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);

    if(d2 ==  && A.r == B.r) return -;   //无限多条切线

    if(d2 == rdiff*rdiff)           //内切一条切线

    {

        a[cnt] = A.point(base);

        b[cnt] = B.point(base);

        cnt++;

        return ;

    }

    //有外共切线

    double ang = acos((A.r-B.r) / sqrt(d2));

    a[cnt] = A.point(base+ang);

    b[cnt] = B.point(base+ang);

    cnt++;

    a[cnt] = A.point(base-ang);

    b[cnt] = B.point(base-ang);

    cnt++;

    if(d2 == rsum*rsum)    //一条公切线

    {

        a[cnt] = A.point(base);

        b[cnt] = B.point(PI+base);

        cnt++;

    }

    else if(d2 > rsum*rsum)       //两条公切线

    {

        double ang = acos((A.r + B.r) / sqrt(d2));

        a[cnt] = A.point(base+ang);

        b[cnt] = B.point(PI+base+ang);

        cnt++;

        a[cnt] = A.point(base-ang);

        b[cnt] = B.point(PI+base-ang);

        cnt++;

    }

    return cnt;

}

typedef vector<Point> Polygon;

//点在多边形内的判定

int isPointInPolygon(Point p, Polygon poly)

{

    int wn = ;

    int n = poly.size();

    for(int i = ; i < n; i++)

    {

        if(OnSegment(p, poly[i], poly[(i+)%n])) return -; //在边界上

        int k = dcmp(Cross(poly[(i+)%n]-poly[i], p-poly[i]));

        int d1 = dcmp(poly[i].y - p.y);

        int d2 = dcmp(poly[(i+)%n].y - p.y);

        if(k >  && d1 <=  && d2 > ) wn++;

        if(k <  && d2 <=  && d1 > ) wn++;

    }

    if(wn != ) return ;       //内部

    return ;                   //外部

}

//凸包

/***************************************************************

* 输入点数组p， 个数为p， 输出点数组ch。 返回凸包顶点数

* 不希望凸包的边上有输入点，把两个<= 改成 <

* 高精度要求时建议用dcmp比较

* 输入点不能有重复点。函数执行完以后输入点的顺序被破坏

****************************************************************/

int ConvexHull(Point *p, int n, Point* ch)

{

    sort(p, p+n);      //先比较x坐标，再比较y坐标

    int m = ;

    for(int i = ; i < n; i++)

    {

        while(m >  && Cross(ch[m-] - ch[m-], p[i]-ch[m-]) <= ) m--;

        ch[m++] = p[i];

    }

    int k = m;

    for(int i = n-; i >= ; i++)

    {

        while(m > k && Cross(ch[m-] - ch[m-], p[i]-ch[m-]) <= ) m--;

        ch[m++] = p[i];

    }

    if(n > ) m--;

    return m;

}

//用有向直线A->B切割多边形poly， 返回“左侧”。 如果退化，可能会返回一个单点或者线段

//复杂度O(n2);

Polygon CutPolygon(Polygon poly, Point A, Point B)

{

    Polygon newpoly;

    int n = poly.size();

    for(int i = ; i < n; i++)

    {

        Point C = poly[i];

        Point D = poly[(i+)%n];

        if(dcmp(Cross(B-A, C-A)) >= ) newpoly.push_back(C);

        if(dcmp(Cross(B-A, C-D)) != )

        {

            Point ip = GetLineIntersection(A, B-A, C, D-C);

            if(OnSegment(ip, C, D)) newpoly.push_back(ip);

        }

    }

    return newpoly;

}

//半平面交

//点p再有向直线L的左边。（线上不算）

bool Onleft(Line L, Point p)

{

    return Cross(L.v, p-L.p) > ;

}

//两直线交点，假定交点唯一存在

Point GetIntersection(Line a, Line b)

{

    Vector u = a.p - b.p;

    double t = Cross(b.v, u) / Cross(a.v, b.v);

    return a.p+a.v*t;

}

int HalfplaneIntersection(Line* L, int n, Point* poly)

{

    sort(L, L+n);               //按极角排序

    int first, last;            //双端队列的第一个元素和最后一个元素

    Point *p = new Point[n];    //p[i]为q[i]和q[i+1]的交点

    Line *q = new Line[n];      //双端队列

    q[first = last = ] = L[]; //队列初始化为只有一个半平面L[0]

    for(int i = ; i < n; i++)

    {

        while(first < last && !Onleft(L[i], p[last-])) last--;

        while(first < last && !Onleft(L[i], p[first])) first++;

        q[++last] = L[i];

        if(fabs(Cross(q[last].v, q[last-].v)) < EPS)

        {

            last--;

            if(Onleft(q[last], L[i].p)) q[last] = L[i];

        }

        if(first < last) p[last-] = GetIntersection(q[last-], q[last]);

    }

    while(first < last && !Onleft(q[first], p[last-])) last--;

    //删除无用平面

    if(last-first <= ) return ;   //空集

    p[last] = GetIntersection(q[last], q[first]);

    //从deque复制到输出中

    int m = ;

    for(int i = first; i <= last; i++) poly[m++] = p[i];

    return m;

}

int fa[];

int Find(int x)

{

    if(x!=fa[x]) fa[x]=Find(fa[x]);

    return fa[x];

}

double ShortgetLen(Point a,Point b,Point c,Point d)

{

    double len = DistanceToSegmentS(a,c,d);

    len = min(len,DistanceToSegmentS(b,c,d));

    return len;

}

int n;

double m;

int x,y,w,h;

struct P

{

   Point A,B,C,D;

}He[];

bool cmd(int i,int j){

    double shortlen=1000000000.0;

    shortlen = min({shortlen,ShortgetLen(He[i].D,He[i].A,He[j].A,He[j].B),ShortgetLen(He[i].C,He[i].D,He[j].C,He[j].D),ShortgetLen(He[i].C,He[i].D,He[j].A,He[j].B),ShortgetLen(He[i].B,He[i].C,He[j].C,He[j].D),ShortgetLen(He[i].A,He[i].B,He[j].D,He[j].A),ShortgetLen(He[i].B,He[i].C,He[j].A,He[j].B),ShortgetLen(He[i].B,He[i].C,He[j].B,He[j].C)});

    shortlen = min({shortlen,ShortgetLen(He[i].C,He[i].D,He[j].D,He[j].A),ShortgetLen(He[i].C,He[i].D,He[j].B,He[j].C),ShortgetLen(He[i].B,He[i].C,He[j].D,He[j].A),ShortgetLen(He[i].A,He[i].B,He[j].A,He[j].B),ShortgetLen(He[i].A,He[i].B,He[j].B,He[j].C),ShortgetLen(He[i].A,He[i].B,He[j].C,He[j].D)});

    shortlen = min({shortlen,ShortgetLen(He[i].D,He[i].A,He[j].D,He[j].A),ShortgetLen(He[i].D,He[i].A,He[j].B,He[j].C),ShortgetLen(He[i].D,He[i].A,He[j].C,He[j].D)});

    if(m-shortlen>=0.00) return true;

    else return false;

}

void init()

{

    for(int i=; i<=n; i++) fa[i]=i;

}

map<int,int>p;

map<int,int>::iterator it;

int ans;

int main()

{

    p.clear();

    cin>>n>>m;

    init();

    for(int i=; i<=n; i++)

    {

        scanf("%d%d%d%d",&x,&y,&w,&h);

        He[i].A.x = x;

        He[i].A.y = y;

        He[i].B.x = x+w;

        He[i].B.y = y;

        He[i].C.x = x+w;

        He[i].C.y = y+h;

        He[i].D.x = x;

        He[i].D.y = y+h;

    }

    for(int i=; i<=n; i++)

    {

        for(int j=i+; j<=n; j++)

        {

            if(cmd(i,j))

            {

                int a=Find(i);

                int b=Find(j);

                if(a!=b) fa[a]=b;

            }

        }

    }

    for(int i=; i<=n; i++)

    {

        fa[i]=Find(fa[i]);

    }

    for(int i=; i<=n; i++)

    {

        p[fa[i]]++;

    }

    for(it=p.begin();it!=p.end();it++)

    {

         ans++;

    }

    cout<<ans<<endl;

    return ;

}
上一篇：su鉴定故障 普通用户无法切换回root用户处理-centos7网卡速率设置


下一篇：Linux CentOS6.x ip设置(网卡设置)