模考DAY3总结
1.题解部分
第一题：(田忌赛马)
你有没有听过田忌赛马的故事？啊？你没听过，那没关系，你看题就好了
呵呵呵，你就是随便怎么乱搞也是 O(1) 的复杂度，所以。。。。。
三重循环！！！上！！
for(ll i=0;i<3;i++){
for(ll j=0;j<3;j++){
for(ll k=0;k<3;k++){
if(i==j||j==k||i==k) continue;
ll a1=b[0]>a[i];
ll b1=b[1]>a[j];
ll c1=b[2]>a[k];
if(a1+b1+c1>=2){
cout << "Yes";
return 0;
}
}
}
}
cout << "No";
太简单了，不过这个东西是只有智灵基础才会写的**代码，所以。。。
咱们来分析一波！！
知周所众，田忌赛马是齐威王按顺序出马，田忌不按套路出马，so,我们先对两个数组进行排序，然后把田忌的中等马与齐威王的下等马进行比较，如果成功获胜，那么再看田忌的上等马和齐威王的中等马，如果再次获胜，哼，后面就不用我说了吧。那田忌的下等马怎么办捏，没事，不用管他，不管赢或不赢，我们的三局两胜依然是成立的，这个其实就是更加牛的数学推理，和智灵基础的暴力代码不知道好了多少。
部分代码;
sort(a, a+3);
sort(b, b+3);
if(b[2]>a[1]&&b[1]>a[0]) cout << "Yes";
else cout << "No";
十分简单有木有！！（虽然我用的是暴力代码）
第二题：(地精的金币)
我有个问题。。。。这样哪里像地精啦！！-_-
咳咳，我开玩笑的…
来正常分析一波!
我们发现输入的字符的顺序和输出没有半毛钱关系！！所以我们只需要统计每种字符的个数就行了。
统计完成后我们来看它能表示的最大的数如何计算（要不然直接搜索会超时）。
首先，肯定是有眼睛在左边才能出现地精，那为了让利益最大化，我们把所有眼睛全放在左边，但是我们发现右边没有眼睛，导致这个字符串表示的数字是0，那么，我们如果把一个眼睛放在右边呢？
那么它的计算公式就是：
(所有眼睛数-1)* 嘴巴数 * 1
我们发现其实公式里的1就是右边的眼睛数，所以计算公式就是
左眼睛数*嘴巴数*右眼睛数
我们已知嘴巴数和左右眼睛数之和，现在的问题就是怎么让左右眼睛乘积
最大。
大家看到我得出结论的那一刻可能就想到解决方法了（当然，我说的是数学大佬们）没错，我们要引用一个超级nb的数学结论：
和不变，两数之间差越小，积越大
那么就可以很容易得出最终的计算公式！
（没错，BB了这么久终于能写点有用的了）
(眼睛和/2)*嘴巴数*(眼睛和/2)
那么也可以上一个部分代码了！
for(ll i=0;i<n;i++){
if(s[i]=='_'){
num1++;
}
else{
num2++;
}
}
if(num2%2==0){
cout << num1*(num2/2)*(num2/2);
}
else{
cout << num1*(num2/2+1)*(num2/2);
}
PS：这里要加一个特判，因为奇数用这个公式会凭空少1，所以我们要加上去。
第三题：(数（shu）矩形)
这道题我建议去看 李予劼的题解 因为整体的思路十分难，要进行逻辑推理的话还需要打很多字，这里就偷个懒，先不写了，贴一个部分代码吧
for(ll i=0;i<n;i++){
cin >> a[i];
s[i+1]=a[i]+s[i]; // 前缀和
}
for(ll i=0;i<n;i++){
{
ll l=lower_bound(a, a+n, a[i]+k+1)-a;
ll r=upper_bound(a, a+n, a[i]+k+m)-a;
if(l<r){
ans+=(m+a[i]+k+1)*(r-l)-(s[r]-s[l]);
}
}
{
ll l=i+1;
ll r=upper_bound(a, a+n, a[i]-k+m)-a; // 二分查左右边界
if(l<r){
ans+=(m+a[i]-k+1)*(r-l)-(s[r]-s[l]); // 贡献计算
}
}
第四题：（小信打扑克）
这道题直接可以看出是LIS（最长上升子序列），因为原始序列变为排序好的序列不需要动的就是原数组的最长上升子序列，但是直接LIS会超时，那咋么办呢，我们可以用贪心+二分的方法进行优化，优化到 O(nlog(n)) 的时间复杂度，这样就可以了，这个方法这里不细讲，直接贴个部分代码就跳过。
vector<ll>d;
for(ll i=0;i<n;i++){
if(d.empty()||b[i]>d.back()) d.push_back(b[i]);
else{
ll p=lower_bound(d.begin(),d.end(),b[i])-d.begin();
d[p]=b[i];
}
}
return d.size();
这里我们主要要细讲的是预处理部分（因为这里又要头脑风暴了）
咱们来分析一波！！！
这里有一个十分讨厌的地方就是字母花色，当我们用最长上升子序列来解决问题的时候字母花色也需要考虑在内
我们发现字母花色C A M P的顺序并没有明确要求，他只是要求要把花色放在一起，于是我们就可以随意安排四个花色的先后顺序，一共有 4*3*2*1 种排序可能，也就是 24 种排序可能
我们对每一个排列可能都进行一次LIS，这个时候把字母花色按照已经枚举好的先后顺序将其转为数就可以了
PS：X要特殊处理
部分代码：
struct node{
char c;
ll a;
};
node a[100005];
ll b[100005];
char p[] = {'A', 'C', 'M', 'P'};
do{
map<char, ll> mp;
for(ll i=0;i<4;i++){
mp[p[i]]=i*n+i*n;
}
mp['X']=4*n+4*n;
for(ll i=0;i<n;i++){
b[i]=mp[a[i].c]+a[i].a;
}
vector<ll>d;
for(ll i=0;i<n;i++){
if(d.empty()||b[i]>d.back()) d.push_back(b[i]);
else{
ll p=lower_bound(d.begin(),d.end(),b[i])-d.begin();
d[p]=b[i];
}
}
ll x=(n-d.size());
ans=min(ans, x);
}while(next_permutation(p, p+4));
PS:我用的函数需要让字符数组按照字典序排序，所以我没按照camp这个英文单词来放置数组
PPS：你有没有发现其实这几个花色组成了X-CAMP
2.做题情况
第一题
额，第一题看了半天愣是没看出正解做法，于是一咬牙用了一个满级暴力，虽然这样不会超时，但是其实我应该停下来想一想正解的，最后推理也很简单。
分数：AC 100pt
第二题
这道题比第一题做的更快，我做完的时候其他人还在冥思苦想，这道题补足了第一题的时间浪费，给下一道题和下下道题留够了时间。
分数：AC 100pt
第三题
这道题很难，我写了一个暴力做法，我调了半天居然还不懂第二个样例是啥意思，于是我又去做第四题，可是我同桌样例过了，我连忙又切回第三题，在我的努力调试下终于发现了问题，并改完了代码。
分数：TLE 20pt (后来我发现有人用暴力拿了70pt QWQ)
第四题
这道题更难，我思索了很久，决定用最长公共子序列来做，虽然超时了，但是如果没有时间限制的话应该是AC的，就是先排序然后找排序和原数列的最长公共子序列就可以了。
分数：TLE 5pt（全场只有我和李心晨拿到了这5分哦）
3.总结
整体来看这次的模考很成功，第一题和第二题发挥稳定，第三第四题拿到了该拿的部分分。
预期得分：225pt
实际得分：225pt
和上次比就是时间掌控的比之前好很多，后面全做完还有时间检查前面的题
祝我下次模考
