https://ac.nowcoder.com/acm/contest/5758
B：减成一
分析：
1.如果前面那个数比这个数大，那直接跳过，因为前面一个数可以带它躺成1。
2.如果前面那个数比这个数小，那区间是只能扩到前一个数这么大，因此还要进行多余的操作使自己变成1，于是产生了(a[i]-a[i-1])代价。
代码：
#include "bits/stdc++.h"
using namespace std ;
typedef long long ll;
ll t,n,sum;
ll a[100005];
int main(){
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=a[i]-1;
}
sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=a[i-1]){
sum+=a[i]-a[i-1];
}
}
cout<<sum<<endl;
}
return 0;
}c:面积
分析：
面积=正方形的面积x^2+两个圆面积23.14(a/2)^2
代码：
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
int i,j,cnt,n,k,t,b,m,ans;
using namespace std;
int main()
{
scanf("%d",&t);
while(t--){
double x;
scanf("%lf",&x);
double r=x/2;
printf("%.2lf\n",3.14*r*r*2+x*x);
}
}E：赛马
分析：
田忌赛马改编题，直接贪心即可。
如此贪心：
从我方大的马和敌方大的马开始比，如果我方的马大于敌方，则贡献值+1，换到对方下一匹马，换到我放下一匹马。
如果我方最大的马都输了，则换到对方下一匹马，我方不变。
大体上懂得取舍便可以了，详细分析可以百度田忌赛马贪心了解。
代码：
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
bool ran(int x,int y)
{
return x<y;
}
int tj[1001],king[1001];
int main()
{
int k,i,j,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&k);
if(k==0) continue;
memset(tj,0,sizeof(tj));
memset(king,0,sizeof(king));
for(i=0;i<k;i++) cin>>tj[i];
for(i=0;i<k;i++) cin>>king[i];
sort(tj,tj+k,ran);
sort(king,king+k,ran);
long int count=0;
int tj_min=0,tj_max=k-1;
int king_min=0,king_max=k-1;
while(tj_min<=tj_max)
{
if(tj[tj_max]>king[king_max])
{
count++;
tj_max--;king_max--;
}
else if(tj[tj_min]>king[king_min])
{
count++;
tj_min++;king_min++;
}
else
{
// if(tj[tj_min]<king[king_max])
// count--;
tj_min++;king_max--;
}
}
cout<<count<<endl;
}
return 0;
}F：三角形
分析：
三角形两边之和大于第三边，为了使得切割段数最多，我们由切割为1的片段开始，一开始为1，下个为1，再下个不能取1了，因为会组成三角形，所以我们取敲好不能组成三角形的最小片段2，然后2也不能取了，因为221会组成三角形，进而取3，于是我们发现每次取得的数恰好等于前面两个数的和，由此使得其恰好不能构成三角形，而112358这些数我们不难看出是斐波那契数列，由于斐波那契增长很快，从1开始枚举到总长度即可，记得开unsigned long long.
代码：
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
ll a[105];
int main(){
int T;
cin>>T;
a[1]=1,a[2]=1;
for(int i=3;i<=100;i++)
a[i]=a[i-1]+a[i-2];
while(T--){
ll n;
cin>>n;
ll res=0;
for(int i=1;i<=100;i++){
if(a[i]>n) break;
else n-=a[i],res++;
}
cout<<res<<endl;
}
return 0;
}H：直线
分析：
结论题，答案为n*（n-1）/2
最优方案每条线都与其他的线相交，则每条线的贡献值为n-1,总共有n条线，同一根线算了两次。
数据范围要用大数，最好写个python，当然套用大数板子还是蛮舒服的。
代码：
#include "bits/stdc++.h"
using namespace std ;
typedef long long ll;
void reverse(char * c)
{
int len = strlen(c);
for(int i=0; i<len/2; i++)
swap(c[i],c[len-i-1]);
}
void multiplication(char * srca,char * srcb,char * dest)//未翻转
{
int ia,ib,c,
na = strlen(srca),
nb = strlen(srcb);
reverse(srca);
reverse(srcb);
for(ia=0; ia<na; ia++)
{
c = 0;
for(ib=0; ib<nb; ib++)
{
int t = (srca[ia]-48) * (srcb[ib]-48) + c,tt;
if(dest[ia+ib]>47)
tt = dest[ia+ib]-48 + t;
else
tt = t;
dest[ia+ib] = tt%10 +48;
c = tt/10;
}// for
while(c) //处理进位，直到进位为0
{
int t;
if(dest[ia+ib]>47)
t = dest[ia+ib] - 48 + c;
else
t = c;
dest[ia+ib++] = t%10 + 48;
c /= 10;
}// while
}// for
//将两个乘数和乘积都改为大端法
reverse(dest);
reverse(srca);
reverse(srcb);
}
void division(char * src,int n,char * dest)
{
int len = strlen(src),
i, //计数
k, //商的下标
t = 0, //新的余数
s = 0; //余数
bool flag = true; //商是否有了第一个有效位，防止商首部一直出现0
for(i=0,k=0; i<len; i++)
{
t = s*10+(src[i]-48); //新余数
if(t/n>0 || t==0) //余数为0要修改商
dest[k++] = t/n+48,s = t%n,flag = false;
else //不够除，修改余数
{
s = t;
if(!flag) //商已经有有效位了，补零
dest[k++] = '0';
}// if
}// for
//::memset(src,0,len);
//memcpy(src,dest,strlen(dest));
}
char a[100],b[100],c[100],temp[100],ans[100];
int main()
{
int t;
scanf("%d",&t);
while(t--){
memset(a,'\0',sizeof(a));
memset(b,'\0',sizeof(b));
memset(c,'\0',sizeof(c));
memset(temp,'\0',sizeof(temp));
memset(ans,'\0',sizeof(ans));
long long n,m;
scanf("%lld",&n);
m=n-1;
sprintf(a, "%lld", n);
sprintf(b, "%lld", m);
multiplication(a,b,c);
division(c,2,ans);
printf("%s",ans);
printf("\n");
}
}python：
n=int(input())
i=0
while i < n:
a=int(input())
print (int(a*(a-1)//2))
i=i+1J：最大值
分析：
正解好像是kmp，但是不会，看了大佬题解我才知道可以用二分蛮过去。
截取字符串0-len，再用非前缀长度为len的字符串与它比较，如果相等就是表示len这个长度可以做到，不相等判断下一个，如此进行二分选择，如果到最后还没有相等的，就是len不行。
代码：
#include "bits/stdc++.h"
using namespace std ;
typedef long long ll;
string s;
ll n,T;
int check(int len){
string tmp=s.substr(0,len);
for(int i=1;i+len<=n;i++){
string q=s.substr(i,len);
if(q==tmp) return 1;
}
return 0;
}
int main(){
cin>>T;
while(T--){
cin>>s;
n=s.size();
int l=0,r=n,res;
while(l<=r){//二分
int mid=(l+r)>>1;
if(check(mid)){
res=mid;
l=mid+1;
}
else r=mid-1;
}
cout<<res<<endl;
}
return 0;
}
京公网安备 11010502036488号