我只想说面对这种难度的题目就是冲着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}$ 。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 ll i,j;

 int tot=;

 int flag=;

 inline ll f(ll a,ll b)

 {

     if(tot>)

     {

         flag=;

         return ;

     }

     if(a==b) return ;

     if(a>b)

     {

         tot++;

         return f(a-b,b+b)+;

     }

     else

     {

         tot++;

         return f(a+a,b-a)+;

     }

 }

 int main()

 {

         ll n;

         ll ans=;

         cin>>n;

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

         {

             for(j=;j<=n;j++)

             {

                 tot=;

                 flag=;

                 ll p=f(i,j);

                 if(flag==)continue;

                 else

                 ans=ans+p;

             }

         }    cout<<ans;

     return ;

 }

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 4

1 2 3 4 5

1 2 1 1 3

5 5 1 2 2 4

2 4 2 0

3 4 2 1 4

输出样例#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$ 。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 const int MAXN=;

 int p;

 int n,m;

 int a[MAXN];

 int tou[MAXN];

 int piaonow[MAXN];//记录每一个区间内人的得票数

 int main()

 {

     scanf("%d%d",&n,&m);

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

     {

         scanf("%d",&p);

         a[p]++;

         tou[i]=p;//第i个人投给了p个人

     }

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

     {

         memset(piaonow,,sizeof(piaonow));

         int l,r,s,k;

         int flag=;// 区间内没有人获胜

         int where=-;

         scanf("%d%d%d%d",&l,&r,&s,&k);

         for(int j=l;j<=r;j++)

         {

             piaonow[tou[j]]++;

         }

         for(int j=l;j<=r;j++)

             if(piaonow[tou[j]]>(r-l+)/)

             {

                 flag=;//有人获胜

                 where=tou[j];

                 break;

             }

         int to;// 将要改投谁

         if(flag==)

         to=where;

         else to=s;

         for(int j=;j<=k;j++)

         {

             scanf("%d",&p);

             a[tou[p]]--;

             a[to]++;

             tou[p]=to;

         }

         int maxn=-;

         printf("%d\n",to);

     }

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

     {

         if(a[i]>(n/))

         {

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

             return ;

         }

     }

     printf("-1");

     return ;

 }

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.25000000

0.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$ 。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<map>

 using namespace std;

 int n;

 double ans;

 int x;

 map<double,int>ma;

 int main()

 {

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

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

             ma[pow(i,j)]++;

     cin>>n;

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

     {

         cin>>x;

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

             ans+=ma[i]*1.0000/i;

         printf("%.8lf\n",ans);

         ans=;

     }

     return ;

 }

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.25000000000000

0.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$ 。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<map>

 using namespace std;

 int n;

 double ans;

 int x;

 map<double,int>ma;

 int main()

 {

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

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

             ma[pow(i,j)]++;

     cin>>n;

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

     {

         cin>>x;

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

             ans+=ma[i]*1.0000/i;

         printf("%.14lf\n",ans);

         ans=;

     }

     return ;

 }

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为质数。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 ll i,j;

 int tot=;

 int flag=;

 ll mod;

 ll p;

 ll n;

 ll ans=;

 int gcd(int x,int y)

 {

     if(y==)return x;

     else return gcd(y,x%y)%p;

 }

 int main()

 {

         cin>>p>>n;

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

             for(j=;j<=n;j++)

                 ans=(ans%p+(gcd(i,j)*i*j)%p)%p;

         cout<<ans;

     return ;

 }

赛后感就不多说了，。。

暴力打的爽！！！

巴特西

洛谷2017 5月月赛R1

T1 签到题 III

题目背景

题目描述

输入输出格式

输入输出样例

说明

T2 总统选举

题目背景

题目描述

输入输出格式

输入输出样例

说明

T3 核心密码A

题目背景

题目描述

输入输出格式

输入输出样例

说明

T4 核心密码B

题目背景

题目描述

输入输出格式

输入输出样例

说明

T4345 简单的数学题

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章