洛谷2017 5月月赛R1

阅读量：5078 次

发布时间：2019-06-12

本文共 6428 字，大约阅读时间需要 21 分钟。

我只想说面对这种难度的题目就是冲着20%的数据暴力。。。

分数：40+20+36.1+38+0+19

T1 签到题 III

题目背景

pj组选手zzq近日学会了求最大公约数的辗转相除法。

题目描述

类比辗转相除法，zzq定义了一个奇怪的函数：

typedef long long ll;ll f(ll a,ll b) { if(a==b) return 0; if(a>b) return f(a-b,b+b)+1; else return f(a+a,b-a)+1; }

zzq定义完这个函数兴高采烈，随便输入了两个数，打算计算f值，发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。

现在zzq输入了一个数n，想要求出 $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$ 。

输入输出格式

输入格式：

一行两个数n。

输出格式：

一行一个数 $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$ 。

输入输出样例

输入样例#1：

输出样例#1：

输入样例#2：

输出样例#2：

说明

对于10%的数据， $n \leq 300$ 。

对于40%的数据， $n \leq 2000$ 。

对于70%的数据， $n \leq 5 \times 10^5$ 。

对于100%的数据， $1 \leq n \leq 5 \times 10^{11}$ 。

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 typedef long long ll; 6 ll i,j; 7 int tot=0; 8 int flag=0; 9 inline ll f(ll a,ll b)10 {11     if(tot>10)12     {13         flag=1;14         return 0;15     }16     if(a==b) return 0;17     if(a>b) 18     {19         tot++;20         return f(a-b,b+b)+1;21     }22     else 23     {24         tot++;25         return f(a+a,b-a)+1;26     }27 }28 int main()29 {30         ll n;31         ll ans=0;32         cin>>n;33         for(i=1;i<=n;i++)34         {35             for(j=1;j<=n;j++)36             {37                 tot=0;38                 flag=0;39                 ll p=f(i,j);40                 if(flag==1)continue;41                 else42                 ans=ans+p;43             }44         }    cout<

View Code

T2 总统选举

题目背景

黑恶势力的反攻计划被小C成功摧毁，黑恶势力只好投降。秋之国的人民解放了，举国欢庆。此时，原秋之国总统因没能守护好国土，申请辞职，并请秋之国人民的大救星小C钦定下一任。作为一名民主人士，小C决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同，小C认为，一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人，小C只好自己来当临时大总统。为了尽可能避免这种情况，小C决定先进行几次小规模预选，根据预选的情况，选民可以重新决定自己选票的去向。由于秋之国人数较多，统计投票结果和选票变更也成为了麻烦的事情，小C找到了你，让你帮他解决这个问题。

题目描述

秋之国共有n个人，分别编号为1,2,…,n，一开始每个人都投了一票，范围1~n，表示支持对应编号的人当总统。共有m次预选，每次选取编号[li,ri]内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜，如果没有人获胜，则由小C钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有ki个人决定将票改投向该次预选的获胜者。全部预选结束后，公布最后成为总统的候选人。

输入输出格式

输入格式：

第一行两个整数n,m，表示秋之国人数和预选次数。

第二行n个整数，分别表示编号1~n的选民投的票。

接下来m行，每行先有4个整数，分别表示li,ri,si,ki，si表示若此次预选无人胜选，视作编号为si的人获得胜利，接下来ki个整数，分别表示决定改投的选民。

输出格式：

共m+1行，前m行表示各次预选的结果，最后一行表示最后成为总统的候选人，若最后仍无人胜选，输出-1。

输入输出样例

输入样例#1：

5 41 2 3 4 51 2 1 1 35 5 1 2 2 42 4 2 03 4 2 1 4

输出样例#1：

1552-1

说明

对于前20%的数据， $1 \leq n,m \leq 5000$ 。

对于前40%的数据， $1 \leq n,m \leq 50000$ ， $\sum k_i \leq 50000$ 。

对于前50%的数据， $1 \leq n,m \leq 100000$ ， $\sum k_i \leq 200000$ 。

对于数据点6~7，保证所有选票始终在1~10之间。

对于100%的数据， $1 \leq n,m \leq 500,000$ ， $\sum k_i \leq 10^6$ ， $1 \leq l_i \leq r_i \leq n$ ， $1 \leq s_i \leq n$ 。

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5 const int MAXN=10001; 6 int p; 7 int n,m; 8 int a[MAXN]; 9 int tou[MAXN];10 int piaonow[MAXN];//记录每一个区间内人的得票数 11 int main()12 {13     scanf("%d%d",&n,&m);14     for(int i=1;i<=n;i++)15     {16         scanf("%d",&p);17         a[p]++;18         tou[i]=p;//第i个人投给了p个人    19     }20     for(int i=1;i<=m;i++)21     {22         memset(piaonow,0,sizeof(piaonow));23         int l,r,s,k;24         int flag=0;// 区间内没有人获胜25         int where=-1; 26         scanf("%d%d%d%d",&l,&r,&s,&k);27         for(int j=l;j<=r;j++)28         {29             piaonow[tou[j]]++;30         }31         for(int j=l;j<=r;j++)32             if(piaonow[tou[j]]>(r-l+1)/2)33             {34                 flag=1;//有人获胜 35                 where=tou[j];36                 break;37             }38         int to;// 将要改投谁 39         if(flag==1)40         to=where;41         else to=s;42         for(int j=1;j<=k;j++)43         {44             scanf("%d",&p);45             a[tou[p]]--;46             a[to]++;47             tou[p]=to;48         }49         int maxn=-1;50         printf("%d\n",to);51     }52     for(int i=1;i<=n;i++)53     {54         if(a[i]>(n/2))55         {56             printf("%d",a[i]);57             return 0;58         }59     }60     printf("-1");61     return 0;62 }

View Code

T3 核心密码A

题目背景

黑恶势力的基地被射线武器重创，小C带领ZAJANG人民志愿军乘胜追击，一路屡战屡胜，打得敌人溃不成军。终于，小C的军队包围了被黑恶势力占领的秋之国首都，准备展开最终决战。

但黑恶势力也不是吃素的，黑恶势力的头目们秘密制定了一个反攻计划，准备两天内立刻实行。可惜，小C研发的Very-Strong号信号监听器早已将这一消息汇报给小C，并提供了秘密截获的某一黑恶势力头目电子密信中详细的计划安排。黑恶势力阴险狡诈，密信中的计划经过了多重复杂的加密处理，小C利用他研发的一套完整的破密系统成功破解了90%以上的密码，破密系统提示若要继续破解密码，先要提供几个复杂函数的计算方法，这当然难不倒小C，但为了节省时间，身为小C助手的你能否帮他解决其中一个简单的函数？

题目描述

令g(n)表示n能表示成几种不同的完全k次方数（k>1），求 $f(n)=\sum_{i=2}^n \frac{g(i)}{i}$ 。

例如， $64=2^6=4^3=8^2$ ，所以g(64)=3。

输入输出格式

输入格式：

多组询问，第一行一个整数T表示询问组数。

接下来T行，每行一个整数n，表示询问f(n)。

输出格式：

T行，每行一个实数，表示f(n)，保留八位小数。

由于精度误差，你的答案和标准答案差的绝对值在 $2 \times 10^{-8}$ 以内即可通过

输入输出样例

输入样例#1：

输出样例#1：

0.250000000.48611111

说明

对于20%的数据， $n \leq 1000$ 。

对于40%的数据， $n \leq 10^6$ ， $T \leq 5$ 。

对于100%的数据， $2 \leq n \leq 10^{18}$ ， $1 \leq T \leq 50000$ 。

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
            5 using namespace std; 6 int n; 7 double ans; 8 int x; 9 map
            
             ma;10 int main()11 {12     for(int i=2;i<=1000;i++)13         for(int j=2;j<=1000;j++)14             ma[pow(i,j)]++;15     cin>>n;16     for(int i=0;i
             
              >x;19 for(int i=2;i<=x;i++)20 ans+=ma[i]*1.0000/i;21 printf("%.8lf\n",ans);22 ans=0;23 }24 return 0;25 }

View Code

T4 核心密码B

题目背景

懒得拷题目背景了，参见核心密码A...

请注意两道题的唯一差别。

题目描述

令g(n)表示n能表示成几种不同的完全k次方数（k>1），求 $f(n)=\sum_{i=2}^n \frac{g(i)}{i}$ 。

例如， $64=2^6=4^3=8^2$ ，所以g(64)=3。

输入输出格式

输入格式：

多组询问，第一行一个整数T表示询问组数。

接下来T行，每行一个整数n，表示询问f(n)。

输出格式：

T行，每行一个实数，表示f(n)，保留十四位小数。

由于精度误差，你的答案和标准答案差的绝对值在 $2 \times 10^{-14}$ 以内即可通过

输入输出样例

输入样例#1：

输出样例#1：

0.250000000000000.48611111111111

说明

对于20%的数据， $n \leq 1000$ 。

对于40%的数据， $n \leq 10^6$ ， $T \leq 5$ 。

对于100%的数据， $2 \leq n \leq 10^{18}$ ， $1 \leq T \leq 50000$ 。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
           5 using namespace std; 6 int n; 7 double ans; 8 int x; 9 map
           
            ma;10 int main()11 {12     for(int i=2;i<=1000;i++)13         for(int j=2;j<=1000;j++)14             ma[pow(i,j)]++;15     cin>>n;16     for(int i=0;i
            
             >x;19 for(int i=2;i<=x;i++)20 ans+=ma[i]*1.0000/i;21 printf("%.14lf\n",ans);22 ans=0;23 }24 return 0;25 }

View Code

T4345 简单的数学题

题目描述

由于出题人懒得写背景了，题目还是简单一点好。

输入一个整数n和一个整数p，你需要求出 $(\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j))~mod~p$ ，其中gcd(a,b)表示a与b的最大公约数。

