Educational Codeforces Round 58 (Rated for Div. 2) (题解)

C题卡了一个小时, 又被教育场教育了...

A. Minimum Integer

大意:求不在$[l,r]$范围内的最小被$d$整除的数

模拟

#include <iostream>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

int main() {
    int t;
    scanf("%d", &t);
    REP(i,1,t) {
        int l,r,d;
        scanf("%d%d%d", &l, &r, &d);
        if (d<l) printf("%d\n",d);
        else printf("%d\n", r/d*d+d);
    }
}

B. Accordion

大意: 给定字符串, 可以删除任意字符, 求最长的的手风琴, 手风琴类似于$[::],[:|:],[:||:],[:|||:]$

直接求出最左端$[:$和最右端$:]$, 再加上中间$|$就行了

#include <iostream>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 5e5+10;
char s[N];
int f[N];

int main() {
    scanf("%s", s+1);
    int n = strlen(s+1);
    REP(i,1,n) f[i]=f[i-1]+(s[i]==‘|‘);
    int L = 0, R = 0;
    REP(i,1,n) {
        if (!L&&s[i]==‘[‘) L = i;
        if (L&&s[i]==‘:‘) {
            L = i;
            break;
        }
    }
    PER(i,1,n) {
        if (!R&&s[i]==‘]‘) R = i;
        if (R&&s[i]==‘:‘) {
            R = i;
            break;
        }
    }
    if (!L||L>=R) return puts("-1"),0;
    printf("%d\n",4+f[R]-f[L]);
}

C. Division and Union

大意:给定n个区间, 求划分为两个非空集合, 集合间任意两区间无公共点

注意到只需要找到所有区间的一个分界点$x$即可, 即$x$处无区间覆盖

然后将$x$左端划为一个集合, 右端划为一个集合

可以离散化后差分来覆盖区间

#include <iostream>
#include <algorithm>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
const int N = 5e5+10;
char s[N];
int n;
int L[N], R[N], f[N], c[N], q[N];

int id(int x) {
    return lower_bound(f+1,f+1+*f,x)-f;
}

void work() {
    scanf("%d", &n);
    *f = 0;
    REP(i,1,n) {
        scanf("%d%d", L+i, R+i);
        L[i]*=2, R[i]*=2;
        f[++*f] = L[i];
        f[++*f] = L[i]+1;
        f[++*f] = R[i];
        f[++*f] = R[i]+1;
    }
    sort(f+1,f+1+*f),*f=unique(f+1,f+1+*f)-f-1;
    *q = 0;
    REP(i,1,n) {
        ++c[id(L[i])],--c[id(R[i]+1)];
        q[++*q] = id(L[i]);
        q[++*q] = id(R[i]+1);
    }
    sort(L+1,L+1+n);
    int sum = 0, ok = 0;
    REP(i,1,*f) {
        sum += c[i];
        if (!sum) {
            int t = *lower_bound(L+1,L+1+n,f[i]);
            if (t>f[i]) {
                REP(j,1,n) {
                    printf("%d ",R[j]<f[i]?1:2);
                }
                ok = 1;
                printf("\n");
                break;
            }
        }
    }
    if (!ok) puts("-1");
    REP(i,1,*q) c[q[i]] = 0;
}

int main() {
    int t;
    scanf("%d", &t);
    REP(i,1,t) work();
}

D. GCD Counting

大意: 给定树, 每个结点有一个值, 求树上最长路径, 要求满足路径上结点的总$gcd>1$

这题最后调了半天发现是子树间转移多加了1....

直接对每个结点开$map$暴力转移$gcd$, $dp[x][y]$表示到$x$结点$gcd=y$时的最大长度

转移时再暴力统计一下子树之间两条链的最大值即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define x first
#define y second
using namespace std;

int gcd(int x, int y) {return y?gcd(y,x%y):x;}

const int N = 5e5+10;
int n, ans;
int a[N];
vector<int> g[N];
map<int,int> dp[N];

void dfs(int x, int fa) {
    for (int y:g[x]) if (y!=fa) {
        dfs(y,x);
        //先考虑子树间转移
        for (auto f1:dp[y]) {
            int g1 = gcd(f1.x,a[x]);
            if (g1<=1) continue;
            for (auto f2:dp[x]) {
                int g2 = gcd(f2.x,g1);
                if (g2<=1) continue;
                ans = max(ans, f1.y+f2.y);
            }
        }
        //最后再用子树更新x
        for (auto f1:dp[y]) {
            int g1 = gcd(f1.x,a[x]);
            if (g1<=1) continue;
            ans = max(ans, f1.y+1);
            dp[x][g1] = max(dp[x][g1], f1.y+1);
        }
    }
    dp[x][a[x]] = max(dp[x][a[x]],1);
}

