文档章节

2019 年百度之星·程序设计大赛 - 初赛三

o
 osc_ogi0qclx
发布于 2019/08/24 18:06
字数 1865
阅读 7
收藏 0
mu

精选30+云产品,助力企业轻松上云!>>>

 

P.S:关于初赛二,在高铁上打代码真是奇怪的体验!!!

1003,1004的题解很不错,学习了!

 

===========================================

 

一开场把所有的题目看了一遍,这题面风格,感觉凉凉。还好,往下做时,题目不是太坑。

 

1002

floyd转dijkstra+堆优化,感觉是套路题了

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 #include <queue>
 11 
 12 const double eps=1e-8;
 13 const ll inf=1e9;
 14 const ll mod=998244353;
 15 const int maxn=1e3+10;
 16 
 17 struct node
 18 {
 19     int d;
 20     ll len;
 21     node *to;
 22 }*e[maxn];
 23 
 24 struct rec
 25 {
 26     int d,maxd;
 27     ll dist;
 28     bool operator<(const rec &y) const
 29     {
 30         return dist>y.dist;
 31     }
 32 };
 33 
 34 priority_queue<rec,vector<rec> > st;
 35 
 36 ll dist[maxn];
 37 int maxp[maxn];
 38 
 39 int main()
 40 {
 41     node *p;
 42     int t,n,m,u,v,i,j,be,dd;
 43     ll sum,w;
 44     scanf("%d",&t);
 45     while (t--)
 46     {
 47         scanf("%d%d",&n,&m);
 48         for (i=1;i<=n;i++)
 49             e[i]=0;
 50         while (m--)
 51         {
 52             scanf("%d%d%I64d",&u,&v,&w);
 53             p=new node();
 54             p->d=v;
 55             p->len=w;
 56             p->to=e[u];
 57             e[u]=p;
 58 
 59             p=new node();
 60             p->d=u;
 61             p->len=w;
 62             p->to=e[v];
 63             e[v]=p;
 64         }
 65         sum=0;
 66         for (be=1;be<=n;be++)
 67         {
 68             memset(dist,0x7f,sizeof(dist));
 69             dist[be]=0;
 70             memset(maxp,0,sizeof(maxp));
 71 
 72             while (!st.empty())
 73                 st.pop();
 74 
 75             st.push({be,0,0});
 76             while (!st.empty())
 77             {
 78                 u=st.top().d;
 79                 v=st.top().maxd;
 80                 w=st.top().dist;
 81                 st.pop();
 82                 if (w!=dist[u] || v!=maxp[u])
 83                     continue;
 84                 if (u!=be)
 85                     v=max(v,u);
 86 
 87                 p=e[u];
 88                 while (p)
 89                 {
 90                     dd=p->d;
 91                     if (dist[dd]>w+p->len || (dist[dd]==w+p->len && maxp[dd]>v))
 92                     {
 93                         dist[dd]=w+p->len;
 94                         maxp[dd]=v;
 95                         st.push({dd,v,dist[dd]});
 96                     }
 97                     p=p->to;
 98                 }
 99             }
100 
101             for (i=1;i<=n;i++)
102                 sum+=maxp[i];
103         }
104         printf("%I64d\n",sum%mod);
105     }
106     return 0;
107 }
108 /*
109 2
110 4 2
111 1 2 3
112 2 3 4
113 
114 4 4
115 1 2 1
116 2 3 1
117 3 4 1
118 4 1 1
119 */
120 
121

 

 

但群里有人说,数据不严谨,很多水方法都过了。

 

1003

应该是本人生涯中mobius第一题(赛中),庆祝一下。。。

虽然已经退役了……

 

公式:

mu(x*y)=mu(x)*mu(y)*(gcd(x,y)==1)

跟同学探讨后,以下方法更合理一点

(gcd(i,k)==1)*(gcd(j,k)==1)*mu(i)*mu(j)
=
(gcd(i,k)==1)*(gcd(j,k)==1)*mu(i)*mu(j)*mu(k)*mu(k)
=
mu(ik)*mu(jk)

 

为什么要这样做呢?

想着肯定是只能留一个,即去掉剩下的两个gcd()。

关于gcd(x,y)=1,就是套路了。

 

计算了一下i=1-1e6 mu(i)非0的个数

607926

 

n=1e6时的值,

9185685 (mu!=0)
13970034 (无限制)

 

9185685*10(T) 九千万……

 

原来还是抱了服务器的大腿过的……

 

进一步优化,来自Codeforces讨论(翻译)群群友,

k和d两项合并,

 

时间复杂度

预处理 一千多万

查询 O(nT)

这下没问题了。

 

未优化的代码

