710官方网站先上壹道简单的入门题,你有 11分之5 可能率走到((i-一)mod n)号点

我们发现答案只有整数,于是打表,发现ans=(n-x)*x

~~今天高1秋游,作者不想去(貌似小编还交了钱~可惜了~),于是待(呆)在机房和高中二年级大佬壹起考试。。~~

 八、Infiniti体系

 

不过种类
infinit
.pas/c/cpp
1s /
128M
[ [
难点讲述] ]
笔者们按以下格局发出系列:
1、
开头时系列是: “一” ;
贰、
每三回生成把系列中的 “一” 变成 “十” ,”0″ 变成 “一”。
经过极其次生成,大家赢得系列”10110拾1101拾拾1拾一…”。
总结有 Q
个询问,每回询问为:在间隔 A 和 B 之间某些许个 一。
请写3个程序回答
Q 个询问。
[ [
输入 数据 ]
先是表现一个平头
Q,前面有 Q 行,每行多少个数用空格隔断的平头 a, b。
[ [
输出 数据 ]
共 Q
行,每行贰个应答
[ [
输入 样例] ]
1
2
8
[ [
输出样例] ]
4
[ [
数据 范围] ]
1 <= Q
<= 5000
1 <= a
<= b < 2^63

期待公式:
E[x]=0 (x==0);
E[x]=0.5*(E[x-1]+1)+0.5*(E[x+1]+1);
(x!=0)

移项得,-E[i-1]*0.5+E[i]-E[i+1]*0.5=1
n 个方程高斯消元求解。

2、滑雪

  **ski.cpp/in/out**

1s / 128M

 

【难题讲述】

滑雪是壹项尤其振奋的移位,为了获取速度,滑雪的区域必须向下倾斜,而且当你滑到坡底,你只好再度走上坡大概等待电梯来载你。给出二个由二维数组表示的滑雪区域,数组的数字代表各点的可观。请您找出这一个区域中最长的滑坡。

上边是1个例子:

1  2  3  4  5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一位方可从某些点滑向左右左右紧邻七个点之1,当且仅当高度收缩。在上头的例子中,一条可滑行的压缩为2四-17-1陆-一。当然,二五-二四-2三-…-3-二-1越来越长。事实上,那是最长的一条减弱。

【输入文件】

输入文件ski.in的第1表现七个数奥迪Q5, C,表示滑雪区域的行数和列数(一≤R,C≤100)。上面是CRUISER行,每行有C个整数,表示中度H(0≤H≤一千0)。

【输出文件】

出口文件ski.out归纳一行,只包蕴2个整数,表示滑雪区域中最长滑坡的长度,即经过的点的多少最大值。

【样例输入】

5 5

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

【样例输出】

25

Solution:

一、很熟稔的题,没有错《C++1本通》(C++从入门到入土~)下面的题,当时听得不太懂…未来回过头来看,哦呵呵太easy了。

2、记念化搜索F[i][j]意味着走到
i 行 j 列的最大尺寸枚举从每2个点出发 f[i][j] = max(f[i][j],f[i

  • dx[k]][j + dy[k]] + 一) ,dx,dy
    是方向数组。图上倒霉递推,则应用搜索的款式,一定要纪念化。(不懂就翻书吧,上边写的比本身详细)

    1 #include
    2 #include
    3 #include
    4 #include
    5 #include
    6 #include
    7 #include
    8 #include
    9 #include

    10 using namespace std;
    11 int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
    12 int r,c,p,t,ans,m[105][105],f[105][105];
    13 inline int dfs(int x,int y)
    14 {
    15 int t,tmp,nx,ny;
    16 if(f[x][y])return f[x][y];
    17 t=1;
    18 for(int i=1;i<=4;i++) 19 { 20 nx=x+dx[i];ny=y+dy[i]; 21 if(nx>=1&&ny<=r&&ny>=1&&ny<=c&&m[x][y]t)t=tmp;
    25 }
    26 }
    27 f[x][y]=t;
    28 return t;
    29 }
    30 int main()
    31 {
    32 freopen(“ski.in”,”r”,stdin);
    33 freopen(“ski.out”,”w”,stdout);
    34 scanf(“%d%d”,&r,&c);
    35 for(int i=1;i<=r;i++) 36 for(int j=1;j<=c;j++)scanf("%d",&m[i][j]); 37 for(int i=1;i<=r;i++) 38 for(int j=1;j<=c;j++) 39 { 40 t=dfs(i,j); 41 f[i][j]=t; 42 if(t>ans)ans=t;
    43 }
    44 printf(“%d”,ans);
    45 return 0;
    46 return 0;
    47 }

 

Solution:

那是一个基本的动态规划难点。
我们用
F[i][j]意味着按规则消去数列 a[i..j]得到的的最大值;
除去第 i
个数获得的最大值为 a[i];
删除
a[i..j]收获的最大值为:1回性删除数列
a[i..j]获得的值是|a[i]-a[j]|*(j-i+1)
抑或是先删除
a[i..k] 再删除 a[k+1..j], k 在 i 到 j-一 之间,获得的值是
F[i][k]+F[k+1][j].
我们获得气象转移方程:
F[i][i]=a[i],
for i=1..N
对此随意的
i<j,有:
F[i][j]=max{|a[i]-a[j]|*(j-i+1),
f[i][i]+f[i+1][j],
F[i][i+1]+F[i+2][j],…,F[i][j-1]+F[j][j]}
F[1,n]为所求的解
时刻复杂度:o(N^3);
此题须求选手对算法的时光复杂度举办解析,
不难的物色是无法在分明时间内求出结果, 必
需选用高效的算法,首要考察选手采取火速算法——动态规划化解难题的力量

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<vector>
 7 #include<queue>
 8 using namespace std;
 9 int n,ans,a[505],f[505][505];
10 int main()
11 {
12     freopen("remove.in","r",stdin);
13     freopen("remove.out","w",stdout);  
14     scanf("%d",&n);  
15     for(int i=1;i<=n;i++)  
16     {  
17         scanf("%d",&a[i]);  
18         f[i][1]=a[i];  
19     }  
20     for(int j=2;j<=n;j++)   
21     for(int i=1;i<=n-j+1;i++)  
22     {  
23         f[i][j]=j*fabs(a[i]-a[i+j-1]);  
24         for(int k=1;k<j;k++)  
25         f[i][j]=max(f[i][j],f[i][k]+f[k+i][j-k]);  
26     }  
27     for(int i=1;i<=n;i++)ans=max(ans,f[i][n]);    
28     printf("%d",ans); 
29     return 0;
30 }
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 double a[302][302];
 8 int n;
 9 int main()
10 {
11     int i,j,now,k,x,T;
12     freopen("circle.in","r",stdin);
13     freopen("circle.out","w",stdout);
14     cin>>T;
15     while (T--)
16     {
17     cin>>n>>x;
18     memset(a,0,sizeof(a));
19     for (i=0; i<=n-1; i++)
20     {
21         if (i==x)
22         {
23             a[i+1][i+1]=1;
24             a[i+1][n+1]=0;
25         }
26         else
27         {
28             a[i+1][i+1]=1;
29             a[i+1][(i-1+n)%n+1]=a[i+1][(i+1)%n+1]=-0.5;
30             a[i+1][n+1]=1;
31         }
32     }
33     for (i=1; i<=n; i++)
34     {
35         now=i;
36         for (j=i+1; j<=n; j++)
37             if (fabs(a[now][i])<fabs(a[j][i]))
38                 now=j;
39         for (j=i; j<=n+1; j++)
40             swap(a[now][j],a[i][j]);
41         for (j=i+1; j<=n+1; j++)
42             a[i][j]/=a[i][i];
43         a[i][i]=1;
44         for (j=i+1; j<=n; j++)
45         {
46             for (k=i+1; k<=n+1; k++)
47                 a[j][k]-=a[i][k]*a[j][i];
48             a[j][i]=0;
49         }
50     }
51     for (i=n; i>=1; i--)
52     {
53         for (j=i+1; j<=n; j++)
54         {
55             a[i][n+1]-=a[i][j]*a[j][n+1];
56             a[i][j]=0;
57         }
58         a[i][n+1]/=a[i][i];
59         a[i][i]=1;
60     }
61     printf("%.4lf\n",a[1][n+1]);
62     }
63 }

三、公司控制

control.cpp/in/out

1s / 128M

 

【标题叙述】

稍微公司是其余集团的某个拥有者,因为她们得到了其它卖家发行的股票的1局地。例如,Ford公司负有马自达公司12%的股票。据他们说,若是至少满意了以下七个标准之一,公司A就足以控制集团B了:

1、公司A = 公司B。

2、公司A拥有压倒一半的店堂B的股票。

③、集团A控制K(K >= 一)个公司,记为C一, …, CK,每一个公司Ci拥有xi%的合营社B的股票,并且x一+ …. + xK > 五成。(包含公司本来具有的股票)

给你贰个表,每行李包裹含四个数(i,j,p);评释公司i享有公司j的p%的股票。计算有所的数对(h,s),注明公司h控制集团s。至多有91九个集团。

写一个顺序读入N组数(i,j,p),i,j和p是都在限制(一..100)的正整数,并且找出装有的数对(h,s),使得商家h控制公司s。

【输入数据】

输入文件名:control.in

第3行: N,申明接下去八个数的数量,即(i,j,p)的数量。

第2行到第N+1行: 每行四个整数作为3个3对数(i,j,p),表示i公司拥有j集团 p%的股金。

【输出数据】

输出文件名:control.out

输出零个或更多少个的控制其他集团的合营社。每行李包裹罗七个整数A、B,表示A集团决定了B公司。将出口的数对以升序排列。注意,本人主宰本人的决不输出。

【输入样例】

3

1 2 80 

2 3 80

3 1 20

【输出样例】

1 2

1 3

2 3

【数据范围】

对于100%的数据,N<=5000,1<i,j,p<=100

Solution:

1、那道题其实很不难,因为数量很水,才9四个铺面,所以无论是找找一下就好了。考试的时候想到了寻找,不知怎么的想法(脑子1抽)写了个floyd,结果呵呵呵~~7十二分,多个点答案错误。。仔细一想,小编的章程对于第三种情况判断后并未有再实行第二种情形的判定,于是改了反复断定,结果成了九十多分,照旧wa贰个点。。再想,点的双重啊什么反例啊什么各样情况(于是烦~懒得写),果断打搜索。搜索其实不够长的,气死哦作者了,搞了半天仍旧写了追寻。。

2、设
a[i][j]为 i 集团控制 j 集团的股份,con[i][j]意味着 i 集团是或不是操纵 j
集团。首先枚举每种 i,j 公司,对于每种 i 能说了算的营业所 j,则要一而再枚举 j
占有股份的合营社 k,总计其股份和,跟新 a[i][k],然后添加 i 控制
j,而每一回添加新的控制关系则要再更新1遍具有涉嫌。时间复杂度小于
O(n^4),对于焦点完全能过。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<set>
 8 #include<map>
 9 #include<queue>
10 #include<cstring>
11 #include<string>
12 using namespace std;
13 int n,m,dis[101][101];
14 bool vis[101][101];
15 inline void pd(int i,int k){
16     if(vis[i][k])return;
17     vis[i][k]=1;
18     for(int j=1;j<=n;j++){
19         dis[i][j]+=dis[k][j];
20         if(dis[i][j]>50)pd(i,j);
21     }
22 }
23 int main()
24 {
25     freopen("control.in","r",stdin);
26     freopen("control.out","w",stdout);
27     scanf("%d",&m);
28     //memset(dis,0x3f,sizeof(dis));
29     for(int i=1;i<=m;i++)
30     {
31         int x,y,z;
32         scanf("%d%d%d",&x,&y,&z);
33         dis[x][y]=z;n=max(n,max(x,y));
34     }
35     for(int i=1;i<=n;i++)
36     for(int j=1;j<=n;j++)
37     if(dis[i][j]>50)pd(i,j);
38     for(int i=1;i<=n;i++)
39     for(int j=1;j<=n;j++)
40     if(vis[i][j]&&i!=j)printf("%d %d\n",i,j);
41     return 0;
42 }

Solution:

 

作者们先看看系列变化规律,
S一 = “1”, S二 = “拾”, S三 = “10壹”, S四 = “10110”, S伍 = “101十101”,
等等. Si
是 S(i+1)的前缀。
队列 Si
是由体系 S(i-壹) 和 S(i-二), 连接而成的。
即 Si =
Si-壹 + Si-2 (实际上上是 Fibonacci 数列)。
找到规律未来,大家得以能够用递归的办法求出从从职责一 到岗位 X 之间有着的 一 的个数,
用3个函数 F
总括,结果为 f(b)-f(a-一)。
切实的参见:http://blog.csdn.net/famousdt/article/details/6907408
光阴复杂度为:
O(Q * log MAX_VAL)
此题须要先找出数学规律,
再进用递归达成。 首要考查选手的数学思维能力和递归程序的实
现。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 #define ll long long
 8 ll q,x,y,f[100];
 9 inline ll gi()
10 {
11     ll a=0;char x=getchar();bool f=0;
12     while((x<'0'||x>'9')&&x!='-')x=getchar();
13     if(f=='-')x=getchar(),f=1;
14     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
15     return f?-a:a;
16 }
17 inline ll find(ll l,ll k)
18 {
19     if(l==0)return 0;
20     if(l==f[k])return f[k-1];
21     else if(l<=f[k-1])return find(l,k-1);
22     return f[k-2]+find(l-f[k-1],k-2);
23 }
24 int main()
25 {
26     freopen("infinit.in","r",stdin);
27     freopen("infinit.out","w",stdout);
28     q=gi();f[0]=1;f[1]=1;
29     for(int i=2;i<=91;i++)f[i]=f[i-1]+f[i-2];
30     while(q--){
31     x=gi();y=gi();
32     printf("%lld\n",find(y,91)-find(x-1,91));
33     }
34     return 0;
35 
36 }

 

一、总结单词数

(stat.cpp/c/pas)

相似的文件编辑器都有追寻单词的意义,该意义能够便捷稳定一定单词在小说中的位

置,有的还是可以够总计出一定单词在篇章中出现的次数。

现在,请你编制程序完成这一意义,具体必要是:给定2个单词,请你输出它在加以的稿子中冒出的次数和第三回面世的职分。注意:相称单词时,不区分轻重缓急写,但须求完全合营,即给定单词必须与小说中的某1单独单词在不区分轻重缓急写的情状下完全相同(参见样例 壹),假若给定单词仅是小说中某1单词的一片段则不算相称(参见样例 二)。

【输入】

输入文件名称叫 stat.in,贰 行。

第 1 行为三个字符串,个中只含字母,表示给定单词;

第 贰 表现三个字符串,在那之中只恐怕含有字母和空格,表示给定的文章。

【输出】

输出文件名字为 stat.out。 唯有一行,假诺在篇章中找到给定单词则输出七个整数,三个整数之间用一个空格隔开分离,

个别是单词在篇章中冒出的次数和率先次出现的职位(即在篇章中首先次面世时,单词首字母在小说中的地方,地方从 0 初阶);假诺单词在篇章中未有出现,则一向出口3个整数-一。

【输入输出样例 一】

stat.in 

To

to be or not to be is a question

stat.out

2 0

【输入输出样例 壹 表明】

出口结果表示给定的单词 To 在小说中出现四回,第2遍面世的地点为 0。

【输入输出样例 二】

Stat.in

to

Did the Ottoman Empire lose its power at that time

stat.out

-1

【输入输出样例 2 认证】

表示给定的单词 to 在作品中并没有出现,输出整数-1。

【数据范围】

一 ≤ 单词长度 ≤ 10。

① ≤ 文章长度 ≤ 1,000,000。

Solution:

一、首先那是某年普及组的水(难)题。

2、明天才被第1题坑过,所以,呵呵呵~~,果然单词有七个空格。

三、思路直接模拟,先把字母大小写统壹(本题不区分轻重缓急写,所以要联合),然后枚举每二个稿子中的单词,与原来的单词进行相比。
枚举的历程:枚举每三个篇章中的字母,然后从日前字母 A
开头向后枚举所必要单词 B 的长短,然后 A 与 B
比较,若是完全相同,然后再判断单词 A
的前、后是还是不是都以空格(否则有极大可能率出现枚举二个单词1局地的情状),如若是首先次革新,就把答案设置为枚举时所循环的值(壹般是
i)。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<string>
 7 using namespace std;
 8 int main()
 9 {
10     freopen("stat.in","r",stdin);
11     freopen("stat.out","w",stdout);
12     string a,b;
13     int x=-1,y=0;
14     getline(cin,a);getline(cin,b);
15     int la=a.length(),lb=b.length();
16     int i=0;
17     while(i<lb){
18     while(b[i]==' '&&i<lb)i++;
19     int j=0;
20     while(j<la&&i<lb){
21     if(a[j]==b[i]||abs(a[j]-b[i])==32){i++;j++;}
22     else
23     break;}
24     if(j==la&&(b[i]==' '||i==lb-1))
25     {
26     if(x==-1)x=i-la;
27     y++;
28     }
29     while(b[i]!=' '&&i<lb)i++;
30     }
31     if(x==-1)cout<<x<<endl;
32     else cout<<y<<' '<<x<<endl; 
33     return 0;
34 }

 

输入输出样例

输入样例#1:

……boyogirlyy……girl…….

出口样例#1:

4
2

数码范围:

  对于百分之百的多少,满意字符串之间无空格且字符串长度小于十6

 

%%%%%YZD佬orz

4、圆圈

circle.cpp/in/out

1s / 128M

[标题叙述]

当今有一个圆形,顺时针标号分别从0到n-1,每一回等概率顺时针走一步依旧逆时针走一步,即倘使你在i号点,你有五成可能率走到((i-壹)mod n)号点,二分之一概率走到((i+一)mod n)号点。问从0号点走到x号点的期待步数。

[输入]

率先行李包裹涵一个平头T,表示数据的组数。

接下去有T行,每行包罗七个整数n, x。

T<=10, 0<=x<n<=300;

[输出]

对此每组数据,输出壹行,包罗1个4个人小数表示答案。

[样例输入]

3

3 2

5 4

10 5

[样例输出]

2.0000

4.0000

25.0000

[数量范围]

对于 30% 的数据,n<=20

对于 50% 的数据,n<=100

对于 70% 的数据,n<=200

对于 100%的数据,n<=300

Solution:

壹、那题贼有意思,开始怀恋dp,不过当往邻点走领悟后大概又会走回来,绕过来绕去,很难处理dp的后效性难题。。于是思虑找规律(立flag),找了半天,怕是错的不敢打。。再去想拿个暴力分,搜索,死循环,f**k,不屑(写)了。。之后看了看最后①题,什么字符字串啊,数据还200000,果断扬弃,于是去打乒球去了~。

贰、考完后,看了1人神犇–撸哥的代码,立时惊呆了(打二个dp暴力然后找规律,五行代码AC),flag:早知道本身也去找规律了。。上面是找规律的代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int t,n,x;
 5 int main()
 6 {
 7     freopen("circle.in","r",stdin);
 8     freopen("circle.out","w",stdout);
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%d%d",&n,&x);
13         printf("%d.0000\n",(n-x)*x);
14     }
15     return 0;
16 }

