题目列表
考场 $225\ \tt{pts}$，
考完改了 $10$ 个字节 $335\ \tt{pts}$，
回家改了 $2$ 个字节 $400\ \tt{pts}$。
水平没长进挂分的水平进步不小。
D.三角形个数 count
很显然 $\mathcal O(n^2)$ 枚举两个角度会超时。
考虑到题目隐藏数据范围 $a_i\leq 180$，我们实际只要开桶记录每个度数出现次数，然后枚举三角形角度得到每个度数出现次数，相乘即可。
考场的 $j$ 和 $k$ 变量忘记 $+1$，$-80\ \tt{pts}$。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
long long h[200];
long long cnt;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
h[x]++;
}
for(int i=1;i<180;i++)
{
for(int j=i+1;j<180;j++)
{
for(int k=j+1;k<180;k++)
{
if(i+j+k!=180)continue;
cnt+=h[i]*h[j]*h[k];
}
}
}
cout<<cnt<<endl;
return 0;
}
/*
5
20 20 30 130 14
*/E.牛队 cow
考虑到这头牛能网友看到的牛的高度具单调递减，具有单调性。
直接单调栈维护，一旦即将进入的高度比栈顶高就连续排出元素最后插入进栈。
看到的牛高度是严格小于当前牛的高度。
考场没有发现是严格小于，写的小于等于，$-65\ \tt{pts}$。
代码
#include<bits/stdc++.h>
using namespace std;
stack<int>s;
int n;
int a[1000020];
long long ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
}
for(int i=1;i<=n;i++)
{
if(s.empty()||s.top()>a[i])
{
// cout<<"insert:"<<a[i]<<endl;
s.push(a[i]);
}
else
{
// ans+=1LL*s.size()*(s.size()-1)/2;
while(!s.empty()&&s.top()<=a[i])
{
ans+=s.size()-1;
s.pop();
}
// cout<<"insert:"<<a[i]<<endl;
s.push(a[i]);
}
}
ans+=1LL*s.size()*(s.size()-1)/2;
// for(int i=1;i<=n;i++)
// {
// for(int j=i+1;j<=n;j++)
// {
// if(a[j]>=a[i])break;
// ans++;
// }
// }
printf("%lld\n",ans);
return 0;
}
/*
5
3 2 4 1 5
5
1 4 2 3 5
10
6 7 10 3 4 8 1 2 5 9
*/F.机房分组 team
求最值，考虑穷举贪心二分答案。
这题显然有贪心性质，每次插到最小但是能容纳下这个同学的列去。
建议的证明就是，其他列的可能可以给比你大的人坐，为了每一列坐得多你不能抢别人位置。
不知道为啥这个代码稀里糊涂的跑过去了，应该是可以二分得到最小位置继续优化的。
考场的 $top$ 变量第一次调用没有 ++top，$- 20\ \tt{pts}$。
代码
#include<bits/stdc++.h>
using namespace std;
int top,n;
int a[200020];
vector<int>b[200020];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
// for(int i=1;i<=n;i++)
// {
// if(!top||a[i]>f[top])
// {
// f[++top]=a[i];
// }
// else
// {
// int p=lower_bound(f+1,f+top+1,a[i])-f;
// f[p]=a[i];
// }
// }
b[++top].push_back(a[1]);
for(int i=2;i<=n;i++)
{
int minn=INT_MAX,p=0;
for(int j=1;j<=top;j++)
{
if(a[i]<=b[j][int(b[j].size())-1]&&b[j][int(b[j].size())-1]<minn)
{
minn=b[j][int(b[j].size())-1];
p=j;
}
}
if(!p)
{
b[++top].push_back(a[i]);
}
else
{
b[p].push_back(a[i]);
}
}
cout<<top<<endl;
return 0;
}
/*
7
6 3 6 1 2 4 5
8
389 207 155 300 299 170 158 65
*/G.买铅笔 pencil
完全背包板子。
但是，完全背包是求能装下的最大价值，这里是求超过的最小价值。
那么显然，除了最大最小需要改变，观察到 $a_i,b_i\leq 100$，我们只需上限调到 $n+100$ 即可，然后在 $[n,n+100]$ 的范围内找最小花费，保险一点右端点可以写成 $n+200$。
代码
#include<bits/stdc++.h>
using namespace std;
long long f[4000500];
int n;
int x,y;
int main()
{
memset(f,0x3f,sizeof(f));
cin>>n;
f[0]=0;
for(int i=1;i<=3;i++)
{
cin>>x>>y;
for(int j=x;j<=n+200;j++)
{
f[j]=min(f[j],f[j-x]+y);
}
}
for(int j=n;j<=n+200;j++)
{
f[n]=min(f[n],f[j]);
}
cout<<f[n]<<endl;
return 0;
}
/*
57
2 2
50 30
30 27
*/