设n封信完全错排的点子有f,第③作为数据组数T(T&lt

先是次上机

Description

图片 1

地址

率先次上机

Input

一共T+1行

第①行事数据组数T(T<=10)

第2~T+1行每行三个非负整数N,代表一组领悟

难点列表

Output

总共T行,每行五个用空格分隔的数ans1,ans2

解题报告

Sample Input

6
1
2
8
13
30
2333

871 The stupid owls

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

杜教筛模板

对于ans1:

组织函数g,求出∑(f*g)(i)

$\sum_{i=1}^{n}(f*g)(i)=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})=\sum_{ij<=n}f(i)g(j)=\sum_{i=1}^{n}g(i)F(\left
\lfloor \frac{n}{i} \right
\rfloor)$

所以有$g(1)F(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)F(\left
\lfloor \frac{n}{i} \right
\rfloor)$

因为有$$\sum_{d|i}\varphi(d)=i$$

故而协会g(x)=1

那正是说于是就有$F(n)=\sum_{i=1}^{n}i-\sum_{i=2}^{n}F(\left
\lfloor \frac{n}{i} \right \rfloor)$

下一场就足以杜教筛了

对于ans2则有$F(n)=1-\sum_{i=2}^{n}F(\left
\lfloor \frac{n}{i} \right \rfloor)$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<map>
 7 using namespace std;
 8 typedef long long lol;
 9 const int N=6000000;
10 struct Node
11 {
12   lol phi,mu;
13 }ans;
14 lol mu[N+5],phi[N+5];
15 int prime[N+5],tot;
16 bool vis[N+5];
17 map<lol,lol> M1,M2;
18 void pre()
19 {int i,j;
20   mu[1]=1;phi[1]=1;
21   for (i=2;i<=N;i++)
22     {
23       if (vis[i]==0)
24     {
25       tot++;
26       prime[tot]=i;
27       mu[i]=-1;
28       phi[i]=i-1;
29     }
30       for (j=1;j<=tot;j++)
31     {
32       if (1ll*i*prime[j]>N) break;
33       vis[i*prime[j]]=1;
34       if (i%prime[j]==0)
35         {
36           mu[i*prime[j]]=0;
37           phi[i*prime[j]]=phi[i]*prime[j];
38           break;
39         }
40       else
41         {
42           mu[i*prime[j]]=-mu[i];
43           phi[i*prime[j]]=phi[i]*(prime[j]-1);
44         }
45     }
46     }
47   for (i=1;i<=N;i++)
48     phi[i]+=phi[i-1],mu[i]+=mu[i-1];
49 }
50 Node query(lol n)
51 {lol s1,s2;
52   lol i,pos;
53   if (n<=N) return (Node){phi[n],mu[n]};
54   if (M1[n])
55     {
56       return (Node){M1[n],M2[n]};
57     }
58   s1=0;s2=0;
59   for (i=2;i<=n;i=pos+1)
60     {
61       pos=n/(n/i);
62       Node p=query(n/i);
63       s2+=1ll*(pos-i+1)*p.mu;
64       s1+=1ll*(pos-i+1)*p.phi;
65     }
66   s1=((n+1)*n>>1)-s1;
67   s2=1-s2;
68   M2[n]=s2;M1[n]=s1;
69   return (Node){s1,s2};
70 }
71 int main()
72 {int T;
73   lol n;
74   cin>>T;
75   pre();
76   while (T--)
77     {
78       scanf("%lld",&n);
79       if (n<=N)
80     {ans.phi=phi[n];ans.mu=mu[n];}
81       else ans=query(n);
82       printf("%lld %lld\n",ans.phi,ans.mu);
83     }
84 }

 

分析

emmm怕塞尔维亚语表述的不完了,决定给Hint…但是
看了咱们的解题报告,看来作者的Hint给的依旧太直白了
那着实是个精光错排的题目,但期待大家不只是百度了眨眼之间间直接用了居家的公式而是真的精晓这几个递推公式的意思
设n封信完全错排的办法有f[n]种。
那般想,第壹封信是送错的,那么有(n-1)种选用,若是放在了地点k;信k也是送错的,那是它有两类选取:倘诺它正幸亏第①封信本该到的职分,那么余下的n-2封信正是新的完全错排难题有f[n-2]种办法;尽管没有放在第三封信的岗位,那这正是(n-1)封信的错排(能够清楚为那儿第k封新本应送到第③个职位只是为了错排无法送,也便是n-1封信意况下的一点一滴错排)。所以有
f[n]=(n-1)*(f[n-1]+f[n-2]);
有了这几个推导公式后就足以自底向上的演绎。记得要同时记录总的排列数,n封信的话有n!种排列格局,相除即可。记得用long
long来储存。
上机的时候有同学不太了然这些可能率是怎么回事,f[n]算的是截然错排有多少种选取,应当再除以n!也正是送n封信全体的大概