刚才题面打错了，已修改

输入输出格式

输入格式：

一行两个整数p、n。

输出格式：

一行一个整数 $(\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j))~mod~p$ 。

输入输出样例

输入样例#1：

998244353 2000

输出样例#1：

883968974

说明

对于20%的数据， $n \leq 1000$ 。

对于30%的数据， $n \leq 5000$ 。

对于60%的数据， $n \leq 10^6$ ，时限1s。

对于另外20%的数据， $n \leq 10^9$ ，时限3s。

对于最后20%的数据， $n \leq 10^{10}$ ，时限6s。

对于100%的数据， $5 \times 10^8 \leq p \leq 1.1 \times 10^9$ 且p为质数。

1 #include
        
          2 #include
         
           3 #include
          
            4 using namespace std; 5 typedef long long ll; 6 ll i,j; 7 int tot=0; 8 int flag=0; 9 ll mod;10 ll p;11 ll n;12 ll ans=0;13 int gcd(int x,int y)14 {15     if(y==0)return x;16     else return gcd(y,x%y)%p;17 }18 int main()19 {20         cin>>p>>n;21         for(i=1;i<=n;i++)22             for(j=1;j<=n;j++)23                 ans=(ans%p+(gcd(i,j)*i*j)%p)%p;24         cout<

View Code

赛后感就不多说了，。。

暴力打的爽！！！

转载于:https://www.cnblogs.com/zwfymqz/p/6821862.html

你可能感兴趣的文章

iOS基础-UIKit框架-多控制器管理-实例：qq界面框架

Ubuntu 14.04下安装CUDA8.0