2.LOL Lovers
我们可以从 1 遍历到 len−1，以第 𝑖i 个位置为分割线，统计 [0,i−1] 与 [i,len−1] 的 l 和 o 的个数，判断是否不相等，如果不相等，输出 i，然后退出即可。
如果到最后一直没有输出，就输出 −1。
//暴力枚举
#include<bits/stdc++.h>
using namespace std;
int main()
{
int len;
cin>>len;
string s;
cin>>s;
for(int i=1;i<len;i++)
{
int l=0,o=0;
for(int j=i-1;j>=0;j--)
{
if(s[j]=='L') l++;//统计左边
else o++;
}
int ll=0,oo=0;
for(int j=i;j<len;j++)
{
if(s[j]=='L') ll++;//统计右边
else oo++;
}
if(l!=ll&&o!=oo) //不相等输出
{
printf("%d",i);
return 0;
}
}
printf("-1");
return 0;
}3.质因数分解
learn：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int num1,num2,i;
cin>>n;
for(i=2;i<=sqrt(n);i++)
{
if(n%i==0)
num1=i;
}
num2=n/num1;
cout<<num2;
return 0;
}4.寻宝
6.排队接水
等待时间的话，从小到大排序，注意等待时间
#include<bits/stdc++.h>
using namespace std;
struct water
{
int num,time;
} people[1010],t;
int main()
{
int n;
cin>>n;
int i,j;
for(i=0;i<n;i++)
{
cin>>people[i].time;
people[i].num=i+1;
}
//选择法排序
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(people[i].time>people[j].time)
{
t=people[i];
people[i]=people[j];
people[j]=t;
}
}
}
double sum=0;
for(i=0;i<n;i++)
{
sum=sum+people[i].time*(n-i-1);//剩余人
cout<<people[i].num<<" ";
}
cout<<endl;
sum=sum/n;
printf("%.2f\n",sum);
return 0;
}
7.凌乱的yyy / 线段覆盖
贪心算法
#include<bits/stdc++.h>
using namespace std;
struct game {
int start;
int end;
}a[1000008];
bool cmp(game x,game y)
{
return x.end<y.end;
}
int main()
{
int n,i,count=1,flag=1;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i].start>>a[i].end;
sort(a,a+n,cmp);//按照结束时间排序
int early=0;//当前最早结束时间
当是最后一个或者没有符合条件的时候退出
while(early!=n&&flag!=0)
{
flag=0;
for(i=early;i<n;i++)
{
if(a[i].start>=a[early].end)
{
early=i;//更新
count++;//计数加1
flag=1;//说明有符合条件的
}
}
}
cout<<count;
return 0;
}8.小A的糖果
两堆两堆看，先看左边在看右边那堆
#include<bits/stdc++.h>
using namespace std;
int a[1000005];
long long n,m,ans;
int main()
{
int i;
cin>>n>>m;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<n;i++)
{
if(a[i]+a[i+1]>m)
{
if(a[i]>m) //先吃第一堆剩余m
{
ans=ans+a[i]-m;
a[i]=m;
}
if(a[i]+a[i+1]>m)//再吃第二堆，使两堆和小于m
{
ans=ans+a[i]+a[i+1]-m;
a[i+1]=m-a[i];
}
}
}
cout<<ans<<endl;
return 0;
}9.最大子段和
动态规划
思路可以总结为，找以第i个数为结尾的子段的最大和，可以把前i-1的子段和看成一个整体，小于0就不要，大于0就加上。
状态表示：dp[i]表示以第i个数结尾的最大子段和
状态转移方程：dp[i]=max(a[i],dp[i-1]+a[i])
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
int a[999999],dp[999999];
int i;
int ans=-99999;
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=n;i++)
{
dp[i]=max(a[i],dp[i-1]+a[i]);
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}10.Function
记忆化搜索
记忆化搜索：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。
一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，
以后再次遇到这个状态的时候，就不必重新求解了。
#include<bits/stdc++.h>
using namespace std;
long long q[25][25][25];
long long w(long long a,long long b,long long c);
int main()
{
long long a,b,c;
while(1)
{
cin>>a>>b>>c;
if(a==-1&&b==-1&&c==-1) break;
printf("w(%lld, %lld, %lld) = %lld\n",a,b,c,w(a,b,c));
}
return 0;
}
long long w(long long a,long long b,long long c)
{
if(a<=0||b<=0||c<=0) return 1;
else if(a>20||b>20||c>20)
{
q[20][20][20]=w(20,20,20);
return q[20][20][20];
}
if(q[a][b][c]==0)
{
if(a<b&&b<c)
{
q[a][b][c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
return q[a][b][c];
}
else
{
q[a][b][c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
return q[a][b][c];
}
}
else return q[a][b][c];
}
