Codeforces Round #271 (Div. 2) F ,E, D, C, B, A

前言:最近被线段树+简单递推DP虐的体无完肤!真是弱!

A:简单题,照着模拟就可以,题目还特意说不用处理边界

B:二分查找即可,用lower_lound()函数很好用

 #include<string.h>
#include<math.h>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<string>
#include<iostream>
using namespace std;
#define N 200005
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1 int a[N],s[N];
int main()
{
int n;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i]); for (int i=;i<=n;i++)
a[i]+=a[i-];
int m;
scanf("%d",&m);
while (m--)
{
int x;
scanf("%d",&x);
int p=lower_bound(a+,a+n+,x)-a;
printf("%d\n",p);
}

C:没写,但是是一道比较难处理的模拟题吧,求每个点绕它中轴点顺时针旋转90度,求能形成的最小旋转次数,4^4次,还有面积要大于0这个坑点。

D:简单DP,居然推到数学公式,真是SB,我们要使连续的字符串里面个W个数为x*k;当时想到求排列组合,以为可以化简,结果自己掉坑里!

正确做法,定义一维数组,就是求前导和。

方程:DP[I]=DP[I-1]+DP[I-K];(i>=k);(表示:I不为好的话,和为好的发时的总数)

DP[I]=DP[I-1];

s[i]=s[i-1]+DP[I]; (对前i段累加)

中间有Mod 操作,有很多询问,所以要一次做,然后之间求区间值即可!

 #include<bits/stdc++.h>
typedef long long ll;
using namespace std; #define mod 1000000007
#define N 100007
int a[N];
ll s[N]; int main()
{
int k,t;
scanf("%d%d",&t,&k);
a[]=;
for (int i=;i<N;i++)
{
if (i>=k) {a[i]=a[i-]+a[i-k];a[i]%=mod;}
else {a[i]=a[i-];a[i]%=mod;} s[i]=s[i-]+a[i];
s[i]%=mod;
} while (t--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",(s[y]-s[x-]+mod)%mod);
} return ;

E:题目简短,二维可以写出,但会TLE。

然后看到一个神奇骗AC代码,可以看看

 include<bits/stdc++.h>
#define N 111111
using namespace std;
typedef long long ll;
int n;
ll h[N],ans[N],next[N];
ll d;
int main()
{
cin>>n>>d;
for (int i=;i<=n;i++)
{
cin>>h[i];
ans[i]=;
next[i]=-;
}
int mx=;
int start=n;
for (int i=n;i>=;i--){
for (int j=i+;j<=min(i+,n);j++)
{
if (abs(h[j]-h[i])>=d&&ans[j]+>ans[i])
{
next[i]=j;
ans[i]=ans[j]+;
}
} if (ans[i]>mx)
{
mx=ans[i];
start=i;
}
} cout<<mx<<endl;
int i=start;
while (i!=-)
{
cout<<i<<" ";
i=next[i];
} return ;
}

它这里限制了第二重循环的次数,实际上可以第二重循环可以弄到300,或者更少,数据太弱吧!

正解:线段树单点跟新+二分!

分析写到代码里吧!

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l, m,rt<<1
#define rson m+1,r,rt<<1|1
#define N 111111
ll h[N],hh[N],k;
int n;
int pre[N],ss[N];
int sum[N<<];
int dp[N]; void pushup(int rt)//求区间最大值
{
sum[rt]=max(sum[rt<<],sum[rt<<|]);
} void update(int p,int y,int l,int r,int rt)//单点更新
{ if (l==r)
{
if (sum[rt]<y) sum[rt]=y;
return;
}
int m=(l+r)>>;
if (p<=m) update(p,y,lson);
else update(p,y,rson);
pushup(rt);
} //询问L,R区间最大值
int query(int L,int R,int l,int r,int rt)
{
if (R<L) return ;
if (L<=l&&R>=r) return sum[rt]; int m=(l+r)>>;
int ret=;
if (L<=m) ret=query(L,R,lson);
if (m<R) ret=max(ret,query(L,R,rson));
return ret;
} int main()
{
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++)
scanf("%I64d",&h[i]),hh[i]=h[i];
sort(h+,h+n+);
int len=;
for (int i=;i<=n;i++)
if (h[i]!=h[i-]) h[++len]=h[i];//排序处理 int ans=;
//整体说一下思路
//我们先排序出去重,把每个数据抽象变成一个点,然后维护。
//我们知道DP[I]=MAX(DP[J])+1,abs(h[i]-h[j])>=k;
//于是我们在前面找到h[i]-h[j]>=k中左右区间然后跟新,这应该是线段树+DP的共同点
//对H[J]-H[J]>=K同样处理。
for (int i=;i<=n;i++)
{
int l=lower_bound(h+,h+len+,hh[i]+k)-h;//这里的lower_bound与upper_bound不能弄错
int r=len;
int x=query(l,r,,len,);
r=upper_bound(h+,h+len+,hh[i]-k)-h;//求出左右区间,这里得多看看 x=max(x,query(,r-,,len,));
dp[i]=x+;
int y=lower_bound(h+,h+len+,hh[i])-h;
update(y,dp[i],,len,);
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
ll hp=1e17;
int inx=;//输出的处理
for (int i=n;i>=;i--)
{
if (ans==) break;
if (dp[i]==ans&&abs(hh[i]-hp)>=k)
{
hp=hh[i];
ans--;
ss[++inx]=i; }
}
for (int i=inx;i>=;i--) printf("%d ",ss[i]);
return ;
}

F:可以这么认为求出(L,R)区间的GCD,然后问(L,R)有多少个值=GCD();

线段树求GCD()不是难点,

求一段区间有多少值=GCD();要用到神奇处理

int x=upper_bound(a+1,a+n+1,mp(mi,r))-lower_bound(a+1,a+n+1,mp(mi,l));

这里用pair()容器,可以知道有多少个

 #include<bits/stdc++.h>

 #define lson l,m,rt<<1
#define rson m+1,r, rt<<1|1
#define N 111111 #define mp make_pair
using namespace std;
pair<int,int>a[N]; int s[N<<]; int gcd(int x,int y)
{
if (y==) return x;
if (x%y==) return y;
return gcd(y,x%y);
} void pushup(int rt)
{
s[rt]=gcd(s[rt<<],s[rt<<|]);
} void build(int l,int r,int rt)
{
if (l==r)
{
s[rt]=a[l].first;
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
pushup(rt);
} int query(int L,int R,int l,int r,int rt)
{
if (L<=l&&R>=r)
return s[rt];
int m=(l+r)>>;
int ret=;
if (L<=m) ret=gcd(ret,query(L,R,lson));
if (R>m) ret=gcd(ret,query(L,R,rson));
return ret;
} int main()
{
int n;
scanf("%d",&n);
for (int i=;i<=n;i++) scanf("%d",&a[i].first),a[i].second=i;
build(,n,);
sort(a+,a+n+); int Q;
scanf("%d",&Q);
while (Q--)
{
int l,r;
scanf("%d%d",&l,&r);
int mi=query(l,r,,n,);
int x=upper_bound(a+,a+n+,mp(mi,r))-lower_bound(a+,a+n+,mp(mi,l));
printf("%d\n",r-l+-x);
}
return ;
}
上一篇:Windows下使用图形化mount挂载磁盘到文件夹


下一篇:jq与原生js实现收起展开效果