我只想说面对这种难度的题目就是冲着20%的数据暴力。。。
分数:40+20+36.1+38+0+19
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,想要求出
。
输入格式:
一行两个数n。
输出格式:
一行一个数
。
输入样例#1:
100
输出样例#1:
1124
输入样例#2:
2000
输出样例#2:
68204
对于10%的数据,
。
对于40%的数据,
。
对于70%的数据,
。
对于100%的数据,
。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
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 else
42 ans=ans+p;
43 }
44 } cout<<ans;
45 return 0;
46 }
黑恶势力的反攻计划被小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:
1
5
5
2
-1
对于前20%的数据,
。
对于前40%的数据,
,
。
对于前50%的数据,
,
。
对于数据点6~7,保证所有选票始终在1~10之间。
对于100%的数据,
,
,
,
。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
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 }
黑恶势力的基地被射线武器重创,小C带领ZAJANG人民志愿军乘胜追击,一路屡战屡胜,打得敌人溃不成军。终于,小C的军队包围了被黑恶势力占领的秋之国首都,准备展开最终决战。
但黑恶势力也不是吃素的,黑恶势力的头目们秘密制定了一个反攻计划,准备两天内立刻实行。可惜,小C研发的Very-Strong号信号监听器早已将这一消息汇报给小C,并提供了秘密截获的某一黑恶势力头目电子密信中详细的计划安排。黑恶势力阴险狡诈,密信中的计划经过了多重复杂的加密处理,小C利用他研发的一套完整的破密系统成功破解了90%以上的密码,破密系统提示若要继续破解密码,先要提供几个复杂函数的计算方法,这当然难不倒小C,但为了节省时间,身为小C助手的你能否帮他解决其中一个简单的函数?
令g(n)表示n能表示成几种不同的完全k次方数(k>1),求
。
例如,
,所以g(64)=3。
输入格式:
多组询问,第一行一个整数T表示询问组数。
接下来T行,每行一个整数n,表示询问f(n)。
输出格式:
T行,每行一个实数,表示f(n),保留八位小数。
由于精度误差,你的答案和标准答案差的绝对值在
以内即可通过
输入样例#1:
2
5
15
输出样例#1:
0.25000000
0.48611111
对于20%的数据,
。
对于40%的数据,
,
。
对于100%的数据,
,
。
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<map>
5 using namespace std;
6 int n;
7 double ans;
8 int x;
9 map<double,int>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<n;i++)
17 {
18 cin>>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 }
懒得拷题目背景了,参见核心密码A...
请注意两道题的唯一差别。
令g(n)表示n能表示成几种不同的完全k次方数(k>1),求
。
例如,
,所以g(64)=3。
输入格式:
多组询问,第一行一个整数T表示询问组数。
接下来T行,每行一个整数n,表示询问f(n)。
输出格式:
T行,每行一个实数,表示f(n),保留十四位小数。
由于精度误差,你的答案和标准答案差的绝对值在
以内即可通过
输入样例#1:
2
5
15
输出样例#1:
0.25000000000000
0.48611111111111
对于20%的数据,
。
对于40%的数据,
,
。
对于100%的数据,
,
。
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<map>
5 using namespace std;
6 int n;
7 double ans;
8 int x;
9 map<double,int>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<n;i++)
17 {
18 cin>>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 }
由于出题人懒得写背景了,题目还是简单一点好。
输入一个整数n和一个整数p,你需要求出
,其中gcd(a,b)表示a与b的最大公约数。
刚才题面打错了,已修改
输入格式:
一行两个整数p、n。
输出格式:
一行一个整数
。
输入样例#1:
998244353 2000
输出样例#1:
883968974
对于20%的数据,
。
对于30%的数据,
。
对于60%的数据,
,时限1s。
对于另外20%的数据,
,时限3s。
对于最后20%的数据,
,时限6s。
对于100%的数据,
且p为质数。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
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<<ans;
25 return 0;
26 }
赛后感就不多说了,。。
暴力打的爽!!!