经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C » 查看文章
[20181107][模拟赛]
来源:cnblogs  作者:wxyww  时间:2018/11/8 9:52:48  对本文有异议

[20181107][模拟赛]

题面

T1

思路

考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) - 1的所有数就行了。

代码

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstdlib>
  4. #include<ctime>
  5. #include<queue>
  6. #include<cstring>
  7. #include<algorithm>
  8. using namespace std;
  9. typedef long long ll;
  10. const int N = 100000 + 100;
  11. ll read() {
  12. ll x = 0, f = 1;
  13. char c = getchar();
  14. while(c < '0' || c > '9') {
  15. if(c == '-') f = -1;
  16. c = getchar();
  17. }
  18. while(c >= '0' && c <= '9') {
  19. x = x * 10 + c - '0';
  20. c = getchar();
  21. }
  22. return x * f;
  23. }
  24. int n,m,K,a[N],b[N],k[N];
  25. int gcd(int x,int y) {
  26. return !y ? x : gcd(y,x % y);
  27. }
  28. namespace BF1 {
  29. void Main() {
  30. memset(a,0,sizeof(a));
  31. memset(b,0,sizeof(b));
  32. int aa = read();
  33. for(int i = 1;i <= aa;++i) a[read()] = 1;
  34. int bb = read();
  35. for(int i = 1;i <= bb;++i) b[read()] = 1;
  36. read();
  37. for(int i = 0;i <= 100000;++i) {
  38. int x1 = i % n, x2 = i % m;
  39. a[x1] = b[x2] = a[x1] | b[x2];
  40. }
  41. for(int i = 0;i < n;++i) {
  42. if(a[i] != 1) {
  43. puts("No");
  44. return;
  45. }
  46. }
  47. for(int i = 0;i < m;++i) {
  48. if(b[i] != 1) {
  49. puts("No");
  50. return;
  51. }
  52. }
  53. puts("Yes");
  54. }
  55. }
  56. namespace BF2 {
  57. int tmp[N * 5],js = 0;
  58. void Main() {
  59. js = 0;
  60. int mod = gcd(gcd(n,m),K);
  61. int aa = read();
  62. for(int i = 1;i <= aa;++i) tmp[++js] = read() % mod;
  63. int bb = read();
  64. for(int i = 1;i <= bb;++i) tmp[++js] = read() % mod;
  65. int kk = read();
  66. for(int i = 1;i <= kk;++i) tmp[++js] = read() % mod;
  67. int now = 0;
  68. sort(tmp + 1,tmp + js + 1);
  69. tmp[0] = -1;
  70. int ans = 0;
  71. for(int i = 1;i <= js;++i) {
  72. if(tmp[i] == tmp[i-1]) continue;
  73. if(tmp[i] == tmp[i-1]+1) now++;
  74. else {
  75. ans = max(ans,now);
  76. now = 1;
  77. }
  78. }
  79. ans = max(ans,now);
  80. if(ans >= mod) puts("Yes");
  81. else puts("No");
  82. return;
  83. }
  84. }
  85. int main() {
  86. freopen("happy2.in","r",stdin);
  87. freopen("happy2.out","w",stdout);
  88. int T = read();
  89. while(T--) {
  90. n = read(),m = read(),K = read();
  91. if(n <= 100 && m <= 100 && K == 0) {
  92. BF1::Main();
  93. continue;
  94. }
  95. BF2::Main();
  96. }
  97. return 0;
  98. }

T2

想了一会感觉不可做,直接55分暴力。

55分代码

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstdlib>
  4. #include<ctime>
  5. #include<queue>
  6. #include<cstring>
  7. #include<algorithm>
  8. #include<bitset>
  9. using namespace std;
  10. typedef long long ll;
  11. const int N = 300000 + 100;
  12. ll read() {
  13. ll x = 0, f = 1;
  14. char c = getchar();
  15. while(c < '0' || c > '9') {
  16. if(c == '-') f = -1;
  17. c = getchar();
  18. }
  19. while(c >= '0' && c <= '9') {
  20. x = x * 10 + c - '0';
  21. c = getchar();
  22. }
  23. return x * f;
  24. }
  25. int n,p;
  26. namespace BF1 {
  27. int du[N];
  28. void Main() {
  29. for(int i = 1;i <= n;++i) {
  30. int x = read(), y = read();
  31. du[x]++;
  32. du[y]++;
  33. }
  34. ll ans1 = 0;
  35. for(int i = 1;i <= n;++i)
  36. if(du[i] == 0) ans1++;
  37. cout<<(ll)n * (ll)(n - 1)/2 - (ans1 * (ans1 - 1) / 2);
  38. return;
  39. }
  40. }
  41. namespace BF2 {
  42. const int NN = 110;
  43. bitset <NN> tmp[NN];
  44. int ans = 0;
  45. inline int check(int x,int y) {
  46. bitset <NN> ls;
  47. ls = tmp[x] | tmp[y];
  48. return ls.count() >= p;
  49. }
  50. void Main() {
  51. for(int i = 1;i <= n;++i) {
  52. int x = read(),y = read();
  53. tmp[x][i] = 1;
  54. tmp[y][i] = 1;
  55. }
  56. for(int i = 1;i <= n;++i) {
  57. for(int j = i + 1;j <= n;++j) {
  58. ans += check(i,j);
  59. }
  60. }
  61. cout<<ans<<endl;
  62. }
  63. }
  64. int main() {
  65. freopen("suspect.in","r",stdin);
  66. freopen("suspect.out","w",stdout);
  67. n = read(),p = read();
  68. if(p == 0) {
  69. cout<<((ll)n*(n-1) / 2);
  70. return 0;
  71. }
  72. if(p == 1) {
  73. BF1::Main();
  74. return 0;
  75. }
  76. if(n <= 100) {
  77. BF2::Main();
  78. return 0;
  79. }
  80. return 0;
  81. }

