2017-2018 ACM-ICPC Latin American Regional Programming Contest
试题地址：http://codeforces.com/gym/101889
总体情况
总共通过7题CEFGHIJ。其中我完成HIJ三题。纯属被大佬带飞系列。
解题报告
H - Hard choice
签到题
#include <bits/stdc++.h>
using namespace std;
int a1,b1,c1,a2,b2,c2;
int main() {
cin>>a1>>b1>>c1>>a2>>b2>>c2;
cout<<max(a2-a1,0)+max(b2-b1,0)+max(c2-c1,0)<<endl;
}I - Imperial roads
比较裸，类似求次小生成树。这里写的是树链剖分+Kruskal，当然用树上倍增或者LCT维护都很棒。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000005;
struct Edge {
int u,v,w;
bool operator < (const Edge &b) const {
return w<b.w;
}
};
struct Ed {
int u,v,w;
bool operator < (const Ed &b) const {
if(u==b.u) return v<b.v;
else return u<b.u;
}
bool operator > (const Ed &b) const {
if(u==b.u) return v>b.v;
else return u>b.u;
}
bool operator == (const Ed &b) const {
return u==b.u && v==b.v;
}
bool operator >= (const Ed &b) const {
return *this>b || *this==b;
}
bool operator <= (const Ed &b) const {
return *this<b || *this==b;
}
};
int n,m,q,t1,t2,t3,t4;
Edge e[N]; Ed E[N];
bool f[N];
vector <pair<int,int> > g[N];
namespace Kruskal {
int fa[N],ans;
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int p,int q) {
p=find(p); q=find(q); fa[p]=q;
}
void solve() {
sort(e+1,e+m+1);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) {
if(find(e[i].u)!=find(e[i].v)) {
merge(e[i].u,e[i].v);
ans+=e[i].w;
f[i]=true;
g[e[i].u].push_back(make_pair(e[i].v,e[i].w));
g[e[i].v].push_back(make_pair(e[i].u,e[i].w));
}
}
}
}
namespace SegmentTree {
int a[N<<2],b[N<<2];
void build(int p,int l,int r,int *src) {
if(l==r) a[p]=src[l];
else {
build(p*2,l,(l+r)/2,src);
build(p*2+1,(l+r)/2+1,r,src);
a[p]=max(a[p*2],a[p*2+1]);
if(a[p*2]<a[p]) b[p]=a[p*2];
else if(a[p*2+1]<a[p]) b[p]=a[p*2+1];
else b[p]=max(b[p*2],b[p*2+1]);
}
}
int query(int p,int l,int r,int ql,int qr) {
if(l>qr||r<ql) return 0;
if(l>=ql && r<=qr) return a[p];
return max(query(p*2,l,(l+r)/2,ql,qr),query(p*2+1,(l+r)/2+1,r,ql,qr));
}
int querys(int p,int l,int r,int ql,int qr) {
if(l>qr||r<ql) return 0;
if(l>=ql && r<=qr) return b[p];
return max(querys(p*2,l,(l+r)/2,ql,qr),querys(p*2+1,(l+r)/2+1,r,ql,qr));
}
}
namespace Tree {
int ind,fa[N],siz[N],dep[N],dis[N],vis[N],wson[N],top[N],dfn[N];
void dfs1(int p) {
vis[p]=1; siz[p]=1;
for(int i=0;i<g[p].size();i++) {
int q=g[p][i].first;
if(vis[q]) continue;
dep[q]=dep[p]+1;
dis[q]=g[p][i].second;
fa[q]=p;
dfs1(q);
siz[p]+=siz[q];
if(siz[wson[p]]<siz[q]) wson[p]=q;
}
}
void dfs2(int p) {
vis[p]=1;
dfn[p]=++ind;
if(wson[p]) {
top[wson[p]]=top[p];
dfs2(wson[p]);
}
for(int i=0;i<g[p].size();i++) {
int q=g[p][i].first;
if(vis[q]) continue;
top[q]=q;
dfs2(q);
}
}
void presolve() {
dfs1(1);
memset(vis,0,sizeof vis);
top[1]=1;
dfs2(1);
}
int query(int p,int q) {
int ret=0;
while(top[p]!=top[q]) {
if(dep[top[p]]<dep[top[q]]) swap(p,q);
ret = max(ret,SegmentTree::query(1,1,n,dfn[top[p]],dfn[p]));
p=fa[top[p]];
}
if(dep[p]>dep[q]) swap(p,q);
return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));
}
/*int querys(int p,int q) {
int ret=0, lim=query(p,q);
while(top[p]!=top[q]) {
if(dep[top[p]]<dep[top[q]]) swap(p,q);
if(SegmentTree::query(1,1,n,dfn[top[p]],dfn[p])<lim)
ret=max(ret,SegmentTree::query(1,1,n,dfn[top[p]],dfn[p]));
else
ret=max(ret,SegmentTree::querys(1,1,n,dfn[top[p]],dfn[p]));
p=fa[top[p]];
}
if(dep[p]>dep[q]) swap(p,q);
if(SegmentTree::query(1,1,n,dfn[p]+1,dfn[q])<lim)
return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));
else
return max(ret,SegmentTree::query(1,1,n,dfn[p]+1,dfn[q]));
}*/
}
int val[N];
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&t1,&t2,&t3);
e[i].u=t1;
e[i].v=t2;
e[i].w=t3;
E[i].u=t1;
E[i].v=t2;
E[i].w=t3;
}
sort(E+1,E+m+1);
Kruskal::solve();
Tree::presolve();
for(int i=1;i<=n;i++) {
val[Tree::dfn[i]]=Tree::dis[i];
}
SegmentTree::build(1,1,n,val);
int ans = Kruskal::ans;
scanf("%d",&q);
for(int i=1;i<=q;i++) {
scanf("%d%d",&t1,&t2);
Ed qe;
qe.u = t1; qe.v = t2;
int eid = lower_bound(E+1,E+m+1,qe) - E;
cout<<ans + E[eid].w - Tree::query(t1,t2)<<endl;
}
}J - Jumping frog
容易发现，步数\(k\)可行的充要条件是 \((n,k)\) 可行。于是可以按照 \((n,k)\) 对集合 \(K\) 划分等价类，只需要检验集合 \(D = \{d: d|n\}\) 中的所有元素即可。容易发现对任意 \(d \in D\)，只需要检查是否存在 \(x \in [0,d)\) 使得对任意 \(x+id\) 位置是 Rock。计算答案只要统计所有合法等价类的大小之和即可。
划分等价类时求解若干次GCD，时间复杂度 \(O(n \log{n})\)。检查只需要 \(O(n)\) 扫描，而等价类个数 \(|D|\) ，等于 \((n,k)\) 的所有可能取值。考虑到若\(g=(n,k)\)，则必有 \(g|n\)，因此 \(|D|+1\) 即为 \(n\) 的因数个数。根据因数个数定理容易证明， \(n\) 的因数个数有渐进上界\(O(\sqrt{n})\)，于是总体时间复杂度为 \(O(n \sqrt{n})\)。
#include <bits/stdc++.h>
using namespace std;
int n;
char s[100005];
vector <int> d;
int dsize[100005],buf[100005];
int gcd(int a,int b) {
return !b?a:gcd(b,a%b);
}
bool check(int k) {
memset(buf,0,sizeof buf);
for(int i=0;i<n;i++) if(s[i]=='P') buf[i%k]++;
for(int i=0;i<k;i++) if(buf[i]==0) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin>>s;
n=strlen(s);
for(int i=1;i<n;i++) {
if(n%i==0) d.push_back(i);
}
for(int i=1;i<n;i++) {
dsize[gcd(i,n)]++;
}
int ans = 0;
for(int i=0;i<d.size();i++) {
if(check(d[i])) ans += dsize[d[i]];
}
cout<<ans<<endl;
}