暑假集训3

KafuuChinocpp · 2022-08-15 18:56:25 · 个人记录

暑假集训3

我怎么越来越菜了

T1$ $数列

考察扩展欧几里得，既然没有什么可写的，那我就手推一下扩展欧几里得吧

我们有一个方程k_1*a+k_2*b=gcd(a,b)

欧几里得告诉我们gcd(a,b)==gcd(b,a mod b)

我们假设我们已经知道了一个方程k_1*b+k_2*(a mod b)=gcd(a,b)的一组可行解

那么我们拆开mod有k_1*b+k_2*(a-\lfloor\tfrac{a}{b}\rfloor*b)=gcd(a,b)

那么我们有k_2*a+(k_1-k_2*\lfloor\tfrac{a}{b}\rfloor)*b=gcd(a,b)

那么我们就可以递归求解了

这道题需要我们求出\left|k_1\right|+\left|k_2\right|，我们知道对于k_1和k_2

它们的解集分别为k_1=k_1+k*\tfrac{b}{gcd(a,b)},k_2=k_2-k*\tfrac{a}{gcd(a,b)}

很容易发现\left|k_1\right|+\left|k_2\right|是一个单峰函数，那么我们就可以进行二分，我们可以二分k计算答案

code

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
const long long inf = 9999999999;
int n;
long long A,B,x[MAX + 5],ans;
long long Exgcd ( long long a,long long b,long long &k1,long long &k2 )
{
    if ( !b ){k1 = 1;k2 = 0;return a;}
    long long ans = Exgcd(b,a % b,k1,k2);
    long long t = k1 - a / b * k2;
    k1 = k2,k2 = t;
    return ans;
}
long long lower_find ( long long k1,long long k2,long long a,long long b )
{
    long long l,r,mid,lower,upper,now;
    l = ~inf,r = inf;
    while ( l <= r )
    {
        mid = ( l + r ) / 2;
        lower = abs(k1 + ( mid - 1 ) * a) + abs(k2 - ( mid - 1 ) * b);
        upper = abs(k1 + ( mid + 1 ) * a) + abs(k2 - ( mid + 1 ) * b);
        now = abs(k1 + mid * a) + abs(k2 - mid * b);
        if ( lower > now && now > upper ) l = mid + 1;
        else if ( lower < now && now < upper ) r = mid - 1;
        else return abs(k1 + mid * a) + abs(k2 - mid * b);
    }
    return abs(k1 + mid * a) + abs(k2 - mid * b);
}
int main()
{
    long long k1,k2,g,k;
    scanf("%d%lld%lld",&n,&A,&B);
    for ( int i = 1;i <= n;i ++ ) scanf("%lld",&x[i]);
    g = Exgcd(A,B,k1,k2);
    for ( int i = 1;i <= n;i ++ )
    {
        if ( x[i] % g ){printf("-1");return 0;}
        k = x[i] / g;
        ans += lower_find(k1 * k,k2 * k,B / g,A / g);
    }
    cout << ans;
    return 0;
}

T2$ $数对

我们考虑对这个序列进行排序，再进行其他操作

如果一个点i要放在j的前面，那么i可以放在j的前面我们有a_i<=b_j，j不可以放在i的前面我们有a_j>b_i

那么我们有a_i<=b_j，-a_j<-b_i

将两个式子合并a_i-a_j<b_j-b_i

那么a_i+b_i<a_j+b_j

我们可以以此重载运算符，进行排序，但是我们还需要考虑一下a_i+b_i==a_j+b_j

我们尝试用一些例子进行处理，如果我们有二元组(左边为a，右边为b)

2$ $5

3$ $4

5$ $2

那么对于2 5和3 4的位置我们其实不需要进行考虑，因为当2<4并且3<5，我们需要考虑5 2的位置

最优的方案是把它尽可能放在后边，因为当它在后边时2 5和3 4才有更大的可能被同时选到

因此对于a_i+b_i==a_j+b_j，我们把a<b的放在前面。把a>b的放在后面

