2016年湖南省第十二届大学生计算机程序设计竞赛(重现)

2017-07-06 127点热度 1人点赞

A(1803):2016

Submit Page    Summary    Time Limit: 5 Sec     Memory Limit: 128
Mb
     Submitted: 245     Solved: 134    

Description

 给出正整数 n m,统计满足以下条件的正整数对
(a,b)
的数量:

1. 1≤a≤n,1≤b≤m;

2. a×b 2016的倍数。

Input

输入包含不超过 30
组数据。

每组数据包含两个整数 n,m (1≤n,m≤109).

Output

对于每组数据,输出一个整数表示满足条件的数量。

Sample Input

32 63

2016 2016

1000000000 1000000000

Sample Output

1

30576

7523146895502644

容斥原理实现

以下是暴力实现代码

#include

#include

#include

using namespacestd;

int n,m;

int main(){

       ios::sync_with_stdio(0);

       long long t1=0;

       for(int i=1;i<=2016;i++)

       for(int j=1;j<=2016;j++)

       if(i*j%2016==0) t1++;

       while(cin>>n>>m)

       {

              long long t2=0,t3=0,t4=0,ans=0;

              t2=ans=0;

              int l1=n%2016,l2=m%2016;

              for(int i=1;i<=l1;i++)

              for(int j=1;j<=l2;j++)

              if(i*j%2016==0) t2++;

              for(int i=1;i<=l1;i++)

              for(int j=1;j<=2016;j++)

              if(i*j%2016==0) t3++;

              for(int i=1;i<=l2;i++)

              for(int j=1;j<=2016;j++)

              if(i*j%2016==0) t4++;

              cout<

        }

       return 0;

}

 

B(1804):有向无环图

Submit Page    Summary    Time Limit: 5 Sec     Memory Limit: 128
Mb
     Submitted: 77     Solved: 32    

Description

Bobo 有一个 n个点,m条边的有向无环图(即对于任意点
v
,不存在从点 v开始、点 v结束的路径)。

为了方便,点用 1,2,…,n编号。 count(x,y)表示点
x
到点 y
不同的路径数量(规定 count(x,x)=0),Bobo想知道

除以 (109+7)的余数。

其中,ai,bj 是给定的数列。

Input

输入包含不超过 15
组数据。

每组数据的第一行包含两个整数 n,m (1≤n,m≤105).

接下来 n 行的第 i行包含两个整数 ai,bi (0≤ai,bi≤109).

最后 m 行的第 i行包含两个整数 ui,vi,代表一条从点
u
i  vi 的边
(1≤u
i,vi≤n)

Output

对于每组数据,输出一个整数表示要求的值。

Sample Input

3 3

1 1

1 1

1 1

1 2

1 3

2 3

2 2

1 0

0 2

1 2

1 2

2 1

500000000 0

0 500000000

1 2

Sample Output

4

4

250000014

//有向无环图,记忆化搜索

#include

#include

#include

using namespace std;

const int M=1e+9+7;

const int mn=1e+5+100;

int n,m;

long long a[mn],b[mn];

int head[mn];

int in[mn];//入度个数

long long dp[mn];

struct node

{

    int to,next;

} edge[mn];

long long dfs(int u)

{

        if(dp[u]!=-1)return dp[u];

        dp[u]=0;

    for(intj=head[u]; j!=-1; j=edge[j].next)

    {

        intv=edge[j].to;

       dp[u]+=dfs(v)+b[v];

    }

    returndp[u]=dp[u]%M;//一开始没打=,wa了半天

}

int main()

