2017 ICPC 北京

朱雀 2023-10-11 13:27 154阅读 0赞

E.

0:19:15 solved by hl

按照题意模拟即可

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <algorithm>
  10. using namespace std;
  11. int N,M,X;
  12. struct point{
  13. int c,t;
  14. point(int c = 0,int t = 0):c(c),t(t){}
  15. friend bool operator < (point a,point b){
  16. if(a.t == b.t) return a.c > b.c;
  17. return a.t > b.t;
  18. }
  19. };
  20. int main(){
  21. while(~scanf("%d%d%d",&N,&M,&X)){
  22. priority_queue<point>Q;
  23. for(int i = 1; i <= M ; i ++){
  24. int x; scanf("%d",&x);
  25. Q.push(point(x,0));
  26. }
  27. int sum1 = 0,sum2 = 0;
  28. while(!Q.empty() && sum1 < N){
  29. point u = Q.top(); Q.pop();
  30. u.t += u.c;
  31. sum1++;
  32. if(u.t > X) sum2++;
  33. if(u.t < X) Q.push(u);
  34. }
  35. N = max(0,N - sum1);
  36. printf("%d %d\n",N,sum2);
  37. }
  38. return 0;
  39. }

E

F.

0:40:05 solved by gbs

也是模拟题

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <iostream>
  2. #include<stdio.h>
  3. #include <string.h>
  4. using namespace std;
  5. int t,n;
  6. char sa[105][105];
  7. char ans[105][105];
  8. int nowx1,nowy1;
  9. int nowx2,nowy2;
  10. int flag1;
  11. int flag2;
  12. int newx,newy;
  13. bool judge()
  14. {
  15. if (newx<0||newx>=n)
  16. return false;
  17. if (newy<0||newy>=n)
  18. return false;
  19. return true;
  20. }
  21. bool judge2()
  22. {
  23. if (newx<0||newx>=n)
  24. return false;
  25. if (newy<0||newy>=n)
  26. return false;
  27. if (ans[newy][newx] != 0)
  28. return false;
  29. return true;
  30. }
  31. void next1()
  32. {
  33. if (flag1 == 0 )
  34. {
  35. if (nowx1 == n-1)
  36. {
  37. flag1++;
  38. nowy1++;
  39. return ;
  40. }
  41. nowx1++;
  42. flag1++;
  43. return ;
  44. }
  45. else if (flag1 == 2 )
  46. {
  47. if (nowy1 == n-1)
  48. {
  49. flag1++;
  50. nowx1++;
  51. return ;
  52. }
  53. nowy1++;
  54. flag1++;
  55. }
  56. else if (flag1 == 1 )
  57. {
  58. newx = nowx1-1;
  59. newy = nowy1+1;
  60. if (!judge())
  61. {
  62. flag1++;
  63. next1();
  64. }
  65. else
  66. {
  67. nowx1 = newx;
  68. nowy1 = newy;
  69. }
  70. return ;
  71. }
  72. else
  73. {
  74. newx = nowx1+1;
  75. newy = nowy1-1;
  76. if (!judge())
  77. {
  78. flag1=0;
  79. next1();
  80. }
  81. else
  82. {
  83. nowx1 = newx;
  84. nowy1 = newy;
  85. }
  86. return ;
  87. }
  88. }
  89. void next2()
  90. {
  91. newx = nowx2;
  92. newy = nowy2;
  93. if (flag2 == 0)
  94. newx++;
  95. if (flag2 == 1)
  96. newy++;
  97. if (flag2 == 2)
  98. newx--;
  99. if (flag2 == 3)
  100. newy--;
  101. if (judge2())
  102. {
  103. nowx2 = newx;
  104. nowy2 = newy;
  105. }
  106. else
  107. {
  108. flag2 = (flag2+1)%4;
  109. next2();
  110. }
  111. }
  112. int main()
  113. {
  114. while(cin >>n)
  115. {
  116. ;
  117. for (int i=0; i<n; i++)
  118. {
  119. scanf("%s",sa[i]);
  120. }
  121. memset(ans,0,sizeof(ans));
  122. int n2 = n*n;
  123. nowx1 = nowy1 =0;
  124. nowx2 = nowy2 = 0;
  125. flag1 = flag2 = 0;
  126. for (int i=0; i<n2; i++)
  127. {
  128. //cout<<nowy1<<' '<<nowx1<<endl;
  129. ans[nowy2][nowx2] = sa[nowy1][nowx1];
  130. if (i!=n2-1)
  131. {
  132. next1();
  133. next2();
  134. }
  135. }
  136. for (int i=0; i<n; i++)
  137. {
  138. printf("%s\n",ans[i]);
  139. }
  140. }
  141. return 0;
  142. }

