2022.3.9
題單地址:https://codeforces.com/contest/1066

目錄

• A. Vova and Train【思維】
• B. Heaters【貪心】
• C. Books Queries【模擬鏈表】
• D. Boxes Packing【貪心】
• E. Binary Numbers AND Sum【思維 前綴和】

A. Vova and Train【思維】

#include<bits/stdc++.h> using namespace std; int main(void) {int t; cin>>t;while(t--){int L,v,l,r; cin>>L>>v>>l>>r;int cnt=L/v;int cnt1=r/v;int cnt2=(l-1)/v;cout<<max(0,cnt-(cnt1-cnt2))<<endl;}return 0; }

B. Heaters【貪心】

題目理解錯(cuò)了，導(dǎo)致一直wa。題目的意思是1的點(diǎn)可以點(diǎn)亮。點(diǎn)亮最少的1，覆蓋整個(gè)區(qū)間。
我一開始理解錯(cuò)了以為是1的點(diǎn)就是熱的，可以不用管，其實(shí)不然。
貪心思路: 盡可能的向右找1，右邊找不到，左邊找。都找不到則無解。

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],n,r; int main(void) {cin>>n>>r;for(int i=1;i<=n;i++) cin>>a[i];int cnt=0;for(int i=1;i<=n;i++){int pos=-1;for(int j=i;j<=i+r-1&&j<=n;j++) if(a[j]) pos=j;//右邊找if(pos!=-1){cnt++,i=pos+r-1;continue;}pos=-1;for(int j=max(1,i-r+1);j<=i;j++) if(a[j]) pos=j;//左邊找if(pos==-1) {puts("-1");return 0;}cnt++,i=pos+r-1;if(i>=n) break;}cout<<cnt;return 0; }

C. Books Queries【模擬鏈表】

#include<bits/stdc++.h> using namespace std; int n,l=0,r=1; map<int,int>mp; int main(void) {cin>>n;while(n--){char op;int id;cin>>op>>id;if(op=='L') mp[id]=l--;else if(op=='R') mp[id]=r++;else{int len1=mp[id]-(l+1);int len2=r-1-mp[id];cout<<min(len1,len2)<<endl;}}return 0; }

D. Boxes Packing【貪心】

題目的意思是說，我們要將最后的一次全部拿走。那么倒著來就行了。

#include<bits/stdc++.h> using namespace std; const int N=1e5*4+10; int a[N],n,m,k; int main(void) {cin>>n>>m>>k;for(int i=0;i<n;i++) scanf("%d",&a[i]);int sum=0,cnt=1,ans=0;for(int i=n-1;i>=0;i--){if(a[i]>k) break;if(sum+a[i]>k) {if(cnt<m){sum=a[i],cnt++,ans++;}else break;}else sum+=a[i],ans++;if(cnt>m) break;}cout<<ans;return 0; }

E. Binary Numbers AND Sum【思維 前綴和】

對(duì)于每一個(gè)1計(jì)算前面有多少個(gè)1。即只要計(jì)算貢獻(xiàn)就好了。

#include<bits/stdc++.h> using namespace std; typedef long long int LL; const int mod=998244353; const int N=1e5*3+10; int n,m,s[N]; string a,b; int main(void) {cin>>n>>m;cin>>a>>b;reverse(a.begin(),a.end());reverse(b.begin(),b.end());a="0"+a,b="0"+b;for(int i=m;i>=1;i--){s[i]=s[i+1];if(b[i]=='1') s[i]++;}LL sum=0;for(LL i=1,j=1;i<=n;i++,j=j*2%mod)if(a[i]=='1') sum=(sum+j*s[i])%mod;cout<<sum;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #515 (Div. 3)【未完结】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。