我是靠谱客的博主 眼睛大小丸子，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 112 (Rated for Div. 2) 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
题目链接: http://codeforces.com/contest/1555
A. PizzaForces
solve: gcd是120，但是要处理240之内的最优情况，因为121就不是120+1。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int mx = 3e2 + 10;
int sum[mx];
int main(){
memset(sum, inf, sizeof(sum));
sum[0] = 0;
for (int i=1; i < mx; i++){
if (i>=6)
sum[i] = min(sum[i-6]+15, sum[i]);
if (i>=8)
sum[i] = min(sum[i-8]+20, sum[i]);
if (i>=10)
sum[i] = min(sum[i-10]+25, sum[i]);
}
for (int i=mx-2; i; i--)
sum[i] = min(sum[i], sum[i+1]);
int t;
scanf("%d",&t);
while(t--) {
ll n;
scanf("%lld",&n);
if (n <= 240) {
printf("%dn",sum[n]);
} else {
ll a = n / 120 - 1;
ll b = n % 120 + 120;
ll ans = a * 300 + sum[b];
printf("%lldn", ans);
}
}
return 0;
}
B - Two Tables
solve: 往四个方向平移，讨论四种情况即可。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int mx = 3e2 + 10;
int sum[mx];
int main(){
int t;
scanf("%d",&t);
while(t--) {
int W,H;
int x1,y1,x2,y2;
int w,h;
scanf("%d%d",&W,&H);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
scanf("%d%d",&w,&h);
int ans = 1e9;
int w1,h1;
w1 = W; h1 = H - y2;
if (h - h1 <= y1)
ans = min(ans, max(0, h - h1));
//if (W >= h)
//ans = min(ans, max(0, w - h1));
h1 = y1;
if (h - h1 <= H -y2)
ans = min(ans, max(0, h - h1));
//if (W >= h)
//ans = min(ans, max(0, w - h1));
w1 = x1, h1 = H;
if (w - w1 <= W - x2)
ans = min(ans, max(0, w - w1));
//if (H >= w)
//ans = min(ans, max(0, h - w1));
w1 = W - x2;
if (w - w1 <= x1)
ans = min(ans, max(0, w - w1));
//if (H >= w)
//ans = min(ans, max(0, h - w1));
if (ans == 1e9)
puts("-1");
else
printf("%.6lfn", (double)ans);
}
return 0;
}
C - Coin Rows
sovle: 暴力枚举Alice的走法，最后Bob要么从第一行一直走到尾，要么到第二行一直走到尾。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int mx = 1e5 + 10;
int arrays[2][mx];
int pre[mx],suf[mx];
int main(){
int t;
scanf("%d",&t);
while(t--) {
int m;
scanf("%d",&m);
int sums[2] = {0,0};
suf[m+1] = 0;
for (int i=0;i<2;i++) {
for(int j=1;j<=m;j++) {
scanf("%d",arrays[i]+j);
sums[i] += arrays[i][j];
if (i==0)
pre[j] = pre[j-1] + arrays[0][j];
}
}
for (int i=m; i; i--)
suf[i] = suf[i+1] + arrays[1][i];
int ans = 1e9 + 7;
for (int i=1;i<=m;i++) {
int res = 0;
res = max(res, sums[0] - pre[i]);
res = max(res, sums[1] - suf[i]);
ans = min(ans, res);
}
printf("%dn", ans);
}
return 0;
}
D - Say No to Palindromes
sovle: 要想保证不出现回文子串，那么就有a[i+3] == a[i]，所以只要知道前面三个字符是啥，后面就都一样了，又因为3个字符的排列只有六种，然后再用前缀和处理一起求区间的，这里前缀和又要考虑偏移，也就是三种情况，最后是18种情况。预处理一下就可以了。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
const int mx = 2e5 + 10;
char str[mx];
int ans[3][6][mx];
int main(){
int n,m;
scanf("%d%d",&n,&m);
scanf("%s", str+1);
for (int j=1;j<=min(n,3);j++) {
for (int i=j;i<=n;i++) {
ans[j-1][0][i] = ans[j-1][0][i-1];
ans[j-1][1][i] = ans[j-1][1][i-1];
ans[j-1][2][i] = ans[j-1][2][i-1];
ans[j-1][3][i] = ans[j-1][3][i-1];
ans[j-1][4][i] = ans[j-1][4][i-1];
ans[j-1][5][i] = ans[j-1][5][i-1];
if ((i-j) % 3 == 0) {
if (str[i] != 'a') {
ans[j-1][0][i]++;
ans[j-1][1][i]++;
}
if (str[i] != 'b') {
ans[j-1][2][i]++;
ans[j-1][3][i]++;
}
if (str[i] != 'c') {
ans[j-1][4][i]++;
ans[j-1][5][i]++;
}
} else if ((i-j) % 3 == 1) {
if (str[i] != 'a') {
ans[j-1][2][i]++;
ans[j-1][4][i]++;
}
if (str[i] != 'b') {
ans[j-1][0][i]++;
ans[j-1][5][i]++;
}
if (str[i] != 'c') {
ans[j-1][1][i]++;
ans[j-1][3][i]++;
}
} else {
if (str[i] != 'a') {
ans[j-1][3][i]++;
ans[j-1][5][i]++;
}
if (str[i] != 'b') {
ans[j-1][1][i]++;
ans[j-1][4][i]++;
}
if (str[i] != 'c') {
ans[j-1][0][i]++;
ans[j-1][2][i]++;
}
}
}
}
while (m--) {
int x ,y;
scanf("%d%d", &x, &y);
int z = (x-1) % 3;
int ret = 1e9 + 7;
ret = min(ret, ans[z][0][y] - ans[z][0][x-1]);
ret = min(ret, ans[z][1][y] - ans[z][1][x-1]);
ret = min(ret, ans[z][2][y] - ans[z][2][x-1]);
ret = min(ret, ans[z][3][y] - ans[z][3][x-1]);
ret = min(ret, ans[z][4][y] - ans[z][4][x-1]);
ret = min(ret, ans[z][5][y] - ans[z][5][x-1]);
printf ("%dn", ret);
}
return 0;
}
E - Boring Segments
sovle:按value排个序，然后发现具有单调性，双指针扫一下，拿个线段树维护一下。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
const int mx = 3e5 + 10;
struct node {
int l, r;
int w;
bool operator < (const node& a) {
return w < a.w;
}
}s[mx];
int minv[mx<<3];
int lazy[mx<<3];
void update(int l, int r,int rt, int L,int R, int v)
{
if (L <= l && R >= r) {
lazy[rt] += v;
minv[rt] += v;
return;
}
int mid = (l + r) >> 1;
if (lazy[rt]) {
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
minv[rt<<1] += lazy[rt];
minv[rt<<1|1] += lazy[rt];
lazy[rt] = 0;
}
if (L <= mid)
update(lson, L, R, v);
if (R > mid)
update(rson, L, R, v);
minv[rt] = min(minv[rt<<1], minv[rt<<1|1]);
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) {
scanf("%d%d%d", &s[i].l, &s[i].r, &s[i].w);
}
sort(s, s+n);
int l = 0, r = 0;
while (!minv[1]) {
update(1, m-1, 1, s[r].l, s[r].r-1, 1);
r++;
}
int ans = s[r-1].w - s[l].w;
while (l < r) {
update(1, m-1, 1, s[l].l, s[l].r-1, -1);
l++;
while (!minv[1] && r < n) {
update(1, m-1, 1, s[r].l, s[r].r-1, 1);
r++;
}
if (minv[1])
ans = min(ans, s[r-1].w - s[l].w);
}
printf("%dn", ans);
return 0;
}
F - Good Graph
sovle: 首先可以推出以下2个结论
(1)如果一个环的weight是1，那么把这个环分成两半一半是weight是1，另一半肯定是0。由此推出如果两个点u,v可以经过一个环，那么u,v形成的简单环里必有一个weight为。所以不能加u,v边。
(2)假设u所在的图和v所在的图不连通，那么必然可以加u,v这条边
根据第二个结论可以先把成环的边先不考虑，把不成环的边先加进来，那么就会形成若干颗不连通的树，然后我们再把成环的边放进来考虑。设一个dis[u]为树的根到达节点u的weight，那么这个边能加入这棵树必须满足结论(1)以及dis[u]+dis[v]-2*dis[LCA(u,v)]+w(u,v) % 2 == 1,也就是dis[u]+dis[v]+w(u,v) % 2 == 1,这个可以O(1)求得，至于结论(1)可以通过将已经成环的路径染色，然后求u,v父边染色的总和- 2 * LCA(u,v)父边被染色的总和，如果大于0，说明u,v路径上存在成环的边，所以不能加入。时间复杂度大概是(n * long(n) + m*log(n))，不过使用倍增+树状常数过大容易被卡(反正我没过)。另一种更新方法用树链剖分可能也行，还有一种方法是"拆"树，也就可以看做是k个点的环上的边都删除，生成了k颗新的树，这k颗新的树间的节点不能相连。看上去很复杂，实际用线段树更新一下每个节点最近一个父节点在环上的是哪个，用dfs序表示就是保存最大的父节点值，然后只要看u,v两个父节点是否不同就可以了。这里给出倍增+树状和线段树的做法。
倍增+树状:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
const int mx = 3e5 + 10;
struct node {
int first;
int second;
int flag;
node (int f, int s, int f1): first(f), second(s), flag(f1)
{}
node () {}
}s[mx<<1];
bool ans[mx<<1];
bool vis[mx];
vector <node> vec[mx];
int refa[mx];
int deep[mx];
int val[mx];
int sum[mx];
int L[mx], R[mx];
int lca[mx][20];
int siz;
int n,m;
int find(int x) {
return x == refa[x]? x : find(refa[x]);
}
void dfs(int u, int v) {
L[v] = ++siz;
vis[v] = 1;
lca[v][0] = u;
deep[v] = deep[u] + 1;
for (int i=1;i < 20;i++)
lca[v][i] = lca[lca[v][i-1]][i-1];
for (auto sub: vec[v]) {
int son = sub.first;
int w = sub.second;
if (vis[son])
continue;
val[son] = val[v] + w;
dfs(v, son);
}
R[v] = siz;
}
int get_sum(int x) {
int ans = 0;
while (x) {
ans += sum[x];
x -= x&(-x);
}
return ans;
}
void add(int x, int v) {
while (x <= n) {
sum[x] += v;
x += x&(-x);
}
}
int LCA(int u,int v){
if(deep[u]<deep[v]) swap(u,v);
int i = 19,j;
for(j=i;j>=0;j--)
if((deep[u]-(1<<j))>=deep[v])
u=lca[u][j];//使u和v相同深度
if(u==v) return u;
for(j=i;j>=0;j--){
if(lca[u][j]!=lca[v][j]){//不断逼近
u=lca[u][j];
v=lca[v][j];
}
}
return lca[u][0];
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++) {
refa[i] = i;
}
for (int i=0;i<m;i++) {
scanf("%d%d%d",&s[i].first,&s[i].second,&s[i].flag);
int u = s[i].first,v = s[i].second,x = s[i].flag;
int rfu = find(u);
int rfv = find(v);
if (rfu != rfv) {
refa[rfv] = rfu;
vec[u].push_back(node(v,x,1));
vec[v].push_back(node(u,x,1));
ans[i] = 1;
s[i].flag = -1;
}
}
for (int i=1;i<=n;i++)
if(!vis[i])
dfs(i, i);
for (int i=0;i<m;i++) {
if (s[i].flag == -1)
continue;
int u = s[i].first, v = s[i].second, x = s[i].flag;
int cnt = val[u] + val[v] + x;
if ((cnt & 1) == 0)
continue;
int fuv = LCA(u, v);
if (get_sum(L[u]) + get_sum(L[v]) > 2*get_sum(L[fuv]))
continue;
while (u != fuv) {
add(L[u], 1);
add(R[u] + 1, -1);
u = lca[u][0];
}
while (v != fuv) {
add(L[v], 1);
add(R[v] + 1, -1);
v = lca[v][0];
}
ans[i] = 1;
}
for (int i=0;i<m;i++)
puts(ans[i]?"YES":"NO");
return 0;
}"拆"树做法:
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
typedef long long ll;
const int mx = 3e5 + 10;
struct node {
int first;
int second;
int flag;
node (int f, int s, int f1): first(f), second(s), flag(f1)
{}
node () {}
}s[mx<<1];
bool ans[mx<<1];
bool vis[mx];
vector <node> vec[mx];
int refa[mx];
int size[mx];
int deep[mx];
int val[mx];
int up[mx];
int L[mx], R[mx];
int belong[mx<<2];
int lazy[mx<<2];
int siz;
int n,m;
int find(int x) {
return x == refa[x]? x : find(refa[x]);
}
void dfs(int u, int v) {
L[v] = ++siz;
vis[v] = 1;
for (auto sub: vec[v]) {
int son = sub.first;
if (vis[son])
continue;
dfs(v, son);
}
R[v] = siz;
}
void merge(int u, int v)
{
up[v] = u;
deep[v] = deep[u] + 1;
for (auto sub: vec[v]) {
int son = sub.first;
int w = sub.second;
if (son == u)
continue;
val[son] = val[v] + w;
merge(v, son);
}
}
void update(int l,int r,int rt,int L,int R,int v)
{
if (L<=l&&R>=r) {
lazy[rt] = max(lazy[rt], v);
belong[rt] = max(belong[rt], lazy[rt]);
return ;
}
int mid = (l + r) >> 1;
if (lazy[rt]) {
lazy[rt<<1] = max(lazy[rt<<1], lazy[rt]);
lazy[rt<<1|1] = max(lazy[rt<<1|1], lazy[rt]);
belong[rt<<1] = max(belong[rt<<1], lazy[rt]);
belong[rt<<1|1] = max(belong[rt<<1|1], lazy[rt]);
lazy[rt] = 0;
}
if (L <= mid)
update(lson, L, R, v);
if (R > mid)
update(rson, L, R, v);
belong[rt] = max(belong[rt<<1], belong[rt<<1|1]);
}
int query(int l, int r, int rt, int q)
{
if (l == r) {
return belong[rt];
}
int mid = (l + r) >> 1;
if (lazy[rt]) {
lazy[rt<<1] = max(lazy[rt<<1], lazy[rt]);
lazy[rt<<1|1] = max(lazy[rt<<1|1], lazy[rt]);
belong[rt<<1] = max(belong[rt<<1], lazy[rt]);
belong[rt<<1|1] = max(belong[rt<<1|1], lazy[rt]);
lazy[rt] = 0;
}
if (q <= mid)
return query(lson, q);
return query(rson, q);
}
int main() {
scanf("%d%d", &n, &m);
for (int i=1;i<=n;i++) {
size[i] = 1;
refa[i] = i;
up[i] = i;
deep[i] = 1;
}
for (int i=0;i<m;i++) {
scanf("%d%d%d",&s[i].first,&s[i].second,&s[i].flag);
int u = s[i].first,v = s[i].second,x = s[i].flag;
int rfu = find(u);
int rfv = find(v);
if (rfu != rfv) {
if (size[rfu] < size[rfv]) {
swap(u, v);
swap(rfu, rfv);
}
refa[rfv] = rfu;
size[rfu] += size[rfv];
val[v] = val[u] + x;
merge(u, v);
vec[u].push_back(node(v,x,1));
vec[v].push_back(node(u,x,1));
ans[i] = 1;
s[i].flag = -1;
}
}
for (int i=1;i<=n;i++)
if(!vis[i]) {
int fi = find(i);
dfs(fi, fi);
}
for (int i=0;i<m;i++) {
if (s[i].flag == -1)
continue;
int u = s[i].first, v = s[i].second, x = s[i].flag;
int qu = query(1, n, 1, L[u]);
int qv = query(1, n, 1, L[v]);
if (qu != qv)
continue;
int cnt = val[u] + val[v] + x;
if ((cnt & 1) == 0)
continue;
int du = u, dv = v;
while (du != dv) {
if (deep[du] > deep[dv]) {
update(1, n, 1, L[du], R[du], L[du]);
du = up[du];
} else {
update(1, n, 1, L[dv], R[dv], L[dv]);
dv = up[dv];
}
}
ans[i] = 1;
}
for (int i=0;i<m;i++)
puts(ans[i]?"YES":"NO");
return 0;
}最后
以上就是眼睛大小丸子为你收集整理的Educational Codeforces Round 112 (Rated for Div. 2) 题解的全部内容，希望文章能够帮你解决Educational Codeforces Round 112 (Rated for Div. 2) 题解所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[luogu P1495] 【模板】中国剩余定理(CRT)/曹冲养猪题目解题思路代码](/uploads/reation/bcimg13.png)
发表评论 取消回复