int main() {
    scanf("%d", &n);
    REP(i,1,n) {
        scanf("%d", a+i);
        if (a[i]>1) ans=1;
    }
    REP(i,2,n) {
        int u, v;
        scanf("%d%d", &u, &v);
        //这里优化一下
        if (gcd(a[u],a[v])>1) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    REP(i,1,n) {
        if (dp[i].empty()) dfs(i,0);
    }
    printf("%d\n", ans);
}

E. Polycarp‘s New Job

题意: 给若干硬币, 可以90度旋转, 询问是否能将所有放进钱包, 硬币钱包均为矩形

模拟就行了

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int a=0, b=0;
    REP(i,1,n) {
        char op;
        int x, y;
        scanf(" %c%d%d", &op, &x, &y);
        if (x>y) swap(x,y);
        if (op==‘+‘) a=max(a,x),b=max(b,y);
        else puts(x>=a&&y>=b?"YES":"NO");
    }
}

F. Trucks and Cities

题意: n个城市, 第$i$个城市在位置$a_i$, 第$i$个城市与第$j$个城市相距$|a_i-a_j|$公里

汽车每公里需要$x$汽油, 每个到一个城市可以加满汽油

给定$m$个汽车, 第$i$辆车从城市$s_i$到$t_i$, 最多加$r_i$次油, 每公里消耗油$c_i$

每辆汽车容量均为$V$, 初始满汽油, 求最小的$V$, 使得所有汽车均能到达目的地

$dp[k][i][j]$为预处理出加$k$次油从$i$到$j$时, 每次加油后行驶的最大距离的最小值

可以得到转移方程$dp[k][i][j]=\min\limits_{i \leq t \leq j} \{ max(dp[k-1][i][t],a_j-a_{t}) \}$

明显$dp[k][i][j]$是关于$j$是单增的, 双指针可以均摊O(1)转移或者二分O(log)转移也能过

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef long long ll;

const int N = 401;
int n, m;
int dp[N][N][N];
int a[N];

int main() {
    scanf("%d%d", &n, &m);
    REP(i,1,n) scanf("%d", a+i);
    REP(i,1,n) REP(j,i,n) dp[0][i][j]=a[j]-a[i];
    REP(k,1,n) REP(i,1,n) {
        int now = i;
        REP(j,i,n) {
            while (now<j&&max(dp[k-1][i][now],a[j]-a[now])>max(dp[k-1][i][now+1],a[j]-a[now+1])) ++now;
            dp[k][i][j] = max(dp[k-1][i][now], a[j]-a[now]);
        }
    }
    ll ans = 0;
    REP(i,1,m) {
        int s,f,c,r;
        scanf("%d%d%d%d",&s,&f,&c,&r);
        ans = max(ans,(ll)dp[r][s][f]*c);
    }
    printf("%lld\n", ans);
}

G. (Zero XOR Subset)-less

大意: 给定序列$a$, 求将$a$划分为连续的若干个非空区间, 使得任选若干区间$xor$和均不为$0$, 输出最大划分数

$xor$的性质还是太弱了啊, 没有什么单调性, 一般直接考虑线性基, 或者$trie$上贪心就好了

首先可以注意到划分数必然是不超过线性基的

对于总$xor$和为$0$一定不能划分, 否则贪心的划分一下就发现一定可以达到线性基大小的

然后就没了... 代码就几行

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
int a[50], n;

int main() {
    scanf("%d", &n);
    int sum = 0, t;
    REP(i,1,n) {
        scanf("%d", &t);
        sum ^= t;
        REP(j,1,*a) t = min(t,t^a[j]);
        if (t) a[++*a]=t;
    }
    printf("%d\n", sum?*a:-1);
}

原文地址:https://www.cnblogs.com/uid001/p/10258671.html

时间: 01-11

Educational Codeforces Round 58 (Rated for Div. 2) (题解)的相关文章

Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