3、正解是高斯消元。

期望公式:

E[x]=0
 (x==0);

E[x]=0.5*(E[x-1]+1)+0.5*(E[x+1]+1);
 (x!=0)

移项得,-E[i-1]*0.5+E[i]*0.5-E[i+1]*0.5=1

n个方程高斯消元求解。因为种种方程唯有两个不为零周详,所以当TLE能够适合剪枝。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string.h>
  5 #include <cmath>
  6 #include <iomanip>
  7 #include <algorithm>
  8 using namespace std;
  9  
 10 ///浮点型高斯消元模板
 11 const double eps=1e-12;
 12 const int maxm=1000;///m个方程,n个变量
 13 const int maxn=1000;
 14 int m,n;
 15 double a[maxm][maxn+1];///增广矩阵
 16 bool free_x[maxn];///判断是否是不确定的变元
 17 double x[maxn];///解集
 18  
 19 int sign(double x)
 20 {
 21     return (x>eps)-(x<-eps);
 22 }
 23 /**返回值:
 24 -1 无解
 25 0 有且仅有一个解
 26 >=1 有多个解,根据free_x判断哪些是不确定的解
 27 */
 28 int Gauss()
 29 {
 30     int i,j;
 31     int row,col,max_r;
 32     m=n;///n个方程,n个变量的那种情况
 33     for(row=0,col=0;row<m&&col<n;row++,col++)
 34     {
 35         max_r=row;
 36         for(i=row+1;i<m;i++)///找到当前列所有行中的最大值(做除法时减小误差)
 37         {
 38             if(sign(fabs(a[i][col])-fabs(a[max_r][col]))>0)
 39                 max_r=i;
 40         }
 41         if(max_r!=row)
 42         {
 43             for(j=row;j<n+1;j++)
 44                 swap(a[max_r][j],a[row][j]);
 45         }
 46         if(sign(a[row][col])==0)///当前列row行以下全为0(包括row行)
 47         {
 48             row--;
 49             continue;
 50         }
 51         for(i=row+1;i<m;i++)
 52         {
 53             if(sign(a[i][col])==0)
 54                 continue;
 55             double tmp=a[i][col]/a[row][col];
 56             for(j=col;j<n+1;j++)
 57                 a[i][j]-=a[row][j]*tmp;
 58         }
 59     }
 60     for(i=row;i<m;i++)///col=n存在0...0,a的情况,无解
 61     {
 62         if(sign(a[i][col]))
 63             return -1;
 64     }
 65     if(row<n)///存在0...0,0的情况,有多个解,自由变元个数为n-row个
 66     {
 67         for(i=row-1;i>=0;i--)
 68         {
 69             int free_num=0;///自由变元的个数
 70             int free_index;///自由变元的序号
 71             for(j=0;j<n;j++)
 72             {
 73                 if(sign(a[i][j])!=0&&free_x[j])
 74                     free_num++,free_index=j;
 75             }
 76             if(free_num>1)
 77                 continue;///该行中的不确定的变元的个数超过1个,无法求解,它们仍然为不确定的变元
 78         ///只有一个不确定的变元free_index,可以求解出该变元,且该变元是确定的
 79             double tmp=a[i][n];
 80             for(j=0;j<n;j++)
 81             {
 82                 if(sign(a[i][j])!=0&&j!=free_index)
 83                     tmp-=a[i][j]*x[j];
 84             }
 85             x[free_index]=tmp/a[i][free_index];
 86             free_x[free_index]=false;
 87         }
 88         return n-row;
 89     }
 90     ///有且仅有一个解,严格的上三角矩阵(n==m)
 91     for(i=n-1;i>=0;i--)
 92     {
 93         double tmp=a[i][n];
 94         for(j=i+1;j<n;j++)
 95         if(sign(a[i][j])!=0)
 96             tmp-=a[i][j]*x[j];
 97                 x[i]=tmp/a[i][i];
 98     }
 99     return 0;
100 }///模板结束
101  
102 int t,xx;
103  
104 int main()
105 {
106     freopen("circle.in","r",stdin);
107     freopen("circle.out","w",stdout);
108     cin>>t;
109     while(t--)
110     {
111         cin>>n>>xx;
112         memset(a,0,sizeof(a));
113         for(int i=0;i<n;i++)
114         {
115             if(i==xx)
116             {
117                 a[i][i]=1;
118                 a[i][n]=0;
119                 continue;
120             }
121             a[i][i]=1;
122             a[i][n]=1;
123             a[i][(i-1+n)%n]=-0.5;
124             a[i][(i+1)%n]=-0.5;
125         }
126         Gauss();
127         cout<<setiosflags(ios::fixed)<<setprecision(4)<<x[0]<<endl;
128     }
129     return 0;
130 }

 

 5、字符串

