2021CCPC网络赛(重赛)——1005.E.Monopoly
2021/10/10 23:49:38
本文主要是介绍2021CCPC网络赛(重赛)——1005.E.Monopoly,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> #define ll long long #define fir first #define sec second #define PB push_back #define ALL(a) begin(a),end(a) #define mem(a,n) memset(a,n,sizeof(a)) #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int maxn = 2e5+5; ll n, m, rd, x; ll a[maxn], pre[maxn]; map<ll,int> vs; map<ll,vector<pair<ll,int>>> shu; void solve() { cin>>n>>m; bool flag = 0; rd = 0; for(int i=1;i<=n;i++) { cin>>a[i]; pre[i] = pre[i-1] + a[i]; rd += a[i]; } if(rd < 0) { rd = -rd; flag = 1; for(int i=1;i<=n;i++) pre[i] = -pre[i]; } // if(rd == 0) { vs.clear(); for(int i=1;i<=n;i++) { if(vs.find(pre[i])==vs.end()) vs[pre[i]] = i; } while(m--) { cin>>x; if(x==0) { cout<<0<<endl; continue; } if(vs.find(x)==vs.end()) cout<<-1<<endl; else cout<<vs[x]<<endl; } return ; } // shu.clear(); for(int i=1;i<=n;i++) { ll yus = (pre[i] % rd + rd) % rd; shu[yus].PB({-pre[i],i}); } for(auto it=shu.begin(); it!=shu.end(); it++) sort(it->second.begin(), it->second.end()); while(m--) { cin>>x; if(flag) x = -x; if(x==0) { cout<<0<<endl; continue; } ll xx = (x % rd + rd) % rd; if(shu.find(xx)==shu.end()) { cout<<-1<<endl; continue; } pair<ll,int> ask = {-x, 0}; int pos = lower_bound(ALL(shu[xx]), ask) - shu[xx].begin(); if(pos == shu[xx].size()) { cout<<-1<<endl; } else { ll ans = shu[xx][pos].sec; ans += (x + shu[xx][pos].fir) / rd * n; cout<<ans<<endl; } } } int main() { IOS; int _;cin>>_;while(_--) solve();return 0; }
这篇关于2021CCPC网络赛(重赛)——1005.E.Monopoly的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级