金币
思路
直接暴力加和就行，到达对应天数时停止
代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int k;
cin>>k;
int sum=0,day=0;
for(int i=1;;i++)
{
for(int j=1;j<=i;j++)
{
day++;
sum+=i;
if(day>=k)
{
cout<<sum;
return 0;
}
}
}
return 0;
}
小红的ABC
思路
一看到回文，第一反应是栈，但是这个题貌似跟栈没太大关系。
这个题需要枚举字串，判断是否是回文
可以优化的是：
从长度较少的字串开始枚举，找到即停止；
另外注意这个题对字串的定义是必须相连的字符；
代码
#include<bits/stdc++.h>
using namespace std;
bool check(string s,int b,int e)
{
int len=s.size();
for(int i=b;i<len;)
{
for(int j=e;j>=0;)
{
if(s[i]!=s[j])
{
return false;
}
else
{
i++;
j--;
if(i>=j)
{
return true;
}
}
}
}
return true;
}
int main()
{
string s;
cin>>s;
int a=2;
int len=s.size();
bool q;
for(a=2;a<=len;a++)
{
for(int i=0;i+a<=len;i++)
{
q=check(s,i,i+a-1);
if(q)
{
cout<<a;
return 0;
}
}
}
cout<<-1;
return 0;
}
木棍游戏
思路
木棍有两种状态：用或不用，借助二值思想，可以用二进制0、1来对应表示用或不用，每条边都用一个n位的二进制表示，需要注意的是木棍不能重复使用
代码
通过率为90.9，还没有找到是什么原因
#include<bits/stdc++.h>
using namespace std;
//海伦公式，直接由三边长求面积
double area(long long a,long long b,long long c)
{
double p=(a+b+c)/2;
double s;
s=sqrt(p*(p-a)*(p-b)*(p-c));
return s;
}
bool tri(long long a,long long b,long long c)
{
if(a+b<=c||a+c<=b||b+c<=a)
{
return false;
}
else
return true;
}
long long getlen(long long s,int *len,int n)
{
long long l=0;
for(int i=n-1;i>=0;i--)
{
if(s&1)
{
l+=len[i];
}
s>>=1;
}
return l;
}
int main()
{
int n;
cin>>n;
int*len=new int[n];
for(int i=0;i<n;i++)
{
cin>>len[i];
}
long long uper=1;
for(int i=1;i<n;i++)
{
uper<<=1;
uper++;
}
long long a,b,c;
double max=-1;
double s=-1;
for(long long i=0;i<=uper;i++)
{
a=getlen(i,len,n);
if(a==0)continue;
for(long long j=i+1;j<=uper;j++)
{
b=getlen(j,len,n);
if(b==0)continue;
for(long long k=j+1;k<=uper;k++)
{
c=getlen(k,len,n);
if(c==0)continue;
if(i&j||i&k||j&k)continue;
if(tri(a,b,c))
{
s=area(a,b,c);
if(s>max)
{
max=s;
}
}
}
}
}
if(max==-1)
{
cout<<-1;
}
else
cout<<fixed<<setprecision(1)<<max;
delete []len;
return 0;
}
思路2
这个题还有另一种枚举方式，即通过dfs，这里直接贴上题解的代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 10;
int q[N];
double res;
int n;
bool st[N];
double ju(double a, double b, double c) // 求三角形面积
{
double p = (a + b + c) / 2;
double s = sqrt(p * (p - a) * (p - b) * (p - c));
return s;
}
void dfs(int a, int b, int c, int index) // 枚举每种情况
{
if (a + b > c && a + c > b && b + c > a)
{
res = max(res, ju(a, b, c));
}
for (int i = index; i <= n; i++)
{
if (!st[i])
{
st[i] = true;
dfs(a + q[i], b, c, index + 1); // 分别加到三条边上
dfs(a, b + q[i], c, index + 1);
dfs(a, b, c + q[i], index + 1);
st[i] = false;
dfs(a, b, c, index + 1); // 都不加
}
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> q[i];
dfs(0, 0, 0, 1);
if (res > 0) printf("%.1lf", res);
else cout << -1;
return 0;
}
空调遥控
题目
思路
室内温度为k时，|a-k|<p时，即k-p<a<p+k时，a-p<k<a+p对应的运动员能进入训练状态，所以直接枚举所有的k，看哪个在范围里的人多；
然后就是要思考下怎么减少所需枚举的个数，
分析下可以理解，使范围的上限或者下限刚好在某个成员的需要温度时，才可能是优解，否则会有浪费
代码
#include<bits/stdc++.h>
using namespace std;
int getnum(int k,int p,int*a,int n )
{
int q,b;
q=lower_bound(a,a+n,k-p)-a;
b=upper_bound(a,a+n,k+p)-a;
return b-q;
}
int main()
{
int n,p;
cin>>n>>p;
int k;
int *a=new int[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int num=-1;
int max=-1;
for(int i=0;i<n;i++)
{
k=a[i]+p;
num=getnum(k,p,a,n);
if(num>max)
{
max=num;
}
}
cout<<max;
return 0;
}