排完序后我们考虑dp，我们设f[i][j]表示到达了第i个决策点，以往选过的二元组中最大的a等于j的最大权值

我们考虑枚举第i-1个决策点的状态，显然我们需要满足j<=b[i]，我们转移出j=max(j,a[i])

那么我们分类讨论

如果a[i]<=b[i]我们有

f[i][a[i]]=max(f[i-1][a[i]],max_{j=1}^{a[i]}(f[i-1][j]+w[i]))

f[i][j]=f[i-1][j]+w[i](j>=a[i]+1)

如果a[i]>b[i]我们有

f[i][a[i]]=max(f[i-1][a[i]],max_{j=1}^{b[i]}(f[i-1][j]+w[i]))

我们发现这些操作其实是区间加和，区间取max，单点修改的操作，因此我们用线段树进行优化，时间复杂度为nlog2n

code

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
const long long inf = 99999999999999;
struct Kcc
{
    int a,b,w;
    inline bool operator < ( const Kcc &Q ) const
    {
        if ( (long long) a + b == (long long) Q.a + Q.b ) return a < b;
        return (long long) a + b < (long long) Q.a + Q.b;
    }
}s[MAX + 5];
int n,save[MAX * 2 + 5],len;
struct Segment_tree
{
    #define lson(now) ( now << 1 )
    #define rson(now) ( now << 1 | 1 )
    struct Struct_segment_tree
    {
        long long maxn,lazy;
        Struct_segment_tree(){maxn = lazy = 0;}
    }tree[MAX * 8 + 5];
    inline void push_up ( int now ){tree[now].maxn = max(tree[lson(now)].maxn,tree[rson(now)].maxn);return;}
    inline void push_down ( int now )
    {
        if ( tree[now].lazy )
        {
            tree[lson(now)].lazy += tree[now].lazy;
            tree[rson(now)].lazy += tree[now].lazy;
            tree[lson(now)].maxn += tree[now].lazy;
            tree[rson(now)].maxn += tree[now].lazy;
            tree[now].lazy = 0;
        }
        return;
    }
    void Update ( int now,int l,int r,int ql,int qr,long long x )
    {
        if ( l >= ql && r <= qr ){tree[now].lazy += x;tree[now].maxn += x;return;}
        push_down(now);
        int mid = ( l + r ) >> 1;
        if ( ql <= mid ) Update(lson(now),l,mid,ql,qr,x);
        if ( qr > mid ) Update(rson(now),mid + 1,r,ql,qr,x);
        push_up(now);
        return;
    }
    long long Query_max ( int now,int l,int r,int ql,int qr )
    {
        if ( l >= ql && r <= qr ) return tree[now].maxn;
        push_down(now);
        int mid = ( l + r ) >> 1;
        long long ans = ~inf;
        if ( ql <= mid ) ans = max(ans,Query_max(lson(now),l,mid,ql,qr));
        if ( qr > mid ) ans = max(ans,Query_max(rson(now),mid + 1,r,ql,qr));
        return ans;
    }
    void Update ( int now,int l,int r,int pos,long long x )
    {
        if ( l == r ){tree[now].maxn = max(tree[now].maxn,1ll * x);return;}
        push_down(now);
        int mid = ( l + r ) >> 1;
        if ( pos <= mid ) Update(lson(now),l,mid,pos,x);
        else if ( pos > mid ) Update(rson(now),mid + 1,r,pos,x);
        push_up(now);
        return;
    }
}Tree;
int main()
{
    scanf("%d",&n);
    for ( int i = 1;i <= n;i ++ )
    {
        scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].w);
        save[++len] = s[i].a;
        save[++len] = s[i].b;
    }
    sort(s + 1,s + 1 + n);
    sort(save + 1,save + 1 + len);
    len = unique(save + 1,save + 1 + len) - ( save + 1 );
    for ( int i = 1;i <= n;i ++ )
    {
        s[i].a = lower_bound(save + 1,save + 1 + len,s[i].a) - save;
        s[i].b = lower_bound(save + 1,save + 1 + len,s[i].b) - save;
    }
    for ( int i = 1;i <= n;i ++ )
    {
        if ( s[i].a <= s[i].b )
        {
            if ( s[i].a + 1 <= s[i].b ) Tree.Update(1,1,len,s[i].a + 1,s[i].b,s[i].w);
            Tree.Update(1,1,len,s[i].a,Tree.Query_max(1,1,len,1,s[i].a) + s[i].w);
        }
        else if ( s[i].a > s[i].b )
        {
            Tree.Update(1,1,len,s[i].a,Tree.Query_max(1,1,len,1,s[i].b) + s[i].w);
        }
    }
    cout << Tree.Query_max(1,1,len,1,len);
    return 0;
}