F

G.披着bfs题外衣的计算几何题

难点在于判断线段穿过三角形内部

需要分三种情况

1.线段两端在三角形外

2.线段两端都在三角形内

3.线段两端一个在外一个在内

讨论一下就

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <algorithm>
  10. #define LL long long
  11. using namespace std;
  12. #define fi first
  13. #define se second
  14. #define db double
  15. int ma[25][25];
  16. int vis[25][25];
  17. int dx[]={
  18. 1,0,-1,0,1,-1,1,-1};
  19. int dy[]={
  20. 0,1,0,-1,1,-1,-1,1};
  21. double X1,X2,X3,Y1,Y2,Y3;
  22. int n;
  23. struct Point
  24. {
  25. double x,y;
  26. Point (double x=0,double y=0):x(x),y(y){}
  27. Point operator - (const Point &b) const {
  28. return Point(x-b.x,y-b.y); }
  29. };
  30. Point t1,t2,t3;
  31. double Cross(Point a,Point b)
  32. {
  33. return a.x*b.y-b.x*a.y;
  34. }
  35. double eps=1e-8;
  36. int dcmp(double x)
  37. {
  38. if(x<-eps) return -1;
  39. if(x>eps) return 1;
  40. return 0;
  41. }
  42. bool SegmentProperIntersection(const Point &a1,const Point &b1,const Point &a2,const Point &b2)//两线段规范相交、即每条线段的端点分别在另一条一段的两侧
  43. {
  44. db c1=Cross(b1-a1,a2-a1),c2=Cross(b1-a1,b2-a1);
  45. db c3=Cross(b2-a2,a1-a2),c4=Cross(b2-a2,b1-a2);
  46. return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
  47. }
  48. bool in(Point a,Point t1,Point t2,Point t3)
  49. {
  50. int s1=dcmp(Cross(a-t1,t2-t1));
  51. int s2=dcmp(Cross(a-t2,t3-t2));
  52. int s3=dcmp(Cross(a-t3,t1-t3));
  53. return ((s1<0&&s2<0&&s3<0)||(s1>0&&s2>0&&s3>0));
  54. }
  55. bool legle(int a,int b,int c,int d,int j)
  56. {
  57. if(c<0||c>=n||d<0||d>=n||ma[c][d]==0||vis[c][d]) return false;
  58. if(in(Point(c,d),t1,t2,t3)) return false;
  59. if(in(Point(a+dx[j]*0.01,b+dy[j]*0.01),t1,t2,t3)) return false;
  60. if(in(Point(c-dx[j]*0.01,d-dy[j]*0.01),t1,t2,t3)) return false;
  61. if(SegmentProperIntersection(Point(a,b),Point(c,d),t1,t2)) return false;
  62. if(SegmentProperIntersection(Point(a,b),Point(c,d),t3,t2)) return false;
  63. if(SegmentProperIntersection(Point(a,b),Point(c,d),t1,t3)) return false;
  64. return true;
  65. }
  66. int main()
  67. {
  68. while(cin>>n)
  69. {
  70. cin>>X1>>Y1>>X2>>Y2>>X3>>Y3;
  71. t1=Point(X1,Y1);
  72. t2=Point(X2,Y2);
  73. t3=Point(X3,Y3);
  74. char s[50];
  75. for(int j=n-1;j>=0;j--)
  76. {
  77. scanf("%s",s);
  78. for(int i=0;i<n;i++)
  79. {
  80. if(s[i]=='.')
  81. {
  82. ma[i][j]=1;
  83. }
  84. else
  85. {
  86. ma[i][j]=0;
  87. }
  88. vis[i][j]=0;
  89. }
  90. }
  91. queue<pair<int,int> > q;
  92. q.push(make_pair(0,0));
  93. vis[0][0]=1;
  94. while(!q.empty())
  95. {
  96. pair<int,int> top=q.front();
  97. q.pop();
  98. //cout<<top.fi<<' '<<top.se<<endl;
  99. for(int t=0;t<8;t++)
  100. {
  101. if(legle(top.fi,top.se,top.fi+dx[t],top.se+dy[t],t))
  102. {
  103. vis[top.fi+dx[t]][top.se+dy[t]]=vis[top.fi][top.se]+1;
  104. q.push(make_pair(top.fi+dx[t],top.se+dy[t]));
  105. }
  106. }
  107. }
  108. if(!vis[n-1][n-1]||ma[0][0]==0)
  109. {
  110. puts("-1");
  111. }
  112. else
  113. {
  114. printf("%d\n",vis[n-1][n-1]-1);
  115. }
  116. }
  117. return 0;
  118. }