std

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<vector>
  7. #include<queue>
  8. #include<map>
  9. #include<set>
  10. #include<stack>
  11. #include<cstdlib>
  12. #define INF 100000000
  13. using namespace std;
  14. typedef long long LL;
  15. struct Edge
  16. {
  17. int from,to,pre;
  18. }e[1000000];
  19. int h[300005]={0},cou=0;
  20. int c[300005],ed[300005];
  21. void Addedge(int from,int to)
  22. {
  23. cou++;
  24. e[cou]=((Edge){from,to,h[from]});
  25. h[from]=cou;
  26. }
  27. inline void update(int x)
  28. {
  29. if(x==0)
  30. {
  31. c[0]++;
  32. return;
  33. }
  34. for(;x<=300000;x+=x&-x)
  35. c[x]++;
  36. }
  37. inline int get(int x)
  38. {
  39. if(x==-1) return 0;
  40. int sum=0;
  41. for(;x;x-=x&-x)
  42. sum+=c[x];
  43. return sum+c[0];
  44. }
  45. int main()
  46. {
  47. freopen("suspect.in","r",stdin);
  48. freopen("suspect.out","w",stdout);
  49. LL ans=0;
  50. int sum,i,n,p,a,b,v,j;
  51. cin>>n>>p;
  52. for(i=1;i<=n;i++)
  53. {
  54. scanf("%d%d",&a,&b);
  55. Addedge(a,b); Addedge(b,a);
  56. ed[a]++; ed[b]++;
  57. }
  58. for(i=1;i<=n;i++)
  59. update(ed[i]);
  60. for(i=1;i<=n;i++)
  61. {
  62. if(ed[i]>=p)
  63. ans+=n-1;
  64. else
  65. {
  66. sum=n-get(p-ed[i]-1);
  67. if(ed[i]>=p-ed[i]) sum--;
  68. for(j=h[i];j;j=e[j].pre)
  69. {
  70. v=e[j].to;
  71. if(ed[v]==p-ed[i]) sum--;
  72. ed[v]--;
  73. }
  74. for(j=h[i];j;j=e[j].pre)
  75. {
  76. v=e[j].to;
  77. ed[v]++;
  78. }
  79. ans+=sum;
  80. }
  81. }
  82. cout<<ans/2<<endl;
  83. return 0;
  84. }

T3

80分思路

暴力分感觉都可做,然后就写了80分暴力。用莫队卡一下100分???会TLE吧(真麻烦,不想写)。

100分思路

如果这个题让着求区间出现奇数次的数的异或和就很简单了。所以我们可以对于询问先离线一下。按照右端点拍个序。然后用树状数组维护一下区间异或和。就是从1扫到n,同时将当前的数上一次出现的位置(在树状数组里)异或上这个数。然后查询就好了。

100分代码

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<vector>
  7. #include<queue>
  8. #include<map>
  9. #include<set>
  10. #include<stack>
  11. #include<cstdlib>
  12. #include<string>
  13. #include<bitset>
  14. #include<iomanip>
  15. #include<deque>
  16. #include<utility>
  17. #define INF 1000000000
  18. #define fi first
  19. #define se second
  20. #define N 1000005
  21. #define P 1000000007
  22. #define debug(x) cerr<<#x<<"="<<x<<endl
  23. #define MP(x,y) make_pair(x,y)
  24. using namespace std;
  25. typedef long long LL;
  26. typedef pair<int,int> pii;
  27. int c[N],now,sum,a[N],b[N],ans[N],nxt[N],n;
  28. map<int,int> vis,pre;
  29. vector<pii> Q[N];
  30. void Add(int x,int w)
  31. {
  32. for(;x<=n;x+=x&-x)
  33. c[x]^=w;
  34. }
  35. int Get(int x)
  36. {
  37. int s=0;
  38. for(;x;x-=x&-x)
  39. s^=c[x];
  40. return s;
  41. }
  42. int main()
  43. {
  44. int i,m,ql,qr,j;
  45. freopen("xor.in","r",stdin);
  46. freopen("xor.out","w",stdout);
  47. cin>>n;
  48. now=0;
  49. for(i=1;i<=n;i++)
  50. {
  51. scanf("%d",&a[i]);
  52. vis[a[i]]++;
  53. nxt[pre[a[i]]]=i;
  54. pre[a[i]]=i;
  55. if(vis[a[i]]>1)
  56. now^=a[i];
  57. b[i]=now;
  58. //debug(b[i]);
  59. }
  60. cin>>m;
  61. for(i=1;i<=m;i++)
  62. {
  63. scanf("%d%d",&ql,&qr);
  64. Q[ql].push_back(MP(qr,i));
  65. }
  66. for(i=1;i<=n;i++)
  67. {
  68. //debug(sum);
  69. for(j=0;j<Q[i].size();j++)
  70. ans[Q[i][j].se]=Get(Q[i][j].fi)^b[Q[i][j].fi];
  71. ql=nxt[i];
  72. if(ql)
  73. {
  74. sum^=a[i];
  75. Add(ql,a[i]);
  76. }
  77. }
  78. for(i=1;i<=m;i++)
  79. printf("%d\n",ans[i]);
  80. return 0;
  81. }

总结

期望得分:100 + 55 + 80 = 235

实际得分:100 + 55 + 80 = 235

暴力没挂真的感动。越来越菜了

一言

那时我怎么都想不到,原来也有这一天,念及你,竟既无风雨也无晴。 ——我亦飘零久

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号