首页 > 代码库 > Codeforces 459(#261 (Div. 2) ) 解题报告
Codeforces 459(#261 (Div. 2) ) 解题报告
A：给你一个正方形的两点，让你求其余亮点
解法：乱搞
解题代码：
1 // File Name: a.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月15日 星期五 23时24分04秒 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 int n , m ,n1,m1; 30 scanf("%d %d %d %d",&n,&m,&n1,&m1);31 // printf("%d %d %d %d\n",n,m1,n1,m);32 if(n == n1)33 {34 printf("%d %d %d %d\n",n+abs(m-m1),m,n1+abs(m-m1),m1); 35 }else if(m == m1){36 printf("%d %d %d %d\n",n,m+abs(n-n1),n1 ,abs(n-n1)+m1); 37 }else {38 if(abs(n-n1) != abs(m-m1)) 39 {40 printf("-1\n");41 return 0; 42 }43 printf("%d %d %d %d\n",n,m1,n1,m);44 }45 return 0;46 }
B：求n个数中最大差值的总数
解法：乱搞
解题代码：
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月15日 星期五 23时41分47秒 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 map<int,int>a;28 int main(){29 int n;30 a.clear();31 int mxnum = -1e9+1; 32 int minum = 1e9 + 1;33 int temp ;34 scanf("%d",&n);35 for(int i =1 ;i <= n;i ++)36 {37 scanf("%d",&temp);38 a[temp] = a[temp] + 1; 39 if(temp > mxnum)40 mxnum = temp ;41 if(temp < minum)42 minum = temp ;43 }44 printf("%d ",mxnum - minum);45 if(mxnum != minum)46 {47 printf("%lld\n",1ll*a[mxnum]*a[minum]);48 }else {49 printf("%lld\n",1ll*a[mxnum]*(a[mxnum] - 1)/2) ;50 }51 return 0;52 }
C：给你n个人，有k辆车，有d天d个景点，求怎么安排使得任意两人不能d天都同一辆车
解法：可以知道一竖行的数字不能都相等，那这就是一个求d位k进制的数
解题代码：
1 // File Name: c.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月16日 星期六 00时10分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 LL n ,k,d;28 int dp[1004][1004];29 int check()30 {31 LL t = 1;32 for(int i = 1;i <= d ;i ++)33 {34 t = t * k ; 35 if(t >= n)36 return 0 ;37 }38 printf("-1\n");39 return 1;40 }41 int main(){42 scanf("%I64d %I64d %I64d",&n,&k,&d);43 if(check())44 return 0 ;45 for(int i =1;i <= d;i ++)46 dp[i][1] = 1; 47 int t = 0 ; 48 for(int i = 2;i <= n;i ++)49 { 50 t = 1 ; 51 for(int j = 1;j <= d;j ++)52 {53 t = dp[j][i-1] + t; 54 if(t == k+1)55 {56 dp[j][i] = 1; 57 }else {58 dp[j][i] = t;59 }60 t = t /(k+1);61 }62 }63 for(int i = 1;i <= d;i ++)64 { 65 for(int j = 1;j <= n;j ++)66 printf("%d ",dp[i][j]);67 printf("\n");68 } 69 return 0;70 }
D：给你一个公式 f(i,j,x) 求的是 序列中 i 到 j 等于 x 数的个数 ，现在问你有多少 （1 <= i < j <= n） f（1,i,a[i]） > f(j,n,a[j])
解法：树状数组，从后往前扫一遍，用map记录个数，再加一个辅助数组表示这个从后往前是第几个，然后再从前往后扫，map记录个数，每遍历到一个，就删除一个辅助数组的值，直接数状数组求和累加就行。
1 // File Name: d.cpp 2 // Author: darkdream 3 // Created Time: 2014年08月16日 星期六 00时57分59秒 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 const int maxn = 1000010;28 map<int ,int >mp;29 map<int ,int >be;30 int a[maxn];31 int num[maxn];32 int n;33 int anst[maxn];34 int lowbit(int x)35 {36 return x &(-x);37 }38 void update(int x,int st)39 {40 while(x <= n)41 {42 anst[x] += st;43 x += lowbit(x);44 }45 }46 LL getsum(int x)47 {48 LL sum = 0 ; 49 while(x >= 1 )50 {51 sum += anst[x];52 x -= lowbit(x);53 }54 return sum;55 }56 int main(){57 scanf("%d",&n);58 int temp ; 59 mp.clear();60 be.clear();61 for(int i = 1;i <= n;i ++)62 {63 scanf("%d",&a[i]);64 }65 for(int i = n;i >= 1; i --)66 {67 int t= mp[a[i]];68 mp[a[i]]++;69 num[i] = t+1;70 update(t+1,1);71 }72 LL ans = 0 ; 73 for(int i = 1;i <= n;i ++)74 {75 int t = be[a[i]];76 update(num[i],-1);77 be[a[i]] = t + 1; 78 //printf("%I64d\n",getsum(t));79 ans += getsum(t);80 }81 printf("%I64d\n",ans);82 return 0 ;83 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。