[关闭]
@KirinBill 2017-10-30T10:14:34.000000Z 字数 6087 阅读 519

2017.10.30 NOIP模拟赛

题解 套题

目录


赛跑

7eLir.png
7exQt.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. using std::__gcd;
  31. int a,b,c,d;
  32. void exgcd(int a,long long &x,int b,long long &y){
  33. if(b==0){
  34. x=1,y=0;
  35. return;
  36. }
  37. exgcd(b,y,a%b,x);
  38. y-=a/b*x;
  39. }
  40. inline long long solve(){
  41. int gcd=__gcd(a,c);
  42. if((d-b)%gcd!=0) return -1;
  43. long long i,j;
  44. exgcd(a,i,c,j);
  45. i*=(d-b)/gcd;
  46. int tmp=c/gcd;
  47. i=(i%tmp+tmp)%tmp;
  48. return b+a*i;
  49. }
  50. int main(){
  51. setIO("run");
  52. read(a),read(b);
  53. read(c),read(d);
  54. write(solve());
  55. return 0;
  56. }

暗中观察

7esx0.png
7eTzF.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. using std::sort;
  31. using std::unique;
  32. using std::lower_bound;
  33. const int MAXN=50005;
  34. int n,tot;
  35. int x[MAXN],y[MAXN],d[MAXN];
  36. struct people{
  37. int y,lp,rp;
  38. long long l,r;
  39. static bool cmp_y(const people &a,const people &b){return a.y<b.y;}
  40. }p[MAXN];
  41. class segT{
  42. #define ls (u<<1)
  43. #define rs (ls|1)
  44. private:
  45. bool cov[MAXN<<2],tag[MAXN<<2];
  46. void upd(int u){cov[u]=cov[ls]&cov[rs];}
  47. void add_tag(int u){cov[u]=tag[u]=true;}
  48. void push_d(int u){
  49. if(!tag[u]) return;
  50. add_tag(ls),add_tag(rs);
  51. tag[u]=false;
  52. }
  53. void ist(int u,int l,int r,int lp,int rp){
  54. if(lp<=l && r<=rp){
  55. add_tag(u);
  56. return;
  57. }
  58. push_d(u);
  59. int mid=l+r>>1;
  60. if(lp<=mid) ist(ls,l,mid,lp,rp);
  61. if(rp>mid) ist(rs,mid+1,r,lp,rp);
  62. upd(u);
  63. }
  64. bool qry(int u,int l,int r,int lp,int rp){
  65. if(lp<=l && r<=rp) return cov[u];
  66. push_d(u);
  67. int mid=l+r>>1;
  68. bool ret=true;
  69. if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
  70. if(rp>mid) ret&=qry(rs,mid+1,r,lp,rp);
  71. return ret;
  72. }
  73. public:
  74. void ist(int lp,int rp){ist(1,1,tot,lp,rp);}
  75. bool qry(int lp,int rp){return qry(1,1,tot,lp,rp);}
  76. #undef ls
  77. #undef rs
  78. }T;
  79. inline void deal(){
  80. for(int i=1;i<=n;++i){
  81. p[i].l=(long long)d[i]*(0-x[i]-1);
  82. p[i].r=(long long)d[i]*(0-x[i]);
  83. p[i].y=y[i];
  84. }
  85. }
  86. inline void decrete(){
  87. static long long tmp[MAXN<<1];
  88. for(int i=1;i<=n;++i){
  89. tmp[++tot]=p[i].l;
  90. tmp[++tot]=p[i].r;
  91. }
  92. sort(tmp+1,tmp+tot+1);
  93. tot=unique(tmp+1,tmp+tot+1)-tmp-1;
  94. for(int i=1;i<=n;++i){
  95. p[i].lp=lower_bound(tmp+1,tmp+tot+1,p[i].l)-tmp;
  96. p[i].rp=lower_bound(tmp+1,tmp+tot+1,p[i].r)-tmp;
  97. }
  98. }
  99. inline int solve(){
  100. sort(p+1,p+n+1,people::cmp_y);
  101. int ret=0;
  102. for(int i=1;i<=n;++i){
  103. if(!T.qry(p[i].lp,p[i].rp)) ++ret;
  104. T.ist(p[i].lp,p[i].rp);
  105. }
  106. return ret;
  107. }
  108. int main(){
  109. setIO("watch");
  110. read(n);
  111. for(int i=1;i<=n;++i)
  112. read(x[i]),read(y[i]),read(d[i]);
  113. deal();
  114. decrete();
  115. write(solve());
  116. return 0;
  117. }

占领

