Codeforces Round #382 (Div. 2) (模拟|数学）

题目链接：

A:Ostap and Grasshopper

B:Urbanization

C:Tennis Championship

D:Taxes

分析：这场第一二题模拟，三四题数学题

直接模拟即可

排序从大到小取n1个数到城市1，n2个数到城市二，n1<=n2

递推、斐波拉契数列

dp[i] 表示赢i场比赛需要多少人，

则 dp[0] = 1,dp[1] = 2,dp[3] = dp[1] +dp[0], dp[ans] = dp[ans-1] + dp[ans-2]一次类推直到n不够用，ans即为答案。

复杂度 O(85)

详情见代码

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define ll long long
 4 ll x,dp[100100];
 5 int main()
 6 {
 7     scanf("%lld",&x);
 8     dp[0]=1,dp[1]=2;int i=0;
 9     while(dp[i]<=x)
10     {
11         i++;
12         if(i==1) continue;
13         dp[i]=dp[i-1]+dp[i-2];
14     }
15     printf("%d
",i-1); 
16 }

View Code

利用哥德巴赫猜想

若x为素数，输出1

若x为偶数输出2

若x-2为素数输出2

其他输出3

之间关系皆为if-else

详情见代码

 1 #include<stdio.h>
 2 #include<math.h>
 3 #define ll long long
 4 ll x;
 5 bool judge(ll x)
 6 {
 7     for(int i=2;i*i<=x;++i) if(x%i==0) return 0; return 1;
 8 }
 9 int main()
10 {
11     scanf("%lld",&x);
12     if(judge(x)) puts("1");
13     else if((x&1)==0) puts("2");
14     else if(judge(x-2)) puts("2");
15     else puts("3");
16 }

View Code