Problem A. Two distinct points
[题解]
显然 ， 当l1不等于r2时 , (l1 , r2)是一组解
否则 , (l1 , l2)是一组合法的解
时间复杂度 : O(1)
[代码]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
int main()
{ int T;
read(T);
while (T--)
{
int l1 , r1 , l2 , r2;
read(l1); read(r1); read(l2); read(r2);
if (l1 != r2) cout<< l1 << ' ' << r2 << '\n';
else cout<< l1 << ' ' << l2 << '\n';
}
return ; }
Problem B. Divisors of Two Integers
[题解]
首先 ， 给定序列中的最大数一定是x和y中的一个数
将该数的所有因子从序列中删除一次 ， 剩余数中的最大数即为另一个数
时间复杂度 : O(M) (取M = 10 ^ 4)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n;
int d[MAXN] , cnt[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
int main()
{ read(n);
int fst = , sec = ;
for (int i = ; i <= n; i++)
{
read(d[i]);
if (d[i] > fst) fst = d[i];
++cnt[d[i]];
}
for (int i = ; i <= fst; i++)
if (fst % i == ) --cnt[i];
for (int i = (int)1e4; i >= ; i--)
{
if (cnt[i])
{
sec = i;
break;
}
}
cout<< fst << ' ' << sec << '\n'; return ; }
Problem C. Nice Garland
[题解]
通过观察发现 ， 答案一定是一个以"R" , "G" , "B"三个字符所形成的一个排列为循环节循环得到的字符串
枚举排列 ， 计算最优解 ， 即可
时间复杂度 : O(N)
[代码]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ;
const int inf = 1e9;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n;
char s[MAXN] , t1[MAXN] , t2[MAXN] , t3[MAXN] , t4[MAXN] , t5[MAXN] , t6[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
int main()
{ scanf("%d" , &n);
scanf("%s" , s + );
for (int i = ; i <= n; i++)
{
if (i % == ) t1[i] = 'R';
if (i % == ) t1[i] = 'G';
if (i % == ) t1[i] = 'B';
}
int stp = , ans = , mstp = inf;
for (int i = ; i <= n; i++)
if (s[i] != t1[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} for (int i = ; i <= n; i++)
{
if (i % == ) t2[i] = 'R';
if (i % == ) t2[i] = 'B';
if (i % == ) t2[i] = 'G';
}
stp = ;
for (int i = ; i <= n; i++)
if (s[i] != t2[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} for (int i = ; i <= n; i++)
{
if (i % == ) t3[i] = 'B';
if (i % == ) t3[i] = 'R';
if (i % == ) t3[i] = 'G';
}
stp = ;
for (int i = ; i <= n; i++)
if (s[i] != t3[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} for (int i = ; i <= n; i++)
{
if (i % == ) t4[i] = 'B';
if (i % == ) t4[i] = 'G';
if (i % == ) t4[i] = 'R';
}
stp = ;
for (int i = ; i <= n; i++)
if (s[i] != t4[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} for (int i = ; i <= n; i++)
{
if (i % == ) t5[i] = 'G';
if (i % == ) t5[i] = 'R';
if (i % == ) t5[i] = 'B';
}
stp = ;
for (int i = ; i <= n; i++)
if (s[i] != t5[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} for (int i = ; i <= n; i++)
{
if (i % == ) t6[i] = 'G';
if (i % == ) t6[i] = 'B';
if (i % == ) t6[i] = 'R';
}
stp = ;
for (int i = ; i <= n; i++)
if (s[i] != t6[i]) ++stp;
if (stp < mstp)
{
mstp = stp;
ans = ;
} cout<< mstp << '\n';
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t1[i]);
cout<< '\n';
}
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t2[i]);
cout<< '\n';
}
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t3[i]);
cout<< '\n';
}
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t4[i]);
cout<< '\n';
}
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t5[i]);
cout<< '\n';
}
if (ans == )
{
for (int i = ; i <= n; i++) putchar(t6[i]);
cout<< '\n';
} return ; }
Problem D. Diverse Garland
[题解]
简单贪心即可
时间复杂度 : O(N)
[代码]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n , cnt;
char s[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
int main()
{ scanf("%d" , &n);
scanf("%s" , s + );
map<char , int> mp;
mp.clear();
for (int i = ; i < n; i++)
{
if (s[i] != s[i - ]) continue;
mp.clear();
mp[s[i - ]]++; mp[s[i + ]]++;
if (mp['R'] && mp['G'])
{
s[i] = 'B';
++cnt;
} else if (mp['R'] && mp['B'])
{
s[i] = 'G';
++cnt;
} else if (mp['B'] && mp['G'])
{
s[i] = 'R';
++cnt;
} else if (mp['R'])
{
s[i] = 'G';
++cnt;
} else if (mp['G'])
{
s[i] = 'B';
++cnt;
} else
{
s[i] = 'R';
++cnt;
}
}
if (s[n] == s[n - ])
{
int i = n;
mp.clear();
++mp[s[n - 1]];
if (mp['R'])
{
s[i] = 'G';
++cnt;
} else if (mp['G'])
{
s[i] = 'B';
++cnt;
} else
{
s[i] = 'R';
++cnt;
}
}
cout<< cnt << '\n';
for (int i = ; i <= n; i++) putchar(s[i]);
printf("\n"); return ; }
Problem E. Array and Segments
[题解]
Easy Version :
枚举序列中的最大值和最小值的出现位置 ， 然后枚举每一条线段 ， 贪心地选择所有覆盖了最小值出现位置的线段
时间复杂度 : O(N ^ 2M)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 310
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n , m , ans;
int a[MAXN] , l[MAXN] , r[MAXN];
vector< int > fans; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline void solve(int x , int y)
{
int tx = a[x] , ty = a[y];
vector< int > res;
res.clear();
for (int i = ; i <= m; i++)
{
if (l[i] <= x && r[i] >= x) continue;
if (l[i] <= y && r[i] >= y)
{
res.push_back(i);
--ty;
}
}
if (tx - ty > ans)
{
ans = tx - ty;
fans.clear();
for (unsigned i = ; i < res.size(); i++) fans.push_back(res[i]);
}
} int main()
{ read(n); read(m);
for (int i = ; i <= n; i++) read(a[i]);
for (int i = ; i <= m; i++)
{
read(l[i]);
read(r[i]);
}
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (i != j)
solve(i , j);
}
}
cout<< ans << '\n';
cout<< (int)fans.size() << '\n';
for (unsigned i = ; i < (int)fans.size(); i++) cout<< fans[i] << ' ';
cout<< '\n'; return ; }
Hard Version :
我们可以先选择所有线段
那么 ， 问题就转化为 ， 选择一些区间进行操作 ， 使得[li , ri]每个数增加1 ， 最大化序列中的最大值 - 最小值
考虑枚举最大值出现的位置 ， 显然 ， 我们可以贪心地选择所有覆盖了该位置的线段
那么我们就可以使用扫描线算法 :
从1-n按顺序枚举最大值出现的位置i ， 考虑所有以i为左端点的线段 ， 我们选择这些线段进行操作 ， 然后考虑所有以i为右端点的线段 ， 取消对这些线段的操作
维护一棵支持区间修改 ， 询问区间最大 / 最小值的线段树即可
时间复杂度 : O(NMlogN)
[代码]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + ; #pragma GCC optimize(2)
#define rint register int typedef long long ll;
typedef long double ld;
typedef unsigned long long ull; int n , m;
int l[MAXN] , r[MAXN] , val[MAXN];
vector< int > s[MAXN] , e[MAXN];
bool tag[MAXN]; struct Segment_Tree
{
struct Node
{
int l , r , tag;
pair<int , int> value;
} a[MAXN << ];
inline void build(int index , int l , int r)
{
a[index].l = l , a[index].r = r;
a[index].tag = ;
if (l == r)
{
a[index].value = make_pair(val[l] , val[l]);
return;
}
int mid = (l + r) >> ;
build(index << , l , mid);
build(index << | , mid + , r);
update(index);
}
inline void update(int index)
{
a[index].value.first = min(a[index << ].value.first , a[index << | ].value.first);
a[index].value.second = max(a[index << ].value.second , a[index << | ].value.second);
}
inline void pushdown(int index)
{
a[index << ].value.first += a[index].tag;
a[index << | ].value.first += a[index].tag;
a[index << ].value.second += a[index].tag;
a[index << | ].value.second += a[index].tag;
a[index << ].tag += a[index].tag;
a[index << | ].tag += a[index].tag;
a[index].tag = ;
}
inline void modify(int index , int l , int r , int val)
{
if (a[index].l == l && a[index].r == r)
{
a[index].value.first += val;
a[index].value.second += val;
a[index].tag += val;
return;
}
pushdown(index);
int mid = (a[index].l + a[index].r) >> ;
if (mid >= r) modify(index << , l , r , val);
else if (mid + <= l) modify(index << | , l , r , val);
else
{
modify(index << , l , mid , val);
modify(index << | , mid + , r , val);
}
update(index);
}
inline pair<int , int> query()
{
return a[].value;
}
} SGT; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
} int main()
{ read(n); read(m);
for (rint i = ; i <= n; i++) read(val[i]);
SGT.build( , , n);
for (rint i = ; i <= m; i++)
{
read(l[i]);
read(r[i]);
s[l[i]].push_back(r[i]);
e[r[i]].push_back(l[i]);
SGT.modify( , l[i] , r[i] , -);
}
int mx = , loc = ;
for (rint i = ; i <= n; i++)
{
for (unsigned j = ; j < s[i].size(); j++)
SGT.modify( , i , s[i][j] , );
pair<int , int> tmp = SGT.query();
if (tmp.second - tmp.first > mx)
{
mx = tmp.second - tmp.first;
loc = i;
}
for (unsigned j = ; j < e[i].size(); j++)
SGT.modify( , e[i][j] , i , -);
}
cout<< mx << '\n';
vector< int > res;
for (int i = ; i <= m; i++)
{
if (l[i] > loc || r[i] < loc)
res.push_back(i);
}
cout<< (int)res.size() << '\n';
for (unsigned i = ; i < res.size(); i++) cout<< res[i] << ' ';
cout<< '\n'; return ; }
Problem F. MST Unification
[题解]
首先用kruskal算法求出这个图的任意一棵最小生成树
枚举不在这颗最小生成树上的每一条边(u , v , w)
若加入这条边 ， 则形成了一个环 ， 若环上的边权除这条边外的最大值 = w ， 那么说明可以用这条边替换环上权值 = w的边 ， 我们需要将这条边的权值加一
倍增即可
时间复杂度 : O((N + M)logN)
[代码]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int MAXN = 2e5 + ;
const int MAXLOG = ; struct Edge
{
int x,y;
long long w;
} edge[MAXN << ]; int T,n,m,i;
long long val;
vector< pair<int,long long> > e[MAXN];
bool on_mst[MAXN];
int fa[MAXN],anc[MAXN][MAXLOG],dep[MAXN];
long long mx[MAXN][MAXLOG];
bool not_unique; inline bool cmp(Edge a,Edge b) { return a.w < b.w; }
inline int get_root(int x)
{
if (fa[x] == x) return x;
return fa[x] = get_root(fa[x]);
}
inline void kruskal()
{
int i,x,y,sx,sy;
long long w;
for (i = ; i <= n; i++) fa[i] = i;
for (i = ; i <= m; i++) on_mst[i] = false;
sort(edge+,edge+m+,cmp);
for (i = ; i <= m; i++)
{
x = edge[i].x;
y = edge[i].y;
w = edge[i].w;
sx = get_root(x);
sy = get_root(y);
if (sx != sy)
{
on_mst[i] = true;
val += w;
fa[sx] = sy;
e[x].push_back(make_pair(y,w));
e[y].push_back(make_pair(x,w));
}
}
}
inline void build(int u)
{
int i,v;
for (i = ; i < MAXLOG; i++)
{
anc[u][i] = anc[anc[u][i-]][i-];
mx[u][i] = max(mx[u][i-],mx[anc[u][i-]][i-]);
}
for (i = ; i < e[u].size(); i++)
{
v = e[u][i].first;
if (anc[u][] != v)
{
dep[v] = dep[u] + ;
anc[v][] = u;
mx[v][] = e[u][i].second;
build(v);
}
}
}
inline long long get(int x,int y)
{
int i,t;
long long ans = ;
if (dep[x] > dep[y]) swap(x,y);
t = dep[y] - dep[x];
for (i = ; i < MAXLOG; i++)
{
if (t & ( << i))
{
ans = max(ans,mx[y][i]);
y = anc[y][i];
}
}
if (x == y) return ans;
for (i = MAXLOG - ; i >= ; i--)
{
if (anc[x][i] != anc[y][i])
{
ans = max(ans,max(mx[x][i],mx[y][i]));
x = anc[x][i];
y = anc[y][i];
}
}
return max(ans,max(mx[x][],mx[y][]));
}
int main()
{ scanf("%d%d",&n,&m);
val = ;
not_unique = false;
for (i = ; i <= n; i++)
{
dep[i] = ;
e[i].clear();
memset(anc[i],,sizeof(anc[i]));
memset(mx[i],,sizeof(mx[i]));
}
for (i = ; i <= m; i++) scanf("%d%d%lld",&edge[i].x,&edge[i].y,&edge[i].w);
kruskal();
build();
int ans = ;
for (i = ; i <= m; i++)
{
if (!on_mst[i])
ans += (get(edge[i].x,edge[i].y) == edge[i].w);
}
cout<< ans << '\n'; return ; }