@Dmaxiya
2018-08-17T10:23:31.000000Z
字数 8014
阅读 1141
Codeforces
Contests 链接:Codeforces Round #493 (Div. 2)
过题数:4
排名:47/5210
总共有 个袋子,第 个袋子里放 个气球,现在要把所有的袋子分成非空的两部分,要求第一部分的气球总数不等于第二部分的气球总数,输出合法的分配方案。
第一行为一个整数 ,第二行为 个整数 。
如果无法将所有袋子分成合法的两部分,输出 ,否则在第一行输出一个整数 ,表示分给第一部分的袋子数,接下去一行为 个整数,表示将编号为 的袋子分到第一部分,如果有多解输出任意一组。
输入 | 输出 | 提示 |
---|---|---|
3 1 2 1 |
2 1 2 |
第一部分有 个气球而第二部分有 个气球。 |
2 5 5 |
-1 | 只有一种分法:第一个袋子分给第一部分,第二个袋子分给第二部分,而这种分法将使得 第一部分的气球数量等于第二部分的气球。 |
1 10 |
-1 | 两部分中的任意一部分将会为空。 |
如果 ,一定输出 ,否则找出最小的数字 ,如果 ,则将这个数字分配到第一部分,否则输出 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, sum, Min;
int num[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF) {
sum = 0;
Min = 1;
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
if(num[i] < num[Min]) {
Min = i;
}
sum += num[i];
}
if(n == 1) {
printf("-1\n");
continue;
}
if(sum - num[Min] == num[Min]) {
printf("-1\n");
} else {
printf("1\n%d\n", Min);
}
}
return 0;
}
给定一个长度为 的数列,这个数列的奇数项的个数和偶数项的个数相等,将这个数列分割成多个数列,要让每个数列的奇数项个数都等于偶数项个数,如果在数列中的两个数字 和 之间分割,将花费 个比特币,问在满足花费不超过 个比特币的情况下,最多可以分割多少次。
第一行包含两个整数 和 ,第二行包含 个整数 ,其中奇数项的个数一定等于偶数项的个数。
输出满足条件的最大分割次数。
输入 | 输出 | 提示 |
---|---|---|
6 4 1 2 5 10 15 20 |
1 | 最优的分割方式是在 和 之间,分割的花费为 。 |
4 10 1 3 2 4 |
0 | 没有任何位置可以进行分割。 |
6 100 1 2 3 4 5 6 |
2 | 可以在 和 之间进行分割,花费为 。 |
首先预处理出每个可以分割的位置以及花费,将所有花费按从小到大排序,贪心地每次取花费最小的点进行分割,就能得到最多的分割次数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100 + 100;
int n, B, tmp, cnt;
int num[maxn], sum[maxn];
int *it;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &B) != EOF) {
for(int i = 0; i < n; ++i) {
scanf("%d", &num[i]);
}
tmp = 0;
cnt = 0;
for(int i = 0; i < n - 1; ++i) {
if(num[i] % 2 == 0) {
++tmp;
} else {
--tmp;
}
if(tmp == 0) {
sum[cnt++] = abs(num[i] - num[i + 1]);
}
}
sort(sum, sum + cnt);
for(int i = 1; i < cnt; ++i) {
sum[i] += sum[i - 1];
}
it = upper_bound(sum, sum + cnt, B);
printf("%d\n", it - sum);
}
return 0;
}
对一个长度为 的 字符串,可以进行以下两种操作:
- 选择其中一个子串(也可以选择整个字符串),将这个子串翻转,这将花费 元,例如:‘
- 选择其中一个子串,将这个子串中所有的 变为 ,所有 变为 ,这将花费 元,例如:。
以上操作可以以任意顺序执行,问要将一个给定的 字符串通过以上两种操作转化为全为 的字符串,最小的花费是多少?
第一行包含三个整数 ,第二行为一个长度为 的 串。
输出最少花费。
输入 | 输出 | 提示 |
---|---|---|
5 1 10 01000 |
11 | 首先你需要对子串 进行操作 ,然后对子串 进行操作 ,字符串变化过程为: 总的花费为 。 |
5 10 1 01000 |
2 | 首先你需要对子串 进行操作 ,然后对子串 进行操作 ,字符串的变化过程为: 总的花费为 |
7 2 3 1111111 |
0 | 字符串本身就是一个全为 的串,所以不需要进行任何操作。 |
通过画样例可以发现,操作 和操作 的总操作次数等于字符串中 的段数 ,且至少执行一次操作 ,所以可以从 到 枚举操作 的次数,取花费的最小值就是答案。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 300000 + 100;
bool flag;
LL n, x, y, len, cnt, ans;
char str[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%I64d%I64d%I64d", &n, &x, &y) != EOF) {
ans = 1e18;
cnt = 0;
flag = false;
scanf("%s", str);
len = strlen(str);
for(int i = 0; i <= len; ++i) {
if(str[i] != '0') {
if(flag) {
++cnt;
flag = false;
}
} else {
flag = true;
}
}
if(cnt == 0) {
printf("0\n");
continue;
}
for(LL i = 1; i <= cnt; ++i) {
ans = min(ans, i * y + (cnt - i) * x);
}
printf("%I64d\n", ans);
}
return 0;
}
在罗马数字和阿拉伯数字之间存在映射:,对于任意一个由罗马数字组成的数字,它表示的数值等于每一位对应映射的和,如:,注意这里的表达方式和一般的罗马数字的表达方式不同, 的值为 而不是 ,如果现在有一个 位的罗马数字,问这个罗马数字表示的值有几种可能的情况?
输入只包含一个整数 。
输出为一个整数,表示用 位罗马数字能够表示的不同的数字的个数。
输入 | 输出 | 提示 |
---|---|---|
1 | 4 | 可以表示的数字为:。 |
2 | 10 | 可以表示的数字为:。 |
10 | 244 |
通过暴力打表找规律到第 项可以发现,除了前 项是没有规律的,第 项开始就是一个公差为 的等差数列。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
LL n;
LL num[15] = {0, 4, 6, 10, 15, 21, 27, 33, 39, 43, 46, 48};
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
for(int i = 1; i <= 11; ++i) {
num[i] += num[i - 1];
}
while(scanf("%I64d", &n) != EOF) {
if(n <= 11) {
printf("%I64d\n", num[n]);
continue;
}
printf("%I64d\n", 292LL + 49LL * (n - 11));
}
return 0;
}
在一个 的网格中,可以给每一格方格填充红、绿、蓝中的一种颜色,则总共有 种涂色方案,问在这些方案中,至少有一行或者一列颜色相同的涂色方案数。
输入只包含一个整数 。
输出所有合法的涂色方案数对 取模的结果。
输入 | 输出 | 提示 |
---|---|---|
1 | 3 | 由于只有一行一列,因此所有涂色方案都是合法的,总共有 种涂色方案。 |
2 | 63 | 当 时,以下两种涂色方案是合法的: 而以下两种涂色方案是不合法的: |
3 | 9933 |
首先计算某几行以及某几列颜色相同的情况,如:
在这些情况中,颜色相同的所有行和列都为同一种颜色的情况会被重复计算如:
这些情况在计算行时会计算一次,计算列时又计算了一次,因此要减去这些情况。
首先来计算某几行颜色相同的情况,由容斥原理可以知道,某几行颜色相同的情况等于至少一行颜色相同的情况,减去至少两行颜色相同的情况,加上至少三行颜色相同的情况……而至少 行颜色相同的方案数为 ,因此某几行颜色相同的方案数为:
某几列的计算方式与某几行的计算方式完全相同,所以直接将上式乘 ,即可得到某几行颜色相同与某几列颜色相同的方案数的和,而接下来要减去某几行与某几列颜色完全相同的情况。
同样地,这也是一个容斥,对于每一个 行去枚举 列,就是有 行至少一列颜色相同的情况,减去有 行至少两列颜色相同的情况,加上 行至少 列颜色相同的情况……在枚举 行的时候也是同样的容斥。如果至少有 行 列的颜色完全相同,那么所有的方案数为 ,因此某几行某几列颜色完全相同的方案数为:
这个公式计算的复杂度为 ,因此需要化简,可以发现其中隐含了二项式 ,对于每个固定的 ,将关于 的项化简可以得到:
最终的结果就是:
这个公式本身的计算次数是 的,但是由于存在幂次,所以应该用快速幂将幂运算的时间复杂度降低到 ,因此总的时间复杂度为 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <ctime>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const LL MOD = 998244353;
const int maxn = 1000000 + 100;
LL n, ans;
LL inv[maxn], pro[maxn], invpro[maxn];
void Prepare_C() {
inv[1] = 1;
for(int i = 2; i < maxn; ++i) {
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}
pro[0] = invpro[0] = 1;
for(int i = 1; i < maxn; ++i) {
pro[i] = pro[i - 1] * i % MOD;
invpro[i] = invpro[i - 1] * inv[i] % MOD;
}
}
LL get_C(LL n, LL m) {
if(n < m) {
return 0;
}
return pro[n] * invpro[m] % MOD * invpro[n - m] % MOD;
}
LL fast_pow(LL x, LL n) {
LL ans;
for(ans = 1; n != 0; n >>= 1) {
if((n & 1) == 1) {
ans = (ans * x) % MOD;
}
x = (x * x) % MOD;
}
return ans;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
Prepare_C();
while(scanf("%I64d", &n) != EOF) {
ans = 0;
for(LL i = 1; i <= n; ++i) {
LL first = 1;
LL second = 1;
if(i % 2 == 0) {
first = (-1 * first % MOD + MOD) % MOD;
second = first;
}
first = 2 * first % MOD * get_C(n, i) % MOD * fast_pow(3, (n - i) * n + i) % MOD;
LL tmp = ((fast_pow(3, n - i) - 1) % MOD + MOD) % MOD;
tmp = ((fast_pow(tmp, n) - fast_pow(3, (n - i) * n)) % MOD + MOD) % MOD;
second = 3 * second % MOD * get_C(n, i) % MOD * tmp % MOD;
ans = (ans + first + second) % MOD;
}
printf("%I64d\n", ans);
}
return 0;
}