string.cpp/in/out

4s / 128M

[难点叙述]

给四个字符串,在具备分裂的子串中,找到字典序第K大的子串。

如abab的富有不一致子串有(已按字典序排列)

a

ab

aba

abab

b

ba

bab

[输入]

首先行李包裹括叁个字符串S,只包括小写字母。

第贰行包涵3个平头Q,表示驾驭的个数。

接下去有Q行,每行李包裹罗3个整数K,表示要询问第K大的子串。

|S|<=九千0, Q<=500, 0<K<二^31,并且K不当先S不相同子串的个数。

[输出]

对此每一种询问,输出1行包涵字典序第K大的子串。

[样例输入]

aaa

2

2

3

[样例输出]

aa

aaa

[数据范围]

对于 20% 的数据,|S|<=200

对于 50% 的数据,|S|<=5000

对于 80% 的数据,|S|<=50000

对于 100%的数据,|S|<=90000

Solution:

一、那题笔者间接扬弃了,暴力是没分的,等本身学了AC自动机再回过头解析那题(立FALG)。

二、那里是李总给的标程和剖析:标题来源
SPOJ SUBLEX   
指标是省代表队的校友团结去搜题解吧。没有错,就这么点完了~~

于是自身搜了一晃网上的分析也很少:

先是对此给出的字符串建立后缀自动机,
然后使用后缀自动机的质量, 全体同一的子串一定会在同1些停歇, 那么,
从根起初, 每一遍都选取尽量小的字符走,
首先大家得以dfs预处理出各种景况点处代表的也许向下的不等字串有微微个,
然后就领会种种字符向下走会有个别许种恐怕了,
于是依据这些图中年老年是沿着满意向下能找到第K小的边走即可。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #include <vector>
  5 
  6 using namespace std;
  7 
  8 const int maxn = 90000;
  9 
 10 int last, cnt, root;
 11 char s[maxn + 1];
 12 int ch[maxn * 2][26];
 13 int mx[maxn * 2];
 14 int fa[maxn * 2];
 15 int deg[maxn * 2];
 16 vector<int> G[maxn * 2];
 17 long long sz[maxn * 2];
 18 
 19 void insert(int x)
 20 {
 21     int np = ++cnt;
 22     int p = last;
 23     mx[np] = mx[p] + 1;
 24     while (p && !ch[p][x])
 25         ch[p][x] = np, p = fa[p];
 26     if (!p)
 27         fa[np] = root;
 28     else
 29     {
 30         int q = ch[p][x];
 31         if (mx[q] == mx[p] + 1)
 32             fa[np] = q;
 33         else
 34         {
 35             int nq = ++cnt;
 36             mx[nq] = mx[p] + 1;
 37             for (int j = 0; j < 26; ++j)
 38                 ch[nq][j] = ch[q][j];
 39             fa[nq] = fa[q];
 40             fa[np] = fa[q] = nq;
 41             while (p && ch[p][x] == q)
 42                 ch[p][x] = nq, p = fa[p];
 43         }
 44     }
 45     last = np;
 46 }
 47 
 48 int main()
 49 {
 50     freopen("string.in","r",stdin);
 51     freopen("string.out","w",stdout);
 52     scanf("%s", s);
 53     int n = strlen(s);
 54     root = last = ++cnt;
 55     for (int i = 0; i < n; ++i)
 56         insert(s[i] - 'a');
 57     for (int i = 1; i <= cnt; ++i)
 58         for (int j = 0; j < 26; ++j)
 59             if (ch[i][j])
 60             {
 61                 ++deg[i];
 62                 G[ch[i][j]].push_back(i);
 63             }
 64     queue<int> q;
 65     for (int i = 1; i <= cnt; ++i)
 66         if (!deg[i])
 67             q.push(i);
 68     while (!q.empty())
 69     {
 70         int u = q.front();
 71         q.pop();
 72         ++sz[u];
 73         for (int i = 0; i < G[u].size(); ++i)
 74         {
 75             int v = G[u][i];
 76             sz[v] += sz[u];
 77             if (--deg[v] == 0)
 78                 q.push(v);
 79         }
 80     }
 81     int Q;
 82     scanf("%d", &Q);
 83     while (Q--)
 84     {
 85         int K;
 86         scanf("%d", &K);
 87         int p = root;
 88         while (K > 0)
 89         {
 90             int sum = 0;
 91             for (int i = 0; i < 26; ++i)
 92                 if (sum + sz[ch[p][i]] >= K)
 93                 {
 94                     K -= sum + 1;
 95                     putchar('a' + i);
 96                     p = ch[p][i];
 97                     break;
 98                 }
 99                 else
100                     sum += sz[ch[p][i]];
101         }
102         puts("");
103     }
104     return 0;
105 }

 