比赛时ok,赛后超时了,尴尬……

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 #include <vector>
11 
12 const double eps=1e-8;
13 const ll inf=1e9;
14 const ll mod=1e9+7;
15 const int maxn=1e6+10;
16 
17 int maxv=1e6;
18 
19 bool vis[maxn];
20 int zhi[maxn],cnt_zhi,mu[maxn];
21 vector<int> vec[maxn];
22 
23 int main()
24 {
25     int t,n,m,i,j,k,p,q;
26     ll sum,ans;
27     for (i=2;i<=maxv;i++)
28     {
29         if (!vis[i])
30         {
31             zhi[++cnt_zhi]=i;
32             mu[i]=-1;
33         }
34         for (j=1;j<=cnt_zhi;j++)
35         {
36             k=i*zhi[j];
37             if (k>maxv)
38                 break;
39             vis[k]=1;
40             if (i%zhi[j]==0)
41                 break;
42             else
43                 mu[k]=-mu[i];
44         }
45     }
46     mu[1]=1;
47 
48     for (i=1;i<=maxv;i++)
49     {
50         sum=0;
51         vec[i].push_back(0);
52         for (j=i,k=1;j<=maxv;j+=i,k++)
53         {
54             sum+=mu[j];
55             vec[i].push_back(sum);
56         }
57     }
58 //    exit(0);    ///2.147 s
59 //    printf("%d %d %d",vec[1][5],vec[1][3],vec[2][3]);
60 
61 //    for (i=1;i<=5;i++)
62 //        printf("%d ",mu[i]);
63 //    printf("\n");
64 //    for (i=1;i<=5;i++)
65 //        printf("%d ",vec[1][i]);
66 //    printf("\n");
67 //    for (i=1;i<=5;i++)
68 //        printf("%d ",vec[2][i]);
69 //    printf("\n");
70 
71     scanf("%d",&t);
72     while (t--)
73     {
74         sum=0;
75         scanf("%d%d",&n,&m);
76         p=min(n,m);
77         ///array cal mu[i]!=0
78         for (i=1;i<=p;i++)
79             if (mu[i]!=0)
80             {
81                 ans=0;
82                 q=p/i;
83                 for (j=1;j<=q;j++)
84 //                    ans+=1ll*mu[j]*vec[j][n/(i*j)]*vec[j][m/(i*j)];
85                     ans+=1ll*mu[j]*vec[i*j][n/(i*j)]*vec[i*j][m/(i*j)];
86                 sum+=mu[i]*ans;
87             }
88         printf("%I64d\n",sum);
89     }
90     return 0;
91 }

 

优化后的代码

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 #include <vector>
11 
12 const double eps=1e-8;
13 const ll inf=1e9;
14 const ll mod=1e9+7;
15 const int maxn=1e6+10;
16 
17 int maxv=1e6;
18 
19 bool vis[maxn];
20 int zhi[maxn],cnt_zhi,mu[maxn];
21 ll ans[maxn];
22 vector<int> vec[maxn];
23 
24 int main()
25 {
26     int t,n,m,i,j,k,p;
27     ll sum;
28     for (i=2;i<=maxv;i++)
29     {
30         if (!vis[i])
31         {
32             zhi[++cnt_zhi]=i;
33             mu[i]=-1;
34         }
35         for (j=1;j<=cnt_zhi;j++)
36         {
37             k=i*zhi[j];
38             if (k>maxv)
39                 break;
40             vis[k]=1;
41             if (i%zhi[j]==0)
42                 break;
43             else
44                 mu[k]=-mu[i];
45         }
46     }
47     mu[1]=1;
48 
49     for (i=1;i<=maxv;i++)
50     {
51         sum=0;
52         vec[i].push_back(0);
53         for (j=i,k=1;j<=maxv;j+=i,k++)
54         {
55             sum+=mu[j];
56             vec[i].push_back(sum);
57         }
58     }
59 
60     for (i=1;i<=maxv;i++)
61         if (mu[i]!=0)
62         {
63             k=maxv/i;
64             for (j=1;j<=k;j++)
65                 ans[i*j]+=mu[i]*mu[j];
66         }
67 
68     scanf("%d",&t);
69     while (t--)
70     {
71         sum=0;
72         scanf("%d%d",&n,&m);
73         p=min(n,m);
74         ///array cal mu[i]!=0
75         for (i=1;i<=p;i++)
76             sum+=ans[i]*vec[i][n/i]*vec[i][m/i];
77         printf("%I64d\n",sum);
78     }
79     return 0;
80 }

 

 

1004

可能求导数,卡了一波人,尤其是现在以小学生打比赛比较多的情况下……

