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 long 25 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,m1,n1,m); 32 if(n == n1) 33 { 34 printf("%d %d %d %d ",n+abs(m-m1),m,n1+abs(m-m1),m1); 35 }else if(m == m1){ 36 printf("%d %d %d %d ",n,m+abs(n-n1),n1 ,abs(n-n1)+m1); 37 }else { 38 if(abs(n-n1) != abs(m-m1)) 39 { 40 printf("-1 "); 41 return 0; 42 } 43 printf("%d %d %d %d ",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 long 25 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 ",1ll*a[mxnum]*a[minum]); 48 }else { 49 printf("%lld ",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 long 25 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 "); 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(" "); 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 long 25 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 ",getsum(t)); 79 ans += getsum(t); 80 } 81 printf("%I64d ",ans); 82 return 0 ; 83 }