传送门

目录

A

B

C

D

E1

E2

F

A   Two distinct points

给出两条线段，可能相交也可能重合，要求找出两个点（A ！= B），一个在第一个线段中，另外一个在第二个线段中，判断一下重合，直接输出即可

代码略

B  Divisors of Two Integers

这个题的题意，比赛的时候花了五十分钟我才弄懂，要不是打星心态就崩了，我理解的是给你n个数，他们都作为x和y的因子，要求你找出来x和y两个数分别是多少，注意是有重复的，比如1 2 3 6 1 2 3 4 6 12 应该是 12 和 6，1 2 3 6 都是出现了两次的，所以需要标记一下 

代码如下：

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
vector<vector<ll> >v;
const int maxn = 2e6;
int  n;
map<int,int>m;
int a[maxn];
bool vis[maxn];
string str;bool cmp(int a,int b) {return a > b;
}
int main() {while(cin >> n) {for(int i = 1; i <= n; i++) cin >> a[i],m[a[i]]++;sort(a + 1,a + 1 + n,cmp);map<int,int>mm;cout << a[1] << " ";for(int i = 1;i <= n;i++)if(a[1] % a[i] == 0 && !mm[a[i]])  mm[a[i]] = 1;for(int i = 1;i <= n;i++){if(m[a[i]] > 1||!mm[a[i]]){cout << a[i] << endl;return 0;}}}return 0;
}

C  Nice Garland

他会给你三个颜色的灯泡，并且有一个现在有的排列，GRB三种颜色，要求每个相同的颜色相隔大于等于三才算符合规则，问你现在排列好的灯泡需要修改几次颜色，并且输出改变后的灯泡摆放序列 

很简单，可以直接暴力所有排列方式，并且挨个去和当前的序列比较，取个min即可，我写的可能有点麻烦了。 。

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
vector<vector<ll> >v;
const int maxn = 2e6;
int  n,m;
int a[maxn];
bool vis[maxn];
string str;
int main() {while(cin >> n >> str) {int cnt  = 0;char c = str[0];char op[4] = {'R','G','B'};int ans = 1e9;string anss = str;for(int i = 0; i < 3; i++) {for(int j = 0; j < 3; j++) {for(int k = 0; k < 3; k++) {if(i != j && j != k && i != k) {string strr = "";strr += op[i];strr += op[j];strr += op[k];int num = 0;for(int q = 0; q < n; q += 3) {if(str[q] != strr[0]) num++;}for(int q = 1; q < n; q += 3) {if(str[q] != strr[1]) num++;}for(int q = 2; q < n; q += 3) {if(str[q] != strr[2]) num++;}if(num < ans) {ans = min(ans,num);anss = "";for(int q = 0;;) {anss += op[i];q++;if(q >= n) break;anss += op[j];q++;if(q >= n) break;anss += op[k];q++;if(q >= n) break;}}}}}}cout << ans << endl;cout << anss << endl;}return 0;
}

D Diverse Garland

在C题的基础上，还是给你一个序列，并且要求两两之间不能相同问你最少改变的方式和最终序列，直接贪心即可

代码：

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
vector<vector<ll> >v;
const int maxn = 2e6;
int  n,m;
int a[maxn];
bool vis[maxn];
string str;
int main() {while(cin >> n >> str) {int cnt = 0;for(int i = 0; i < n - 1; i++) {if(str[i] == str[i - 1]) {cnt++;if((str[i + 1] == 'G' && str[i - 1] == 'B') || (str[i + 1] == 'B' && str[i - 1] == 'G')) {str[i] = 'R';} else if((str[i + 1] == 'R' && str[i - 1] == 'B') || (str[i + 1] == 'B' && str[i - 1] == 'R')) {str[i] = 'G';} else if((str[i + 1] == 'G' && str[i - 1] == 'R') || (str[i + 1] == 'R' && str[i - 1] == 'G')) {str[i] = 'B';} else {if(str[i + 1] == 'G') str[i]  = 'R';if(str[i + 1] == 'R') str[i]  = 'B';if(str[i + 1] == 'B') str[i]  = 'R';}}}if(str[n - 1] == str[n - 2]) {if(str[n - 2] == 'G') str[n - 1]  = 'R';if(str[n - 2] == 'B') str[n - 1]  = 'R';if(str[n - 2] == 'R') str[n - 1]  = 'B';cnt++;}cout << cnt << endl;cout << str << endl;}return 0;
}

E1  Array and Segments (Easy version)

给你n个数，m个区间，可以取任意个区间，使得n个数中最大值和最小值的绝对值差最大

因为E1的n和m都很小，所以我们可以枚举任意两个点，一个在线段外，一个在线段内，遍历m个区间，暴力更新，找到最大的差，对结果取个max

代码如下：

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
vector<vector<ll> >v;
const int maxn = 2e6;
int  n,m;
int a[maxn];
bool vis[500];
string str;
struct node {int l,r;
} g[maxn];
int main() {while(cin >> n >> m) {for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= m; i++) cin >> g[i].l >> g[i].r;int Max = 1e8;int ans = 0;vector<int>anss;for(int i = 1; i <= n; i++) {for(int j = 1; j <= n; j++) {vector<int>v;int x = a[i],y = a[j];memset(vis,0,sizeof(vis));for(int k = 1; k <= m; k++)if( (i > g[k].r || i < g[k].l) && (j >= g[k].l && g[k].r >= j)) y--,v.push_back(k);if(ans < x - y)ans = x - y,   anss = v;}}cout << ans << endl;cout << anss.size() << endl;for(auto d:anss)cout << d << " ";cout << endl;}return 0;
}

