[关闭]
@KirinBill 2017-10-27T22:57:52.000000Z 字数 4630 阅读 1053

2017.10.27 NOIP模拟赛

题解 套题

目录


Graph

qxjMu.png
qxQLd.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 <vector>
  30. using std::vector;
  31. const int MAXN=100005,MAXM=200005;
  32. int n,cnt;
  33. int he[MAXN],deg[MAXN],de[MAXN];
  34. bool vis[MAXN];
  35. vector<int> ans[MAXN];
  36. struct line{int to,nex;}ed[MAXM<<1];
  37. inline void addE(int u,int v){
  38. static int cnt;
  39. ed[++cnt]=(line){v,he[u]};
  40. he[u]=cnt;
  41. }
  42. void DFS(int u,int fa){
  43. vis[u]=true;
  44. for(int i=he[u],v;i;i=ed[i].nex){
  45. v=ed[i].to;
  46. if(v==fa) continue;
  47. if(!vis[v]){
  48. de[v]=de[u]+1;
  49. DFS(v,u);
  50. }
  51. else if(de[v]>de[u]){
  52. ++deg[u];
  53. ans[u].push_back(v);
  54. }
  55. }
  56. if(fa){
  57. if(deg[u]&1) ans[u].push_back(fa);
  58. else{
  59. ++deg[fa];
  60. ans[fa].push_back(u);
  61. }
  62. }
  63. }
  64. inline void solve(){
  65. for(int i=1;i<=n;++i){
  66. if(!vis[i]) DFS(i,0);
  67. }
  68. for(int i=1;i<=n;++i)
  69. cnt+=ans[i].size()>>1;
  70. }
  71. int main(){
  72. setIO("graph");
  73. int m;
  74. read(n),read(m);
  75. for(int i=1,u,v;i<=m;++i){
  76. read(u),read(v);
  77. addE(u,v),addE(v,u);
  78. }
  79. solve();
  80. write(cnt,'\n');
  81. for(int i=1;i<=n;++i){
  82. for(int j=0;j+1<ans[i].size();j+=2){
  83. write(ans[i][j],' ');
  84. write(i,' ');
  85. write(ans[i][j+1],'\n');
  86. }
  87. }
  88. return 0;
  89. }

Permutation

qxpFD.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <queue>
  5. #include <cstring>
  6. using std::min;
  7. using std::priority_queue;
  8. const int MAXN=500005;
  9. int n,k;
  10. int p[MAXN],id[MAXN];
  11. int he[MAXN],inD[MAXN];
  12. struct line{int to,nex;}ed[MAXN<<1];
  13. class segT{
  14. #define ls (u<<1)
  15. #define rs (ls|1)
  16. private:
  17. int minw[MAXN<<2];
  18. void upd(int u){
  19. minw[u]=min(minw[ls],minw[rs]);
  20. }
  21. void ist(int u,int l,int r,int pos,int x){
  22. if(l==r){
  23. minw[u]=min(minw[u],x);
  24. return;
  25. }
  26. int mid=l+r>>1;
  27. if(pos<=mid) ist(ls,l,mid,pos,x);
  28. else ist(rs,mid+1,r,pos,x);
  29. upd(u);
  30. }
  31. int qry(int u,int l,int r,int lp,int rp){
  32. if(lp<=l && r<=rp) return minw[u];
  33. int mid=l+r>>1,ret=INT_MAX;
  34. if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
  35. if(rp>mid) ret=min(ret,qry(rs,mid+1,r,lp,rp));
  36. return ret;
  37. }
  38. public:
  39. segT(){memset(minw,0x7f,sizeof(minw));}
  40. void ist(int pos,int x){ist(1,1,n,pos,x);}
  41. int qry(int lp,int rp){return qry(1,1,n,lp,rp);}
  42. #undef ls
  43. #undef rs
  44. }T;
  45. inline void addE(int u,int v){
  46. static int cnt;
  47. ed[++cnt]=(line){v,he[u]};
  48. he[u]=cnt;
  49. }
  50. inline void build(){
  51. for(int i=n,v;i;--i){
  52. v=T.qry(id[i]-k+1,id[i]);
  53. if(v<=n){
  54. addE(id[v],id[i]);
  55. ++inD[id[i]];
  56. }
  57. v=T.qry(id[i],id[i]+k-1);
  58. if(v<=n){
  59. addE(id[v],id[i]);
  60. ++inD[id[i]];
  61. }
  62. T.ist(id[i],i);
  63. }
  64. }
  65. inline void topo_sort(){
  66. static priority_queue<int> pq;
  67. for(int i=1;i<=n;++i){
  68. if(!inD[i]) pq.push(i);
  69. }
  70. for(int i=n,u;i;--i){
  71. u=id[i]=pq.top();
  72. pq.pop();
  73. for(int j=he[u],v;j;j=ed[j].nex){
  74. v=ed[j].to;
  75. if(--inD[v]==0) pq.push(v);
  76. }
  77. }
  78. }
  79. int main(){
  80. freopen("permutation.in","r",stdin);
  81. freopen("permutation.out","w",stdout);
  82. scanf("%d%d",&n,&k);
  83. for(int i=1;i<=n;++i)
  84. scanf("%d",&p[i]);
  85. for(int i=1;i<=n;++i)
  86. id[p[i]]=i;
  87. build();
  88. topo_sort();
  89. for(int i=1;i<=n;++i)
  90. p[id[i]]=i;
  91. for(int i=1;i<=n;++i)
  92. printf("%d\n",p[i]);
  93. return 0;
  94. }

Tree

qxbfa.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. int main(){
  30. setIO("tree");
  31. int n;
  32. read(n);
  33. long long ans=0;
  34. for(int i=1,w;i<n;++i){
  35. scanf("%*d%*d%d",&w);
  36. ans+=w;
  37. }
  38. write(ans);
  39. return 0;
  40. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注