G

H.

4:03:48 solved by hl

常规的子矩阵最大值之间复杂度是 n²m,即枚举上下界压缩维度之后O(m)

那么这题直接暴力的做法就是n3m2,如果n > m,就n,m互换,时间复杂度就是503 * 1502,然后通过一系列诸如从大到小枚举修改之类的大力剪枝,仰仗着数据不太硬给过了

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <algorithm>
  10. #define LL long long
  11. using namespace std;
  12. int N,M;
  13. LL p;
  14. const int maxn = 155;
  15. const int INF = 0x3f3f3f3f;
  16. LL MAP[maxn][maxn],MAP2[maxn][maxn];
  17. LL pre[maxn][maxn];
  18. LL a[maxn];
  19. LL Max = 0;
  20. LL solve(){
  21. for(int i = 1; i <= N ; i ++){
  22. for(int j = 1; j <= M ; j ++){
  23. pre[i][j] = pre[i - 1][j] + MAP[i][j];
  24. }
  25. }
  26. LL ans = -INF;
  27. for(int L = 1; L <= N ; L++){
  28. for(int R = L;R <= N; R++){
  29. for(int i = 1; i <= M; i ++){
  30. a[i] = pre[R][i] - pre[L - 1][i];
  31. }
  32. LL p = 0,pr = 0;
  33. for(int i = 1; i <= M ; i ++){
  34. pr += a[i];
  35. ans = max(ans,pr - p);
  36. p = min(p,pr);
  37. }
  38. }
  39. }
  40. return ans;
  41. }
  42. #define PII pair<int,int>
  43. #define fi first
  44. #define se second
  45. PII tmp[maxn * maxn];
  46. bool cmp(PII a,PII b){
  47. return MAP[a.fi][a.se] > MAP[b.fi][b.se];
  48. }
  49. int main(){
  50. while(~scanf("%d%d%lld",&N,&M,&p)){
  51. for(int i = 1; i <= N ; i ++){
  52. for(int j = 1; j <= M ; j ++){
  53. scanf("%lld",&MAP2[i][j]);
  54. }
  55. }
  56. if(N > M){
  57. swap(N,M);
  58. for(int i = 1; i <= N ; i ++){
  59. for(int j = 1; j <= M ; j ++){
  60. MAP[i][j] = MAP2[j][i];
  61. }
  62. }
  63. }else{
  64. for(int i = 1; i <= N ; i ++){
  65. for(int j = 1; j <= M ; j ++){
  66. MAP[i][j] = MAP2[i][j];
  67. // cout << MAP[i][j] << ' ';
  68. }
  69. // cout << endl;
  70. }
  71. }
  72. LL Min = solve();
  73. LL s = Min;
  74. int cnt = 0;
  75. for(int i = 1; i <= N; i ++){
  76. for(int j = 1; j <= M ; j ++) tmp[++cnt] = make_pair(i,j);
  77. }
  78. sort(tmp + 1,tmp + 1 + cnt,cmp);
  79. for(int i = 1; i <= cnt; i ++){
  80. if(s + p - MAP[tmp[i].fi][tmp[i].se] >= Min) break;
  81. LL q = MAP[tmp[i].fi][tmp[i].se];
  82. MAP[tmp[i].fi][tmp[i].se] = p;
  83. Min = min(Min,solve());
  84. MAP[tmp[i].fi][tmp[i].se] = q;
  85. }
  86. cout << Min << endl;
  87. }
  88. return 0;
  89. }

