[关闭]
@KirinBill 2017-10-09T15:10:42.000000Z 字数 4784 阅读 1149

2017.9.4 NOIP模拟赛

题解 套题

不要急,慢慢来。

目录


命令序列

AFM9F.png

思路

代码

  1. #include <cstdio>
  2. #include <utility>
  3. #define x first
  4. #define y second
  5. using std::pair;
  6. typedef pair<int,int> position;
  7. const int MAXN=4e5+5;
  8. int n;
  9. char cmd[MAXN];
  10. namespace solve1
  11. {
  12. inline int operate(int l){
  13. position pos(0,0);
  14. int ret=0;
  15. for(;l<=n;++l){
  16. switch(cmd[l]){
  17. case 'U': ++pos.y; break;
  18. case 'D': --pos.y; break;
  19. case 'L': --pos.x; break;
  20. case 'R': ++pos.x; break;
  21. }
  22. if(pos.x==0 && pos.y==0) ++ret;
  23. }
  24. return ret;
  25. }
  26. inline int solve(){
  27. int ret=0;
  28. for(int i=1;i<=n;++i)
  29. ret+=operate(i);
  30. return ret;
  31. }
  32. }
  33. namespace solve2
  34. {
  35. int arr[MAXN<<1];
  36. inline long long solve(){
  37. long long ret=0;
  38. int *sum=&arr[n+1];
  39. sum[0]=1;
  40. for(int i=1,tmp=0;i<=n;++i){
  41. cmd[i]=='L' ? --tmp:++tmp;
  42. ret+=sum[tmp];
  43. ++sum[tmp];
  44. }
  45. return ret;
  46. }
  47. }
  48. int main(){
  49. freopen("command.in","r",stdin);
  50. freopen("command.out","w",stdout);
  51. scanf("%d%s",&n,cmd+1);
  52. if(n<=4000) printf("%d",solve1::solve());
  53. else printf("%lld",solve2::solve());
  54. return 0;
  55. }

找位置

AFWwr.png
AFvJ1.png

思路

代码

  1. #include <cstdio>
  2. #include <vector>
  3. using std::vector;
  4. const int MAXN=1e5+5;
  5. int n,q,tot,idx;
  6. int he[MAXN],up_pos[MAXN],dwn_pos[MAXN],pos[MAXN][2];
  7. bool vis[MAXN];
  8. vector<int> cir[MAXN];
  9. struct line{int to,nex;}ed[MAXN<<1];
  10. inline void addE(int u,int v){
  11. static int cnt=0;
  12. ed[++cnt]=(line){v,he[u]};
  13. he[u]=cnt;
  14. }
  15. inline void build(){
  16. for(int i=1;i<=n;++i)
  17. addE(dwn_pos[i],up_pos[i]);
  18. }
  19. void find_cir(int u){
  20. cir[tot].push_back(u);
  21. pos[u][0]=tot,pos[u][1]=++idx;
  22. vis[u]=true;
  23. for(int i=he[u],v;i;i=ed[i].nex){
  24. v=ed[i].to;
  25. if(!vis[v]) find_cir(v);
  26. }
  27. }
  28. int main(){
  29. freopen("position.in","r",stdin);
  30. freopen("position.out","w",stdout);
  31. scanf("%d%d",&n,&q);
  32. for(int i=1,u,d;i<=n;++i){
  33. scanf("%d%d",&u,&d);
  34. up_pos[u]=i;
  35. dwn_pos[d]=i;
  36. }
  37. build();
  38. for(int i=1;i<=n;++i){
  39. if(!vis[i]){
  40. ++tot,idx=0;
  41. find_cir(i);
  42. }
  43. }
  44. for(int i=1,k,s;i<=q;++i){
  45. scanf("%d%d",&k,&s);
  46. printf("%d\n",cir[pos[k][0]][(pos[k][1]+s-1)%cir[pos[k][0]].size()]);
  47. }
  48. return 0;
  49. }

摧毁道路

