@Dmaxiya
2018-08-17T10:21:46.000000Z
字数 10714
阅读 1025
Codeforces
Contests 链接:Codeforces Round #496 (Div. 3)
过题数:5
排名:237/7632
在上楼梯的时候会一阶一阶地数,当她上一个 阶的楼梯时,她会数 ,到达第二层时,她会同样地一阶一阶地数上去,现在已经知道她数的 个数字,问她走的每一层有多少个台阶。
第一行为一个整数 ,第二行为 个整数 ,表示 数的每个数字,数据保证合法。
第一行为一个整数 ,表示 上的楼层数,第二行为 个整数 ,表示 上的每层的台阶数量。
输入 | 输出 |
---|---|
7 1 2 3 1 2 3 4 |
2 3 4 |
4 1 1 1 1 |
4 1 1 1 1 |
5 1 2 3 4 5 |
1 5 |
5 1 2 1 2 1 |
3 2 2 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 = 1000 + 100;
int n, cnt;
int num[maxn], ans[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) {
cnt = 0;
for(int i = 0; i < n; ++i) {
scanf("%d", &num[i]);
}
num[n] = 1;
for(int i = 0; i < n; ++i) {
if(num[i + 1] <= num[i]) {
ans[cnt++] = num[i];
}
}
printf("%d\n", cnt);
for(int i = 0; i < cnt; ++i) {
if(i != 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
给定两个字符串 和 ,问至少将这两个字符串从前面往后面删掉多少个字符,才能使得两个字符串相等,空字符串与空字符串也是相等的。
输入为两行字符串 和 ,且两个字符串都只包含小写字母。
输出最少需要删除的前缀字符数量。
输入 | 输出 | 提示 |
---|---|---|
test west |
2 | 应该将两个字符串都删除到只剩下 ,这样需要删除 个字符。 |
codeforces yes |
9 | 应该将两个字符串都删除到只剩下 ,第一个字符串被删了 个字符而第二个字符串被删了 个字符。 |
test yes |
7 | 应该将两个字符串都删除到空,总共要删除 个字符。 |
b ab |
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 = 200000 + 100;
int len1, len2;
char s[maxn], t[maxn];
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
while(scanf("%s%s", s, t) != EOF) {
len1 = strlen(s);
len2 = strlen(t);
int Min = min(len1, len2);
int ans = Min;
for(int i = 1; i <= Min; ++i) {
if(s[len1 - i] != t[len2 - i]) {
ans = i - 1;
break;
}
}
printf("%d\n", len1 + len2 - ans * 2);
}
return 0;
}
定义一个长度为 的序列 为好的序列,当且仅当对于序列中的每一个整数 ,都可以找到一个对应的数字 ,使得 是 的整数次幂,一个空的序列也是一个好的序列。现在给定一个长度为 的序列 ,问最少删除多少个数字,可以使这个序列成为一个好的序列。
第一行为一个整数 ,第二行为 个整数 。
输出最少要删除的数字个数。
输入 | 输出 | 提示 |
---|---|---|
6 4 7 1 5 4 9 |
1 | 删除第 个数字 ,剩下的序列 就是一个好的序列。 |
5 1 2 3 4 5 |
2 | |
1 16 |
1 | |
4 1 1 1 1023 |
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 = 120000 + 100;
int n;
LL num[maxn], two[50];
set<LL> st;
map<LL, int> mp;
map<LL, int>::iterator it, itt;
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
for(int i = 0; i <= 31; ++i) {
two[i] = (1LL << i);
}
while(scanf("%d", &n) != EOF) {
mp.clear();
st.clear();
for(int i = 0; i < n; ++i) {
scanf("%I64d", &num[i]);
++mp[num[i]];
}
for(it = mp.begin(); it != mp.end(); ++it) {
for(int j = 0; j <= 31; ++j) {
itt = mp.find(two[j] - it->first);
if(itt != mp.end()) {
if(itt->first != it->first) {
st.insert(it->first);
break;
} else {
if(itt->second != 1) {
st.insert(it->first);
break;
}
}
}
}
}
int ans = 0;
for(it = mp.begin(); it != mp.end(); ++it) {
if(st.find(it->first) == st.end()) {
ans += it->second;
}
}
printf("%d\n", ans);
}
return 0;
}
给定一个大整数,将这个大整数进行分割,使得被分割的每一部分除了 以外都不含前导零,且都能被 整除,问最多能分割成多少部分。
输入为一个正整数 , 的长度在 到 之间,最左边的数字保证不为 。
输出能够切割的合法的最大段数。
输入 | 输出 | 提示 |
---|---|---|
3121 | 2 | 一种合法的切割方式为 |
6 | 1 | 一位数字无法切割,且这个数字能被 整除,所以答案为 。 |
1000000000000000000000000000000000 | 33 | 应该在每位数字之间进行分割,这样将会得到一个 以及 个 。 |
201920181 | 4 | 一种合法的分割为 ,其中有 段数字能够被 整除。 |
先将每位数字对 取模后得到一个新的数字串,然后从前往后进行贪心,只要碰到 ,就直接进行分割,就能得到最优解。
#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 = 200000 + 100;
int len, ans;
int num[maxn];
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("%s", str) != EOF) {
len = strlen(str);
for(int i = 0; i < len; ++i) {
num[i] = (str[i] - '0') % 3;
}
ans = 0;
for(int i = 0; i < len; ++i) {
if(num[i] == 0) {
++ans;
continue;
}
if(i + 1 < len && num[i] == 2 && num[i + 1] == 1) {
++ans;
++i;
continue;
}
if(i + 1 < len && num[i] == 1 && num[i + 1] == 2) {
++ans;
++i;
continue;
}
if(i + 2 < len && num[i] == 1 && num[i + 1] == 1 && num[i + 2] == 1) {
++ans;
i += 2;
}
if(i + 2 < len && num[i] == 2 && num[i + 1] == 2 && num[i + 2] == 2) {
++ans;
i += 2;
}
}
printf("%d\n", ans);
}
return 0;
}
给定一个 的排列 ,问这个序列有多少个区间满足中位数等于 的条件。
其中中位数的定义为:对于长度为奇数的序列,将这个序列按从小到大排序后中间的数字就是中位数,对于长度为偶数的序列,将这个序列按从小到大排序后,取中间两个数中小的那个数就是中位数。
第一行为两个整数 ,第二行为 的排列 。
输出满足条件的区间的个数。
输入 | 输出 | 提示 |
---|---|---|
5 4 2 4 5 3 1 |
4 | 满足条件的区间为: 和 . |
5 5 1 2 3 4 5 |
1 | |
15 8 1 15 2 14 3 13 4 8 12 5 11 6 10 7 9 |
48 |
所有满足条件的区间一定都包含数字 ,所以这些区间的左端点一定在 左边,右端点一定在 的右边,先统计 的右边 的值,再对于 的左边的每个端点,计算有多少个右端点满足 (区间长度为奇数的情况) 以及 (区间长度为偶数的情况),将所有满足条件的区间个数求和就是答案。
#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 = 200000 + 100;
int n, m, Index;
int num[maxn], cnt[2];
map<int, int> mp;
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, &m) != EOF) {
mp.clear();
memset(cnt, 0, sizeof(cnt));
++mp[0];
for(int i = 1; i <= n; ++i) {
scanf("%d", &num[i]);
if(num[i] == m) {
Index = i;
}
if(num[i] > m) {
num[i] = 1;
} else {
num[i] = 0;
}
}
for(int i = Index + 1; i <= n; ++i) {
++cnt[num[i]];
++mp[cnt[0] - cnt[1]];
}
memset(cnt, 0, sizeof(cnt));
LL ans = mp[0] + mp[-1];
for(int i = Index - 1; i > 0; --i) {
++cnt[num[i]];
if(mp.find(cnt[1] - cnt[0]) != mp.end()) {
ans += mp[cnt[1] - cnt[0]];
}
if(mp.find(cnt[1] - cnt[0] - 1) != mp.end()) {
ans += mp[cnt[1] - cnt[0] - 1];
}
}
printf("%I64d\n", ans);
}
return 0;
}
给定一个长度为 的序列 ,问这个序列有多少个区间满足中位数等于 的条件。中位数的定义同 E1 题。
第一行为两个整数 ,第二行为 个整数 。
输出满足条件的区间的个数。
输入 | 输出 | 提示 |
---|---|---|
5 4 1 4 5 60 4 |
8 | 满足条件的区间为:。 |
3 1 1 1 1 |
6 | |
15 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 |
97 |
如果将所有大于等于 的数字标记为 ,所有小于 的数字标记为 ,那么对于任意一个区间,这个区间的中位数大于等于 当且仅当区间和大于 ,对 做相同的操作,则答案为 。
求解 的方法为:对这个只包含 和 的数组,从前往后扫描,扫描到第 个数字的前缀和 时,统计有多少个 满足条件 ,即有多少个区间和大于 ,统计满足条件的前缀和个数可以用树状数组维护。
#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 = 200000 + 100;
LL n, m, nn, Sum;
LL num[maxn], numtmp[maxn];
LL sum[maxn << 1];
int id(int x) {
return x + maxn;
}
int lowbit(int x) {
return x & (-x);
}
void update(int Index, int x) {
while(Index <= nn) {
sum[Index] += x;
Index += lowbit(Index);
}
}
int query(int Index) {
int ret = 0;
while(Index != 0) {
ret += sum[Index];
Index -= lowbit(Index);
}
return ret;
}
LL solve(LL m) {
memset(sum, 0, sizeof(sum));
LL ret = 0;
Sum = 0;
update(id(0), 1);
for(int i = 1; i <= n; ++i) {
int tmp = 1;
if(num[i] < m) {
tmp = -1;
}
Sum += tmp;
ret += query(id(Sum) - 1);
update(id(Sum), 1);
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
nn = maxn * 2 - 1;
while(scanf("%I64d%I64d", &n, &m) != EOF) {
for(int i = 1; i <= n; ++i) {
scanf("%I64d", &num[i]);
}
printf("%I64d\n", solve(m) - solve(m + 1));
}
return 0;
}
在一个 个节点 条边的无向图中,选出 条边,使得这些边能构成一个节点为 的树,假设树上每个节点到节点 的最短路为 ,则要使构造出来的树满足 最小,输出 中选边的方案,如果总的合法方案数少于 种,则直接输出所有方案。
第一行为三个整数 ,接下去 行每行两个整数 ,表示图上的 条边,图保证连通。
第一行为将要输出的方案数 ,如果总的方案数大于 ,则只要输出任意 个方案,否则输出所有方案,接下去 行每行为一个 字符串,第 位为 表示不选第 条边,为 表示选择这条边,数据保证 。
输入 | 输出 |
---|---|
4 4 3 1 2 2 3 1 4 4 3 |
2 1110 1011 |
4 6 3 1 2 2 3 1 4 4 3 2 4 1 3 |
1 101001 |
5 6 2 1 2 1 3 2 4 2 5 3 4 3 5 |
2 111100 110110 |
首先对这张图从 开始进行一次 ,计算每个点到达 的最短距离 ,对于第 个节点,查找与其相连的所有节点中, 的节点,这些节点一定可以作为节点 的父节点(在生成的树中),每个节点的前缀节点个数为 ,则所有的方案数为 ,注意所有方案数可能会爆 。
#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 = 200000 + 100;
const int maxm = 1000000 + 100;
struct Node {
int pos, Index;
Node() {}
Node(int p, int I) {
pos = p;
Index = I;
}
};
int INF;
LL ans;
int n, m, k, u, v;
int dis[maxn];
char str[maxm];
vector<Node> G[maxn], pre[maxn];
queue<int> que;
void bfs() {
dis[1] = 0;
que.push(1);
while(!que.empty()) {
int tmp = que.front();
que.pop();
int len = G[tmp].size();
for(int i = 0; i < len; ++i) {
int pos = G[tmp][i].pos;
if(dis[pos] == INF) {
dis[pos] = dis[tmp] + 1;
que.push(pos);
}
}
}
}
void dfs(int depth) {
if(depth == n + 1) {
printf("%s\n", str + 1);
--ans;
return ;
}
int len = pre[depth].size();
for(int i = 0; i < len; ++i) {
str[pre[depth][i].Index] = '1';
dfs(depth + 1);
str[pre[depth][i].Index] = '0';
if(ans <= 0) {
return ;
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
ios::sync_with_stdio(false);
memset(&INF, 0x3f, sizeof(INF));
while(scanf("%d%d%d", &n, &m, &k) != EOF) {
ans = 1;
memset(str, '0', sizeof(str));
str[m + 1] = '\0';
for(int i = 1; i <= n; ++i) {
dis[i] = INF;
G[i].clear();
pre[i].clear();
}
for(int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(Node(v, i));
G[v].push_back(Node(u, i));
}
bfs();
for(int i = 2; i <= n; ++i) {
int len = G[i].size();
for(int j = 0; j < len; ++j) {
int pos = G[i][j].pos;
if(dis[pos] == dis[i] - 1) {
pre[i].push_back(Node(pos, G[i][j].Index));
}
}
}
for(int i = 2; i <= n; ++i) {
ans *= (LL)pre[i].size();
if(ans > k) {
ans = k;
break;
}
}
ans = min(ans, (LL)k);
printf("%I64d\n", ans);
dfs(2);
}
return 0;
}