[关闭]
@KirinBill 2017-10-07T14:03:33.000000Z 字数 6258 阅读 598

2017.10.7 NOIP模拟赛

题解 套题

目录


流光溢彩

AHYfW.png

思路

代码

  1. #include <cstdio>
  2. #include <map>
  3. using std::map;
  4. const int MAXN=1e6+5;
  5. int n,a,b;
  6. int suma[MAXN],sumb[MAXN];
  7. char s[MAXN];
  8. map<int,int> mp;
  9. inline int pow(int x,int y,int p){
  10. int ret=1;
  11. for(;y;y>>=1,x=(long long)x*x%p){
  12. if(y&1) ret=(long long)ret*x%p;
  13. }
  14. return ret;
  15. }
  16. inline void deal(){
  17. for(int i=1;i<=n;++i)
  18. suma[i]=((long long)suma[i-1]*10%a+(s[i]^'0'))%a;
  19. for(int i=n;i;--i)
  20. sumb[i]=((long long)(s[i]^'0')*pow(10,n-i,b)%b+sumb[i+1])%b;
  21. }
  22. int main(){
  23. scanf("%d%d%d",&n,&a,&b);
  24. scanf("%s",s+1);
  25. deal();
  26. for(int i=1;i<=n;++i){
  27. printf("%d\n",mp[sumb[i+1]]);
  28. if(suma[i]==0) ++mp[sumb[i+1]];
  29. }
  30. return 0;
  31. }

世代相传

AHoFR.png

思路

代码

  1. #include <cstdio>
  2. #include <queue>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <climits>
  6. using std::queue;
  7. using std::min;
  8. using std::__gcd;
  9. const int MAXN=2005;
  10. int n,s,t;
  11. int he[MAXN],iter[MAXN],dis[MAXN];
  12. unsigned a[MAXN];
  13. struct line{int to,nex,cap;}ed[MAXN*MAXN];
  14. inline void addE(int u,int v,int cap){
  15. static int cnt=1;
  16. ed[++cnt]=(line){v,he[u],cap};
  17. he[u]=cnt;
  18. }
  19. inline int revE(int i){return i^1;}
  20. int aug(int u,int rest){
  21. if(u==t || !rest) return rest;
  22. int ret=0;
  23. for(int &i=iter[u],v,cap,flow;i;i=ed[i].nex){
  24. v=ed[i].to,cap=ed[i].cap;
  25. if(dis[v]!=dis[u]+1 || !cap) continue;
  26. flow=aug(v,min(rest,cap));
  27. ed[i].cap-=flow,ed[revE(i)].cap+=flow;
  28. rest-=flow,ret+=flow;
  29. if(!rest) return ret;
  30. }
  31. if(!ret) dis[u]=-1;
  32. return ret;
  33. }
  34. inline bool BFS(){
  35. static queue<int> que;
  36. memset(dis,-1,sizeof(dis));
  37. dis[s]=0;
  38. que.push(s);
  39. int u;
  40. while(que.size()){
  41. u=que.front();
  42. que.pop();
  43. for(int i=he[u],v;i;i=ed[i].nex){
  44. if(!ed[i].cap) continue;
  45. v=ed[i].to;
  46. if(dis[v]==-1){
  47. dis[v]=dis[u]+1;
  48. que.push(v);
  49. }
  50. }
  51. }
  52. return dis[t]!=-1;
  53. }
  54. inline int Dinic(){
  55. int ret=0;
  56. while(BFS()){
  57. memcpy(iter,he,sizeof(iter));
  58. ret+=aug(s,INT_MAX);
  59. }
  60. return ret;
  61. }
  62. inline void build(){
  63. static int odd[MAXN],even[MAXN];
  64. s=n+1,t=n+2;
  65. for(int i=1;i<=n;++i){
  66. if(a[i]&1) odd[++odd[0]]=i;
  67. else even[++even[0]]=i;
  68. }
  69. for(int i=1;i<=odd[0];++i){
  70. for(int j=1;j<=even[0];++j){
  71. if(__gcd(a[odd[i]],a[even[j]])==1 && __gcd(a[odd[i]]+1,a[even[j]]+1)==1)
  72. addE(odd[i],even[j],INT_MAX),addE(even[j],odd[i],0);
  73. }
  74. }
  75. for(int i=1;i<=odd[0];++i)
  76. addE(s,odd[i],1),addE(odd[i],s,0);
  77. for(int i=1;i<=even[0];++i)
  78. addE(even[i],t,1),addE(t,even[i],0);
  79. }
  80. int main(){
  81. scanf("%d",&n);
  82. for(int i=1;i<=n;++i)
  83. scanf("%d",&a[i]);
  84. build();
  85. printf("%d",n-Dinic());
  86. return 0;
  87. }

继往开来

AHdMw.png
AHELL.png

思路

