首页 > 代码库 > 2015 长春

2015 长春

F  t 组数据  n 然后n个数

恰好要去掉一个数  使得序列递增  或者递减   (不严格)

画2个图模拟  或者nlong(n)求最长上升子序列

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<stdlib.h>
#include<vector>
#include<map>

using namespace std;

#define MAXN 100100
#define inf  1000000007
#define ll long long

int z[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&z[i]);
        int ok=0;

        int cnt=0;
        z[0]=inf;
        z[n+1]=-1;
        int i;
        for(i=2;i<=n;i++)
        {
            if(z[i]>z[i-1])//递减
            {
                if(ok==1)
                 {
                      ok=0;
                      break;
                 }
                if(z[i-1]>=z[i+1])
                    ok=1;
                else
                {
                    if(z[i-2]>=z[i])
                        ok=1;
                    else
                    {
                        ok=0;
                        break;
                    }
                }

            }
        }
        if(ok==0&&i==n+1)
            ok=1;
        if(ok==1)
        {
            printf("YES\n");
            continue;
        }
        z[0]=-1;
        z[n+1]=inf;
        for(i=2;i<=n;i++)
        {
            if(z[i]<z[i-1])//递减
            {
                if(ok==1)
                 {
                      ok=0;
                      break;
                 }
                if(z[i-1]<=z[i+1])
                    ok=1;
                else
                {
                    if(z[i-2]<=z[i])
                        ok=1;
                    else
                    {
                        ok=0;
                        break;
                    }
                }

            }
        }
        if(ok==0&&i==n+1)
            ok=1;
        if(ok==1)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}
View Code

L  t组数据  n m  然后m*n矩阵  求表面积  最下面不算

找相邻2个柱子之间的关系 

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<math.h>
#include<queue>
#include<stdlib.h>
#include<vector>
#include<map>

using namespace std;

#define MAXN 110
#define inf  1000000007
#define ll long long

int z[MAXN][MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
         memset(z,0,sizeof(z));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&z[i][j]);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(z[i][j-1]<z[i][j])
                {
                    ans=ans+z[i][j]-z[i][j-1];
                }
                if(z[i][j+1]<z[i][j])
                {
                    ans=ans+z[i][j]-z[i][j+1];
                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(z[j][i]>z[j-1][i])
                    ans=ans+z[j][i]-z[j-1][i];
                if(z[j+1][i]<z[j][i])
                    ans=ans+z[j][i]-z[j+1][i];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                if(z[i][j])
                    ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

n^3 

技术分享
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>

using namespace std ;

#define ll __int64
#define MAXN 1010
#define inf  1000000007
#define exp  1e-8

int z[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&z[i]);
        int ans=0;

        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                int a=z[i]+z[j];
                for(int k=1;k<=n;k++)
                {
                    if(i==k||j==k)
                        continue;
                    int b=a^z[k];
                    if(b>ans)
                        ans=b;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

G 求是不是正多边形    极角排序  相邻的2点构成的边 边长相等   然后相邻的边形成的夹角相等 

技术分享
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>

using namespace std ;

#define ll __int64
#define MAXN 310
#define inf  1000000007
#define exp  1e-8

struct point
{
    public:
        int x,y;
        int operator ^ (point b)
        {
            return x*b.y-y*b.x;
        }
        point operator -(point b)
        {
            point c;
            c.x=x-b.x;
            c.y=y-b.y;
            return c;
        }
}res[MAXN];
double dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}


bool cmp(point a,point b)
{
    int tmp=( ((a-res[0]) ^ (b-res[0])));
    if(tmp>0)
        return 1;
    if(tmp==0&&dis(a,res[0])<dis(b,res[0]))
        return 1;
    return 0;
}


int main()
{
        int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d",&res[i].x,&res[i].y);
        int c1=0;
        for(int i=1;i<n;i++)
        {
            if(res[i].x<res[c1].x)
                c1=i;
            if(res[i].x==res[c1].x&&res[i].y<res[c1].y)
                c1=i;
        }
        swap(res[0],res[c1]);
        sort(res+1,res+n,cmp);
        res[n]=res[0];
        res[n+1]=res[1];
        double d1=dis(res[0],res[1]);
        point x,y;
        x=res[1]-res[0];
        y=res[2]-res[1];
        double dd=x.x*y.x+x.y*y.y;
        double c2=dd/(sqrt(x.x*x.x+x.y*x.y)*sqrt(y.x*y.x+y.y*y.y));
        int ok=0;
        for(int i=0;i<n;i++)
        {
            double d2,d3;
            d2=dis(res[i],res[i+1]);
            d3=dis(res[i+1],res[i+2]);
            if(fabs(d1-d2)>exp||fabs(d1-d3)>exp)
                ok=1;
            x=res[i+1]-res[i];
            y=res[i+2]-res[i+1];
            double dd1=x.x*y.x+x.y*y.y;
            double c11=dd/(sqrt(x.x*x.x+x.y*x.y)*sqrt(y.x*y.x+y.y*y.y));
            if(fabs(c11-c2)>exp)
                ok=1;
        }
        if(ok==0)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}
View Code

K  an=2*a(n-2) +a(n-1) + n^4  快速幂 

 7*7矩阵

技术分享
#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#include<math.h>

using namespace std ;

#define ll long long
#define MAXN 1010
#define inf  2147493647
#define exp  1e-8

struct node
{
    ll z[7][7];
};
node mou(node a,node b,ll c)
{
    node ans;
    memset(ans.z,0,sizeof(ans.z));
    for(int i=0;i<7;i++)
    {
        for(int j=0;j<7;j++)
        {
            ll sum=0;
            for(int k=0;k<7;k++)
            {
                sum=(sum+a.z[i][k]*b.z[k][j])%c;
            }
            ans.z[i][j]=sum;
        }
    }
    return ans;
}
node quick(node a,ll b,ll c)
{
    node ans;
    memset(ans.z,0,sizeof(ans.z));
    for(int i=0;i<7;i++)
        ans.z[i][i]=1;
    while(b>0)
    {
        if(b&1)
            ans=mou(ans,a,c);
        b>>=1;
        a=mou(a,a,c);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,d,b;
        scanf("%lld%lld%lld",&n,&d,&b);
        if(n==1)
            printf("%lld\n",d);
        else if(n==2)
            printf("%lld\n",b);
        else
        {
            node a;
            memset(a.z,0,sizeof(a.z));
            a.z[0][1]=2;
            a.z[5][4]=2;
            a.z[1][0]=a.z[1][1]=a.z[2][1]=a.z[2][2]=a.z[3][3]=a.z[4][4]=a.z[5][5]=a.z[6][2]=a.z[6][3]=a.z[6][4]=a.z[6][5]=a.z[6][6]=1;
            a.z[4][3]=a.z[5][3]=3;
            a.z[3][2]=a.z[5][2]=4;
            a.z[4][2]=6;
            a.z[3][1]=4;
            a.z[4][1]=6;
            a.z[5][1]=4;
            a.z[6][1]=1;
            node c=quick(a,n-2,inf);
            int x[7]={0,0,16,8,4,2,1};
            x[0]=d;
            x[1]=b;
            ll ans=0;
            for(int i=0;i<7;i++)
                ans=(ans+(x[i]*c.z[i][1])%inf)%inf;
            printf("%lld\n",ans);
        }
    }
    return 0;
}
View Code

 

2015 长春