一、很容易发现发现对于三个点(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)。这个矩形在rc的大矩形中出现的次数也是给定的,设矩形长为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;
}