题目链接:Educational Codeforces Round 21 G. Anthem of Berland 题意: 给你两个字符串,第一个字符串包含问号,问号可以变成任意字符串. 问你第一个字符串最多包含多少个第二个字符串. 题解: 考虑dp[i][j],表示当前考虑到第一个串的第i位,已经匹配到第二个字符串的第j位. 这样的话复杂度为26*n*m*O(fail). fail可以用kmp进行预处理,将26个字母全部处理出来,这样复杂度就变成了26*n*m. 状态转移看代码(就是一个kmp

Educational Codeforces Round 23 F. MEX Queries(线段树)

题目链接:Educational Codeforces Round 23 F. MEX Queries 题意: 一共有n个操作. 1.  将[l,r]区间的数标记为1. 2.  将[l,r]区间的数标记为0. 3.  将[l,r]区间取反. 对每个操作,输出标记为0的最小正整数. 题解: hash后,用线段树xjb标记一下就行了. 1 #include<bits/stdc++.h> 2 #define ls l,m,rt<<1 3 #define rs m+1,r,rt<&l

Educational Codeforces Round 26 D. Round Subset(dp)

题目链接:Educational Codeforces Round 26 D. Round Subset 题意: 给你n个数,让你选其中的k个数,使得这k个数的乘积的末尾的0的个数最大. 题解: 显然,末尾乘积0的个数和因子2和因子5的个数有关. 然后考虑dp[i][j]表示选i个数,当前因子5的个数为j时,能得到因子2最多的为多少. 那么对于每个数,记录一下因子2和5的个数,做一些01背包就行了. 1 #include<bits/stdc++.h> 2 #define mst(a,b) me

CodeForces 837F - Prefix Sums | Educational Codeforces Round 26

按tutorial打的我血崩,死活挂第四组- - 思路来自FXXL /* CodeForces 837F - Prefix Sums [ 二分,组合数 ] | Educational Codeforces Round 26 题意: 设定数组 y = f(x) 使得 y[i] = sum(x[j]) (0 <= j < i) 求初始数组 A0 经过多少次 f(x) 后 会有一个元素 大于 k 分析: 考虑 A0 = {1, 0, 0, 0} A1 = {1, 1, 1, 1} -> {C(

Educational Codeforces Round 26 D dp,思维

Educational Codeforces Round 26 D. Round Subset 题意:有 n 个数,从中选出 k 个数,要使这 k 个数的乘积末尾的 0 的数量最多. tags:dp好题 dp[i][j][l] 表示前 i 个数,选取了其中 j 个数,分解因子后有 l 个 5时,最多有多少个 2 .i 这一维明显可以省略. 这题一开始有个地方写挫了..选取 j 个数时,应该反着来,即 for( j, k, 1) ,不是 for( j, 1, k) ,不然会多算. #include

Educational Codeforces Round 23 D. Imbalanced Array(单调栈)

题目链接:Educational Codeforces Round 23 D. Imbalanced Array 题意: 给你n个数,定义一个区间的不平衡因子为该区间最大值-最小值. 然后问你这n个数所有的区间的不平衡因子和 题解: 对每一个数算贡献,a[i]的贡献为 当a[i]为最大值时的 a[i]*(i-l+1)*(r-i+1) - 当a[i]为最小值时的a[i]*(i-l+1)*(r-i+1). 计算a[i]的l和r时,用单调栈维护.具体看代码,模拟一下就知道了. 然后把所有的贡献加起来.

Educational Codeforces Round 25 F. String Compression(kmp+dp)

题目链接:Educational Codeforces Round 25 F. String Compression 题意: 给你一个字符串,让你压缩,问压缩后最小的长度是多少. 压缩的形式为x(...)x(...)  x表示(...)这个出现的次数. 题解: 考虑dp[i]表示前i个字符压缩后的最小长度. 转移方程解释看代码,这里要用到kmp来找最小的循环节. 当然还有一种找循环节的方式就是预处理lcp,然后通过枚举循环节的方式. 这里我用的kmp找的循环节.复杂度严格n2. 1 #inclu

Educational Codeforces Round 23 E. Choosing The Commander (trie)

题目链接: Educational Codeforces Round 23 E. Choosing The Commander 题意: 一共有n个操作. 1.  插入一个数p 2.  删除一个数p 3.  询问有多少个数 使得 x^p<l 题解: 对于前两种操作用01trie就能解决. 对于对三个操作,我们考虑在trie上搜索. 1.  当l的bit位是1时,那边bit位是p的字数全部的数都会小于l,(因为p^p=0) 2.  当l的bit为是0时,那边只能向bit位是p的子树中搜. 这样算下来

CodeForces - 837E - Vasya&#39;s Function | Educational Codeforces Round 26

/* CodeForces - 837E - Vasya's Function [ 数论 ] | Educational Codeforces Round 26 题意: f(a, 0) = 0; f(a, b) = 1 + f(a, b-gcd(a, b)); 求 f(a, b) , a,b <= 1e12 分析: b 每次减 gcd(a, b) 等价于 b/gcd(a,b) 每次减 1 减到什么时候呢,就是 b/gcd(a,b)-k 后 不与 a 互质 可先将 a 质因数分解,b能除就除,不能

Educational Codeforces Round 22 E. Army Creation(主席树)

题目链接:Educational Codeforces Round 22 E. Army Creation 题意: 给你n个数和一个数k,然后有q个询问. 每个询问 有一个区间[l,r],问你这个区间内在满足每一种数不超过k的情况下,最大能选多少个数出来. 强制在线. 题解: 一看就要用到主席树,和主席数求区间内有多少不同的数的个数处理方法相同. 依次将每个数插入,当这个数出现的个数等于k了,就把最前面的那个数删掉. 然后询问就访问root[r]就行了. 第一次写完数据结构没有调试一遍过样例,一