AFAht.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <queue>
  4. #include <cstring>
  5. using std::max;
  6. using std::queue;
  7. const int MAXN=3005;
  8. int n,m,s1,t1,l1,s2,t2,l2;
  9. int he[MAXN],G[MAXN][MAXN];
  10. struct line{int to,nex;}ed[MAXN<<1];
  11. inline void addE(int u,int v){
  12. static int cnt=0;
  13. ed[++cnt]=(line){v,he[u]};
  14. he[u]=cnt;
  15. }
  16. inline void BFS(int s){
  17. static bool vis[MAXN];
  18. static queue<int> que;
  19. memset(vis,false,sizeof(vis));
  20. que.push(s);
  21. vis[s]=true;
  22. int u;
  23. int *dis=G[s];
  24. while(que.size()){
  25. u=que.front();
  26. que.pop();
  27. for(int i=he[u],v;i;i=ed[i].nex){
  28. v=ed[i].to;
  29. if(!vis[v]){
  30. dis[v]=dis[u]+1;
  31. que.push(v);
  32. vis[v]=true;
  33. }
  34. }
  35. }
  36. }
  37. inline void cal_APSP(){
  38. memset(G,30,sizeof(G));
  39. for(int i=1;i<=n;++i){
  40. G[i][i]=0;
  41. BFS(i);
  42. }
  43. }
  44. inline int solve(){
  45. if(G[s1][t1]>l1 || G[s2][t2]>l2) return -1;
  46. int ret=m-G[s1][t1]-G[s2][t2];
  47. for(int i=1;i<=n;++i){
  48. for(int j=1;j<=n;++j){
  49. if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][i]+G[i][j]+G[j][t2]<=l2)
  50. ret=max(ret,m-G[s1][i]-G[s2][i]-G[i][j]-G[j][t1]-G[j][t2]);
  51. if(G[s1][i]+G[i][j]+G[j][t1]<=l1 && G[s2][j]+G[j][i]+G[i][t2]<=l2)
  52. ret=max(ret,m-G[s1][i]-G[s2][j]-G[i][j]-G[j][t1]-G[i][t2]);
  53. }
  54. }
  55. return ret;
  56. }
  57. int main(){
  58. freopen("destroy.in","r",stdin);
  59. freopen("destroy.out","w",stdout);
  60. scanf("%d%d",&n,&m);
  61. for(int i=1,u,v;i<=m;++i){
  62. scanf("%d%d",&u,&v);
  63. addE(u,v),addE(v,u);
  64. }
  65. scanf("%d%d%d",&s1,&t1,&l1);
  66. scanf("%d%d%d",&s2,&t2,&l2);
  67. cal_APSP();
  68. printf("%d",solve());
  69. return 0;
  70. }

L君找工作

AFqAJ.png
AF7B0.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. using std::sort;
  4. const int MAXN=200005;
  5. int n,m;
  6. struct day{
  7. int t,id;
  8. friend bool operator< (const day &a,const day &b){
  9. return a.t<b.t;
  10. }
  11. }d[MAXN];
  12. struct work{
  13. int d,r,time,id;
  14. static bool cmp_d(const work &a,const work &b){return a.d<b.d;}
  15. static bool cmp_id(const work &a,const work &b){return a.id<b.id;}
  16. }wk[MAXN];
  17. template<typename type>
  18. class BIT{
  19. private:
  20. type c[MAXN];
  21. int lowbit(int x){return x&-x;}
  22. public:
  23. void add(int l,type val){
  24. for(;l<=m;l+=lowbit(l))
  25. c[l]+=val;
  26. }
  27. type qry(int r){
  28. type ret=0;
  29. for(;r;r-=lowbit(r))
  30. ret+=c[r];
  31. return ret;
  32. }
  33. };
  34. BIT<int> cnt;
  35. BIT<long long> ta;
  36. inline void cal_time(work &now,int id){
  37. static int cur=1;
  38. for(;d[cur].t<=now.d && cur<=m;++cur){
  39. ta.add(d[cur].id,-d[cur].t);
  40. cnt.add(d[cur].id,-1);
  41. }
  42. long long sum=ta.qry(m)-(long long)now.d*cnt.qry(m);
  43. if(now.r>sum){
  44. now.time=0;
  45. return;
  46. }
  47. int l=1,r=m,mid;
  48. while(l<=r){
  49. mid=l+r>>1;
  50. if(now.r<=ta.qry(mid)-(long long)now.d*cnt.qry(mid))
  51. r=mid-1;
  52. else l=mid+1;
  53. }
  54. now.time=l;
  55. }
  56. int main(){
  57. freopen("work.in","r",stdin);
  58. freopen("work.out","w",stdout);
  59. scanf("%d%d",&n,&m);
  60. for(int i=1;i<=m;++i){
  61. scanf("%d",&d[i].t);
  62. ta.add(i,d[i].t);
  63. cnt.add(i,1);
  64. d[i].id=i;
  65. }
  66. sort(d+1,d+m+1);
  67. for(int i=1;i<=n;++i){
  68. scanf("%d%d",&wk[i].d,&wk[i].r);
  69. wk[i].id=i;
  70. }
  71. sort(wk+1,wk+n+1,work::cmp_d);
  72. for(int i=1;i<=n;++i)
  73. cal_time(wk[i],i);
  74. sort(wk+1,wk+n+1,work::cmp_id);
  75. for(int i=1;i<=n;++i)
  76. printf("%d ",wk[i].time);
  77. return 0;
  78. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注