代码样例

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long f[30];
long long b[30];
int main()
{

    int c,n;
    f[1]=0; b[1]=1;
    f[2]= 1; b[2]= 2;
    f[3]=2; b[3]=6;
    for(int i= 4;i<=20;i++)
      {
          b[i]=b[i-1]*i;
        f[i]=(i-1)*(f[i-1]+f[i-2]);
      }

           while(~scanf("%d",&n)){
     double ans = (double)f[n]/b[n];
      ans = ans*100;

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


}

算法分析

用递归的方法也得以做,不过会慢很多;
提出用递推的点子自底向上,\(O(n)\)
的时光内就能够了

843 ModricWang和数论

思路

设\(m = a \% b\), 分为3种情况:

  1. \(b<a\)时,\(m\)一定在 \(1.. \lfloor \frac{a-1}{2}
    \rfloor\) 之间,共 \(\lfloor
    \frac{a-1}{2} \rfloor\)个数
  2. \(b=a\)时,\(m=0\)
  3. \(b>a\)时,\(m=a\)

因此,共 \(\lfloor \frac{a-1}{2}
\rfloor+2\) 个 \(m\),也就是
\(\lfloor \frac{a+1}{2}
\rfloor+1\)

日子复杂度\(O(1)\),空间复杂度\(O(1)\)

代码

#include <iostream>

using namespace std;

int main() {
    long long a;
    cin >> a;
    cout << (a + 1) / 2 + 1;
    return 0;
}

860 AlvinZH去体育地方

序言:由于教授的错误操作,此题的失实数据给大家上机造成影响,在此表示歉意;同时感激李明同学和郭镕昊同学,在上机时挺身嫌疑标题难点,在此建议鼓励。

荒唐的笔触

递推,像斐波那契数列那样递推。
本题能够先转化成从第0块砖走到第n块砖的法子数,令 \(F[i]\) 代表走到第 \(i\) 块砖的法门数。

颠倒是非的剖析

求走到第 \(i\) 块砖的方式数: ①从第
\(i-1\) 块砖走来,\(F[i-1]\); ②从第 \(i-2\) 块砖走来,\(F[i-2]\); ③从第 \(i-3\) 块砖走来,\(F[i-3]\), 那里面,得减去走到 \(i-3\) 的前一步也是骚操作的情景,那不正是
\(F(i-6)\) 么。 最后得到: \(F[i] = F[i-1] + F[i-2] + F[i-3] –
F[i-6]\)。

纠错

错在哪吧?错在调整和裁减的不得了部分!

我们要削减的就是走到 \(i-3\)
的前一步也是骚操作的事态呢?

仔细想想,你别忘了, \(F[i-6]\)
里面也有最终一步是骚操作的场地(从 \(i-9\)
直接骚操作),那一个情形不应有被减去。

据此,那样算出来的答案比真实答案小。那种状态从 \(n≥9\)
开端就会体现,那也是一有个别同学从AC到0.六分的原因。

若是走二次骚操作会促成脚疼,那么大家要缩小的是在 \(i-6\) 地点脚不疼的气象

之所以,也得以生产下边包车型地铁错误方法多削减的是 \(i-6\) 地方脚疼的情事。

科学的缓解方案

什么样避免上述多减的意况?大家能够开四个一维数组:

\(f[52]\) :\(f[i]\) 同上 \(F[i]\) ,表示走到 \(i\) 地方的格局数。

\(g[52]\) :\(g[i]\) 表示走到 \(i\) 位置脚不疼的办法数。

那样的话,递推公式变成 \(f[i] = f[i – 1]

  • f[i – 2] + g[i – 3]\) ,而 \(g[i] = f[i – 1] + f[i – 2]\)
    ,请参考参考代码一。

还有一种思路,其实是如出一辙,在此做简单表明。

二维数组 \(step[52][2]\)
:个中第①维为状态位,为0表示脚不疼,为1代表脚疼。

递推公式: \(step[n][0] =
step[n-1][0] + step[n-2][0] + step[n-1][1] +
step[n-2][1]\) ,而 \(step[n][1] = step[n-3][0]\)
,请参见参考代码二。

上边二维数组变成多少个一维数组效果同样,多数同校利用那种办法。

参照代码一

//感谢@Author: 骆嘉航

#include <cstdio>

long long f[52];
long long g[52];//走到第i块砖不疼的方法数
int n;

int main()
{
    f[0] = 1;
    f[1] = 1;
    g[0] = 1;
    g[1] = 1;
    for(int i = 2;i <= 50; i++)
    {
        f[i] = f[i - 1] + f[i - 2] + g[i - 3];
        g[i] = f[i - 1] + f[i - 2];
    }
    while(~scanf("%d", &n))
    {
        printf("%lld\n", f[n]);
    }
    return 0;
}

参考代码二

//感谢@Author:李明

#include <iostream>
using namespace std;

long long step[51][2];
int n;

int main()
{
    step[1][0] = 1;
    step[1][1] = 0;
    step[2][0] = 2;
    step[2][1] = 0;
    step[3][0] = 3;
    step[3][1] = 1;
    for(n = 4; n < 51; ++n)
    {
        step[n][0] = step[n-1][0] + step[n-2][0] + step[n-1][1] + step[n-2][1];
        step[n][1] = step[n-3][0];
    }
    while(cin >> n)
    {
        cout << step[n][1] + step[n][0] << endl;
    }
    return 0;
}

867 水水的Horner Rule

思路

经鉴定,那道题是真水题。标题标意思很粗大略,给您七个差别进制的数,把他们加起来用十进制表示。

措施:先把五个不等进制的数都转化成十进制,再相加就ok。

分析

在意多个不难难点,由于几个数都以在int范围内的正整数(下跌了难度),标题已经证实是实际尺寸在int范围内,约等于说这几个数很恐怕有3多少人,不过尚未关系,大家才不管它多少长度,用
字符串读入
一点标题也从未!而且动用字符串还有叁个亮点正是小编不用去操作那几个数,除法or求模什么的。

第2个难题是转账十进制,标题叙述中也提供了伪代码方法,采用最小乘法策略,在那之中的x正是大家的进制数,能够长足转化,其它多个int相加有或许跨越int哦!

思考题:
本题下落了难度,想一想,假若有大概是负数又该怎么处理?超越十进制的进制又何以转移呢?

参照代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MaxSize 100005

using namespace std;

long long ConvertToD(char *s, int H)
{
    long long result = 0;
    for (int i = 0; i < strlen(s); i++) {
        result = result * H + (s[i] - '0');
    }
    return result;
}

int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        int H1, H2;
        char x[32], y[32];
        while (n--)
        {
            scanf("%d %s %d %s", &H1, &x, &H2, &y);

            printf("%lld\n",ConvertToD(x, H1) + ConvertToD(y, H2));
        }
    }
}