代码

  1. #include <cstdio>
  2. #include <stack>
  3. #include <cstring>
  4. #include <algorithm>
  5. using std::stack;
  6. using std::min;
  7. const int MAXN=1005,MAXSZ=30,MAXV=MAXSZ<<2,MAXE=MAXV*MAXV;
  8. int n,Ecnt,cnt,tot,idx;
  9. int he[MAXV];
  10. int dfn[MAXV],low[MAXV],scc[MAXV];
  11. int idA[MAXSZ][2],idB[MAXSZ][2];
  12. int cdt[MAXN][2],pers[MAXN],ans[MAXN];
  13. bool away[MAXSZ];
  14. struct line{int to,nex;}ed[MAXE];
  15. inline void addE(int u,int v){
  16. ed[++Ecnt]=(line){v,he[u]};
  17. he[u]=Ecnt;
  18. }
  19. void Tarjan_SCC(int u){
  20. static int low[MAXV];
  21. static bool inS[MAXV];
  22. static stack<int> stk;
  23. dfn[u]=low[u]=++idx;
  24. stk.push(u);
  25. inS[u]=true;
  26. for(int i=he[u],v;i;i=ed[i].nex){
  27. v=ed[i].to;
  28. if(!dfn[v]){
  29. Tarjan_SCC(v);
  30. low[u]=min(low[u],low[v]);
  31. }
  32. else if(inS[v]) low[u]=min(low[u],dfn[v]);
  33. }
  34. if(dfn[u]==low[u]){
  35. ++tot;
  36. int now;
  37. do{
  38. now=stk.top();
  39. stk.pop();
  40. inS[now]=false;
  41. scc[now]=tot;
  42. }while(now!=u);
  43. }
  44. }
  45. inline void mge_node(){
  46. idx=tot=0;
  47. memset(dfn,0,sizeof(dfn));
  48. for(int i=1;i<=cnt;++i){
  49. if(!dfn[i]) Tarjan_SCC(i);
  50. }
  51. }
  52. inline void build(){
  53. Ecnt=0;
  54. memset(he,0,sizeof(he));
  55. for(int i=0;i<26;++i){
  56. //i in A or B is both true and false
  57. if(away[i]){
  58. addE(idA[i][1],idA[i][0]);
  59. addE(idB[i][1],idB[i][0]);
  60. }
  61. //i in A and i in B are different
  62. else{
  63. addE(idA[i][1],idB[i][0]);
  64. addE(idA[i][0],idB[i][1]);
  65. addE(idB[i][0],idA[i][1]);
  66. addE(idB[i][1],idA[i][0]);
  67. }
  68. }
  69. for(int i=1;i<=n;++i){
  70. //i is in A or B or C(the set which the pokers we took out are in)
  71. if(ans[i]==0){
  72. for(int j=0;j<=1;++j){
  73. //cannot in A
  74. if(pers[i]==1) addE(idA[cdt[i][j]][1],idA[cdt[i][j]][0]);
  75. //cannot in B
  76. else addE(idB[cdt[i][j]][1],idB[cdt[i][j]][0]);
  77. }
  78. }
  79. //can know where i is,so <=> in C
  80. else if(ans[i]==2){
  81. for(int j=0;j<=1;++j){
  82. if(pers[i]==1){
  83. addE(idA[cdt[i][j]][0],idA[cdt[i][j]][1]);
  84. addE(idB[cdt[i][j]][1],idB[cdt[i][j]][0]);
  85. }
  86. else{
  87. addE(idB[cdt[i][j]][0],idB[cdt[i][j]][1]);
  88. addE(idA[cdt[i][j]][1],idA[cdt[i][j]][0]);
  89. }
  90. }
  91. }
  92. //cannot know
  93. else{
  94. for(int j=0;j<=1;++j){
  95. if(pers[i]==1){
  96. addE(idA[cdt[i][j]][0],idA[cdt[i][j^1]][1]);
  97. addE(idA[cdt[i][j]][1],idA[cdt[i][j^1]][0]);
  98. addE(idA[cdt[i][j]][0],idB[cdt[i][j^1]][0]);
  99. addE(idB[cdt[i][j]][1],idA[cdt[i][j^1]][1]);
  100. }
  101. else{
  102. addE(idB[cdt[i][j]][0],idB[cdt[i][j^1]][1]);
  103. addE(idB[cdt[i][j]][1],idB[cdt[i][j^1]][0]);
  104. addE(idB[cdt[i][j]][0],idA[cdt[i][j^1]][0]);
  105. addE(idA[cdt[i][j]][1],idB[cdt[i][j^1]][1]);
  106. }
  107. }
  108. }
  109. }
  110. }
  111. inline bool jud(){
  112. for(int i=0;i<26;++i){
  113. if(scc[idA[i][0]]==scc[idA[i][1]])
  114. return false;
  115. else if(scc[idB[i][0]]==scc[idB[i][1]])
  116. return false;
  117. }
  118. return true;
  119. }
  120. inline bool two_SAT(){
  121. build();
  122. mge_node();
  123. return jud();
  124. }
  125. inline int solve(){
  126. int ret=0;
  127. //pockers that are taken away
  128. for(int i=0;i<26;++i){
  129. away[i]=true;
  130. for(int j=i+1;j<26;++j){
  131. away[j]=true;
  132. for(int k=j+1;k<26;++k){
  133. away[k]=true;
  134. ret+=two_SAT();
  135. away[k]=false;
  136. }
  137. away[j]=false;
  138. }
  139. away[i]=false;
  140. }
  141. return ret;
  142. }
  143. inline void prepare(){
  144. for(int i=0;i<26;++i){
  145. for(int j=0;j<=1;++j){
  146. idA[i][j]=++cnt;
  147. idB[i][j]=++cnt;
  148. }
  149. }
  150. char qry[5];
  151. for(int i=1;i<=n;++i){
  152. scanf("%s",qry);
  153. //cdt=condition
  154. for(int j=0;j<=1;++j)
  155. cdt[i][j]=qry[j]-'A';
  156. //pers=person
  157. scanf("%d%d",&pers[i],&ans[i]);
  158. }
  159. }
  160. int main(){
  161. scanf("%d",&n);
  162. prepare();
  163. printf("%d",solve());
  164. return 0;
  165. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注