BestCoder Round #32

问题描述

目前，我们用PM2.5的含量来描述空气质量的好坏。一个城市的PM2.5含量越低，它的空气质量就越好。所以我们经常按照PM2.5的含量从小到大对城市排序。一些时候某个城市的排名可能上升，但是他的PM2.5的含量也上升了。这就意味着他的空气质量并没有改善。所以这样的排序方式是不合理的。为了使得排序合理，我们提出了一个新的排序方法。我们按照两个PM2.5含量测量的差值（第一次-第二次）来对他们按降序排序，如果有重复，按照第二次的测量值升序排序，如果还有重复，按照输入的顺序排序。

输入描述

多组测试数据(大概100组)，每一组测试数据第一行先给出一个整数n，代表有n个城市需要被排序。城市被从0到n−1标号。接下来n行，每一含有两个整数代表每一个城市第一次和第二次被测量的PM2.5值。第i行描述城市i−1的信息。

请处理到文件末尾。

[参数说明]

所有整数都在[1,100]的范围内。

输出描述

对于每一个数据，输出排好序之后的城市ID。

输入样例

输出样例

0 1

0 2 1

思路:三关键词排序

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define maxn 1000

 char ch[maxn];

 using namespace std;

 struct T

 {

     int x;int y;int z;

 }a[maxn];

 int cmp(T x,T y)

 {

     return ((x.x>y.x) ||((x.x==y.x && (x.y<y.y))) || (x.x==y.x && x.y==y.y && (x.z<y.z)));

 }

 int main()

 {

     int n,x,y;

     while(scanf("%d",&n)!=EOF)

     {

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

         {

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

             a[i].x=x-y;

             a[i].y=y;

             a[i].z=i-;

         }

         sort(a+,a++n,cmp);

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

         {

             printf("%d ",a[i].z);

         }

         printf("%d\n",a[n].z);

     }

     return ;

 }

问题描述

给定一个数组(a0,a1,a2,⋯an−1)和一个整数K， 请来判断一下是否存在二元组(i,j)(0≤i≤j<n)使得 NP−sum(i,j) 刚好为K。这里NP−sum(i,j)=ai−ai+1+ai+2+⋯+(−1)j−iaj。

输入描述

多组测试数据。在文件的第一行给出一个T，表示有T组数据。

在接下来的2∗T行里，将会给出每一组数据。

每一组数据占两行，第一行包含n和K。

第二行包含(a0,a1,a2,⋯an−1)以一个空格分开。

[参数说明]

所有输入均为整数。

0<T≤25,1≤n≤1000000,−1000000000≤ai≤1000000000,−1000000000≤K≤1000000000

输出描述

对于每一个数据，输出占一行，输出格式是Case #id: ans,这儿id是数据编号，从1开始，ans是根据是否找到满足的二元组而定为“Yes.” 或 “No.” (不包含引号)

看样例可以获得更多的信息。

输入样例

输出样例

Case #1: Yes.

Case #2: No.

Hint

如果数据比较多，建议使用快速读入