873 ModricWang’s QuickSort

思路

第1需求向大家道歉,标题叙述中的划分函数并不曾兑现快排的剪切函数的一体化意义,给我们带来了困扰。在思维此题时,将其作为一种与快排毫不相关的特殊的划分格局即可。标题中一度提供了伪代码,只必要将其写成实际上代码即可。未来会释放三个此题修复之后的版本给大家。

亟待留意的是,后一层递归时的岗位划分取决于前一层递归时mid元素最后的职责,由此在分割函数中必要以再次来到值或任何方式来提供前二次递归时mid成分的地点。同时也要小心,i和j作为多少个岗位提醒符,必要严格管制相对大小,不得以出现划分的四个区域出现重叠的景色。

鉴于数量较为简单,需求的层数也较浅,完成划分函数后手工业调用即可。

光阴复杂度\(O(n)\),空间复杂度\(O(n)\)

代码

#include <iostream>

using namespace std;

const int MaxN = (int) 1e7 + 10;

int n;
int nums[MaxN];

int partition(int *arr, int n) {
    int mid = arr[n / 2];
    int i = 0, j = n - 1;
    while (i < j) {
        while (arr[i] <= mid && i <= j) i++;
        while (arr[j] > mid && i <= j) j--;
        if (i < j) {
            swap(arr[i], arr[j]);
        }
    }
    return i;

}


int main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    int l, r;
    r = partition(nums, n);
    l = partition(nums, r);

    for (int i = l; i < r; i++) {
        cout << nums[i] << " ";
    }
    cout << "\n";

}

861 AlvinZH的孩提希望——–木匠篇

前言

是因为助教的失误,本题数据的精度出现严重难题,以为取11个人小数完全没难点,考虑不周,望见谅。