Solution:

那道题其实很不难,在洛谷上有原题,而且是入门难度的,呵呵呵,开首还直接纠结题意,真是f**k。大家先解读一下样例,首先第二个boy就不要说了,今后看有一个o,则势必覆盖了1个boy,继续现在看,三个y,则这里覆盖了1个boy,所以一共五个boy,至于girl的豪门都能看出来,那里就不多说了。于是大家便能随随便便得出代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a,b;string c;
 4 int main()
 5 {
 6     cin>>c;
 7     int l=c.size();
 8     for(int i=0;i<l;i++){
 9     if(c[i]=='b'||c[i+1]=='o'||c[i+2]=='y')a++;
10     if(c[i]=='g'||c[i+1]=='i'||c[i+2]=='r'||c[i+3]=='l')b++;}
11     cout<<a<<endl<<b;
12     return 0;
13 }

 

12、序列

【标题叙述】
山山有3个长度为
N 的行列 A,以往他想协会四个新的尺寸为 N 的系列
B,使得 B
中的任意八个数都互质。
并且她要使
最小。
请输出最小值。
【输入格式】
率先行李包裹涵二个数
N 代表体系初步长度
接下去壹行李包裹蕴N 个数 A壹 , A二 ,…, AN ,代表系列 A
【输出格式】
出口包罗壹行,代表最小值
【样例输入】
5
1 6 4 2
8
【样例输出】
3
【样例表明】
样例中 B
数组能够为 一 伍 3 一 8
【数据范围】
对于 40%
的数据,1 ≤ N ≤ 10
对于 100%
的数据,1 ≤ N ≤ 100,1 ≤ ai ≤ 30

 但那百川归海是奇技淫巧,依然上正解