思路: 比赛的时候认为这个规模带log的都会卡,不然直接map了,然后学了种挂链表的神奇的ＨＡＳＨ

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #define maxn 1000009

 #define MOD 10000009

 using namespace std;

 int head[MOD+],nex[maxn],a[maxn];

 long long point[maxn],now=,sum[maxn];

 long long n,k;

 int add(int x,int y)

 {

     nex[++now]=head[x];

     head[x]=now;

     point[now]=y;

 }

 void insert(long long x)

 {

     long long u=x%MOD;if(u<)u*=-;

     for(int i=head[u];i;i=nex[i])

     {

         if(point[i]==x)return;

     }

     add(u,x);

 }

 int find(long long x)

 {

     long long u=x%MOD;if(u<)u*=-;

     for(int i=head[u];i;i=nex[i])

     {

         if(point[i]==x)return ;

     }

     return ;

 }

 long long read()

 {

     long long x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int main()

 {

     int t,cas=;

     t=read();

     while(t--)

     {

         n=read();k=read();

         for(int i=;i<=n;i++)a[n-i+]=read();

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

         {

             if(i&)

             {

                 sum[i]=sum[i-]+a[i];

             }else sum[i]=sum[i-]-a[i];

         }

         int flag=;

         insert();

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

         {

             if(i&)

             {

                 if(find(sum[i]-k)){flag=;break;}

             }

             else if(find(sum[i]+k)){flag=;break;}

             insert(sum[i]);

         }

         printf("Case #%d: ",++cas);

         if(flag)printf("Yes.\n");

         else printf("No.\n");

         memset(head,,sizeof(head));

         now=;

     }

     return ;

 }

HDU 5184 Brackets

问题描述

我们给出下列递归的合法括号序列的定义：

  ● 空序列是合法括号序列

  ● 如果s是一个合法括号序列，那么(s)也是合法括号序列

  ● 如果a和b是合法括号序列，那么ab也是合法括号序列

  ● 没有其它情况是合法括号序列

比如下列括号序列是合法括号序列

(), (()), ()(), ()(())

下列括号序列则不是

(, ), )(, ((), ((()

现在，我们要构造长度为n的合法括号序列，前面的一些括号已经给出，问可以构造出多少合法序列。

输入描述

多组测试数据(大概2000)，每一组数据占两行。

第一行给出一个整数n。

第二行给出一个字符串代表前面已经确定的几个括号。

请处理到文件末尾。

[参数约定]

1≤n≤1000000

字符串只包含’(’和’)’，长度大于0并且不超过n.

输出描述

对于每一个数据，在一行中输出答案对1000000007取余的结果。

输入样例

4

()

4

(

6

()

输出样例

Hint

第一组数据只有一种可能，它就是()().

对于第二组数据他有两种可能，他们是(()) 和()().

对于第三种数据，两种可能是()()() 和()(()).

思路:这题建模有点醉啊问题可以变成,从（０，０）到(n/2-a,n/2-b)且不越过y=x 这条线的方案数,然后从(0,0)到(p,q)且不经过y=x的方案数是Ｃ（p,p+q）-C(p-1,p+q)

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define MOD 1000000007

 #define LLD "%lld"

 #define maxn 1000009

 #define ll long long

 using namespace std;

 char ch[maxn];

 ll fac[maxn],inv[maxn];

 ll qpow(ll a,ll n)

 {

     ll ret=;

     for(;n;n>>=)

     {

         if(n&)ret=(ret*a)%MOD;

         a=(a*a)%MOD;

     }

     return ret;

 }

 ll C(ll n,ll m)

 {

         if(m==)return ;

         ll u=fac[n],v = inv[n-m],w=inv[m];

     return (((fac[n]*inv[n-m])%MOD)*inv[m])%MOD;

 }

 int main()

 {

     ll n;

     fac[]=;

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

     {

         fac[i]=(fac[i-]*(long long)i)%MOD;

         inv[i]=qpow(fac[i],MOD-)%MOD;

     }

     while(scanf( LLD "%s",&n,ch+)!=EOF)

     {

         if(n&)

         {

             puts("");

             continue;

         }

         ll len=strlen(ch+);

         ll lef=,flag=,a=,b=;

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

         {

             if(ch[i]=='(')a++;else b++;

             if(ch[i]=='(')lef++;

             else if(lef!=)lef--;

             else flag=;

         }

         if(flag){puts("");continue;}

         ll p=( n >>  ) - a,q= ( n >>  ) - b;

         if(p< ||q<){puts("");continue;}

         if(p>q)swap(p,q);

         ll u =  C(p + q , p), v = C(p + q ,p - );

         printf(LLD "\n" , (C(p + q , p) - C(p + q,p - ) + MOD ) % MOD);

     }

     return ;

 }

巴特西

BestCoder Round #32

最新文章

热门文章