Codeforces Round #515 (Div. 3) （A+B+C+D+E+F）

A题 题目链接 （数学+签到）

题意：给定[1,L]大区间，给定整数v，给定小区间[l,r]，问大区间内多少个数是v的倍数且不属于小区间。询问T次，1<=T<=1e4。

思路：每次询问应该不能用O（n）的时间求，否则tle 。 对于区间[1,X] ，v的倍数的个数为 X/v . 所以对于区间[L,R],v的倍数的个数为 [1,R]的减去[1,L-1]的，即：R/V-(L-1)/V

//#pragma comment(linker, "/STACK:102400000,102400000")//手动扩栈 #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=0x3f3f3f3f; const double eps=1e-5; const int maxn=2e4+7; int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int T; cin>>T; while(T--) { int L,v,l,r; scanf("%d%d%d%d",&L,&v,&l,&r); int num1=L/v,num2=r/v-(l-1)/v; printf("%d\n",num1-num2); } // system("pause"); return 0; }

B题 题目链接 （贪心）

题意：给定由01组成的数组，每个1可以辐射的半径为r，问最少取多少个1，可以辐射完所有元素。不能辐射完输出-1

思路：由于每个位置都需要被1辐射到，我们根据贪心选取离它最远但可以辐射到的1即可。

//#pragma comment(linker, "/STACK:102400000,102400000")//???? #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=0x3f3f3f; const double eps=1e-5; const int maxn=1e3+7; int n,r; int a[maxn]; int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); scanf("%d%d",&n,&r); for(int i=1;i<=n;i++) scanf("%d",a+i); bool flag=0; int ans=0; for(int i=1;i<=n;i++)//n个位置 { flag=0;//找到那个离i最远，但可以辐射到i的1 for(int j=min(i+r-1,n);j>=1;j--)//j=min(i+r-1,n) 细节 { if(a[j]==1)//找到了 { ans++; flag=1; a[j]=-1; i=j+r-1;//i下一次进入循环会自己+1，所以是j+r-1而不是j+r break; } } if(!flag) { ans=-1; break; } } cout<<ans; // system("pause"); return 0; }

C 题 题目链接（map+思维）

题意：给出q个操作，每次输入字符和一个整数index，L表示从数组最左边插入整数index，R表示从数组最右边插入整数index，？表示询问最少要删去多少个数，才能使index位于最左边或最右边。 保证数组中不会出现两个相同的数。 （1<=q<=2e5）

思路：由于数组中的数是唯一的，我们可以用map给每个数编号。 具体编号方法如下：令第一个插入的数为0，然后左边从-1 -2…编号，右边从1 2…开始编号 。并用一个数组a存插入的这些整数。 比如：如果给出 8 L 1 R 2 R 3 ? 2 L 4 ? 1 L 5 ? 1 最终我们数组a存的就是： 5 4 1 2 3 对应的map编号就是： -2 -1 0 1 2 这样的话，每次询问.就可以用O（1）的时间解决了

//#pragma comment(linker, "/STACK:102400000,102400000")//手动扩栈 #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=0x3f3f3f3f; const double eps=1e-5; const int maxn=2e5+7; map<int,int> mp; int a[maxn<<1]; int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); int T; scanf("%d",&T); getchar(); char ch; int d; scanf("%c %d",&ch,&d); mp[d]=0; a[maxn]=d; T--; int l=0,r=0; while(T--) { getchar(); scanf("%c %d",&ch,&d); if(ch=='L') { mp[d]=--l; a[maxn+l]=d; } else if(ch=='R') { mp[d]=++r; a[maxn+r]=d; } else { int n=mp[d]; int L=mp[a[maxn+l]],R=mp[a[maxn+r]]; printf("%d\n",min(n-L,R-n)); } } // system("pause"); return 0; }

D题 题目链接 （签到）

题意：给定n个体积未必相同的物品，体积小于等于k，m个体积为k的盒子，你可以去掉最左边的几个箱子，保证把剩下的物品都按给定的算法装进盒子里，问最多可以装几个物品。 (2<=n<=2e5) 给定的算法为：1、选出一个空箱子，装入当前物品 2、判断下一个物品的体积是否小于等于当前箱子，若是，装入并重复第二步，否则重复第一步,物品选完则退出

思路：我真傻，老老实实按他的算法去模拟，枚举每次去掉左边几个物品。结果当然是tle。 正确的思路是直接倒着装，从右边开始判断能装多少个，因为箱子都是一样的，无论从哪开始都是一样的。

//#pragma comment(linker, "/STACK:102400000,102400000")//???? #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=0x3f3f3f; const double eps=1e-5; const int maxn=2e5+7; int n,m,k; int a[maxn]; int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",a+i); int left=k-a[n]; m--; int i=n-1; for(i=n-1;i>=1;i--) { if(left>=a[i]) { left-=a[i]; } else if(m>0) { m--; left=k-a[i]; } else break;//当前箱子装不下，并且没有空巷子了 } cout<<n-i; // system("pause"); return 0; }