9、删数

[ [
难点讲述] ]
有 N
个分裂的正整数数 x 一 , x 2 , … x N
排成1排,大家能够从左侧或左侧去掉接二连三的 i 个数
(只好从两边删除数),一<=i<=n,剩下
N-i 个数,再把剩下的数按以上操作处理,直到所
一些数都被删去停止。
每一趟操作都有多个操作价值,
比最近后要刨除从 i 地方到 k 地方上的持有的数。 操作价值为
|x i – x
k
|*(k-i+1),倘使只去掉二个数,操作价值为这么些数的值。怎样操作能够取得最大
值,求操作的最大价值。
[ [
输入数据] ]
先是表现二个正整数
N,第一行有 N 个用空格隔离的 N 个差别的正整数。
[
输出数据] ]
包罗2个正整数,为操作的最大值
[ [
样例] ]
re move
.in
6
54 29 196
21 133 118
re move.
. out
768
[ [
数据范围] ]
3<=N<=100
N
个操作数为 壹..一千 之间的整数。
[ [
样例表达] ]
通过 壹回操作能够获取最大值,第一回去掉前边 3 个数 5四、2九、196,操作价值为
426。第
1次操作是在剩余的八个数(21
13三 118)中去掉最终贰个数 11八,操作价值为 118。第一
次操作去掉多余的
二 个数 二一 和 133 ,操作价值为 2二四。操作总价值为 42六+11捌+2贰四=76八。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int main()
 6 {
 7   freopen("circle.in","r",stdin);
 8   freopen("circle.out","w",stdout);
 9   int T;
10   cin>>T;
11   while(T--)
12   {
13     int a,b;
14     cin>>a>>b;
15     cout<<b*(a-b)<<".0000"<<endl;
16   }
17   return 0;
18 }

Solution: 

(逆用)唯一分解定理+神奇的思绪~

对于叁个小于n的处于自然数量级上的数,显著它的质因子越小,那几个数所包蕴的因数就会越多,所以大家能够只枚举多少个较小质数的次方数,同时也足以减少循环的次数。

而对于有一样因子数的三个数,较小的1个更有立异的空间,所以当多个数有同等因子数时,我们取较小1个。

一定要用long
long! 能够去探望那篇评释:http://www.doc88.com/p-389773941498.html

 

 1 #include<cstdio>  
 2 #include<cmath>  
 3 #define ll long long  
 4 ll n,maxx,num[12]={0,2,3,5,7,11,13,17,19,21,23},ans;  
 5 inline void findd(ll now,ll tot,ll u,ll v)  
 6 {  
 7     if(maxx<tot || (tot==maxx && ans>now))  
 8     {  
 9         maxx=tot;ans=now;  
10     }  
11     if(v>=11) return;  
12     for(ll i=1;i<=u;i++)  
13     {  
14         now*=num[v];  
15         if(now>n) return;  
16         findd(now,tot*(1+i),i,v+1);  
17     }  
18 }  
19 int main()  
20 {  
21     freopen("antip.in","r",stdin);  
22     freopen("antip.out","w",stdout);  
23     scanf("%lld",&n);  
24     findd(1,1,500,1);  
25     printf("%lld\n",ans);  
26     return 0;  
27 }

但有3个奇技淫巧

Solution:

第二,期望就不要我赘述了,大家先转移一下题意,有n个数和2个p,在这n个数中取n-三个数相乘再对p取模,将享有意况所得值相加除以n。毋庸置疑,共有n种情形,大家能够如此想,对于第i个数,我们不取它,而是把它后面和后边的数相乘取模,那样大家用数组f维护在此以前以往的前缀积,因为数量较大,所以大家每一趟相乘便取模,同理,用数组b维护从后往前的后缀积,当然也要取模。那样,大家只需以前现在扫二遍,第i个值=f[i-1]*b[i+1]%p,并充分起来,最后输出累加值除以n就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<queue>
 7 #include<map>
 8 using namespace std;
 9 #define ll long long
10 inline ll gi()
11 {
12     ll a=0;char x=getchar();bool f=0;
13     while((x>'9'||x<'0')&&x!='-')x=getchar();
14     if(x=='-')f=1,x=getchar();
15     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
16     return f?-a:a;
17 }
18 ll n,p,a[1000005],f[1000005],b[1000005],tot;
19 int main()
20 {
21     //freopen("nsq.in","r",stdin);
22     //freopen("nsq.out","w",stdout);
23     n=gi(),p=gi();f[0]=1;b[n+1]=1;
24     for(int i=1;i<=n;i++)a[i]=gi(),f[i]=f[i-1]*a[i]%p;
25     b[n+1]=1;
26     for(int i=n;i>=1;i--)b[i]=(b[i+1]*a[i])%p;
27     for(int i=1;i<=n;i++)tot+=(f[i-1]*b[i+1])%p;
28     printf("%.10f",tot*1.0/n);
29     return 0;
30 }

