转载

2015.05.21积分赛题解

一、很容易发现发现对于三个点(x1,y1)(x2,y2)(x3,y3)，如果任意交换坐标费用不变，所以题意变为枚举3个横坐标和3个纵坐标，算合理的方案数

对于x1,x2,x3 , y1,y2,y3，若有x1<x2<x3 , y1<y2<y3，则方案的费用是2(x3-x1)+2(y3-y1)。

所以，不妨令x1<x2<x3 , y1<y2<y3，则由排列组合易得，最后方案数乘6即为答案。

而(x1,y1)和(x3,y3)构成一个矩形，对于一个确定的矩形边框，它的费用是一定的，即2(x3-x1)+2(y3-y1)，也就是矩形的边长。它对答案的贡献也是一定的，即(x3-x1-1) (y3-y1-1)。这个矩形在r c的大矩形中出现的次数也是给定的，设矩形长为x,宽为y，则出现了(r-x+1)*(c-y+1)次。那么直接枚举矩形的边长，然后就可以算出答案。

时间复杂度为O(n^2)

/**         Author: SpringHack - springhack@live.cn         Last modified: 2016-05-15 17:17:57         Filename: main.cpp         Description: Created by SpringHack using vim automatically. **/ #include <iostream> #include <cstdlib> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm>  using namespace std;  #define LL long long  int n, m, minn, maxx, ans; int ta[10005], tb[10005];  int main() {     int i, j;     scanf("%d%d%d%d", &n, &m, &minn, &maxx);     for(i=1;i<=n;++i)         ta[i] = (n - i)*(i - 1);     for(i=1;i<=m;++i)         tb[i] = (m - i)*(i - 1);     for(i=1;i<=n;++i)         for(j=1;j<=m;++j)             if(2*(i + j) >= minn && 2*(i + j) <= maxx)                 ans = (ans + (LL)ta[i]*tb[j]*6%1000000007)%1000000007;     printf("%d", ans);     return 0; }

二、其实第k是个障眼法，假设最长的长度为len，那么len－1(len-1 > 0)长的肯定存在。所以本题就是求最长上升子序列长度len，最后len-k+1和0比较，大于0输出数值否则WTF。

/**         Author: SpringHack - springhack@live.cn         Last modified: 2016-05-15 18:37:46         Filename: main.cpp         Description: Created by SpringHack using vim automatically. **/ #include <iostream>  using namespace std;  #define MAX(A,B) ((A)>(B)?(A):(B))  int a[1010], dp[1010]; int n, k;  int main() {     while (cin >> n >> k)     {         for (int i=0;i<n;++i)         {             cin >> a[i];             dp[i] = 1;             for (int j=0;j<i;++j)                 if (a[i] > a[j])                     dp[i] = MAX(dp[i],dp[j] + 1);         }         int maxn = 0;         for (int i=0;i<n;++i)             maxn = MAX(maxn,dp[i]);         maxn -= k - 1;         if (maxn > 0)             cout << maxn << endl;         else             cout << "WTF" << endl;     }     return 0; }

三、公式都会，二项式定理嘛，C(n,m)这里可以用逆元解决，逆元参见上一篇博文。不过鉴于题目数据比较弱鸡，暴力也是可以的（人家这叫杨辉三角>_<）

/**         Author: SpringHack - springhack@live.cn         Last modified: 2016-05-15 20:27:48         Filename: main.cpp         Description: Created by SpringHack using vim automatically. **/ #include <iostream>  #define N 1005 #define M 10007  using namespace std;  int f[N][N];  int main() {     int a, b, k, n, m, i, j, ans;     cin >> a >> b >> k >> n >> m;     a = a%M;     b = b%M;     for(i=1;i<=k;++i)     {         f[i][i] = f[i][0] = 1;         f[i][1] = i;     }     for(i=3;i<=k;++i)         for(j=2;j<i;++j)             f[i][j] = (f[i - 1][j] + f[i - 1][j - 1])%M;     ans = f[k][m]%M;     for(i=1;i<=n;++i)         ans = (ans*a)%M;     for(i=1;i<=m;++i)         ans = (ans*b)%M;     cout << ans << endl;     return 0; }

四、水题，直接上代码，看着代码好好思考下就懂了

/**         Author: SpringHack - springhack@live.cn         Last modified: 2016-05-15 20:45:15         Filename: main.cpp         Description: Created by SpringHack using vim automatically. **/ #include <iostream> #include <cstdio>  using namespace std;  int main() {     int i, sum;     char str[105];     while(scanf("%s", str) && str[0] != '0')     {         sum = 0;         for(i=0;str[i]!='/0';++i)         {             sum = sum*10 + str[i] - '0';             sum = sum%17;         }         printf("%s/n", sum?"0":"1");     }     return 0; }

文章发布时间为: May 21st , 2016 at 12:00 pm

最后编辑时间为: May 16th , 2016 at 12:54 pm

本文由SpringHack 创作，采用知识共享署名 4.0 国际许可协议进行许可

可自由转载、引用，但需署名作者且注明文章出处

原文 http://blog.90its.cn/archives/78/

正文到此结束