B 减成一
链接：https://ac.nowcoder.com/acm/contest/5758/B
来源：牛客网
题目描述
存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。
数据保证一定有解。
输入描述:
输入t，代表有t组数据。每组数据输入n，代表有n个数。接下来一行输入n个数，数字大小小于1e6。(t<=1000，n<1e5，∑n < 1e6)输出描述:
每组数据输出一个整数代表最少需要操作的次数。
输入
1
6
1 3 5 2 7 1输出
9我的代码
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int array[100000]={0};
int n,ans=0,num,pre=0;
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%d",&array[i]);
if (i==0)
{
ans+=array[i]-1;
}
else
{
ans+=(array[i-1]>array[i]?0:(array[i]-array[i-1]));
}
}
printf("%d\n",ans);
}
return 0;
}C 面积
链接：https://ac.nowcoder.com/acm/contest/5758/C
来源：牛客网
题目描述
如图所示，正方形周围接4个半圆，求图形的面积
输入描述:
输入t，代表有t组数据。每组数据输入正整数x，代表正方形的边长。(t<100, x<1000)输出描述:
输出图形面积，并保留2位小数，其中π取3.14。
输入
1
1输出
2.57我的代码
#include<stdio.h>
int main()
{
int t,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&x);
double ans=x*x+3.14*x*x/2;
printf("%.2f\n",ans);
}
}E 赛马
链接：https://ac.nowcoder.com/acm/contest/5758/E
来源：牛客网
题目描述
一天小明与他同学准备赛马，他们每人有n匹马，每匹马有一个固定的战力值，战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序，小明在更改自己马出场顺序后最多能赢多少场比赛。
输入描述:
输入t，代表有t组数据。每组数据输入正整数n，每人的马匹数量。下一行输入n个值a[i]，代表小明每匹马的战力值。接下来一行输入n个值b[i]，代表对手按顺序出场的每匹马的战力值。(t<=10, n<1000，1<=i<=n，a[i]<1e6，b[i]<1e6)输出描述:
小明在更改马匹出场顺序后，最多能赢的场数。输入
1
3
5 8 8
4 7 10输出
2我的代码
#include<stdio.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,ans=0;
int a[1001],b[1001];
scanf("%d",&n);
for (int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for (int i=0;i<n;i++)
{
scanf("%d",&b[i]);
}
sort(a,a+n,cmp);
sort(b,b+n,cmp);
int k=0,able=0;
for (int i=0;i<n;i++)
{
while(a[k]>b[i]&&k<n)
{
able++;
k++;
}
if (able>0)
{
able--;
ans++;
}
}
printf("%d\n",ans);
}
return 0;
}F 三角形
链接：https://ac.nowcoder.com/acm/contest/5758/F
来源：牛客网
题目描述
小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），
使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？
输入描述:
输入数据的第一行是t，表示数据的组数, 接下来每组数据输入一个a（t<=1000, 1 <= a < 2^64 - 1）输出描述:
对于每组输入样例，打印木棒最多被分为多少段输入
2
1
3输出
1
2我的代码
#include<stdio.h>
int main()
{
int t,flag=1;
scanf("%d",&t);
unsigned long long int dp[50000];
unsigned long long int sum[50000];
unsigned long long int k=18446744073709551615ull;
dp[1]=1ull;
sum[1]=1;
dp[2]=1ull;
sum[2]=sum[1]+dp[2];
for (int i=3;i<92;i++)
{
dp[i]=dp[i-1]+dp[i-2];
sum[i]=sum[i-1]+dp[i];
//printf("%llu\n",dp[i]) ;
//printf("%llu\n",sum[i]) ;
}
while(t--)
{
long long int a;
scanf("%llu",&a);
int l=1,r=91,mid;
while(l<=r)
{
mid=(l+r)/2;
if (sum[mid]>a)
{
r=mid-1;
mid=(l+r)/2;
}
else
{
l=mid+1;
mid=(l+r)/2;
}
}
printf("%d\n",mid);
}
return 0;
}H 直线
链接：https://ac.nowcoder.com/acm/contest/5758/H
来源：牛客网
题目描述
平面上存在n条直线。请问n条直线在平面上最多存在多少交点。
输入描述:
输入数据的第一行是t，表示数据的组数（t < 100）, 接下来每组数据输入一个n（1<=n <= 1e15）输出描述:
对于每组输入样例，打印n条直线最多有多少个交点输入
2
1
2输出
0
1#include<stdio.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* MultipyBigNumber(char *s,char *p)
{
int i,j,x,bit1,bit2;
int len1 = strlen(s);
int len2 = strlen(p);
int len3 = len1 + len2; /* 结果的位数最大应为两个长度相加 */
char *arr;
arr = (char*)malloc(sizeof(char)*(len3+1));
arr[len3] = '\0';
arr = &arr[len3];
len1--;
len2--;
i = x = 0;
while(i < len3 - 1 || x != 0)
{
for(j = 0; j <= i; j++)
{
bit1 = len1 - i + j;
bit2 = len2 - j;
if(bit1 >= 0 && bit2 >= 0)
x += (s[bit1] - '0') * (p[bit2] - '0');
}
*(--arr) = x % 10 + '0';
x /= 10;
i++;
}
if(*arr++ == '0')
*arr = '\0';
return --arr;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int flag=29;
long long int k,m,ans;
char kk[30],mm[30];
scanf("%lld",&k);
m=k-1;
if ((k%2)==0)
{
k=k/2;
}
else
{
m=m/2;
}
sprintf(kk, "%lld",k);
sprintf(mm, "%lld",m);
puts(MultipyBigNumber(kk,mm));
//itoa(k,kk,10);
//itoa(m,mm,10);
//ans=k*m;
//printf("%s\n%s",kk,mm);
}
}J 最大值
链接：https://ac.nowcoder.com/acm/contest/5758/J
来源：牛客网
题目描述
有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少
输入描述:
输入数据第一行是t，表示数据的组数，接下来每组数据输入一个字符串s（t<=10，s<=1e5）输出描述:
输出最大长度输入
2
aaaaa
abacc输出
4
1说明
aaaab的ac串是aaa(2:4)acac的ac串是ac(3:4)#include <iostream>
#include <string>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
string s,sub;
cin>>s;
int len=s.length(),l=0,r=len-1,mid;
while(l<=r)
{
mid=(l+r)/2;
sub=s.substr(0,mid);
if (s.find(sub,1)!=-1)
{
l=mid+1;
mid=(l+r)/2;
}
else
{
r=mid-1;
mid=(l+r)/2;
}
}
sub=s.substr(0,mid);
printf("%d\n",sub.length());
}
return 0;
}A 最大点对符
链接：https://ac.nowcoder.com/acm/contest/5758/A
来源：牛客网
题目描述
这里有一棵树，每个点和每条边都存在一个价值。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。
求这颗树上最大的点对价值为多少。点对至少需要两个点。
输入描述:
输入t，代表有t组样例。每组样例第一行输入n，代表有n个点。接下来有n-1行，第i行有a[i]和b[i]，代表a[i]节点与i节点存在一条边，且边的值为b[i]，2<=i<=n。接下来一行有n个值c[j]，代表每个节点j的价值，1<=j<=n。（t<=10，n>1，n<1e6，a[i]<i，-500<=b[i]<=500，-500<=c[j]<=500）输出描述:
输出最大的点对价值
输入
1
4
1 -2
1 2
1 3
2 -2 3 4输出
12D 扔硬币
链接：https://ac.nowcoder.com/acm/contest/5758/D
来源：牛客网
题目描述
有n枚硬币，每枚硬币扔出来是正面和反面的概率各占50%。小明同时扔下了n枚硬币后，已知至少有m枚硬币是反面。请问恰好有k枚硬币是正面的概率是多少。
输入描述:
输入t，代表有t组数据。每组数据输入一个数n，m，k，代表有n枚硬币，抛出以后至少有m枚是反面的情况下，恰好有k个正面的概率。(t<=1000，n<1e5，m<=1000，k<=n)输出描述:
对于结果是p/q，输出分数取模1e9+7后的结果。
输入
1
10 3 5输出
797520667G 养花
链接：https://ac.nowcoder.com/acm/contest/5758/G
来源：牛客网
题目描述
小明是一个魔法师，他有n棵植物，所有植物排成一排，植物的初始高度为数组h，小明有一些强迫症，他想
让植物的高度都恰好达到k，小明有m瓶药水，但药水分为4种：
1.选择一棵高度为a0的植物变为b0高度的植物
2.选择一棵高度在[a1,a2]区间内的植物变为b1高度的植物
3.选择一棵高度为a1的植物变为[b1, b2]区间内某一高度的植物
4.选择一棵高度在[a1,a2]区间内的植物变为[b1,b2]区间内某一高度的植物
由于每瓶药水有C瓶库存，小明想知道他最多让多少棵植物高度达到k
输入描述:
输入数据第一行是t，表示数据的组数，接下来每组数据输入n，m，k，接下来一行输入n个数，分别是每棵植物的高度h[i]（1 <= h[i] < k）,接下来m行开头的两个数字为op和c表示药水是哪一种和该种药水有几瓶，输入如下若 op=1，则接下来两个整数 a0，b0，意义如上文所述。若 op=2，则接下来三个整数 a1,a2,b1，意义如上文所述。若 op=3，则接下来三个整数 a1,b1,b2，意义如上文所述。若 op=4，则接下来四个整数 a1,a2,b1,b2，意义如上文所述。数据保证，所有 1 <= a0,b0,a1,b1,a2,b2 <= k（t <= 10，n <= 1e4，m <= 300，k <= 100，c <=1e6）输出描述:
输出一个整数，表示最多有多少颗植物能生涨到k。输入
1
5 4 5
1 1 1 1 1
1 3 1 3
1 3 3 2
1 3 2 5
4 1 1 1 4 5输出
4I 字典序
链接：https://ac.nowcoder.com/acm/contest/5758/I
来源：牛客网
题目描述
小明遇到了一个问题希望你能帮他解决
现在有n个数字排成一列构成数组A，数组A中存在n个数a[i], 其中1<=i<=n。
数组sj为删除数组A中的第j个数后，剩余n-1个数构成的数组，其中1<=j<=n。
小明希望你把s1~sn的数组按照字典序大小排列起来，
若两个数组相等，则认为删除元素编号小的数组字典序更小
输入描述:
输入数据第一行是t，表示数据的组数，接下来每组数据输入n，接下来一行一共n个数，a[i]表示数组的第i个数（t<=10，n <= 1e5，a[i] <= 1e9）输出描述:
输出一行n个整数，b1,b2...bn，表示Sb1 < Sb2 < ... < Sbn输入
1
7
1 1 2 1 1 1 2输出
3 7 4 5 6 1 2