[ 标题描述]
前天有二个圆形, 顺时针标号分别从 0 到 n-1,
每一回等可能率顺时针走一步依旧逆时针走一步,
即假诺你在 i 号点,你有 二分一 概率走到((i-1)mod n)号点,百分之五10可能率走到((i+1)mod n)号点。问
从 0 号点走到 x 号点的企盼步数。
[ 输入]
先是行李包裹罗三个平头 T,表示数据的组数。
接下去有 T 行,每行包罗四个整数 n, x。
T<=10, 0<=x<n<=300;
[ 输出]
对于每组数据,输出一行,包蕴三个4个人小数表示答案。
[ 样例输入]
3
3 2
5 4
10 5
[ 样例输出]
2.0000
4.0000
25.0000
[ 数据范围]
对于 30% 的数据,n<=20
对于 50% 的数据,n<=100
对于 70% 的数据,n<=200
对于 100%的数据,n<=300

先上一道不难的入门题:

5、与运算

【标题叙述】
给定 n
个数,找出四个,使得它们经过与运算后结果最大。
注意,选出来的三个数在原数组中的地方不可能平等,可是数值能够1如既往。
【输入格式】
率先行二个平头
n,表示数字个数。
第2行 n
个数,表示给定的数。
【输出格式】
三个整数表示答案。
【样例输入】
3
1 2
1
【样例输出】
1
【数据范围】
对于
伍分一的数据点,n <= 一千
对此别的五分之一的数据点,唯有 0 和 一
对于
百分之百的数据点,n <= 一千00, 0 <= 数值 <= 10^九

 3、Antiprime数

借使1个自然数n(n>=壹),满意全体小于n的自然数(>=一)的约数个数都小于n的约数个数,则n是1个Antiprime数。譬如:一,
2, 四, 6, 1二, 24。

任务:

编一个主次:

壹、 从ANT.IN中读入自然数n。

二、 总括不高于n的最大Antiprime数。

三、将结果输出到ANT.OUT中。

输入( antip.in):

输入文件antip.in唯有3个整数,n(一<= n <= 二 000 000 000)。

输出(antip.out):

输出文件antip.out也只包罗一个整数,即不超出n的最大Antiprime数。

样例输入( antip.in):

1000

样例输出(antip.out):

840

4、Vrisible Lattice Points

【标题叙述】

从原点看率先象限的全数点,能一向看出的点的多少是多少(不含有原点)

【输入文件】
第 1行事测试数据的组数C(1<=C<=1000),

以下C行,每行李包裹括三个数N(一<=N<=1000),表示所求的可视范围。
【输出文件】
对此每1组测试数据,输出1行一个数,表示答案。
【样例输入】
4

2

4

5

231
【样例输出】

5

13

21

32549

无聊中,感觉自个儿思量僵硬,于是,总计一些贼有意思的题(坑),会频频更新。。。

 六、斐波拉契

难点叙述

小 C
养了有的很可喜的兔子。 有壹天,小 C
突然发现兔子们都以从严服从伟大的物工学家斐波那契建议的模型来实行繁衍:1对兔子从诞生后第2个月起,每一个月刚开端的时候都会产下壹对小兔子。我们假诺,
在全路经过中兔子不会油可是生别的意外。

小 C
把兔子按出生顺序,把兔子们从 一 开头标号,并且小 C 的兔子都以 一 号兔子和
壹 号兔子的儿孙。假如某两对兔子是同时出生的,那么小 C
会将父母标号更小的一对先行标 号。

设若大家把那种关涉用画图下来,前6个月大约正是如此的:

710官方网站 1

里头,三个箭头 A
→ B 表示 A 是 B 的祖先,相同的颜色代表同贰个月出生的兔子。

为了更密切地打听兔子们是如何繁衍的,小
C 找来了1些兔子,并且向您提议了 m 个 难题:她想了然关于每两对兔子 aia_iai​ 和 bib_ibi​
,他们的近来公共祖先是什么人。你能帮帮小 C
吗?

1对兔子的祖宗是那对兔子以及她们老人家(假如有的话)的先人,而近日公共祖先是指
两对兔子所共有的祖辈中,离他们的相距之和不久前的1对兔子。比如,5 和 ⑦的近年公共祖 先是 2,1 和 2 的近来集体祖先是 壹,陆 和 6 的近日国有祖先是
六。

输入输出格式

输入格式:

从规范输入读入数据。
输入第二行,包涵1个正整数 m。 输入接下去 m 行,每行李包裹罗 2个正整数,表示 aia_iai​ 和 bib_ibi​

输出格式:

出口到正式输出中。
输入一共 m 行,每行叁个正整数,依次表示你对难点的答案。

输入输出样例

输入样例#1:
复制

5 
1 1 
2 3 
5 7 
7 13 
4 12

出口样例#1:
复制

1 
1 
2 
2 
4 

说明

【数据范围与约定】
子任务会付给部分测试数据的表征。借使你在缓解标题中遇见了诸多不便,能够品味只消除一部分测试数据。 各类测试点的数量规模及特点如下表:

710官方网站 2

特别属性
一:保险 aia_iai​, bib_ibi​
均为某四个月出生的兔子中标号最大的一对兔子。例如,对
于前七个月,标号最大的兔子分别是 一, 二, 三, 伍, 八,
一三。

分外规属性
二:保障 ∣ai−bi∣≤一|a_i-b_i|\le 1∣ai​−bi​∣≤1

题材叙述

在一长串(三<=l<=255)中被反复贴有boy和girl两单词,后贴上的恐怕覆盖已贴上的单词(未有被遮住的用句点表示),最后每一种单词至少有四个字符未有被遮盖。问贴有多少个boy多少个girl?

Solution:

难题来源
sdut 2878:
希望公式:
E[x]=0
(x==0);
E[x]=0.5*(E[x-1]+1)+0.5*(E[x+1]+1);
(x!=0)
移项得,-E[i-1]*0.5+E[i]*0.5-E[i+1]*0.5=1
n
个方程高斯消元求解。因为各类方程唯有多个不为零周到,所以当 TLE
能够适量剪枝。

事实上能够直接打表,然后轻易窥见规律。详见代码。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int t,n,x;
 5 int main()
 6 {
 7     freopen("circle.in","r",stdin);
 8     freopen("circle.out","w",stdout);
 9     scanf("%d",&t);
10     while(t--)
11     {
12         scanf("%d%d",&n,&x);
13         printf("%d.0000\n",(n-x)*x);
14     }
15     return 0;
16 }

 11、偶数