T3$ $最小距离

多源最短路

我们将每个特殊点扔进Spfa的队列或dij的优先队列中，将它们的dis均置成0然后去更新其他点的最短路，同时记录其他点的原点的编号，统计答案时我们枚举每一条边，如果这一条边连接的两个节点u和v的belong不同，那么我们用dis[u]+dis[v]+w去更新两个节点的belong的ans

code

#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5;
int n,m,p,a[MAX + 5];
struct node{int u,v,next,w;}edge[MAX * 2 + 5];
int head[MAX + 5],total;
inline void Add ( int u,int v,int w )
{
    edge[++total].u = u;
    edge[total].v = v;
    edge[total].w = w;
    edge[total].next = head[u];
    head[u] = total;
    return;
}
bool in[MAX + 5];
long long dis[MAX + 5],ans[MAX + 5];
int belong[MAX + 5];
queue <int> q;
inline void Spfa ()
{
    memset(dis,0x3f,sizeof(long long) * ( n + 2 ));
    for ( int i = 1;i <= p;i ++ )
    {
        dis[a[i]] = 0;
        in[a[i]] = true;
        belong[a[i]] = a[i];
        q.push(a[i]);
    }
    while ( !q.empty() )
    {
        int now = q.front();
        q.pop();
        in[now] = false;
        for ( int i = head[now];i;i = edge[i].next )
        {
            if ( dis[edge[i].v] > dis[now] + edge[i].w )
            {
                dis[edge[i].v] = dis[now] + edge[i].w;
                belong[edge[i].v] = belong[now];
                if ( !in[edge[i].v] )
                {
                    in[edge[i].v] = true;
                    q.push(edge[i].v);
                }
            }
        }
    }
    return;
}
int main()
{
    int u,v,w;
    scanf("%d%d%d",&n,&m,&p);
    for ( int i = 1;i <= p;i ++ ) scanf("%d",&a[i]);
    for ( int i = 1;i <= m;i ++ )
    {
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w),Add(v,u,w);
    }
    Spfa();
    memset(ans,0x3f,sizeof(long long) * ( n + 2 ));
    for ( int i = 1;i <= total;i ++ )
    {
        if ( belong[edge[i].u] != belong[edge[i].v] )
        {
            ans[belong[edge[i].u]] = min(ans[belong[edge[i].u]],dis[edge[i].u] + dis[edge[i].v] + edge[i].w);
            ans[belong[edge[i].v]] = min(ans[belong[edge[i].v]],dis[edge[i].u] + dis[edge[i].v] + edge[i].w);
        }
    }
    for ( int i = 1;i <= p;i ++ ) printf("%lld ",ans[a[i]]);
    return 0;
}

T4$ $真相

显然当没有人说这群OIer里有几个人说的是实话时，我们可以随机选一个人，首先假设他说的是实话，那么我们可以推测他的下一个人是否说的是实话，进而推测下一个人的下一个人……这样我们可以一直推测到起点，我们直接check当前的推测与我们的假设是否产生矛盾，如果没有产生矛盾，那么我们找到了一种可行的方案，我们可以输出consistent，如果产生矛盾，我们继续假设他说的是谎话，用同样的方法推测到起点，再次check是否矛盾即可，如果两种假设都不可行，那么我们输出inconsistent