核心当中,PI最好取值的方法是 \(PI =
acos(-1.0)\)。

思路

中等题。先明了难点供给的是如何: \(V = PI
_(x_1 – x_2)^2 / 4_ min(h_1,h_2)\)
。PI大家得以先不管,其实正是在找 \((x_1 –
x_2)^2* min(h_1,h_2)\) 的最大值。

宗旨数据很弱,数据范围也都极小,所以有多样艺术解题,甚至可以试试暴力求解。

分析

措施一:暴力解法
本题由于n、x和h都十分小,所以暴力解法(直接遍历全部组成)没难点,纵然不是教授的初衷,讲师表示不会出题,啊啊啊~

艺术二:从地方x的角度出发,移动指针法

叙述:选拔八个变量分别代表最左和最右的木条,由两边向中档靠拢,移动较短的单向,直至贴近到圆心处。

注解:当左端线段L小于右端线段君越时,大家把L右移,那时抛弃的是L与右端其余线段(奥迪Q5-1,
ENVISION-2,
…)组成的木桶,这一个木桶是没供给判断的因为那一个木桶的体量肯定都不曾L和RAV4组成的木桶容量大。

具体做法:能够有二种做法,一是开1个数组 \(H[205]\) , \(H[i]\) 代表 \(i-100\)
地点木条的万丈,注意那种下标的处理格局,在题材”四和归零”中也有用到。左右指南针开端化为0、200,向100邻近。另一种做法是利用STL容器map,
\(m[i]\)
表示地方i木条的中度,那样可以不要考虑中度为0的地方。

切实可参照参考代码一。

方法三:从高度的角度出发,遍历中度。

讲述:利用几个数组,下标代表中度,值分别为左右两边一样中度离圆心最远的职责。遍历2次中度数组,即可求得最大值。

实际可参考参考代码二(谢谢郭镕昊dalao)。

参照代码一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;
const double PI = acos(-1.0);

int n, pos, h;
map<int, int> m;

int main()
{
    //freopen("in2.txt", "r", stdin);
    //freopen("outme.txt", "w", stdout);
    while (~scanf("%d", &n))
    {
        m.clear();
        for (int i = 0; i < n; i++)
        {
            scanf("%d %d", &pos, &h);
            m[pos] = h;
        }

        double ans = 0.0;
        map<int, int>::iterator m_Head = m.begin();//最左边木条
        map<int, int>::iterator m_Tail = prev(m.end());//最右边木条

        while(m_Head != m_Tail && m_Head->first <= 0 && m_Tail->first >= 0)
        {
            double r = (m_Head->first - m_Tail->first) / 2.0;//半径
            int h = min(m_Head->second, m_Tail->second);

            ans = max(ans, r * r * h);

            if(m_Head->second <= m_Tail->second && m_Head->first < 0)
                advance(m_Head, 1);
            else if (m_Tail->second <= m_Head->second && m_Tail->first > 0)
                advance(m_Tail, -1);
            else if (m_Head->first == 0 && m_Tail->first > 0)
                advance(m_Tail, -1);
            else if (m_Tail->first == 0 && m_Head->first < 0)
                advance(m_Head, 1);
        }

        printf("%.3lf\n", ans * PI);
    }
}

参考代码二

/*
 Author: 郭镕昊(12622)
 Result: AC    Submission_id: 318166
 Created at: Fri Oct 13 2017 20:14:13 GMT+0800 (CST)
 Problem: 861    Time: 79    Memory: 2696
*/

#include<bits/stdc++.h>

const double pi = std::acos(-1.0);
const int N = 104;
inline void Max(int &a, int b) {
    if(b > a) a = b;
}
int n, a[N], b[N];

int main() {
    while(~scanf("%d", &n)) {
        memset(a, -1, sizeof a);
        memset(b, -1, sizeof b);
        int tmp = -1;
        for(int i = 1, x, h; i <= n; ++i) {
            scanf("%d%d", &x, &h);
            if(!x) Max(tmp, h);//记录0位置高度
            if(x > 0) Max(a[h], x);//右边
            if(x < 0) Max(b[h], -x);//左边
        }
        int x = -1, y = -1, ans = 0;
        for(int h = 100; h; --h) {
            Max(x, a[h]);
            Max(y, b[h]);
            if(x > 0 && y > 0) Max(ans, h * (x + y) * (x + y));
            if(tmp > 0 && x > 0) Max(ans, std::min(h, tmp) * x * x);
            if(tmp > 0 && y > 0) Max(ans, std::min(h, tmp) * y * y);
        }
        printf("%.3lf\n", pi * ans / 4.0);
    }
    return 0;
}