7eUqJ.png
7eDt1.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. #include <vector>
  31. using std::max;
  32. using std::swap;
  33. using std::vector;
  34. const int MAXN=100005,MAXM=MAXN;
  35. int n,m;
  36. vector<int> vec[MAXN];
  37. struct chain{int val,u,v;}ln[MAXM];
  38. class BIT{
  39. private:
  40. int c[MAXN];
  41. int lowbit(int x){return x&-x;}
  42. int qry(int r){
  43. int ret=0;
  44. for(;r;r-=lowbit(r))
  45. ret+=c[r];
  46. return ret;
  47. }
  48. public:
  49. void add(int l,int x){
  50. for(;l<=n;l+=lowbit(l))
  51. c[l]+=x;
  52. }
  53. int qry(int l,int r){return qry(r)-qry(l-1);}
  54. };
  55. class TP{
  56. private:
  57. int dp[MAXN];
  58. struct node{int lp,rp,de,top,hson,he,sz,fa;}d[MAXN];
  59. struct line{int to,nex;}ed[MAXN<<1];
  60. BIT ta;
  61. void DFS(int u){
  62. d[u].sz=1;
  63. int fa=d[u].fa;
  64. d[u].de=d[fa].de+1;
  65. for(int i=d[u].he,v,&hson=d[u].hson;i;i=ed[i].nex){
  66. v=ed[i].to;
  67. if(v!=fa){
  68. d[v].fa=u;
  69. DFS(v);
  70. if(d[hson].sz<d[v].sz) hson=v;
  71. d[u].sz+=d[v].sz;
  72. }
  73. }
  74. }
  75. void link(int u){
  76. static int cnt;
  77. d[u].lp=d[u].rp=++cnt;
  78. int fa=d[u].fa;
  79. d[u].top= d[fa].hson==u ? d[fa].top:u;
  80. int hson=d[u].hson;
  81. if(hson) link(hson);
  82. for(int i=d[u].he,v;i;i=ed[i].nex){
  83. v=ed[i].to;
  84. if(v!=fa && v!=hson) link(v);
  85. }
  86. d[u].rp=cnt;
  87. }
  88. int qry(int u,int v){
  89. int ret=0;
  90. int *now;
  91. while(d[u].top!=d[v].top){
  92. now= d[d[u].top].de>d[d[v].top].de ? &u:&v;
  93. ret+=ta.qry(d[d[*now].top].lp,d[*now].lp);
  94. *now=d[d[*now].top].fa;
  95. }
  96. if(d[u].de>d[v].de) swap(u,v);
  97. ret+=ta.qry(d[u].lp,d[v].lp);
  98. return ret;
  99. }
  100. void add(int u,int x){ta.add(d[u].lp,x);}
  101. void treeDP(int u,int fa){
  102. int tmp=0;
  103. for(int i=d[u].he,v;i;i=ed[i].nex){
  104. v=ed[i].to;
  105. if(v!=fa){
  106. treeDP(v,u);
  107. tmp+=dp[v];
  108. }
  109. }
  110. dp[u]=tmp;
  111. for(int i=0,j,lim=vec[u].size();i<lim;++i){
  112. j=vec[u][i];
  113. dp[u]=max(dp[u],qry(ln[j].u,ln[j].v)+tmp+ln[j].val);
  114. }
  115. add(u,tmp-dp[u]);
  116. }
  117. public:
  118. void addE(int u,int v){
  119. static int cnt;
  120. ed[++cnt]=(line){v,d[u].he};
  121. d[u].he=cnt;
  122. }
  123. void build(){DFS(1),link(1);}
  124. int LCA(int u,int v){
  125. int *now;
  126. while(d[u].top!=d[v].top){
  127. now= d[d[u].top].de>d[d[v].top].de ? &u:&v;
  128. *now=d[d[*now].top].fa;
  129. }
  130. return d[u].de<d[v].de ? u:v;
  131. }
  132. int treeDP(){
  133. treeDP(1,0);
  134. return dp[1];
  135. }
  136. }T;
  137. int main(){
  138. setIO("occupy");
  139. read(n),read(m);
  140. for(int i=1,u,v;i<n;++i){
  141. read(u),read(v);
  142. T.addE(u,v),T.addE(v,u);
  143. }
  144. T.build();
  145. for(int i=1;i<=m;++i){
  146. read(ln[i].u),read(ln[i].v),read(ln[i].val);
  147. vec[T.LCA(ln[i].u,ln[i].v)].push_back(i);
  148. }
  149. write(T.treeDP());
  150. return 0;
  151. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注