首页 > 代码库 > Codeforces Round #390 (Div. 2) 解题报告
Codeforces Round #390 (Div. 2) 解题报告
时隔一个月重返coding……
期末复习了一个月也不亏 倒是都过了……
就是计组61有点亏 复变68也太低了 其他都还好……
假期做的第一场cf 三道题 还可以……
最后room第三 standing383简直人生巅峰……
看楼上楼下都是两道题的 如果A题不错那么多估计能进前300了吧……
这场倒是把之前两场的分加回来了 开头不错 这个假期争取紫名~
A.Lesha and array splitting
把给定的数组分割成几个区间 要求各个区间和不能为0
一开始没注意到分割之后的区间重新合成之后还是这个区间错了好几发……
具体思路见注释
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a[1005]; 5 6 int main() 7 { 8 int n; 9 int p = -1, sum = 0;10 scanf("%d",&n);11 for (int i = 1; i <= n; i ++)12 {13 scanf("%d",&a[i]);14 sum += a[i];15 if (a[i] != 0 && p == -1)16 {17 p = i;18 }19 }20 if (p == -1)21 {//都是零的话肯定不行22 puts("NO"); 23 }24 else25 {26 puts("YES");27 if (sum != 0)28 {//数列和不为零 那么一个区间就够了29 printf("1\n1 %d\n",n); 30 }31 else32 {//数列和为零的话 取最前面的分割点就好了33 printf("2\n1 %d\n%d %d\n", p, p+1, n);34 }35 }36 return 0;37 }
B.Ilya and tic-tac-toe game
题意就是问该下的人再下一步能不能赢
4x4的格子强行暴力
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 char mp[10][10],one; 5 6 int main() 7 { 8 int nx=0,no=0; 9 for(int i=0; i<4; i++)10 {11 gets(mp[i]);12 for(int j=0; j<4; j++)13 {14 if(mp[i][j]==‘x‘) nx++;15 if(mp[i][j]==‘o‘) no++;16 }17 }18 if(no==nx) one=‘x‘;19 else one=‘o‘;20 bool ok=false;21 for(int i=0; i<4; i++)22 {23 for(int j=0; j<4; j++)24 {25 if(mp[i][j]==‘.‘) //这个地方是空的 假如把棋子下在这26 {27 mp[i][j]=one;28 for(int k=0; k<4; k++)29 {30 for(int l=0; l<4; l++)31 {32 if(k < 2 && mp[k][l] == one && mp[k+1][l] == one && mp[k+2][l] == one) ok=true;33 if(l < 2 && mp[k][l] == one && mp[k][l+1] == one && mp[k][l+2] == one) ok=true;34 }35 }36 if(mp[0][0] == one && mp[1][1] == one && mp[2][2] == one) ok = true;37 if(mp[0][1] == one && mp[1][2] == one && mp[2][3] == one) ok = true;38 if(mp[0][2] == one && mp[1][1] == one && mp[2][0] == one) ok = true;39 if(mp[0][3] == one && mp[1][2] == one && mp[2][1] == one) ok = true;40 if(mp[1][0] == one && mp[2][1] == one && mp[3][2] == one) ok = true;41 if(mp[1][1] == one && mp[2][2] == one && mp[3][3] == one) ok = true;42 if(mp[1][2] == one && mp[2][1] == one && mp[3][0] == one) ok = true;43 if(mp[1][3] == one && mp[2][2] == one && mp[3][1] == one) ok = true;44 if(ok)45 {46 printf("YES");47 return 0;48 }49 else mp[i][j]=‘.‘; //没赢 换个地方下50 }51 }52 }53 printf("NO\n");54 return 0;55 }
C.Vladik and chat
是个大模拟 还没弄明白……
D.Fedor and coupons
数据结构题
给你n个区间 选择k个求最长交集
自己做没做出来 和别人交流了一下才知道是个堆 现学现卖了一发
写了一个堆 维护前k大值 假设区间i作为最后一个区间必选
ans=max(前i-1个区间右端点的k-1大值，第i区间右端点的最小值) - 第i个区间左端点
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=3e5+10; 5 6 struct A 7 { 8 int x, y, id; 9 } a[maxn];10 11 bool cmp(A x,A y)12 {13 return x.y == y.y ? x.x < y.x : x.y > y.y;14 }15 16 priority_queue<int> q;17 int ans = 0, r = -1,n, k;18 19 void solve() //优先队列维护k大值20 {21 q.push(-2e9);22 for (int i = 0; i < n; i ++)23 {24 if (q.size() == k)25 {26 int l = max(q.top(), a[i].x);27 if (a[i].y - l + 1 >= ans)28 {29 ans = a[i].y - l + 1;30 r = a[i].y;31 }32 }33 q.push(a[i].x);34 if (q.size() > k)35 {36 q.pop();37 }38 }39 }40 41 void print()42 {43 if(ans)44 {45 int l = r - ans + 1;46 for (int i = 0; k > 0; i ++)47 {48 if (a[i].x <= l && a[i].y >= r)49 {50 k --;51 printf("%d ",a[i].id);52 }53 }54 }55 else56 {57 for (int i = 0; i < k; i ++)58 {59 printf("%d ",a[i].id);60 }61 }62 }63 64 int main()65 {66 scanf("%d%d",&n,&k);67 for (int i = 0; i < n; i ++)68 {69 scanf("%d%d",&a[i].x,&a[i].y);70 a[i].id = i + 1;71 }72 sort(a, a + n, cmp); //按区间边界排序73 solve();74 printf("%d\n",ans);75 print();76 return 0;77 }78 /*79 80 81 82 */
E.Dasha and cyclic table
没看懂……
巨巨们讨论的热火朝天 我却啥都听不懂……
等能听懂他们说啥应该就有很大进步了吧……
Codeforces Round #390 (Div. 2) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。