869 D&C–玲珑数

分析

D&C想表明的是divide and conquer的情致,不知我们get到了没
那道题与经典的求逆序数的标题很像。逆序数是数组中,ia[j]的对数。最相似的强力思路在数据量稍大时就会非常的慢,所以化解逆序数多是运用分治思想,借助归并排序
逆序数代码:

void mergee(int A[], int p, int q, int r)
{
    int n0 = r-p+1, n1 = q-p+1,n2 = r-q;
    int L[(n0+1)/2+1], R[(n0+1)/2+1];
    int i,j;
    for(i=1;i<=n1;i++)
        L[i] = A[p+i-1];
    for(j = 1;j<=n2;j++)
        R[j] = A[q+j];
    L[n1+1] = mm; R[n2+1] = mm;
    i = 1; j = 1; int k;
    for(k = p; k<=r;k++)
    {
        if(L[i]<=R[j])
        {
            A[k] = L[i]; i++;
        }
        else
        {   coun += n1-i+1;//最关键的就是添加了这句
            A[k]= R[j];j++;
        }
    }
}

实则只在二路集合的时候添加一句即可,因为在集合时,七个子数组内部已然有序,所以不设有逆序数,只也许发生在多少个数组之间,当左侧的l[i]>r[j]时组合了逆序数,同时l[i]背后属于左边的数组的数自然也都比r[j]大,能够一并加进去。
专注到那一个首要的计量部分是合在合并数组的for循环中的

接下去说那道题的玲珑数,表述上极度的近乎,可是再利用总计逆序数时的边总结边排序就会有毛病,因为a[i]>a[j]是能够直接重视排序中的大小相比较的,不过两倍景况下就会有题目,可能在排序的长河中丢掉一些玲珑数。(能够试一下3
2 1 个别求逆序数和玲珑数的事态)。所以求玲珑数时照旧在Merge
Sort的基本功上,只是先计数然后再排序。但因为究竟依然分治法,所以是比暴力法快很多。那种方法同样适用于总括逆序数,只是可能不如上边包车型客车主意总括的快。
除此以外,担心我们留意不到的坑点已经在Hint中提交了,希望我们都看到了。注意已经在Int范围内的数是有恐怕*2
的时候超出int范围的,可是总的来看半数以上的ac代码直接选拔了用long long

代码样例

#include <iostream>
#include <string.h>
#include <algorithm>
#include<cstdio>
#include<vector>
#include<fstream>
using namespace std;
int a[10005];
int coun;
void Merge(int a[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int *L = new int[n1 + 2];
    int *R = new int[n2 + 2];
    for (int i = 0; i<n1; i++)
        L[i] = a[p + i];
    for (int j = 0; j<n2; j++)
        R[j] = a[q + j + 1];
    int i = 0, j = 0;
    for (int k = p; k <= r; k++)
    {
        if (j >= n2 || (i<n1&&L[i] <= R[j]))
            a[k] = L[i++];
        else
            a[k] = R[j++];
    }
    delete []L;
    delete []R;
}
int MergeAndCount(int a[], int p, int q)
{
    if (p<q)
    {
        int mid = (p + q) / 2;

        MergeAndCount(a, p, mid) ;
         MergeAndCount(a, mid + 1, q);
//int coun = MergeAndCount(a, p, mid)
// + MergeAndCount(a, mid + 1, q);
//上面这行表述方式等价于两次递归调用,
//只不过不用全局的coun变量了
        int j = mid + 1;
        for (int i = p; i <= mid; i++)
        {
            while (j <= q && a[i]>(a[j]*2LL))
                j++;
            coun += j - (mid + 1);
        }
/*上面这个关键的for循环部分专门用来计算玲珑数,
放在Merge里也可以,但是是不同于Merge中
本来就有的合并用的循环的*/
        Merge(a, p, mid, q);
        return  coun;
    }
    else
        return 0;
}
int b[10005];
int main(){
    int n, t, p, q;
    while(scanf("%d",&n)!=EOF)
    {
        for (int i = 0; i < n; i++)
            cin >> a[i];

        cin >> t;
        int ans;
        while (t--)
        {
            coun = 0;
            cin >> p >> q;
            if (q < p)swap(p, q);
            for (int i = 0; i<n; i++)b[i] = a[i];
            ans = MergeAndCount(b, p, q);
            cout << ans << "\n";
        }
    }
    return 0;
}