E题 题目链接 （思维+前缀和）

题意：给定两个二进制数a b，长度分别为n，m。 求a&b + a&b<<1 + a&b<<2 + a&b<<3…+a&0 (1<=n,m<=2e5)

思路：我们观察到，表达式的过程相当于，a不动，求a&b，然后b整体右移1位，再求a&b ，那么对于a的第x位，b对应位以及高位的1都会贡献一次，也就是答案都会加2^x ，所以我们对b求前缀和。然后遍历a的每一位就可以了。

//#pragma comment(linker, "/STACK:102400000,102400000")//???? #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const int INF=998244353; const double eps=1e-5; const int maxn=2e5+7; int n,m; char a[maxn],b[maxn]; int sum[maxn];//对b求反向前缀和 int p[maxn];//2的i次方 void get_pow()//打表 { p[0]=1; for(int i=1;i<=n;i++) p[i]=p[i-1]*2%INF; } int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); scanf("%d%d",&n,&m); scanf("%s%s",a+1,b+1); get_pow(); int ans=0; for(int i=1;i<=m;i++) { sum[i]=sum[i-1]+b[i]-'0'; } for(int d=0;d<n;d++)//d表示枚举a的0~n-1位 0位在最右边 { if(a[n-d]=='1' && m-d>0)//注意加m-d>0 ,m可能很小 { ans=(1ll*ans+1ll*p[d]*sum[m-d])%INF; } } cout<<ans; // system("pause"); return 0; }

F题 题目链接 （贪心+dp）

题目大意：给你一个二维坐标系，之后给你n个点 ( x i , y i ) ，每个点的等级为 max ( x i , y i ) 。最初起点在(0,0)，想走到高一级的点，就要走完本等级所有的点，问最终走完所有点的最小移动距离（每一步只能向上下左右四个位置移动）。

思路：先把点按层排序，然后每层顺时针排序 。把问题简化成一个层次转移的dp问题。 在i i+1层转移过程中，最优解肯定是产生于第i层的最左、下端，第i+1层的最 左、下端这4个点直接的转移。

即：L1->R2->L2 、 L1->L2->R1 、 R1->L2->R2 、 R1->R2->L2 这四种走法。

所以dp的维数是二维，设dp[i][0]/dp[i][1] 表示转移到第i层，停在最左端、最下端的状态下的最优解。

dp[i][0]=min(dp[i-1][0]+dis(L1,R2),dp[i-1][1]+dis(R1,R2))+dis(R2,L2) //分别表示L1->R2->L2 、 R1->R2->L2 dp[i][1]=min(dp[i-1][0]+dis(L1,L2),dp[i-1][1]+dis(R1,L2))+dis(R2,L2) //分别表示L1->L2->R1 、 R1->L2->R2 、

到这里分析得差不多了，但其实写起来还挺麻烦的…具体看代码注释吧

//#pragma comment(linker, "/STACK:102400000,102400000")//???? #include<iostream> #include<algorithm> #include<cstdio> #include<stdlib.h> #include<string.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> #include<math.h> #include<set> #include<unordered_map> using namespace std; #define LL long long #define ULL unsigned long long const LL INF=1e18+7; const double eps=1e-5; const int maxn=2e5+7; struct point { int x,y; }p[maxn]; int n; LL dp[maxn][2];//停在i层 左边 下边 bool cmp(const point &a,const point &b) { int mmax1=max(a.x,a.y),mmax2=max(b.x,b.y); if(mmax1!=mmax2) return mmax1<mmax2; else { if(a.y!=b.y) return a.y>b.y;//上下 左右 else return a.x<b.x; } } LL dis(int a,int b) { return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y); } int main() { // ios::sync_with_stdio(false); // cin.tie(0); // cout.tie(0); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); dp[i][0]=dp[i][1]=INF;//初始化成1e18 保证不会wa } sort(p+1,p+n+1,cmp); int start=1;//本层的左上端 int index=1,right=0,left=0;//index表示下一层的左上端， //所以index-1表示这层的右下端 ， right表示上一层的最右下端 left表示上一层的最左上端 int i=1;//dp转移的层数 while(start<=n) { while(max(p[start].x,p[start].y)==max(p[index].x,p[index].y) && index<=n) index++; //此时index为下一层的左上端，index-1是第i层的右下端 LL d=dis(start,index-1);//走完当前层的路程 dp[i][0]=min(dp[i][0],d+dp[i-1][0]+dis(left,index-1)); dp[i][0]=min(dp[i][0],d+dp[i-1][1]+dis(right,index-1)); dp[i][1]=min(dp[i][1],d+dp[i-1][0]+dis(left,start)); dp[i][1]=min(dp[i][1],d+dp[i-1][1]+dis(right,start)); left=start,right=index-1; start=index;//start更新为i+1层的左上端 i++; } printf("%lld\n",min(dp[i-1][0],dp[i-1][1])); // system("pause"); return 0; }