那么我们再考虑有人说这群OIer里有几个人说的是实话时，这时我们可以发现，这几个说这群OIer里有几个人说的是实话的人将换分割成了几条链，每个链之间不会产生干扰，那么我们可以枚举这群OIer里有几个人说的是实话，然后我们可以确定这几个说这群OIer里有几个人说的是实话的人说的是实话还是谎话，通过他们的实话和谎话我们可以推测他们所属的链中有几个人说的是实话，那么我们只需要检查说实话的人的个数与我们枚举的个数是否相等即可

但是这样的时间复杂度是O(n^2)的，那么我们考虑进行优化，其实对于每一个说这群OIer里有几个人说的是实话的人，他们说的话只有两种可能性，一种是实话，一种是谎话，那么我们可以预处理出每一个说这群OIer里有几个人说的是实话的人说实话时他们所属的链中有几个人说的是实话，谎话时有几个人说的是实话，我们设有一个人说有x个人说实话，那么当他说的是实话时，他所属的链上说实话的人数个数只对我们枚举的i等于x时产生贡献，那么我们用一个桶bin[x]维护i等于x时有几个人说实话，我们可以将刚才我们求得的说实话的人的个数插入bin[x]里，我们考虑他说的是假话，那么他所属的链上说实话的人的个数只对我们枚举的i不等于x时产生贡献，因此我们要将我们求得的说实话的人的个数插入bin[j](j!=x)里，那么这相当于一次区间修改操作，可以使用树状数组或线段树进行优化，但我们有更好的方法，我们可以维护差分数组f，这样我们的时间复杂度为O(n)

code

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5;
int T,n;
char said[MAX + 5];
int say[MAX + 5],total;
inline void Check1 ()
{
    bool truth;
    truth = true;
    for ( int i = 1;i <= n;i ++ ) if ( said[i] == '-' ) truth = !truth;
    if ( truth ){printf("consistent\n");return;}
    truth = false;
    for ( int i = 1;i <= n;i ++ ) if ( said[i] == '-' ) truth = !truth;
    if ( !truth ){printf("consistent\n");return;}
    printf("inconsistent\n");
    return;
}
int bin[MAX + 5],f[MAX + 5];
inline int Front ( int pos ){return ( pos - 1 ) ? ( pos - 1 ) : n;}
inline void Check2 ()
{
    memset(bin,0,sizeof(int) * ( n + 2 ));
    memset(f,0,sizeof(int) * ( n + 2 ));
    int st,ed,pos;
    for ( int i = 1;i <= n;i ++ ) if ( said[i] == '$' ){st = ed = i;break;}
    bool now;
    int cnt1,cnt2;
    do
    {
        pos = st;
        now = true,cnt1 = cnt2 = 0;
        cnt1 ++;
        while ( said[Front(st)] != '$' )
        {
            st = Front(st);
            if ( said[st] == '-' ) now = !now;
            cnt1 += now,cnt2 += !now;
        }
        bin[say[pos]] += cnt1;
        f[0] += cnt2;
        if ( say[pos] <= n ) f[say[pos]] -= cnt2;
        if ( say[pos] + 1 <= n ) f[say[pos] + 1] += cnt2;
        st = Front(st);
    }while ( st != ed );
    bin[0] += f[0];
    for ( int i = 1;i <= n;i ++ )
    {
        f[i] = f[i - 1] + f[i];
        bin[i] += f[i];
    }
    for ( int i = 0;i <= n;i ++ ) if ( bin[i] == i ){printf("consistent\n");return;}
    printf("inconsistent\n");
    return;
}
int main()
{
    cin.tie(NULL);
    scanf("%d",&T);
    while ( T -- )
    {
        total = 0;
        scanf("%d",&n);
        for ( int i = 1;i <= n;i ++ )
        {
            cin >> said[i];
            if ( said[i] == '$' ) cin >> say[i],total ++;
        }
        if ( !total ) Check1();
        else if ( total ) Check2();
    }
    return 0;
}