{

    int u,v;

   ios::sync_with_stdio(0);

   while(cin>>n>>m)

    {

        for(inti=1; i<=n; i++)

           cin>>a[i]>>b[i];

        memset(head,-1,sizeof(head));

       memset(in,0,sizeof(in));

       memset(dp,-1,sizeof(dp));

        for(inti=0; i

        {

           cin>>u>>v;

           edge[i].next=head[u];

           edge[i].to=v;

           head[u]=i;

           in[v]=1;

        }

        for(inti=1; i<=n; i++)

           if(in[i]==0) dfs(i);

    long longans=0;

    for(inti=1;i<=n;i++)

    ans=(ans+(longlong)a[i]*dp[i]%M)%M;

   cout<

    }

    return 0;

}

 

F(1808):地铁

SubmitPage    Summary    TimeLimit: 5 Sec     MemoryLimit: 128 Mb     Submitted: 174     Solved: 14    


Description

 Bobo 居住在大城市 ICPCCamp

ICPCCamp n个地铁站,用 1,2,…,n编号。
m
段双向的地铁线路连接 n个地铁站,其中第 i
段地铁属于 ci 号线,位于站 ai,bi 之间,往返均需要花费 ti 分钟(即从
ai 
bi 需要 ti 分钟,从 bi 
ai 
也需要 ti 分钟)。

众所周知,换乘线路很麻烦。如果乘坐第 i段地铁来到地铁站 s,又乘坐第
j
段地铁离开地铁站 s,那么需要额外花费 |ci-cj |分钟。注意,换乘只能在地铁站内进行。

Bobo 想知道从地铁站 1到地铁站 n所需要花费的最小时间。

Input

输入包含不超过 20组数据。

每组数据的第一行包含两个整数 n,m (2≤n≤105,1≤m≤105).

接下来 m行的第 i行包含四个整数ai,bi,ci,ti (1≤ai,bi,ci≤n,1≤ti≤109).

保证存在从地铁站 1 n的地铁线路(不一定直达)。

Output

对于每组数据,输出一个整数表示要求的值。

Sample Input

3 3

1 2 1 1

2 3 2 1

1 3 1 1

3 3

1 2 1 1

2 3 2 1

1 3 1 10

3 2

1 2 1 1

2 3 1 1

Sample Output

1

3

2

//地铁,把边看做点来做最短路,dijkstra+堆优化

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef pair pii;

const int mn=1e3+10;

const int mm=2e5+10;

int n,m,head[mm];

int t[mm];

long long dis[mm];

bool vis[mm];

struct node{

        intto,w,next;

}edge[mm];

long long dijstra()

{

        priority_queue,greater> q;

        memset(dis,6,sizeof(dis));

        for(inti=head[1];i!=-1;i=edge[i].next)

        {

               dis[i]=edge[i].w;

               q.push(make_pair(dis[i],i));

        }

        pii x;

        while(!q.empty())

        {

               x=q.top();

               q.pop();

               intp=x.second;

               intu=edge[p].to;

               if(u==n)return dis[p];

               for(inti=head[u];i!=-1;i=edge[i].next)

               {

                       intv=edge[i].to;

                       if(!vis[u]&&dis[i]>dis[p]+edge[i].w+abs(t[i]-t[p]))

                       {

                               dis[i]=dis[p]+edge[i].w+abs(t[i]-t[p]);

                               q.push(make_pair(dis[i],i));

                       }

               }

        }

        return -1;

}

int main()

{

        intu,v,tt,w;

        ios::sync_with_stdio(0);

        while(cin>>n>>m)

        {

               memset(head,-1,sizeof(head));

               for(inti=0;i

               {

                       cin>>u>>v>>tt>>w;

                       edge[i].to=v;

                       edge[i].w=w;

                       edge[i].next=head[u];

                       head[u]=i;

                      

                       edge[i+m].to=u;

                       edge[i+m].w=w;

                       edge[i+m].next=head[v];

                       head[v]=i+m;

                      

                       t[i]=t[i+m]=tt;

               }

               cout<

        }

        return 0;

}

 

G(1809): Parenthesis

SubmitPage    Summary    TimeLimit: 5 Sec     MemoryLimit: 128 Mb     Submitted: 447     Solved: 87    


Description

Bobo has abalanced parenthesis sequenceP=p1 p2…pn of length n and q questions.

The i-thquestion is whether P remainsbalanced after pai and pbi  swapped. Note that questionsareindividual so that they have no affect on others.

Parenthesissequence S is balanced if andonly if:

1. S is empty;

2. orthereexists balanced parenthesis sequence A,B such that S=AB;

3. orthereexists balanced parenthesis sequence S' such that S=(S').

Input

The inputcontains at most 30 sets. Foreach set:

The first linecontains two integers n,q(2≤n≤105,1≤q≤105).

The second linecontains n charactersp1 p2…pn.

The i-th of thelast q lines contains 2integers ai,bi (1≤ai,bi≤n,ai≠bi).

Output

For eachquestion, output "Yes"if P remains balanced, or "No"otherwise.

Sample Input

4 2

(())

1 3

2 3

2 1

()

1 2

Sample Output

No

Yes

No

 

//没用线段树,直接暴力过了

#include

#include

#include

using namespace std;

int n,m;

const int mn=100000+10;

char s[mn];

int a[mn];

int main(){

        //freopen("1.txt","r",stdin);

        //freopen("1.txt","w",stdout);

        int l,r;

        while(~scanf("%d%d",&n,&m))

        {

               scanf("%s",s+1);

               intlen=n;

               intft=0;

               for(inti=1;i<=len;i++)

               {

                       if(s[i]=='(')a[i]=a[i-1]+1;

                       elsea[i]=a[i-1]-1;

                       if(a[i]<0)ft=1;

               }

               while(m--)

               {

                       if(ft==1)puts("No");

                       scanf("%d%d",&l,&r);//刚开始没加这个wa了半天

                       if(l>r)swap(l,r);

                       if(s[l]==s[r]||s[l]==')')puts("Yes");

                       elseif(l==1||r==n) puts("No");

                       else

                       {

                               intf=1;

                               for(inti=l;i

                               if(a[i]<2)

                               {

                                      f=0;

                                      break;

                               }

                               if(f)puts("Yes");

                               elseputs("No");

                       }

               }

        }

        return 0;

}

 

未经允许不得转载!2016年湖南省第十二届大学生计算机程序设计竞赛(重现)

本文地址:https://ai.52learn.online/531

站长邮箱:ai52learn@foxmail.com