首页 > 代码库 > Codeforces 486(#277 Div 2) 解题报告
Codeforces 486(#277 Div 2) 解题报告
A：比较简单 判断奇偶 一个公式即可
1 // File Name: a.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月11日 星期二 22时43分28秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 28 int main(){29 LL n ;30 scanf("%lld",&n);31 if(n % 2 == 0 )32 printf("%d\n",n/2);33 else printf("%d\n",n/2 -n);34 return 0;35 }
B：默认 A 所有为 1 先把M[i][j] = 0 的i 行 j列 覆盖成 0 然后再要得到的A 矩阵运算 看能否得出 M
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月11日 星期二 23时03分52秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 int M[200][200];28 int A[200][200];29 int n , m ;30 int dfsr(int k )31 {32 for(int i = 1;i <= n;i ++)33 if(M[i][k] == 0 )34 return 0 ;35 return 1;36 }37 int dfsc(int k )38 {39 //printf("%d\n",k);40 for(int i = 1;i <= m;i ++)41 {42 // printf("***%d %d\n",k,i);43 if(M[k][i] == 0 )44 return 0 ;45 }46 return 1;47 }48 int main(){49 scanf("%d %d",&n,&m);50 for(int i = 1;i <= n;i ++)51 for(int j = 1;j <= m;j ++)52 {53 scanf("%d",&M[i][j]);54 A[i][j] = 1; 55 }56 for(int i = 1;i <= n;i ++)57 for(int j = 1;j <= m;j ++)58 {59 if(M[i][j] == 0)60 {61 //printf("***\n");62 for(int s = 1;s <= m ;s ++)63 {64 A[i][s] = 0 ; 65 }66 for(int s = 1;s <= n ;s ++)67 {68 A[s][j] = 0 ; 69 } 70 }71 }72 for(int i = 1;i <= n;i ++)73 {74 for(int j = 1;j <= m;j ++)75 {76 int tmp = 0 ; 77 for(int s = 1 ; s <= m ;s ++ )78 tmp |= A[i][s];79 for(int s = 1 ; s <= n ;s ++ )80 tmp |= A[s][j];81 if(tmp != M[i][j])82 {83 puts("NO");84 return 0 ; 85 }86 }87 }88 printf("YES\n");89 for(int i = 1;i <= n;i ++)90 {91 for(int j = 1;j <= m ;j ++)92 printf("%d ",A[i][j]);93 printf("\n");94 }95 return 0;96 }
C：这个字符串已知改变的值是已经确定了的。我们只需要看 他怎么样移动才能够覆盖掉半边 要改变的位置，如果他在左边 他只改变左边的是最优的，如果在右边，只
改变右边的也是最优的，如果穿过中线或者边界一定不是最优的了。
1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月11日 星期二 23时28分50秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 char str[100005];28 int num[100005];29 int vis[100005];30 int dp[400005];31 int n , p ; 32 int solve(int t)33 {34 if(t <= 0 )35 {36 return n + t; 37 }38 if(t > n)39 return t- n ;40 }41 int main(){42 scanf("%d %d",&n,&p);43 scanf("%s",&str[1]); 44 int sum = 0 ;45 int num = 0 ; 46 for(int i = 1;i <= n/2;i ++)47 {48 if(str[i] == str[n-i+1])49 continue;50 num ++ ; 51 int mi = min(str[i],str[n-i+1]) ;52 int mx = max(str[i],str[n-i+1]);53 sum += min(mx - mi,mi + 26 -mx);54 vis[i] = 1; 55 vis[n-i+1] = 1; 56 }57 if(sum == 0 )58 {59 printf("0\n");60 return 0 ;61 }62 63 int be = 0 ; 64 int en = 0 ;65 int qd ;66 int zd;67 if(p > n/2)68 {69 qd = n/2 +1;70 zd = n;71 }else {72 qd = 1; 73 zd = n/2;74 }75 76 for(int i = qd;i <= zd;i ++)77 {78 if(!be && vis[i] ==1 )79 be = i ; 80 if(vis[i])81 en = i ; 82 }83 //printf("%d %d\n",be,en);84 if(p >= en)85 sum += p - be;86 else if(p <= be)87 sum += en - p;88 else sum += min(p-be,en-p) + en -be;89 printf("%d\n",sum);90 return 0;91 }
D：从值最小的点开始每个点都要暴搜整颗树，从某个点开始遍历，这个点要是所有遍历到点的最小值 且遍历到的点要满足 val[x] - val[这个点] <= d ，子树用树形DP求出，，每搜过一颗树把根标记掉，下次就不能走了。这样就可以得到所有的子树
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月12日 星期三 19时23分45秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 #define maxn 100005 26 using namespace std; 27 int F1[maxn]; 28 int F2[maxn]; 29 int a[maxn]; 30 int vis[maxn]; 31 vector<int> LIS; 32 int L; 33 int find(int x) 34 { 35 int l = 0; 36 int r = LIS.size() - 1; 37 int m; 38 while(l <= r ) 39 { 40 m = (l + r) >> 1; 41 if(x < LIS[m]) 42 { 43 l = m + 1; 44 }else r = m - 1; 45 } 46 //printf("%d %d %d %d\n",l,m,a[m],x); 47 return l; 48 } 49 int main(){ 50 int n; 51 scanf("%d",&n); 52 for(int i = 1;i <= n;i ++) 53 { 54 scanf("%d",&a[i]); 55 int p = upper_bound(LIS.begin(),LIS.end(),a[i]-1) - LIS.begin(); 56 if(p == LIS.size()) 57 { 58 LIS.push_back(a[i]); 59 }else{ 60 LIS[p] = a[i]; 61 } 62 F1[i] = p + 1; 63 } 64 L = LIS.size(); 65 //printf("%d\n",L); 66 LIS.clear(); 67 for(int i = n;i >= 1;i --) 68 { 69 int p = find(a[i]); 70 if(p == LIS.size()) 71 LIS.push_back(a[i]); 72 else LIS[p] = a[i]; 73 F2[i] = p+1; 74 //printf("%d %d\n",i,F2[i]); 75 } 76 /* for(int i = 1;i <= n;i ++) 77 printf("%d*",F1[i]); 78 printf("\n"); 79 */ memset(vis,0,sizeof(vis)); 80 for(int i = 1;i <= n;i ++) 81 { 82 // printf("%d ",F2[i]); 83 if(F1[i] + F2[i] -1== L) 84 vis[F2[i]] ++ ; 85 } 86 /*for(int i = 1;i <= n;i ++) 87 printf("%d ",vis[i]); 88 printf("\n");*/ 89 //printf("\n"); 90 for(int i = 1;i <= n;i ++) 91 { 92 if(F1[i] + F2[i] -1 < L) 93 printf("1"); 94 else if(vis[F2[i]] == 1) 95 printf("3"); 96 else printf("2"); 97 } 98 99 return 0;100 }
E：
题解：
官方解法2：http://codeforces.com/blog/entry/14678
YYN解法：http://blog.csdn.net/u013368721/article/details/41030775
数列a[i]
F1[i] 表示 以a[i]结尾的最长LIS的长度 顺序遍历二分求得
F2[i] 表示 以a[i]开头的最长LIS的长度 逆序遍历二分求得
L是LIS长度,
然后 YYN 和管方的做法就不用了
YYN：
然后分类：
1)F1[i] + F2[i] - 1 < L
2)F1[i] + F2[i] - 1 == L 且 F1[i] 不唯一（这里如何计数唯一和不唯一 需要把所有 F1[i] + F2[i] == L 的统计一遍）
3）F1[1] + F2[i] - 1 == L 且 F1[i] 唯一
官方2：
再设一个数列 F[i] 表示 如果没有 a[i] LIS 的长度， F[i] = max( 1 <= u <i < v <= n &&a[v] > a[u] |F1[u] + F2[v])
F[i] 需要用到一次线段树 和数组离线来统计
然后就是分类
1） F1[i] + F2[i] -1 < L
2) F[i] == L
3) F[i] == L-1
显然 YYN的做法更巧妙 YM + ORZ
YYN做法代码：
1 // File Name: e.cpp 2 // Author: darkdream 3 // Created Time: 2014年11月12日 星期三 00时35分31秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 struct node{ 28 int v, p ; 29 node(int _v ,int _p) 30 { 31 v = _v; 32 p = _p; 33 } 34 }; 35 int len = 0 ; 36 vector<int>LI; 37 vector<node> LIS[100005]; 38 int ans[100005]; 39 int np[100005]; 40 int n; 41 void solve() 42 { 43 for(int i = 0;i < len - 1; i ++) 44 { 45 int k = LIS[i].size(); 46 if(k == 1) 47 { 48 ans[LIS[i][0].p] = 2; 49 } 50 } 51 int num = LIS[len-1].size(); 52 if(num == 1 ) 53 { 54 ans[LIS[len-1][0].p] = 2; 55 }else{ 56 for(int i = 0 ;i < num;i ++) 57 { 58 ans[LIS[i][0].p] = 1; 59 } 60 } 61 int be = 0; 62 int en = num -1; 63 for(int i = len - 2;i >= 1;i --) 64 { 65 int num = LIS[i].size(); 66 int tbe = -1 ; 67 int ten = -1; 68 int j = 0; 69 int s = be; 70 { 71 node tmp = LIS[i][j]; 72 if(tmp.v < LIS[i+1][s].v && tmp.p < LIS[i+1][s].p) 73 { 74 if(tbe == -1) 75 { 76 tbe = j ; 77 } 78 ten = j; 79 }else if(tmp.v > LIS[i+1][s].v){ 80 81 } 82 } 83 be = tbe; 84 en = ten; 85 if(be == en) 86 { 87 ans[LIS[i][be].p] = 2; 88 }else 89 for(int j= be;j <= en;j ++) 90 { 91 ans[LIS[i][j].p] = 1; 92 } 93 94 } 95 } 96 int main(){ 97 int n; 98 scanf("%d",&n); 99 len = 0 ; 100 for(int i = 1;i <= n;i ++)101 {102 int t; 103 scanf("%d",&t);104 int p = upper_bound(LI.begin(),LI.end(),t) - LI.begin();105 if(p == LI.size())106 {107 LI.push_back(t);108 len ++;109 }110 else LI[p] = t;111 np[x] = LI[p+1].size() - 1;112 LIS[p].push_back(node(t,i));113 }114 solve();115 for(int i =1;i <= n;i ++)116 printf("%d",ans[i]+1);117 return 0;118 }
Codeforces 486(#277 Div 2) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。