【标题叙述】
山山有一个尺寸为
N 的队列。当体系中设有相邻的三个数的和为偶数的话,LGTB 就
能把它们删掉。
山山想让连串尽量短,请问能将连串收缩到多少个数?
【输入格式】
先是行李包裹罗叁个数
N 代表类别初步长度。
接下去1行李包裹含N 个数 a1 ,a二 ,…,aN ,代表系列。
【输出格式】
出口包涵三个数代表操作后系列最短长度
【样例输入】
10
1 3 3 4 2
4 1 3 7 1
【样例输出】
2
【数据范围】
对于 50%
的数据,1 ≤ N ≤ 1000
对于 100%
的数据,1 ≤ N ≤ 10 5 ,0 ≤ ai ≤ 10 9

Solution:

设想到连年的一段奇偶性相同的数字才能被删去,所以直接贪心即可,用栈完成

 1 #include<iostream>
 2 #include<cstdio>
 3 #pragma GCC optimize(2)
 4 using namespace std;
 5 #define ll long long 
 6 #define il inline
 7 ll a[100005],s[100005];
 8 il ll gi()
 9 {
10     ll a=0;char x=getchar();bool f=0;
11     while((x<'0'||x>'9')&&x!='-')x=getchar();
12     if(x=='-')x=getchar(),f=1;
13     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
14     return f?-a:a;
15 }
16 int main()
17 {
18     freopen("even.in","r",stdin);
19     freopen("even.out","w",stdout);
20     ll n=gi(),t=0;
21     for(int i=1;i<=n;i++){
22     a[i]=gi();
23     if(!t)s[++t]=a[i];
24     else if(s[t]+a[i]&1)s[++t]=a[i];
25     else t--;
26     }
27     cout<<t;
28     return 0;
29 }

 7、圆圈

 

圆圈
c c ircle
.cpp/in/out
1s /
128M
[
标题描述]
前些天有多少个圆形,
顺时针标号分别从 0 到 n-一,
每一遍等可能率顺时针走一步依然逆时针走一步,
即只要你在 i
号点,你有 百分之五10 概率走到((i-1)mod n)号点,四分之二 可能率走到((i+1)mod
n)号点。问
从 0
号点走到 x 号点的指望步数。
[
输入]
首先行包罗2个平头
T,表示数据的组数。
接下去有
T 行,每行包含多个整数 n, x。
T<=10,
0<=x<n<=300;
[
输出]
对于每组数据,输出一行,包蕴一个二人小数表示答案。
[
样例输入]
3
3
2
5
4
10
5
[
样例输出]
2.0000
4.0000
25.0000
[
数据范围]
对于 30%
的数据,n<=20
对于 50%
的数据,n<=100
对于 70%
的数据,n<=200
对于
100%的数据,n<=300

Solution:

设若本题你还研讨定式的用高精度总括,那您就完蛋了。
(可以得有个别分)
核心首要调查数学知识。
方法一:统计
n!质因子中 2 的个数
n! = 2^a
* M
a=[n/2]+[n/(2^2)]+[n/(2^3)]+
… +[n/(2^g)] (2^(g+1)>n>=2^g)
注脚:加法原理
于是
C(N)K 质因子中 二 的个数为 F = f(N) – f(K) – f(N – K)
若 F 大于
0,则为偶数,等于零为奇数。
*措施贰:由
Lucas 定理妥当 k==(k&n)时为奇数,不然为偶数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 int t,n,k;
 6 int gi() {
 7     int a=0;bool f=0;char c=getchar();
 8     while (c>'9'||c<'0') {if (c=='-') f=1;c=getchar();}
 9     while (c>='0'&&c<='9') {a=a*10+c-'0';c=getchar();}
10     return f?-a:a;
11 }
12 
13 int main() {
14     freopen("comb.in","r",stdin);
15     freopen("comb.out","w",stdout);
16     t=gi();
17     int ans;
18     while (t--) {
19         n=gi();k=gi();
20         ans=(n&k)==k?1:0;
21         cout<<ans<<endl;
22     }
23     return 0;
24 }

Solution:

 首先,标题主要是求从(0,0)能直接观望的点的个数。先考虑唯有一*一的时候,很通晓只能看到二个点:(0,一)、(一,0)、(壹,一)。其实就是下三角的个数*二+一(斜率为1的点)。那么除开一*1以外,大家只供给总括斜率从0到一之间的个数就行了,不包涵壹,包罗0。结果设为sum,那么最后ans=sum*2+1。

1*3头有三个斜率为0的。

2*2斜率有0,六分之三(0已经算过了,现在不要再算了),其实便是多了二个斜率为四分之二的。

3*3的时候,又多了1/3、2/3两个。

4*4的时候,又多了四分之一、百分之七105也是八个。

5*5的时候,又多了1/5、2/5、3/5、4/5这4个。

……

从地方简单窥见规律,对于n*n,可以从(0,0)连接受(n,0)到(n,n)上,斜率将会是1/n,2/n…(n-壹)/n。

大凡
分子和分母能够约分的,也便是有公约数的,前边都已经面世过了。所以每一回添加的个数正是成员和分母互质的个数。

那么难点就转换到了,对此一个数n,求小于n的与n互质的数的个数,其实正是欧拉函数吧~~!

 

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define maxn 1000008
 7 long long phi[maxn];
 8 void getphi()
 9 {
10     for(int i=1; i<maxn; i++) phi[i]=i;
11     for(int i=2; i<maxn; i+=2) phi[i]>>=1;
12     for(int i=3; i<maxn; i+=2)
13         if(phi[i]==i)
14         {
15             for(int j=i; j<maxn; j+=i)
16                 phi[j]=phi[j]/i*(i-1);
17         }
18     phi[1]=3;
19     for(int i=2; i<maxn; i++)
20         phi[i]=phi[i-1]+2*phi[i];
21 }
22 int main()
23 {
24     getphi();
25     int n,ca=0,t;
26     scanf("%d",&t);
27     while(t--)
28         scanf("%d",&n),
29         printf("%d %d %lld\n",++ca,n,phi[n]);
30     return 0;
31 }

 

Solution:

考虑到ai最多变成5八,如若改为越来越大的数还比不上变成一,而且5八之内只有十四个素数

并且能够作证对于四个数a > b,变成的数A >= B

之所以最三唯有十六个最大的数成为素数,别的的数都会化为一

由此一贯对于前拾8个数dp,dp[i][j]代表到第i个数,哪些素因子被用过了,开销起码为多少。枚举贰个数来更换即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 using namespace std;
 7 #define smax(x,tmp) x=max((x),(tmp))
 8 #define smin(x,tmp) x=min((x),(tmp))
 9 const int INF=0x3f3f3f3f;
