@Dmaxiya
2018-08-17T10:13:50.000000Z
字数 7405
阅读 981
Codeforces
Contests 链接:Codeforces Round #457 (Div. 2)
过题数:2
排名:447/6352
想睡懒觉,但是他必须要在 时刻起床,于是他需要提前定一个含有 数字 的时刻作为第一次闹钟响起的时刻,已经知道他每隔 分钟就会按下闹钟的“贪睡”按钮,问他第一次闹钟的时间是多少。
按照给定时刻每次往前跑 分钟,判断该时间是否含有数字 。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
int x, h, m;
int ans;
void cut_x(int &h, int &m, int x) {
m -= x;
if(m < 0) {
m += 60;
h -= 1;
if(h < 0) {
h += 24;
}
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d%d", &x, &h, &m) != EOF) {
int ans = 0;
while(h % 10 != 7 && m % 10 != 7) {
cut_x(h, m, x);
++ans;
}
printf("%d\n", ans);
}
return 0;
}
将 分成 个 相加,若不能拆分,则输出 ,否则找到 ,且字典序最大的满足条件的序列,题目保证答案的范围在 之间。
先判断是否可以用 个数字来表示 ,若可行,用大顶堆将最大值弹出,拆成两个小的进入堆,直到堆的大小为 ,以此确定 ,然后根据这个值贪心构造数列。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 63;
const int maxm = 100000 + 100;
int cnt, k;
LL n;
LL two[maxn];
int ans[maxm];
priority_queue<int> que;
void Pull(int Max, LL n) {
cnt = 0;
while(n != 0) {
LL *it = upper_bound(two, two + maxn, n);
--it;
n -= *it;
if(Max < it - two) {
for(int i = 0; i < two[it - two - Max]; ++i) {
ans[cnt++] = Max;
}
} else {
ans[cnt++] = it - two;
}
}
while(cnt != k) {
ans[cnt - 1] = ans[cnt - 1] - 1;
ans[cnt] = ans[cnt - 1];
++cnt;
}
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
two[0] = 1;
for(int i = 1; i < maxn; ++i) {
two[i] = two[i - 1] << 1;
}
while(scanf("%I64d%d", &n, &k) != EOF) {
while(!que.empty()) {
que.pop();
}
LL nn = n;
while(n != 0) {
LL *it = upper_bound(two, two + maxn, n);
--it;
que.push(it - two);
n -= *it;
if((int)que.size() == k) {
break;
}
}
if(n != 0) {
printf("No\n");
continue;
}
printf("Yes\n");
while((int)que.size() < k) {
int tmp = que.top();
que.pop();
--tmp;
que.push(tmp);
que.push(tmp);
}
int Max = que.top();
Pull(Max, nn);
for(int i = 0; i < cnt; ++i) {
if(i != 0) {
printf(" ");
}
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
如果一张带权无向图满足以下条件,它就是一张有趣的图:
- 图是连通的,含有 个顶点与 条边;
- 边权是整数且在 内;
- 从点 到点 的最短路径长度是一个质数;
- 最小生成树的路径长度和为质数;
- 图上没有自环和重边。
给定 和 ,请构造出这样的图。
按照 的顺序连边,除了 的权为 ,其他边权都为 ,边 的程度根据总长度来凑出一个质数,这条链就是最小生成树。其他边只要边权大于这个最小生成树的最大边权,就随便加。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
int v, u;
LL dis;
Node() {}
Node(int uu, int vv, LL d) {
u = uu;
v = vv;
dis = d;
}
};
int cnt, n, m;
LL mst;
LL maxlen;
Node ans[maxn];
int id[maxn];
void add(int u, int v, int d) {
ans[cnt].u = u;
ans[cnt].v = v;
ans[cnt++].dis = d;
}
bool isPrime(LL x) {
for(LL i = 2; i * i <= x; ++i) {
if(x % i == 0) {
return false;
}
}
return true;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m) != EOF) {
maxlen = 2;
id[1] = n;
for(int i = 2; i <= n; ++i) {
id[i] = i - 1;
}
cnt = 0;
add(1, n, 2);
for(int i = 2; i < n; ++i) {
add(id[i], id[i + 1], 1);
}
mst = n;
while(!isPrime(mst)) {
++ans[cnt - 1].dis;
++mst;
maxlen = max(maxlen, ans[cnt - 1].dis);
}
++maxlen;
for(int i = 1; i < n - 1; ++i) {
for(int j = i + 2; j <= n; ++j) {
if(cnt < m) {
add(id[i], id[j], maxlen);
} else {
break;
}
}
if(cnt >= m) {
break;
}
}
printf("%d %I64d\n", 2, mst);
for(int i = 0; i < cnt; ++i) {
printf("%d %d %I64d\n", ans[i].u, ans[i].v, ans[i].dis);
}
}
return 0;
}
题给一棵 个节点的树,每个节点上有一个权值 ,接下来有 次操作,按照以下输入进行相应操作:
- : 将 作为树根;
- : — 将包含有节点 和 的最小子树上的所有节点加上 ;
- : 询问以 为根的子树的所有节点的和。
对于每次询问,输出结果。
对于第 和第 种操作,就是裸的线段树构图 ,现在要考虑的是,根改变之后,节点 的根节点会如何改变。
如果记当前的根节点为 ,多画几组样例可以发现,对 两两求 , 序最大的,就是 和 在 为根时的子树的根,记为 ,对于 不在 的子树下的情况(以 为根节点),操作 和 直接对 对应的子树进行操作即可;如果 在 对应的子树下,就先对整棵树进行操作 ,再减去 所在的 的子树的贡献即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
const int Log = 25;
int root;
int n, q, cnt, u, v, command;
LL tmp, ans;
LL num[maxn];
int id[maxn], ide[maxn], rid[maxn];
int fa[Log][maxn];
vector<int> G[maxn];
LL lazy[maxn << 2], sum[maxn << 2];
void push_up(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void push_down(int rt, int len) {
if(lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1] += (len - (len >> 1)) * lazy[rt];
sum[rt << 1 | 1] += (len >> 1) * lazy[rt];
lazy[rt] = 0;
}
}
void build(int l, int r, int rt) {
lazy[rt] = 0;
if(l == r) {
sum[rt] = num[rid[l]];
return ;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
push_up(rt);
}
void add(int L, int R, LL tmp, int l, int r, int rt) {
if(L <= l && r <= R) {
lazy[rt] += tmp;
sum[rt] += (r - l + 1) * tmp;
return ;
}
push_down(rt, r - l + 1);
int m = (r + l) >> 1;
if(L <= m) {
add(L, R, tmp, l, m, rt << 1);
}
if(R > m) {
add(L, R, tmp, m + 1, r, rt << 1 | 1);
}
push_up(rt);
}
LL query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) {
return sum[rt];
}
push_down(rt, r - l + 1);
int m = (l + r) >> 1;
LL ret = 0;
if(L <= m) {
ret += query(L, R, l, m, rt << 1);
}
if(R > m) {
ret += query(L, R, m + 1, r, rt << 1 | 1);
}
return ret;
}
void dfs(int f, int x) {
id[x] = ++cnt;
rid[cnt] = x;
int len = G[x].size();
for(int i = 0; i < len; ++i) {
int pos = G[x][i];
if(pos != f) {
fa[0][pos] = x;
dfs(x, pos);
}
}
ide[x] = cnt;
}
void prepare_skip_table() {
cnt = 0;
fa[0][1] = 1;
dfs(1, 1);
for(int j = 1; j < Log; ++j) {
for(int i = 1; i <= n; ++i) {
fa[j][i] = fa[j - 1][fa[j - 1][i]];
}
}
}
int Find(int x, int y, bool flag) {
if(x == y) {
return x;
}
if(id[x] > id[y]) {
swap(x, y);
}
for(int i = Log - 1; i >= 0; --i) {
if(id[fa[i][y]] > id[x]) {
y = fa[i][y];
}
}
if(flag) {
return fa[0][y];
} else {
return y;
}
}
int Find_real_root(int a, int b, int c) {
int ret;
int ab = Find(a, b, true);
int ac = Find(a, c, true);
if(id[ab] > id[ac]) {
ret = ab;
} else {
ret = ac;
}
int bc = Find(b, c, true);
if(id[ret] < id[bc]) {
ret = bc;
}
return ret;
}
int main() {
#ifdef LOCAL
freopen("test.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false);
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; ++i) {
scanf("%I64d", &num[i]);
}
for(int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
prepare_skip_table();
build(1, n, 1);
for(int i = 0; i < q; ++i) {
scanf("%d", &command);
if(command == 1) {
scanf("%d", &u);
root = u;
} else if(command == 2) {
scanf("%d%d%I64d", &u, &v, &tmp);
int real_root = Find_real_root(u, v, root);
if(real_root == root) {
add(1, n, tmp, 1, n, 1);
} else {
if(id[real_root] < id[root] && ide[real_root] >= id[root]) {
add(1, n, tmp, 1, n, 1);
int rr = Find(real_root, root, false);
add(id[rr], ide[rr], -tmp, 1, n, 1);
} else {
add(id[real_root], ide[real_root], tmp, 1, n, 1);
}
}
} else {
scanf("%d", &u);
if(u == root) {
printf("%I64d\n", query(1, n, 1, n, 1));
} else {
if(id[u] < id[root] && ide[u] >= id[root]) {
ans = query(1, n, 1, n, 1);
int rr = Find(u, root, false);
ans -= query(id[rr], ide[rr], 1, n, 1);
} else {
ans = query(id[u], ide[u], 1, n, 1);
}
printf("%I64d\n", ans);
}
}
}
return 0;
}