H

J.区间dp

3:16:14 solved by hl

dp[l][r][h]表示l到r这个区间内的石子被分为h堆需要的最小花费

然后按照枚举区间长度,枚举左端点,枚举区间堆数,枚举中间点,枚举中间点左边区间的堆数

这样的贡献,写个n5次的dp,仰仗着数据不够硬,剪了个枝就过了

不过正解是n4

也就是原来解法中枚举中间点左边区间的堆数这一层事实上是不用枚举的,这个和寻常的区间dp有些出入,从左边选择x堆右边选择y堆使得x + y = k,和左边选择k - 1堆右边选择1堆的情况是一样的,所以可以少枚举一层

也就是在源代码上这么修改1468815-20190819184407932-674260663.png 就是正解了

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <cstring>
  5. #include <cstdio>
  6. #include <queue>
  7. #include <map>
  8. #include <set>
  9. #include <algorithm>
  10. #define LL long long
  11. using namespace std;
  12. int N,L,R;
  13. const int maxn = 110;
  14. const int INF = 0x3f3f3f3f;
  15. int a[maxn];
  16. LL pre[maxn];
  17. LL dp[maxn][maxn][maxn];
  18. int main(){
  19. while(~scanf("%d%d%d",&N,&L,&R)){
  20. pre[0] = 0;
  21. for(int i = 1; i <= N ; i ++) scanf("%d",&a[i]),pre[i] = pre[i - 1] + a[i];
  22. for(int i = 1; i <= N ; i ++){
  23. for(int j = 1; j <= N ; j ++){
  24. for(int k = 0 ; k <= N; k ++){
  25. dp[i][j][k] = INF;
  26. }
  27. }
  28. dp[i][i][1] = 0;
  29. }
  30. for(int len = 1; len <= N ; len ++){
  31. for(int l = 1; l + len - 1 <= N ; l ++){
  32. int r = l + len - 1;
  33. LL sum = pre[r] - pre[l - 1];
  34. if(len >= L && len <= R) dp[l][r][1] = sum;
  35. for(int p = 2; p <= len; p ++){
  36. for(int k = l ; k < r; k ++){
  37. for(int h = max(1,p + k - r); h <= min(k - l + 1,p); h ++){
  38. dp[l][r][p] = min(dp[l][k][h] + dp[k + 1][r][p - h],dp[l][r][p]);
  39. }
  40. }
  41. if(p >= L && p <= R){
  42. dp[l][r][1] = min(dp[l][r][1],dp[l][r][p] + sum);
  43. }
  44. }
  45. }
  46. }
  47. if(dp[1][N][1] >= INF) dp[1][N][1] = 0;
  48. cout << dp[1][N][1] << endl;
  49. }
  50. return 0;
  51. }

J

转载于:https://www.cnblogs.com/Hugh-Locke/p/11378901.html

发表评论

表情:
评论列表 (有 0 条评论,154人围观)

还没有评论,来说两句吧...

相关阅读