10 const int prime[] = {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
11 int n,a[105],f[17][1<<17],pdd[105];
12 inline bool cmp(int a,int b){return a>b;}
13 int main()
14 {
15     freopen("seq.in","r",stdin);
16         freopen("seq.out","w",stdout);
17         scanf("%d",&n);
18     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
19         sort(a+1,a+n+1,cmp);
20     for(int i=1;i<=58;i++)
21         for(int j=1;j<=16;j++)
22             if(i<prime[j])break;
23             else if(i%prime[j]==0)pdd[i]|=(1<<j-1);
24         memset(f,0x3f,sizeof(f));
25         f[0][0]=0;
26     for(int i=1;i<=min(n,16);i++)
27         for(int j=0;j<(1<<16);j++)
28                 for(int k=1;k<=58;k++)
29                 if(!(pdd[k]&j))smin(f[i][j|pdd[k]],f[i-1][j]+abs(a[i]-k));
30     int ans=INF;
31     for(int j=0;j<(1<<16);j++)smin(ans,f[min(n,16)][j]);
32     if(n>16)for(int i=17;i<=n;i++)ans+=abs(a[i]-1);
33        printf("%d",ans);
34     return 0;
35 }

 

输入输出格式

输入格式:

一行被被反复贴有boy和girl两单词的字符串。

出口格式:

两行,五个整数。第3行事boy的个数,第3行事girl的个数。

2、N 色球

【标题叙述】
山山是八个双色球高手,每便必中实实在在。
终有壹天,他初叶嫌弃双色球的颜料太少了,于是发明了
N 色球。
平整如下:
一个兜子里富有
n 个分寸、形状相同的球,但各类球标有唯一的数字
你要从那几个袋子中摸出
n-一 个球,最终的奖金为那 n-一 个球所标数字的乘积除以 p 的余数。
山山想清楚她赢得奖金的梦想。
【输入文件】
输入文件
nsq.in 的第 一 行包涵 二 个正整数 n,p
其次行李包裹涵 n
个正整数 a壹,a二…an,表示每一个球所标的数字
【输出文件】
输出文件
nsq.out 仅包含1个实数,表示收获奖金的企盼
答案的误差不可能超越壹e-陆
【样例输入】
3
100
2 1
7
【样例输出】
7.6666666667
【数据规模】
对于
20%的数据,n≤2000
对于
20%的数据,n≤10^5,ai≤10^5,p=1000000007
对于
60%的数据,n≤10^6,ai≤10^9,p≤1000000007

1、单词覆盖还原(数据抓牢版)

 10、组合数

【标题叙述】
多年来先生教了小明怎么算组合数,小明又想到了一个问题。
。 。
小明定义
C(N,K)表示从 N 个因素中不重复地挑选 K 个要素的方案数。
小明想清楚的是
C(N,K)的奇偶性。
自然,这几个整天都老是用竖式算
12345678九*9876543二1=?的人不会让你那么让本人那
么轻松,它说:
“N 和 K 都大概相当大。 ”
可是小明也难于了,所以它就找到了你,想请你帮他化解这些题材。
【输入描述】
输入文件:comb.in
第 1行:二个正整数 t,表示数据的组数。

2~二+t-一 行:八个非负整数 N 和 K。 (保险 k<=n)
【输出描述】
出口文件:comb.out
对于每1组输入,如果C(N,K)是奇数则输出 1,不然输出 0。
【样例输入】
3
1
1
1
0
2
1
【样例输出】
1
1
0
【数据范围】
对于 30%
的数据,n<=10^2 t<=10^4
对于 50%
的数据,n<=10^3 t<=10^5
对于
100%的数据,n<=10^8 t<=10^5
【预备知识

C(n, 0) =
C(n, n) = 1 (n > 0;)
C(n, k) =
C(n − 1, k − 1) + C(n − 1, k) (0 < k < n)

Solution:

固然从高耸入云的一个人向下找,假使那一位为1的数多于三个就取出那一个数,把其它数踢出,然后再取出的那些数里面继续下1个人的1样的拍卖,笔者就用递归写的,最终留给的七个数的相与值会最大。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 #define M 100005
 6 il ll gi()
 7 {
 8     int a=0;char x=getchar();bool f=0;
 9     while((x>'9'||x<'0')&&x!='-')x=getchar();
10     if(x=='-')x=getchar(),f=1;
11     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
12     return f?-a:a;
13 }
14 int a[M],n;
15 il int getand(int *num,int len,int w)
16 {
17     int s[len],sta=0;
18     memset(s,0,sizeof(s));
19     int b=0;
20     for(int i=w;i>=0;i--)
21     {
22         for(int j=1;j<=len;j++)
23         {
24             if(num[j]&(1<<i)){
25             b++;
26             s[++sta]=num[j];
27             }
28         }
29         if(b>1)
30         {
31         int ret=getand(s,sta,i-1)+(1<<i);
32         return ret;
33         }
34     b=0;sta=0;
35     }
36 return 0;
37 }
38 int main()
39 {
40     
41     n=gi();
42     for(int i=1;i<=n;i++)a[i]=gi();
43     cout<<getand(a,n,31);
44     return 0;
45 }

Solution:

题材来自于洛谷的二次月赛,考的时候在ka哥提示下AC,值得一说那题其实很不难,关键是思路。

解法:斐波拉契

思路:多几个人直接诶想到了lca吧,但对那道题显著是不得以的。大家考虑列出几项斐波拉契数来搜寻规律:[1]
[2] [3] [4 5] [6 7 8] [9 10 11 12
13]…大家观看一下上述的几项,同贰个[]中的是同时出生的,大家发现第i个月出生的兔子恰巧正是它上个月事先的兔子所生,而且对于一个数x,它的直白老爸便是x-fi,所以大家能够对此每一回询问(a,b),将a、b中较大的数先往前跳到它的爹爹,然后相比较此时a和b的大大小小是或不是一致,若想同则输出该数,若分歧则再一次上述手续继续往前跳。说的切近不太理解,可是我们团结列壹列应该很不难见到。举个例子:借使作者要询问8和1一的近日集体祖先是什么人,大家先对1一往前跳,即1一-八收获了三,此时可比三和八的大小,不对等,so用较大的数八继续往前跳,即捌-5=三,此时3和三相等了,所以三正是1一和捌的近年公共祖先。

注意:难点中数据较大到了10的13次方,所以要开long
long,其它必须得预处理出斐波拉契中的前60项(因为数量唯有拾的1四次方,斐波拉契的第伍0项刚好超越了多少范围),然后正是读入优化(数据有300多万次询问而且数还那么大),最终在可比时最佳二分查找节省时间。

代码量超少,关键是思路有点得考虑。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define il inline
 5 ll m,a,b;
 6 il ll gi()
 7 {
 8     ll a=0;char x=getchar();bool f=0;
 9     while((x<'0'||x>'9')&&x!='-')x=getchar();
10     if(x=='-')x=getchar(),f=1;
11     while(x>='0'&&x<='9')a=a*10+x-48,x=getchar();
12     return f?-a:a;
13 }
14 ll c[1000000];
15 il void find(ll a,ll b)
16 {
17     if(a<b)swap(a,b);
18     if(a==b){printf("%lld\n",a);return;}
19     int w=lower_bound(c,c+62,a)-c;
20     find(b,a-c[w-1]);
21 }
22 int main()
23 {
24     m=gi();
25     c[0]=1;c[1]=1;
26     for(int i=2;i<=61;i++)c[i]=c[i-1]+c[i-2];//printf("%lld\n",c[i]);
27     while(m--)
28     {
29         a=gi(),b=gi();
30         find(a,b);
31     }
32     return 0;
33 }

相关文章