这场比赛+131不是灰名了\^.^/好评
----------------------------------------------------------------------------------------------------------------------
A. Initial Bet
开始有5个人，每人有b个金币（不为零），每一枚金币可以从一个人传到另一个人，给出最后每人的金币数，求最开始每人的金币数，如果不存在这种状态，输出-1
看金币和能不能被5整除，且金币和不为零
#include <cstdio>
#include <cstring>
const int N = 100000;
#define ll long long;
int main() {
//freopen("in.txt", "r", stdin);
int a[100];
int sum = 0;
for (int i = 0; i < 5; i++) {
scanf("%d", &a[i]);
sum += a[i];
}
if (sum%5==0&&sum) printf("%d\n", sum/5);
else printf("-1\n");
return 0;
}
B. Random Teams
给出n个人，要把他们分成m个队且每队至少1个人，同一个队内的两个人能成为朋友，求最多和最少有多少对朋友。
解法：贪心 求最大时 m-1各队每队1人，最后一个队n-m+1人，最多朋友对数：Cn-m+1 2 = （n-m+1)*(n-m)/2
最小的人数 贪心的方法是尽量使每个队的人数平均，尽管不知道为什么这么贪心是对的。。。
最开始贪错了，想平均分，剩的给同一个人 17---> 5 5 7 但是明显 17 ----> 6 6 5 更小 于是。。。17%3 == 2，有两个人要+1（而不是有一个人+2），剩下的一个人按17/3 == 5算，加起来就好了
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100000;
#define ll long long
int main() {
ll n, m;
while (scanf("%lld%lld",&n, &m) != EOF) {
ll maxans = (n-m)*(n-m+1)/2;
ll aver = n/m, left = n%m;
ll minans = left*((aver+1)*aver/2);
minans += (m-left)*(aver*(aver-1)/2);
printf("%lld %lld\n", minans, maxans);
}
return 0;
}
给出r，b，g分别代表红色，蓝色，绿色气球的数量，每三个气球可以布置一张桌子，要求同一个桌子上的三个气球颜色不能全一样，求最多能布置多少张桌子
读完了感觉是贪心，感觉一堆if就好了剩了40min+硬是没写出来，不过房间里大多数写出来的都fst了哈哈哈（好邪恶）
先写下学到的正确思路吧，三种颜色的气球我们先排好序
-------------------------------------------------------- ---------------- -------
---------------------------- 如果最多的气球数目大等于其他两个的和的二倍，
---------------------------- 就把最多的平均折成两部分，这时候最大值取
----------------------- 决于较小的两个的和
注：只有最大的才有可能大于其他两个的二倍
如果我们有两种颜色， 那么我们可以通过合理的搭配尽可能多的把他们用上
----------------------------- ------------------------
------------------ 设长的为X，短的为Y，
------------ ------ （2X+Y）紫色+（X+2Y）蓝色 = a+b
------------ ----- 结果为 X+Y = （a+b）/ 3
如果是三种颜色可以把最少的那种加到中间的那种中变成两种或者分别加到中间的和长的使两者间较大的小于较小的的2倍， 结果为 （a+b+c)/3
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int main() {
LL a, b, c;
scanf("%lld%lld%lld", &a, &b, &c);
LL minn = min(a, min(b, c));
LL maxx = max(a, max(b, c));
LL mid = a+b+c -maxx-minn;
if (maxx >= 2*(minn+mid))
printf("%lld\n", minn+mid);
else
printf("%lld\n", (mid+maxx+minn)/3);
return 0;
}
建造一个有r个红木块，g个绿木块的“红绿塔”。红绿塔的最下层有k个木块，上一层有k-1个木块……直到最上层有一个木块，每层的木块颜色要相同，求这些木块能堆出的最高的“红绿塔”的种数。（r+g个木块不一定全都要用上）
很暴力的DP方法：用DP[k]表示用到k个红色木块时的方法数，从高度1开始枚举，枚举到第i层（第i层全用红色木块）时，第1 —— i-1层一共会用到[0,r-i]个红色木块，那么有DP[i+j] = DP[i+j] + DP[j], 最后从至少需要的红色木块数（塔需要的木块数-绿色木块数）到能用的最多红色木块数（r）求方法数的总和
#include <cstdio>
const int MOD = (int)1e9+7;
#define MAX(A,B) ({ __typeof__(A) __a = (A); __typeof__(B) __b = (B); __a > __b ? __a : __b; })
int dp[201000];
int main() {
int r, g;
scanf("%d%d", &r, &g);
int h = 1;
while (h*(h+1)/2 <= r+g) h++;
h--;
dp[0] = 1;
for (int i = 1; i <= h; i++) {
for (int j = r-i; j >= 0; j--) {
dp[i+j] += dp[j];
if (dp[i+j] >= MOD) dp[i+j] -= MOD;
}
}
int ans = 0;
for (int i = MAX(h*(h+1)/2-g,0); i <= r; i++) {
ans += dp[i];
if (ans >= MOD) ans -= MOD;
}
printf("%d\n", ans);
return 0;
}
cf的话。。。每场能4题就很满足啦23333