本场链接:Educational Codeforces Round 102 (Rated for Div. 2)
闲话
场上过了ABC.心态不好D题没推对方向自爆了.E题的话虽然知道这个做法但是没想到转换那一步,最后就十分惨烈的三题收场了.
A. Replacing Elements
题目大意:给定一个数组(a),你可以执行以下操作若干次:找到三个不同的下标(i,j,k),并(a_i = a_j + a_k).问(a)数组是否可能在若干次操作之后对任何元素来说都不大于(d).
思路
显然直接检查一下是否一开始就是合法的,如果不合法就看两个最小值加起来是不是比(d)小的,如果是的话就可以让违反规则的值直接被覆盖成两个较小的值,解决问题.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 105;
int a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,d;scanf("%d%d",&n,&d);
forn(i,1,n) scanf("%d",&a[i]);
sort(a + 1,a + n + 1);
if(a[n] <= d || a[1] + a[2] <= d) puts("YES");
else puts("NO");
}
return 0;
}
B. String LCM
题目大意:对于形如babababa这样的字符串,如果他是某个子字符串经过若干次首位拼接得到的,则可以记作(x*s),表示字符串(s)重复x次的结果.现给定两个字符串(a,b),求两个字符串的(LCM),此处定义为长度最短的一个串并且对两个串都满足:如果给定的字符串表示为(x*s)这样的形式,那么答案串也必须要能表示成(x'*s)的形式.
思路
显然直接对两个串求最小循环节.直接抠出来就可以,顺便求一下两个串需要使用循环节循环的次数,当两个循环节想登的时候,答案串就是两个重复次数的(LCM),反之答案不存在,因为最小的循环节不相同时意味着不可能再凑出不相同的部分,问题无解.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
string div(string s)
{
string res;int n = s.size();
int cur = 1;res += s[0];
while(cur <= n)
{
// cout << res << endl;
if(n % cur)
{
if(cur < n) res += s[cur];
++cur;
continue;
}
int ok = 1;
for(int i = 0;i < n;i += cur)
{
for(int j = 0;j < cur;++j)
{
if(res[j] != s[i + j])
ok = 0;
}
if(!ok) break;
}
if(ok) return res;
if(cur < n) res += s[cur];
++cur;
}
return res = "-1";
}
int gcd(int x,int y)
{
if(y == 0) return x;
return gcd(y,x % y);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
int T;cin >> T;
while(T--)
{
string a,b;cin >> a >> b;
string da = div(a),db = div(b);
// cout << da << " " << db << endl;
if(da != db)
{
cout << -1 << endl;
continue;
}
int sa = a.size() / da.size(),sb = b.size() / db.size();
int r = sa * sb / gcd(sa,sb);
forn(i,1,r) cout << da;cout << endl;
}
return 0;
}
C. No More Inversions
题目大意:给定(n,k),构造一个(a)形如(1,2,3,...,k-1,k,k-1,...,k - (n - k)).要求你构造一个长度为(k)的排列(p),随之构造一个数组(b[i] = p[a[i]]),要求(b)里的逆序对的数量不多于(a)中的逆序对的数量,并且(b)的字典序最大.
数据范围:
(k < n < 2 * k)
(1 leq k leq 2 * 10^5)
思路
手推大一点的数组之后可以发现对于(a)来说他的逆序对个数只产生于最后(k)那一段,于是可以顺手求一下逆序对的个数,接下来考虑怎么构造(p)的问题,如果通过常规的思路去直接构造排列会非常的困难,因为你需要计算逆序对的产生的贡献,但是这个题肯定不可能这么麻烦,还需要提防逆序对个数超过(a).
所以一个比较直截了当的构造方法就是看(a)的最后一段是完全逆序,所以尝试跟(a)一样把一个正常的排列最后几个数完全逆序过来,那么显然对于排列来说,此时构成的逆序对个数是恰好和(a)相等的,接下来看字典序的问题:不难发现字典序需要是尽可能让前面大,但是这里可以发现如果最后一部分直接reverse之后没有触及到第一个元素的位置,那么第一个元素是不可能去颠倒的,因为他一旦颠倒了就会导致逆序对的个数越界.也就是说在最后一段(n-k +1)个数反转前面的部分是不可能作为逆序对的左边较大的一方的,其次把最后一段逆过来做恰好也是让较大的往前排,那么这个做法就是既保证了逆序对的个数没超,也让合理的位置最大,就可以大胆冲一发了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
int l = 1,r = k,_ = n - k + 1;
forn(i,1,k - _) printf("%d ",l++);
forn(i,1,_) printf("%d ",r--);
puts("");
}
return 0;
}
D. Program
有个变量(x)一开始是0,接下来有(n)个操作,要么使(x)加一或者减一.接下来有(m)个询问,每个询问给出两个数([l,r])表示把这段的操作删除,每个询问需要输出一个答案表示删除这段操作之后,整个过程中(x)的取值有多少种.
数据范围:
(1 leq n,m leq 2*10^5)
思路
由于是讨论取值有多少种,假如说没有这个删除操作,那么我们只需要统计整个过程中(x)的最小值和最大值,也就是(x)可以取到的值域,就可以知道他有多少种取值了.接下来考虑怎么做维护.
由于最大值和最小值两个问题独立,只做一边最小值,另一边对称即可.如果删掉了([l,r])这段操作,那么新的这段过程中,最小值有两种来源:第一种是(l-1)这个操作以及他之前的操作可以让(x)得到的最小值,还有一种是从(l-1)这段刚好接到(r+1)这段之后取的的最小值.
考虑做一个前缀和(s[i])表示(x)前(i)次操作的前缀和.根据上面的分析还需要维护一个在(l)次操作及其之前能取得到的最小值,记作(pmn[i]).那么前者就是其直接定义.现在来看第二种怎么拼接的,首先比较容易想到的是要跟前面一样倒过来求一个后缀的最小值(smn[i]),注意这里的后缀的最小值是对前缀和而言的,不是对原始数列而言的.这里的(smn[i])表示在执行了(jin[i,n])次操作中(s[j])能取得的最小值,那么拼接过来实际上也就是让整一段(smn[r + 1])之中去掉删去的这一段的影响,也就是(smn[r + 1] - d)其中(d=s[r] - s[l - 1]).两种情况直接统计就可以了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
const int N = 2e5+7;
char s[N];
int pmn[N],pmx[N],smn[N],smx[N];
int a[N],pre[N],suf[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
scanf("%s",s + 1);
forn(i,1,n)
{
a[i] = a[i - 1];
if(s[i] == '+') ++a[i];
else --a[i];
pmn[i] = min(pmn[i - 1],a[i]);
pmx[i] = max(pmx[i - 1],a[i]);
}
smn[n + 1] = 1e9,smx[n + 1] = -1e9;
forr(i,1,n)
{
smn[i] = min(smn[i + 1],a[i]);
smx[i] = max(smx[i + 1],a[i]);
}
while(m--)
{
int l,r;scanf("%d%d",&l,&r);
int d = a[r] - a[l - 1];
int dw = min({pmn[l - 1],smn[r + 1] - d});
int up = max({pmx[l - 1],smx[r + 1] - d});
printf("%d
",up - dw + 1);
}
}
return 0;
}
E. Minimum Path
题目大意:给定一个(n)点(m)边有权无向图,图中没有自环和重边.定义一条路径的权是路径上所有的边权之和减去所有边权最大值并加上所有边权的最小值.对每个点(iin[2,n])求出从(1)到(i)的路径权最小值.
数据范围:
(2 leq n leq 2 *10^5)
(1 leq m leq 2 *10^5)
(1 leq w_i leq 10^9)
思路
这个题还是比较显然是最短路的拓展的,需要考虑最大值和最小值,对于这种有附加状态的最短路直接把附加状态和当前到的点放在一起就可以了,这里考虑怎么附加.首先肯定不能直接把最大值和最小值直接和(dist)放在一起,范围太大了,即使离散化了也无法接受.考虑转换权值的统计:所有边权之和减掉最大值加上最小值等价于删除一条边并使一条边代价乘2,考虑这种操作得到的结果是否和原来的权值对应:因为求的是最短路,那么删除最小值,加上最小值的两倍一定是最优的,所以这样转换操作之后得到的最短路的结果等价于原来题目的减去最大值和加上最小值的操作.
把(dist)拓展成(dist[u][j][k])表示从起点走到(u)时,(j=1)表示已经删除了一条边,(k=1)表示已经让一条边代价翻倍时的最短路长度.由于所有边权一定都是(geq 0)的直接从起点跑dijkstra就可以了.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define int ll
const int N = 2e5+7,M = 2 * N,INF = 1e9;
int edge[M],succ[M],cost[M],ver[N],idx;
int n,m;
ll dist[N][2][2];
bool st[N][2][2];
struct Node
{
int u;
ll dist;
int j,k;
bool operator>(const Node& _o) const
{
return dist > _o.dist;
}
};
void add(int u,int v,int w)
{
edge[idx] = v;
cost[idx] = w;
succ[idx] = ver[u];
ver[u] = idx++;
}
void dijkstra()
{
forn(i,1,n) forn(j,0,1) forn(k,0,1) dist[i][j][k] = 1e18;
priority_queue<Node,vector<Node>,greater<Node>> pq;pq.push({1,0,0,0});dist[1][0][0] = 0;
while(!pq.empty())
{
auto f = pq.top();pq.pop();
ll d = f.dist;int u = f.u,f1 = f.j,f2 = f.k;
if(st[u][f1][f2]) continue;
st[u][f1][f2] = 1;
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(dist[v][f1][f2] > d + cost[i])
{
dist[v][f1][f2] = d + cost[i];
pq.push({v,dist[v][f1][f2],f1,f2});
}
if(f1 == 0 && dist[v][1][f2] > d)
{
dist[v][1][f2] = d;
pq.push({v,dist[v][1][f2],1,f2});
}
if(f2 == 0 && dist[v][f1][1] > d + 2 * cost[i])
{
dist[v][f1][1] = d + 2 * cost[i];
pq.push({v,dist[v][f1][1],f1,1});
}
if(f1 == 0 && f2 == 0 && dist[v][1][1] > d + cost[i])
{
dist[v][1][1] = d + cost[i];
pq.push({v,dist[v][1][1],1,1});
}
}
}
}
signed main()
{
memset(ver,-1,sizeof ver);
scanf("%lld%lld",&n,&m);
forn(i,1,m)
{
int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
dijkstra();
forn(i,2,n) printf("%lld ",dist[i][1][1]);
return 0;
}
F. Strange Set
题目大意:给定两个数组(a,b)长度均为(n).定义一个集合(S)是牛逼的,当前仅当对于任何一个数(i),如果(i)在(S)集合中,则对于任意的(jin[1,i-1])且(a_j | a_i)的(j)都在(S)集合中.要求你构造一个这样的牛逼集合,一个牛逼集合的牛逼值为(sumlimits_{iin S} b_i).求牛逼值的最大值.不需要输出方案.
数据范围:
(1 leq n leq 3000)
(1 leq a_i leq 100)
(-10^5 leq b_i leq 10^5)
本题内存限制为32MB
思路
对于这样的特殊关系,考虑建图.对于一个(i)来说,如果某个(j)满足条件,那么选择(i)之后就必须要选择(j).其次,这个问题就是要选出一些点,再把他们的对应的(b_i)加起来就是牛逼值.那么整个问题其实也就是:选出一些点,某些点选了的时候有跟着一些点也必须要选,这个模型就是一个经典的最小割模型.
那么先考虑一下求什么结果:最小割分开的是两个集合,如果一个点属于(S)集合认为是被选入集合的,反之就是没有被选入集合的,那么最小割代表的就是从(S)集合走出去到(T)集合的边容量之和.其次,最开始可以贪心地把所有的正的(b_i)加到答案里,之后考虑把不能放的丢出去.
建图:对于所有(b_i>0)的(i)从源点连一条容量为(b_i)的边,反之连向汇点并且容量是(-b_i),因为容量必须是正的.其次对于(i)如果有一个点(j)是必选的,那么就把(i)连向(j)走一条容量为(+infin)的边,一条正无穷容量的边表示不会被割掉.最后回到之前的问题,跑最小割,求(S)集合走到(T)集合的割首先不包含正无穷的边,那么就只剩下从源点走出到另一个集合的点,这样的点本身是正的,一开始是被选入集合的,那么他被割掉也就意味着不被选择,最小割对应的就是让两个集合分开,最少要删掉多少正的(b_i).
那么最后答案就是一开始正的总和去掉最小割.跑个(dinic)就可以了.
当然到这里还没完,由于这个题内存限制只有32MB,所以不能暴力的从每个(i)直接往他所有左边可以连的(j)直接去连,我们可以只连和他最近的那个(a[j])对应的(j).这样每个就只连了一条回去的.最后注意开大边集的空间.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
const int N = 3015,M = 30 * N,INF = 1 << 29;
int edge[M],succ[M],cap[M],ver[N],idx;
int d[N],now[N],n,m,s,t;
int a[N],b[N],last[N];
bool st[N];
void add(int u,int v,int c)
{
edge[idx] = v;
succ[idx] = ver[u];
cap[idx] = c;
ver[u] = idx++;
edge[idx] = u;
succ[idx] = ver[v];
cap[idx] = 0;
ver[v] = idx++;
}
bool bfs()
{
memset(d,0,sizeof d);
queue<int> q;q.push(s);d[s] = 1;now[s] = ver[s];
while(!q.empty())
{
int u = q.front();q.pop();
for(int i = ver[u];~i;i = succ[i])
{
int v = edge[i];
if(cap[i] && !d[v])
{
d[v] = d[u] + 1;
now[v] = ver[v];
q.push(v);
if(v == t) return 1;
}
}
}
return 0;
}
int dinic(int u,int limit)
{
if(u == t) return limit;
int flow = 0;
for(int i = now[u];~i && flow < limit;i = succ[i])
{
int v = edge[i];
if(cap[i] && d[v] == d[u] + 1)
{
int k = dinic(v,min(limit - flow,cap[i]));
if(!k) d[v] = -1;
flow += k;
cap[i] -= k;
cap[i ^ 1] += k;
}
}
return flow;
}
int dinic()
{
int res = 0,flow;
while(bfs())
while(flow = dinic(s,INF))
res += flow;
return res;
}
int main()
{
memset(ver,-1,sizeof ver);
scanf("%d",&n);s = 0;t = n + 1;
forn(i,1,n)
{
scanf("%d",&a[i]);
forn(j,1,a[i])
{
if(a[i] % j == 0 && last[j])
add(i,last[j],INF);
}
last[a[i]] = i;
}
forn(i,1,n) scanf("%d",&b[i]);
ll res = 0;
forn(i,1,n)
{
if(b[i] > 0) res += b[i],add(s,i,b[i]);
else add(i,t,-b[i]);
}
printf("%lld",res - dinic());
return 0;
}