E2. Array and Segments (Hard version)

题意一样，只是n的范围增加了，比赛的时候也没时间，没想到怎么做，第二天想到一种n*m的做法，假设可以先对线段左端点排序，接着我们可以枚举线段，对于每个线段暴力更新，然后求一遍Max和Min，当第一条线段求完之后，现在可以知道，最大值的点可能位于这个点的右边，而最小值的小，我们现在确定不了，因为后面我还会存在一些线段在更新，其实是完全不影响的，我们一直进行这个暴力更新，就可以找到当右边的点作为最大值的时候的差的最大，那么还可能这个最大值的点是在左边，所以我们还需要对线段右端点排序依次，再进行上面的步骤即可，两边求出来的极值一定最大。并且满足规则，中间更新的地方可以直接暴力，没必要用线段树。

代码如下：

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
const int maxn = 2e6;
int  n,m;
bool vis[500];
struct node {int l,r,id;
} g[maxn];bool cmp2(struct node a,struct node b) {if(a.r == b.r) return a.l > b.l;return a.r > b.r;
}
bool cmp1(struct node a,struct node b) {if(a.l == b.l) return a.r < b.r;return a.l < b.l;
}
int b[maxn];
int a[maxn];
int main() {while(cin >> n >> m) {for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= m; i++) cin >> g[i].l >> g[i].r,g[i].id = i;int ans = 0;vector<int>anss;for(int i = 1; i <= n; i++) b[i] = a[i];int Min = 1e9;int Max = -1e9;for(int j = 1; j <= n; j++) {Max = max(b[j],Max);Min = min(b[j],Min);}ans = abs(Max - Min);sort(g + 1,g + 1 + m,cmp1);vector<int>v;for(int i = 1; i <= m; i++) {for(int j = g[i].l; j <= g[i].r; j++)b[j]--;v.push_back(g[i].id);Min = 1e9,Max = -1e9;for(int j = 1; j <= n; j++)Max = max(b[j],Max),Min = min(b[j],Min);if(abs(Max - Min) > ans)ans = abs(Max - Min),anss = v;}sort(g + 1,g + 1 + m,cmp2);for(int i = 1; i <= n; i++) b[i] = a[i];v.clear();for(int i = 1; i <= m; i++) {for(int j = g[i].l; j <= g[i].r; j++)b[j]--;v.push_back(g[i].id);Min = 1e9,Max = -1e9;for(int j = 1; j <= n; j++)Max = max(b[j],Max),Min = min(b[j],Min);if(abs(Max - Min) > ans)ans = abs(Max - Min), anss = v;}cout << ans << endl;cout << anss.size() << endl;for(auto d:anss)cout << d << " ";cout << endl;}return 0;
}

F MST Unification

刚刚打完教育场自闭，D题都没有做出来，补完D ， 顺便把这场DIV3的F也补了，题意是我给你m个边和权值，然后你可以对任意一条边进行边权值++的操作，问你最少操作多少次，使得这个图的MST唯一。

这个东西真的很有意思 ， 刚刚思考了一下，我们首先应用krus的那种方法，想到合并，假设现在有很多边权值相同的边，那么我们很有可能因为这些边权相同的边 ， 而生成很多个MST，思考如何让它唯一，遇到边权相同的边我们可以先假设把他们全部都加1，然后开始合并，当我们遇到当前这条边是在当前边权下最小的边，并且不连通，那么这条边我们是肯定会拿来生成MST的，那对于刚刚我们对这条边加的1的贡献就可以考虑去掉，然后依次进行这个操作即可，对于每个边权相同的边集，我们都这么跑一遍，就可以找到使得MST唯一所需要加的边权最小值。

代码如下： 

#include <bits/stdc++.h>
#include <time.h>
using namespace std;typedef long long ll;
typedef pair<int,int>  P;
const int Maxn = 2e6;
int  n,m;
bool vis[500];
struct node {int u,v,val;
} g[Maxn];
bool cmp(struct node a, struct node b) {return a.val < b.val;
}
int b[Maxn];
int a[Maxn];
int fa[Maxn];
int Find(int x) {if(x == fa[x]) return x;return fa[x] = Find(fa[x]);
}
int main() {while(cin >> n >> m) {for(int i = 1; i <= m; i++) {int u,v,val;cin >> g[i].u >> g[i].v >> g[i].val;}for(int i = 1; i <= n; i++) fa[i] = i;sort(g + 1,g + 1 + m,cmp);int ans = 0;for(int i = 1, j = 1; i <= m;) {int cnt = 0;int c = g[i].val;while(j <= m && g[j].val == c) j++;for(int k = i; k < j; k++) {int x = g[k].u;int y = g[k].v;int X = Find(x);int Y = Find(y);if(X != Y) cnt++;}for(int k = i; k < j; k++) {int x = g[k].u;int y = g[k].v;int X = Find(x);int Y = Find(y);if(X != Y) cnt--,fa[X] = Y;}i = j;ans += cnt;}cout << ans << endl;}return 0;
}