首页 > 代码库 > (补题解）Codeforces Round #271 (Div. 2)
(补题解）Codeforces Round #271 (Div. 2)
前言：最近被线段树+简单递推DP虐的体无完肤！真是弱！
A:简单题，照着模拟就可以，题目还特意说不用处理边界
B：二分查找即可，用lower_lound()函数很好用
1 #include<string.h> 2 #include<math.h> 3 #include<algorithm> 4 #include<stdio.h> 5 #include<math.h> 6 #include<string> 7 #include<iostream> 8 using namespace std; 9 #define N 20000510 #define lson l, m, rt<<111 #define rson m+1, r, rt<<1|112 13 int a[N],s[N];14 int main()15 {16 int n;17 scanf("%d",&n);18 for (int i=1;i<=n;i++)19 scanf("%d",&a[i]);20 21 for (int i=1;i<=n;i++)22 a[i]+=a[i-1];23 int m;24 scanf("%d",&m);25 while (m--)26 {27 int x;28 scanf("%d",&x);29 int p=lower_bound(a+1,a+n+1,x)-a;30 printf("%d\n",p);31 }
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 操作，有很多询问，所以要一次做，然后之间求区间值即可！
1 #include<bits/stdc++.h> 2 typedef long long ll; 3 using namespace std; 4 5 #define mod 1000000007 6 #define N 100007 7 int a[N]; 8 ll s[N]; 9 10 11 int main()12 {13 int k,t;14 scanf("%d%d",&t,&k);15 a[0]=1;16 for (int i=1;i<N;i++)17 {18 if (i>=k) {a[i]=a[i-1]+a[i-k];a[i]%=mod;}19 else {a[i]=a[i-1];a[i]%=mod;}20 21 s[i]=s[i-1]+a[i];22 s[i]%=mod;23 }24 25 while (t--)26 {27 int x,y;28 scanf("%d%d",&x,&y);29 printf("%d\n",(s[y]-s[x-1]+mod)%mod);30 }31 32 return 0;
E：题目简短，二维可以写出，但会TLE。
然后看到一个神奇骗AC代码，可以看看
1 include<bits/stdc++.h> 2 #define N 111111 3 using namespace std; 4 typedef long long ll; 5 int n; 6 ll h[N],ans[N],next[N]; 7 ll d; 8 int main() 9 {10 cin>>n>>d;11 for (int i=1;i<=n;i++)12 {13 cin>>h[i];14 ans[i]=1;15 next[i]=-1;16 }17 int mx=1;18 int start=n;19 for (int i=n;i>=1;i--){20 for (int j=i+1;j<=min(i+300,n);j++)21 {22 if (abs(h[j]-h[i])>=d&&ans[j]+1>ans[i])23 {24 next[i]=j;25 ans[i]=ans[j]+1;26 }27 }28 29 30 if (ans[i]>mx)31 {32 mx=ans[i];33 start=i;34 }35 }36 37 cout<<mx<<endl;38 int i=start;39 while (i!=-1)40 {41 cout<<i<<" ";42 i=next[i];43 }44 45 return 0;46 }
它这里限制了第二重循环的次数，实际上可以第二重循环可以弄到300，或者更少，数据太弱吧！
正解：线段树单点跟新+二分！
分析写到代码里吧！
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define lson l, m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 #define N 111111 7 ll h[N],hh[N],k; 8 int n; 9 int pre[N],ss[N];10 int sum[N<<2];11 int dp[N];12 13 void pushup(int rt)//求区间最大值14 {15 sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);16 }17 18 19 void update(int p,int y,int l,int r,int rt)//单点更新20 {21 22 if (l==r)23 {24 if (sum[rt]<y) sum[rt]=y;25 return;26 }27 int m=(l+r)>>1;28 if (p<=m) update(p,y,lson);29 else update(p,y,rson);30 pushup(rt);31 }32 33 //询问L，R区间最大值34 int query(int L,int R,int l,int r,int rt)35 {36 if (R<L) return 0;37 if (L<=l&&R>=r) return sum[rt];38 39 int m=(l+r)>>1;40 int ret=0;41 if (L<=m) ret=query(L,R,lson);42 if (m<R) ret=max(ret,query(L,R,rson));43 return ret;44 }45 46 int main()47 {48 scanf("%d%d",&n,&k);49 for (int i=1;i<=n;i++)50 scanf("%I64d",&h[i]),hh[i]=h[i];51 sort(h+1,h+n+1);52 int len=0;53 for (int i=1;i<=n;i++)54 if (h[i]!=h[i-1]) h[++len]=h[i];//排序处理55 56 int ans=0;57 //整体说一下思路58 //我们先排序出去重，把每个数据抽象变成一个点，然后维护。59 //我们知道DP[I]=MAX(DP[J])+1,abs(h[i]-h[j])>=k;60 //于是我们在前面找到h[i]-h[j]>=k中左右区间然后跟新，这应该是线段树+DP的共同点61 //对H[J]-H[J]>=K同样处理。62 for (int i=1;i<=n;i++)63 {64 int l=lower_bound(h+1,h+len+1,hh[i]+k)-h;//这里的lower_bound与upper_bound不能弄错65 int r=len;66 int x=query(l,r,1,len,1);67 r=upper_bound(h+1,h+len+1,hh[i]-k)-h;//求出左右区间，这里得多看看68 69 x=max(x,query(1,r-1,1,len,1));70 dp[i]=x+1;71 int y=lower_bound(h+1,h+len+1,hh[i])-h;72 update(y,dp[i],1,len,1);73 ans=max(ans,dp[i]);74 }75 printf("%d\n",ans);76 ll hp=1e17;77 int inx=0;//输出的处理78 for (int i=n;i>=1;i--)79 {80 if (ans==0) break;81 if (dp[i]==ans&&abs(hh[i]-hp)>=k)82 {83 hp=hh[i];84 ans--;85 ss[++inx]=i;86 87 }88 }89 for (int i=inx;i>=1;i--) printf("%d ",ss[i]);90 return 0;91 }
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()容器，可以知道有多少个
1 #include<bits/stdc++.h> 2 3 #define lson l,m,rt<<1 4 #define rson m+1,r, rt<<1|1 5 #define N 111111 6 7 #define mp make_pair 8 using namespace std; 9 pair<int,int>a[N];10 11 int s[N<<2];12 13 int gcd(int x,int y)14 {15 if (y==0) return x;16 if (x%y==0) return y;17 return gcd(y,x%y);18 }19 20 void pushup(int rt)21 {22 s[rt]=gcd(s[rt<<1],s[rt<<1|1]);23 }24 25 void build(int l,int r,int rt)26 {27 if (l==r)28 {29 s[rt]=a[l].first;30 return;31 }32 int m=(l+r)>>1;33 build(lson);34 build(rson);35 pushup(rt);36 }37 38 int query(int L,int R,int l,int r,int rt)39 {40 if (L<=l&&R>=r)41 return s[rt];42 int m=(l+r)>>1;43 int ret=0;44 if (L<=m) ret=gcd(ret,query(L,R,lson));45 if (R>m) ret=gcd(ret,query(L,R,rson));46 return ret;47 }48 49 int main()50 {51 int n;52 scanf("%d",&n);53 for (int i=1;i<=n;i++) scanf("%d",&a[i].first),a[i].second=i;54 build(1,n,1);55 sort(a+1,a+n+1);56 57 int Q;58 scanf("%d",&Q);59 while (Q--)60 {61 int l,r;62 scanf("%d%d",&l,&r);63 int mi=query(l,r,1,n,1);64 int x=upper_bound(a+1,a+n+1,mp(mi,r))-lower_bound(a+1,a+n+1,mp(mi,l));65 printf("%d\n",r-l+1-x);66 }67 return 0;68 }
(补题解）Codeforces Round #271 (Div. 2)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。