题目链接在这里
给定矩阵的两个点,判断正方形是否存在,存在则打印剩余的两个顶点。
注意按三种情况处理就可以了。
int main()
{
int x[4],y[4];
cin >> x[0] >> y[0] >> x[1] >> y[1];
//vertical
if (x[0] == x[1])
{
x[2] = x[3] = x[0] + y[1] - y[0];
y[2] = y[0];
y[3] = y[1];
}
//horizontal
else if (y[0] == y[1])
{
y[2] = y[3] = y[0] + x[1] - x[0];
x[2] = x[0];
x[3] = x[1];
}
else if (abs(x[0] - x[1]) == abs(y[0] - y[1]))
{
x[2] = x[1];
y[2] = y[0];
x[3] = x[0];
y[3] = y[1];
}
else
{
cout << -1 << endl;
return 0;
}
cout << x[2] << " "
<< y[2] << " "
<< x[3] << " "
<< y[3] << endl;
return 0;
}
要求得到最大的差,因此只要求出最大值和最小值就可以了。
再次遍历分别得到个数相乘就是组合数。
注意最大值最小值相等的情况,即所有花的beauty完全相等。此时组合数为C(n,2)。
n的范围[2,2*1e5],n*(n - 1)可能会超int范围,要用long long。
int main()
{
LL n;
LL b[200000] = {0};
cin >> n;
for (LL i = 0; i < n; ++i)
cin >> b[i];
LL maxb = max(b[0], b[1]);
LL minb = min(b[0], b[1]);
for (LL i = 2; i < n; ++i)
{
maxb = max(b[i], maxb);
minb = min(b[i], minb);
}
LL max_cnt = 0, min_cnt = 0;
for (LL i = 0; i < n; ++i)
{
if (b[i] == maxb)
max_cnt++;
if (b[i] == minb)
min_cnt++;
}
LL cnt = max_cnt * min_cnt;
if (maxb == minb)
{
cnt = n * (n - 1) / 2;
}
cout << (maxb - minb) << " " << cnt << endl;
return 0;
}
题目意思为有k辆车,n个学生做d天,能否使得没有任何学生会跟另外一个学生一直坐一辆车。
k辆车d天的话,一共有k**d种排列,只要排列数≤n即可。
数值的范围: 1≥n,d≤1000 1≥k≤1000
注意两点:
n最大为1000,因此计算k**d过程中能够大于该值就可以返回了,否则会越界。
如何打印全排列,我用的是递归的办法。
例子后面贴了另外一种思路更清楚办法
typedef long long LL;
LL n,k,d, stu;
int a[1001][1001] = {0};
int b[1001];
void f(int day)
{
if (day == d)
{
for (int i = 0; i < d; ++i)
a[stu][i] = b[i];
stu++;
if (stu == n)
return;
}
else if (day < d)
{
for (int i = 1; i <= k; ++i)
{
b[day] = i;
f(day + 1);
if (stu == n)
return;
}
}
}
int main()
{
cin >> n >> k >> d;
int tmp = 1;
for (int i = 0; i < d; ++i)
{
tmp *= k;
if (tmp >= n)
break;
}
if (tmp >= n)
{
f(0);
for (int i = 0; i < d; ++i)
{
for (int j = 0; j < n; ++j)
{
cout << a[j][i] << " ";
}
cout << endl;
}
}
else
{
cout << -1 << endl;
}
return 0;
}
一种比较清晰的打印全排列的方式是看做k进制,位数为d。
f/g分别是两种表现,本质相同
具体看程序,打印前20个排列:
int n,k,d;
void f()
{
for (int m = 0; m < n; ++m)
{
//直接计算m的k进制表示
int j = m;
vector<int> v;
while (j)
{
v.push_back(j % k);
j /= k;
}
for (int i = 0; i < d - v.size(); ++i)
{
cout << 1 << " ";
}
for (int i = v.size() - 1; i >= 0; --i)
{
cout << v[i] + 1 << " ";
}
cout << endl;
}
}
int a[1000][1000];
void g()
{
//i = 0可以单独稍后输出
for (int i = 1; i <= n; ++i)
{
//根据i-1的k进制表示+1得到i的k进制表示
for (int j = 0; j < d; ++j)
{
a[i][j] = a[i - 1][j];
}
for (int j = d - 1; j >= 0; --j)
{
a[i][j] = (a[i][j] + 1) % k;
if (a[i][j])
break;
}
for (int j = 0; j < d; ++j)
cout << a[i][j] + 1 << " ";
cout << endl;
}
}
int main()
{
n = 20; k = 4; d = 5;
cout << "===================================" << endl;
f();
cout << "===================================" << endl;
g();
cout << "===================================" << endl;
return 0;
}
PREVIOUScodeforces Contest 454