感觉是个大水题,遗憾没时间写了。

 

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <string>
  6 #include <algorithm>
  7 #include <iostream>
  8 using namespace std;
  9 #define ll long long
 10 
 11 const double eps=1e-8;
 12 const ll inf=1e9;
 13 const ll mod=998244353;
 14 const int maxn=1<<20|1;
 15 
 16 ll x[maxn];
 17 char op[maxn];
 18 
 19 int main()
 20 {
 21     int m,q,mode,ind,d,dd,i;
 22     ll v,y;
 23     scanf("%d%d",&m,&q);
 24     for (i=1;i<=(1<<(m-1));i++)
 25         x[(1<<(m-1))-1+i]=i;
 26     scanf("%s",op+1);
 27 
 28     ///init
 29     for (i=(1<<(m-1))-1;i>=1;i--)
 30     {
 31         d=i;
 32         if (op[d]=='1')
 33             x[d]=x[d<<1]*x[d<<1|1]%mod;
 34         else
 35             x[d]=(x[d<<1]+x[d<<1|1])%mod;
 36     }
 37 
 38     while (q--)
 39     {
 40         scanf("%d%d",&mode,&ind);
 41         d=ind-1+(1<<(m-1));
 42         if (mode==1)
 43         {
 44             scanf("%lld",&y);
 45             x[d]=y;
 46             while (d!=1)
 47             {
 48                 if (d&1)
 49                     dd=d-1;
 50                 else
 51                     dd=d+1;
 52 
 53                 if (op[d>>1]=='1')
 54                     x[d>>1]=x[d]*x[dd]%mod;
 55                 else
 56                     x[d>>1]=(x[d]+x[dd])%mod;
 57                 d>>=1;
 58             }
 59         }
 60         else
 61         {
 62             v=1;
 63             while (d!=1)
 64             {
 65                 if (d&1)
 66                     dd=d-1;
 67                 else
 68                     dd=d+1;
 69 
 70                 if (op[d>>1]=='1')
 71                     v=v*x[dd]%mod;
 72                 d>>=1;
 73             }
 74             printf("%lld\n",v);
 75         }
 76     }
 77     return 0;
 78 }
 79 /*
 80 3 100
 81 000
 82 2 1
 83 2 2
 84 2 3
 85 2 4
 86 
 87 3 100
 88 001
 89 2 1
 90 2 2
 91 2 3
 92 2 4
 93 
 94 
 95 3 100
 96 110
 97 2 1
 98 2 2
 99 2 3
100 2 4
101 
102 3 100
103 101
104 2 1
105 2 2
106 2 3
107 2 4
108 
109 */

 

 

1005

a[i]>=min(a[i-1],a[i-2])

然后……

 

1006

感觉自己写不出来,没细想。

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
报名 | 第14届百度之星报名正热,PaddlePaddle解锁中国式深度学习

  2018 百度之星大赛于 7 月 4 日正式启动报名,涵盖百度之星·程序设计大赛与百度之星·开发者大赛两大子赛事,怀揣梦想的技术咖们,还在等什么呢?   程序设计大赛与开发者大赛两项赛事...

机器之心
2018/07/31
0
0
15年累计参赛选手近30万人次!2020百度之星大赛火热报名中

在AI人才正式进入产业之前,各项赛事可以说是绝佳的“演兵场”,为广大学子提供将理论转化为实践的契机。5月20日,由深度学习技术及应用国家工程实验室与百度联合主办的“WAVE SUMMIT”2020深...

飞桨PaddlePaddle
06/01
10
0
AI+遥感卫星比赛新上线,报名进行中

雷锋网(公众号:雷锋网) AI 科技评论按,由联合国教科文组织国际工程科技知识中心(IKCEST)、中国工程院科技知识中心、百度公司及西安交通大学共同主办的大数据竞赛日前上线啦,参赛队伍 4 ...

汪思颖
2019/05/04
0
0
4000选手参赛,首届“全国人工智能大赛”初赛回顾

全国人工智能大赛(以下简称大赛)由深圳市人民政府设立于 2019 年 8 月。大赛由深圳市人民政府主办,深圳市科创委、鹏城实验室及科技部指导成立的新一代人工智能产业技术创新战略联盟共同承...

张路
2019/12/12
0
0
高手过招,首届「全国人工智能大赛」初赛完成比拼

11 月 30 日,经过 33 天的激烈角逐,首届「全国人工智能大赛」初赛完成比拼。 全国人工智能大赛(以下简称大赛)由深圳市人民政府设立于 2019 年 8 月。大赛将立足国际视野,营造人工智能创...

skura
2019/12/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

63. Unique Paths II

题目: 63. Unique Paths II A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any p......

JiaMing
43分钟前
30
0
前后端分离了,跨域问题怎么处理?

利用Nginx反向代理解决跨域问题 使用jsonp 来进行解决,不推荐,老项目可以使用此方案,但是发送的http 请求体有大小限制,并且发送方式为get方式,大小限制、不安全。 服务器代理 CORS 请求...

SpringForA
45分钟前
19
0
Hacker News 简讯 2020-07-10

更新时间: 2020-07-10 00:00 How to track and display profile views on GitHub - (rushter.com) 如何在GitHub上跟踪和显示概要视图 得分:80 | 评论:36 XMEMS Announces World's First Mon......

FalconChen
59分钟前
103
2
如何在Java中将文本追加到现有文件 - How to append text to an existing file in Java

问题: I need to append text repeatedly to an existing file in Java. 我需要将文本重复添加到Java中的现有文件中。 How do I do that? 我怎么做? 解决方案: 参考一: https://stackoom...

fyin1314
昨天
12
0
Eclipse HotKey:如何在选项卡之间切换? - Eclipse HotKey: how to switch between tabs?

问题: How can I switch between opened windows in Eclipse? 如何在Eclipse中打开的窗口之间切换? There is Ctrl + F6 , but it's asking me which one I want, but I want switch it lik......

富含淀粉
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部