t1 浇花
考场代码：
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 1010
int n,minn=0,pos=0,min_h=1e9;
int mincf[N][N],ans[N],h[N],cf[N];
int main()
{
freopen("read.txt","r",stdin);
rd(n);
rep(i,1,n)
{
rd(h[i]);
if(h[i]<min_h)
{
min_h=h[i];
pos=i;
}
cf[i]=h[i]-h[i-1];
ans[i]++;
}
rep(i,1,n)
{
if(cf[i]>0)
ans[i-1]++;
else ans[i]++;
}
rep(i,1,n)
{
if(h[i]<h[i-1] && h[i]<h[i+1])ans[i]++;
else if(h[i-1]<h[i] && h[i-1]<h[i+1])ans[i-1]++;
else if(h[i+1]<h[i] && h[i+1]<h[i-1])ans[i+1]++;
}
rep(i,1,n)
{
if(h[i]<h[i-1] && h[i]<h[i+1] && h[i]<h[i+2])ans[i]++;
else if(h[i-1]<h[i] && h[i-1]<h[i+1] && h[i-1]<h[i+2])ans[i-1]++;
else if(h[i+1]<h[i] && h[i+1]<h[i-1] && h[i+1]<h[i+2])ans[i+1]++;
else if(h[i+2]<h[i] && h[i+2]<h[i-1] && h[i+2]<h[i+1])ans[i+2]++;
}
if(pos==1)ans[1]=n;
if(pos==n)ans[n]==n;
ans[pos]++;
/*rep(l,1,n)//当前区间长度
rep(i,1,n)//当前区间起点
for(int j=i+l;i<=n;++i)//终点
{
anss[i][j]=min(h[i],h[j]);
}
*/
rep(i,1,n)
printf("%d ",ans[i]);
return 0;
}
正解：
思路：
根据乘法原理，一个数被统计的次数==(i-l[i])* (r[i]-r)
l[i]:i左边第一个<i的数
r[i]:i左边第一个<i的数
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 1000010
int n;
int a[N],l[N],r[N];
map<int,long long>h;
int main()
{
freopen("read.txt","r",stdin);
rd(n);
rep(i,1,n)
{
rd(a[i]);
l[i]=i-1,r[i]=i+1;//注意要初始化
}
rep(i,1,n)
while(a[l[i]]>a[i])
l[i]=l[l[i]];//更新l[i]
dwn(i,n,1)
while(a[r[i]]>a[i])
r[i]=r[r[i]];//更新r[i]
rep(i,1,n)
printf("%lld ",(long long)(i-l[i])*(r[i]-i));
//注意一定要转long long！！！！乘积有可能会爆掉int
return 0;
}
t2 ABCDEF
思路：
-
(a × b + c) ÷ d – e = f 变形成(a * b+c)==(f+e) * d,省去除法（浮点数懒得判断）
-
使用map<int,long long>h，哈希表来做等式两边的中转
-
十年OI一场空，不开long long 见祖宗
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 110
int n;
map<int,long long>h;
int x[N];
ll ans;
int main()
{
freopen("readda.txt","r",stdin);
rd(n);
rep(i,1,n)rd(x[i]);
rep(a,1,n)
rep(b,1,n)
rep(c,1,n)
h[x[a]*x[b]+x[c]]++;
rep(d,1,n)
rep(e,1,n)
rep(f,1,n)
{
if(x[d]==0)continue;
ans+=h[(x[f]+x[e])*x[d]];
}
printf("%lld",ans);
return 0;
}
t3奶牛健美操
题目大意：
给定一棵树，可以删掉s条边，求删掉后森林中所有树直径的最大值的最小值
思路：
-
最大值最小，典型的二分答案
-
此题我们二分树的直径，每次二分DFS一次，对于每个节点统计出所有子树删边后的dis，排序，贪心删掉最大的，直到最大的两个子树相加不会超过二分的答案为止
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
const int N=1e5+10;
struct Edge{int v,next;}e[N<<1];
int n,s,tot,ans,head[N],a[N],f[N];
void add(int x,int y){e[++tot].v=y;e[tot].next=head[x];head[x]=tot;}
void dfs(int u,int fa,int limit)
{
int cnt=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
dfs(e[i].v,u,limit);
}
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
a[++cnt]=f[v]+1;
}
sort(a+1,a+cnt+1);
while(cnt && a[cnt]+a[cnt-1]>limit)
cnt--,ans++;
f[u]=a[cnt];
}
inline bool check(int x)
{
ans=0;
dfs(1,0,x);
return ans<=s;
}
int main()
{
freopen("input.txt","r",stdin);
rd(n),rd(s);
rep(i,1,n-1)
{
int u,v;rd(u),rd(v);
add(u,v),add(v,u);
}
int l=0,r=n,mid,ans;
while(l<=r)
{
mid=l+r>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d",ans);
return 0;
}
分数与总结：
t1 0pts
t2 30pts
t3 0pts
考试的时候心态崩了，t1、t3都写挂了，只拿了t2的暴力分……我ｓｋｒ ｚｚ
暴露出的问题：
- map
- 单调栈
- 树形DP+二分