CF1108A. Two distinct points
做法:模拟
如果两者左端点重合就第二条的左端点++就好,然后输出左端点
#include
using namespace std;int T;
int l1, r1, l2, r2;int main() {scanf("%d", &T);while(T--) {scanf("%d%d%d%d", &l1, &r1, &l2, &r2);printf("%d ", l1);if(l1 == l2) l2++;printf("%d\n", l2);}
}
CF1108B. Divisors of Two Integers
做法:模拟
坑点好多...首先因为所有因数都有,所以最大的数一定是x,y中的一个.把它拎出来,然后删掉它的因子,剩下的最大的就是x,y中的另外一个了
#include
using namespace std;
typedef long long ll;int n;
int a[100000];
int cnt[101000];int main() {scanf("%d", &n);int mx &#61; 0;for(int i &#61; 1; i <&#61; n; &#43;&#43;i) {scanf("%d", &a[i]);cnt[a[i]]&#43;&#43;;mx &#61; max(mx, a[i]);}printf("%d ", mx);for(int i &#61; 1; i * i <&#61; mx; &#43;&#43;i) {if(mx % i &#61;&#61; 0) {cnt[i]--;if(mx / i !&#61; i) cnt[mx / i]--;}}int ans &#61; 0;for(int i &#61; 1; i <&#61; mx; &#43;&#43;i) {if(cnt[i] > 0) ans &#61; i;}printf("%d\n", ans);
}
CF1108C. Nice Garland
做法:模拟
依旧是模拟qwq.显然合法的排列方式也就那么6种...于是6种方式都跑一遍,然后取min即可
#include
using namespace std;
typedef long long ll;
const int N &#61; 2e5 &#43; 10;int n, id &#61; 0;
char s[N];
string f[6] &#61; {"RGB", "RBG", "BRG", "BGR", "GRB", "GBR"};
int main() {scanf("%d%s", &n, s &#43; 1);int ans &#61; N;for(int k &#61; 0; k <6; &#43;&#43;k) {int sum &#61; 0, pos &#61; 0;for(int i &#61; 1; i <&#61; n; &#43;&#43;i, pos &#61; (pos &#43; 1) % 3) {if(s[i] !&#61; f[k][pos]) &#43;&#43;sum;}if(sum
CF1108D. Diverse Garland
做法:dp
第一问显然sb dp,设f[i,j]表示点i然后点i填的是RGB中的一个(分别对应一个j),直接转移即可.输出方案反而比较难,有各种方法,我的方法是记录每个dp值的转移点,从后往前推回去.
#include
using namespace std;
typedef long long ll;
const int N &#61; 2e5 &#43; 10;int n, id &#61; 0;
char s[N], p[3] &#61; {&#39;R&#39;, &#39;G&#39;, &#39;B&#39;};
int f[N][3], to[N][3];
char t[N];int main() {scanf("%d%s", &n, s &#43; 1);memset(f, 0x3f, sizeof(f));f[1][0] &#61; f[1][1] &#61; f[1][2] &#61; 1;if(s[1] &#61;&#61; &#39;R&#39;) f[1][0] &#61; 0;else if(s[1] &#61;&#61; &#39;G&#39;) f[1][1] &#61; 0;else f[1][2] &#61; 0;for(int i &#61; 2; i <&#61; n; &#43;&#43;i) for(int j &#61; 0; j <3; &#43;&#43;j) for(int k &#61; 0; k <3; &#43;&#43;k) {if(j &#61;&#61; k) continue; if(p[j] &#61;&#61; s[i]) {if(f[i - 1][k]
CF1108E1. Array and Segments (Easy version)
做法:暴力
考虑怎么样才能让结果最大,把线段分成两类,一种是没有覆盖最大值,一种是有覆盖最大值的,如果选了覆盖最大值的显然只会减小答案,所以可以暴力枚举最大值,并累加不覆盖最大值的线段,对所有情况取max即可复杂度是\(O(n^2m)\)的
#include
using namespace std;
typedef long long ll;
const int N &#61; 2e5 &#43; 10;
const int inf &#61; 0x3f3f3f3f;int n, m, a[N], b[N];
int vis[N];
struct seg {int l, r, id;
} s[N];
vector
int ans &#61; -1;int main() {scanf("%d%d", &n, &m);for(int i &#61; 1; i <&#61; n; &#43;&#43;i) scanf("%d", &a[i]);for(int i &#61; 1; i <&#61; m; &#43;&#43;i) scanf("%d%d", &s[i].l, &s[i].r), s[i].id &#61; i;for(int i &#61; 1; i <&#61; n; &#43;&#43;i) {vector
CF1108E2. Array and Segments (Hard version)
做法:线段树优化暴力
考虑优化E1的暴力,注意到m很小,所以复杂度里面是可以有一个m的.然后利用线段树来优化把线段覆盖下去的过程,即利用线段树维护区间修改,维护区间min.这样的复杂度是\(O(nmlogn)\)的.这样朴素的去做会TLE on 12.发现每次如果加入线段然后再删除线段会有很多重复的操作,可以拿一个数组来标记哪条线段有覆盖哪条没有,如果有线段不能覆盖下去且已经覆盖了,那么就&#43;1回去,能覆盖下去的同理,这样修改次数就大大降低了.这样就能通过本题了
#include
using namespace std;
typedef long long ll;
const int N &#61; 1e5 &#43; 10;
const int inf &#61; 0x3f3f3f3f;int n, m, a[N], b[N];
struct seg {int l, r, id;
} s[N];
vector
int ans &#61; -1;struct tree {int l, r, mn, tag;
} t[N<<2];#define lc (rt <<1)
#define rc (rt <<1 | 1)
void pushup(int rt) { t[rt].mn &#61; min(t[lc].mn, t[rc].mn); }
void build(int l, int r, int rt) {t[rt].l &#61; l; t[rt].r &#61; r; t[rt].mn &#61; inf;if(l &#61;&#61; r) { t[rt].mn &#61; a[l]; return; }int mid &#61; (l &#43; r) >> 1;build(l, mid, lc); build(mid &#43; 1, r, rc); pushup(rt);
}
void pushdown(int rt) {if(t[rt].tag) {int &x &#61; t[rt].tag;t[lc].tag &#43;&#61; x; t[rc].tag &#43;&#61; x;t[lc].mn &#43;&#61; x; t[rc].mn &#43;&#61; x;x &#61; 0;}
}
#define l (t[rt].l)
#define r (t[rt].r)
void upd(int L, int R, int c, int rt) {if(L <&#61; l && r <&#61; R) {t[rt].tag &#43;&#61; c; t[rt].mn &#43;&#61; c;return;}pushdown(rt); int mid &#61; (l &#43; r) >> 1;if(L <&#61; mid) upd(L, R, c, lc); if(R > mid) upd(L, R, c, rc); pushup(rt);
}
#undef l
#undef r
#undef lc
#undef rcbool vis[N];int main() {scanf("%d%d", &n, &m);for(int i &#61; 1; i <&#61; n; &#43;&#43;i) scanf("%d", &a[i]);for(int i &#61; 1; i <&#61; m; &#43;&#43;i) scanf("%d%d", &s[i].l, &s[i].r), s[i].id &#61; i;build(1, n, 1);for(int i &#61; 1; i <&#61; n; &#43;&#43;i) {vector
CF1108F. MST Unification
做法:最小生成树
考虑怎么样才会使一个最小生成树不唯一.设有一条边边权为val,且它没有在最小生成树中,那么加入最小生成树之后,就会出来一个环,如果这个环中有一条边边权为val,那么这个mst就是不唯一的.可以倍增实现这个过程但是比较麻烦,也可以选择就是对所有边权相同的边权统一考虑一下:如果此边的两个端点已经在最小生成树里面了,那么显然这条边对mst的唯一性没有影响(因为连接它的边边权一定更小),不用管它.如果两端点之前还未接入最小生成树,但是在加到这条边的时候又已经加入了(即有同样长度的边使两端点联通),那么这条边就一定会对答案产生影响,需要&#43;1保证mst的唯一性
#include
using namespace std;
typedef long long ll;
const int N &#61; 200010;struct edge {int x, y, v;
} e[N];
int n, m, f[N];bool cmp(edge a, edge b) {return a.v
}int main() {scanf("%d%d", &n, &m);for(int i &#61; 1; i <&#61; m; &#43;&#43;i) {scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].v);}sort(e &#43; 1, e &#43; m &#43; 1, cmp);for(int i &#61; 1; i <&#61; n; &#43;&#43;i) f[i] &#61; i;int ans &#61; 0;for(int i &#61; 1, j &#61; 1; i <&#61; m; i &#61; j) {while(j <&#61; m && e[j].v &#61;&#61; e[i].v) &#43;&#43;j;int tot &#61; j - i;for(int k &#61; i; k