首页 > 代码库 > 2017 女生赛

2017 女生赛

A直接模拟

1 CE算罚时 2  后面的罚时不算  3错掉 过了才算罚时

技术分享
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<iterator>
#include<stack>

using namespace std;

#define ll  __int64
#define MAXN  101000
#define inf  1000000007

bool vis[MAXN];
int w[MAXN];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        memset(vis,0,sizeof(vis));
        memset(w,0,sizeof(w));
        scanf("%d%d",&n,&m);
        int ans=0;
        int cnt=0;
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            char s[10];
            scanf("%d %d:%d %s",&a,&b,&c,s);
            int t=b*60+c;
            if(vis[a]==0&&strcmp(s,"AC")!=0)
            {
                w[a]++;
            }
            if(vis[a]==0&&strcmp(s,"AC")==0)
            {
                vis[a]=1;
                ans=ans+t+w[a]*20;
            }
        }
        for(int i=1;i<=2000;i++)
            if(vis[i]==1)
               cnt++;
        printf("%d %d\n",cnt,ans);
    }

    return 0;
}
View Code

B

n 个地点然后 位置 开糖果店的花费如果这个点不开  那么花费算这个点到左边最近的糖果店的距离

dp[i][j] dp[0][j] 代表这个点不开最小花费  dp[1][j]代表开  最小花费 时间 n方

技术分享
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<iterator>
#include<stack>

using namespace std;

#define ll  long long
#define MAXN  301000
#define inf  1000000007

struct node
{
    ll x,y;
}z[MAXN];

bool cmp(node a,node b)
{
    return a.x<b.x;
}
ll dp[2][MAXN];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%lld%lld",&z[i].x,&z[i].y);
        sort(z+1,z+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            dp[0][i]=inf;
            dp[1][i]=inf;
        }
        dp[0][0]=0;
        dp[1][0]=0;
        for(int i=1;i<=n;i++)
        {
            dp[1][i]=min(dp[0][i-1],dp[1][i-1])+z[i].y;
            ll ans=0;
            for(int j=i-1;j>=1;j--)
            {
                ans=ans+(i-j)*(z[j+1].x-z[j].x);
                dp[0][i]=min(dp[0][i],dp[1][j]+ans);
            }
        }
        printf("%lld\n",min(dp[0][n],dp[1][n]));
    }
    return 0;
}
View Code

C求去掉一个数剩下数的GCD  求最大的GCD

我用线段树维护了gcd 其实可以不用 维护前缀gcd和后缀gcd 时间是n  我的是nlog(n)

技术分享
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<iterator>
#include<stack>

using namespace std;

#define ll  __int64
#define MAXN  101000
#define inf  1000000007

struct node
{
    int l,r,w;
}tree[MAXN<<2];
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}

void Build(int l,int r,int a)
{
    tree[a].l=l;
    tree[a].r=r;
    if(l==r)
    {
        scanf("%d",&tree[a].w);
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,a<<1);
    Build(mid+1,r,a<<1|1);
    tree[a].w=gcd(tree[a<<1].w,tree[a<<1|1].w);
}
int Ques(int l,int r,int a1,int b1,int a)
{
    if(a1<=l&&r<=b1)
        return tree[a].w;
    int mid=(l+r)>>1;
    int ans=0;
    if(a1<=mid)
        ans=gcd(ans,Ques(l,mid,a1,b1,a<<1));
    if(b1>mid)
        ans=gcd(ans,Ques(mid+1,r,a1,b1,a<<1|1));
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        Build(1,n,1);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(i==1)
            {
                ans=max(ans,Ques(1,n,i+1,n,1));
            }
            else if(i==n)
            {
                ans=max(ans,Ques(1,n,1,i-1,1));
            }
            else
            {
                int d=gcd(Ques(1,n,1,i-1,1),Ques(1,n,i+1,n,1));
                ans=max(d,ans);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

E直接暴力

技术分享
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<iterator>
#include<stack>

using namespace std;

#define ll  __int64
#define MAXN  101000
#define inf  1000000007

ll z[6][10010];

int main()
{
    for(int i=1;i<=10000;i++)
    {
         z[0][i]=z[0][i-1]+1;
         z[1][i]=(z[1][i-1]+i)%inf;
         z[2][i]=(z[2][i-1]+i*i)%inf;
         z[3][i]=(z[3][i-1]+((((long long)i*i)%inf)*i)%inf)%inf;
         z[4][i]=((z[4][i-1]+(((((long long)i*i)%inf)*i)%inf)*i)%inf)%inf;
         z[5][i]=(z[5][i-1]+(((((((((long long)i*i)%inf)*i)%inf)*i)%inf)%inf)*i)%inf)%inf;
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",z[m][n]);
    }
    return 0;
}
View Code

G n个点  n-1个操作   1 或者2  1 代表这个点和前面的点都有边  2 没操作 

问能不能是个完美匹配的图   水题一个  记录下前面没匹配的点的数目就行了   

技术分享
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<map>
#include<iterator>
#include<stack>

using namespace std;

#define ll  long long
#define MAXN  101000
#define inf  1000000007

int z[MAXN];

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

        for(int i=2;i<=n;i++)
        {
            if(z[i]==1&&c1>0)
            {
                c1--;
                cnt=cnt-2;
            }
            else
            {
                c1++;
            }
        }
        if(cnt==0)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
View Code

 

2017 女生赛