拓扑结构+差分约束+SLF最长路+扩欧

倦怠，但还不能休息，我的牌还没有到手~

E. Exchanging Gifts

997m过了，超时了就多交几次就可能过吧……可以把vector改成链式前向行，vector改为二维数组，会优化100ms左右。

#include 
#define endl '\n'
//#define int long long
#define ll long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>
#define re register
using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int n,ind[N];
ll num[N];
bool vis[N],tag[N];
vector<int>v[N],e[N];
unordered_map<ll,ll>mp;
inline void bfs()
{
    queue<int>q;
    q.push(n);
    while(!q.empty())
    {
        int cur=q.front();q.pop();
        if(vis[cur]) continue;
        vis[cur]=1;
        for(int v:e[cur])
        {
            ind[v]++;
            q.push(v);
        }
    }
    num[n]=1;
    q.push(n);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v:e[u])
        {
            num[v]+=num[u];
            ind[v]--;
            if(!ind[v]) q.push(v);
        }
        if(tag[u])
        {
            for(auto x:v[u])
                mp[x]+=num[u];
        }
    }
}
inline void solve()
{
    cin>>n;
    for(re int i=0;i<=n;i++)
    {
        e[i].clear();v[i].clear();
        ind[i]=tag[i]=num[i]=vis[i]=0;
    }
    mp.clear();
    for(re int i=1;i<=n;i++)
    {
        int op;cin>>op;
        if(op==1)
        {
            tag[i]=1;
            int m;cin>>m;
            for(int j=1;j<=m;j++)
            {
                int x;cin>>x;
                v[i].push_back(x);
            }
        }
        else
        {
            int x,y;cin>>x>>y;
            e[i].push_back(x);e[i].push_back(y);
        }
    }
    bfs();
    ll sum=0,mx=0;
    for(auto x:mp)
        sum+=x.second,mx=max(mx,x.second);

    if(mx>=sum-mx) cout<<2ll*(sum-mx)<<endl;
    else cout<<sum<<endl;
}
signed main()
{
    ios;
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

A. Artful Paintings

二分+差分约束
思路：
1.两个未知量可能想到扩欧，本题是毫不相关。而且本题三个变量，需要枚举出sum[n]的值
2.采用求最长路的SLF双端队列实现操作。
4.四类见图方式：sum[r]-sum[l-1]>=k、sum[l-1]-sum[r]>=k-sum[n]、sum[i]-sum[i-1]>=0、sum[i-1]-sum[i]>=-1、sum[n]-sum[0]>=x、sum[0]-sum[n]>=-n

#include 
#define endl '\n'
//#define int long long
#define ll long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>
#define re register
using namespace std;
const int N =7e5+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int n,m1,m2,cnt;
struct border
{
    int l,r,w;
}b1[N],b2[N];
int head[N],dis[N],vis[N],ct[N];
struct node
{
    int to,nxt,w;
}e[N];
void add(int from,int to,int w)
{
    e[++cnt].to=to;
    e[cnt].nxt=head[from];
    e[cnt].w=w;
    head[from]=cnt;
}
int check(int x)         //求最长路
{
    for(int i=0;i<=n;i++) head[i]=-1,dis[i]=-1e9,vis[i]=ct[i]=0;
    cnt=0;
    for(int i=1;i<=m1;i++)
    {
        int l=b1[i].l,r=b1[i].r,w=b1[i].w;
        add(l-1,r,w);
    }
    for(int i=1;i<=m2;i++)
    {
        int l=b2[i].l,r=b2[i].r,w=b2[i].w;
        add(r,l-1,w-x);
    }
    for(int i=1;i<=n;i++)
    {
        add(i-1,i,0);add(i,i-1,-1);
    }
    add(0,n,x);add(n,0,-x);
    vis[0]=ct[0]=1;
    dis[0]=0;
    deque<int>q;
    q.push_back(0);
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=e[i].nxt)
        {
            int v=e[i].to,w=e[i].w;
            if(dis[v]<dis[u]+w)
            {
                dis[v]=dis[u]+w;
                ct[v]=ct[u]+1;
                if(ct[v]>n+1)
                    return 0;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(!q.empty()&&dis[v]>dis[q.front()])
                        q.push_front(v);
                    else
                        q.push_back(v);
                }
            }
        }
    }
    return 1;
}
void solve()
{
    cin>>n>>m1>>m2;
    for(int i=1;i<=m1;i++)
    {
        int l,r,w;cin>>l>>r>>w;
        b1[i]={l,r,w};
    }
    for(int i=1;i<=m2;i++)
    {
        int l,r,w;cin>>l>>r>>w;
        b2[i]={l,r,w};
    }
    int l=0,r=n,mid,ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid))
            r=mid-1,ans=mid;
        else
            l=mid+1;
    }
    cout<<ans<<endl;
}
signed main()
{
    //ios;
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

G - 01Sequence

要废了 。。。最短路都写错了 ，哭

#include 
#define endl '\n'
#define int long long
#define ll long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>
#define re register
using namespace std;
const int N =7e5+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int n,m,dis[N];
vector<PII>g[N];
bool vis[N];

void dij()
{
    for(int i=0;i<=n;i++) dis[i]=inf;
    dis[0]=0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,0});
    while(q.size())
    {
        int u=q.top().second,d=q.top().first;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto x:g[u])
        {
            int v=x.first,w=x.second;
            if(dis[v]>d+w)
            {
                dis[v]=d+w;
                q.push({dis[v],v});
            }
        }
    }
}

void solve()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int l,r,x;cin>>l>>r>>x;
        x=r-l+1-x;
        g[l-1].push_back({r,x});
    }
    for(int i=0; i<=n-1; i++)
    {
        g[i].push_back({i+1,1});
        g[i+1].push_back({i,0});
    }
    dij();
    for(int i=1; i<=n; i++)
        cout<<((dis[i]-dis[i-1])^1)<<" ";
    cout<<endl;
}
signed main()
{
    ios;
//    int T;
//    cin>>T;
//    while(T--)
    solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

D. ConstructOR

思路：
很容易想到要构造的那个数肯定是d的倍数，同时二进制a、b中出现的1.
令k=a|b，此时k不一定是d的倍数，我们只需要找到一个k是d的倍数。
可得出方程：r=d-k%d，也就是说k需要减去这样一个数r才会是d的倍数。
因此：x==r(mod d),由于低位的1会重复，因此左移30位2^30*x==r(mod d)

#include 
#define endl '\n'
#define int long long
//#define ll long long
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define PII pair<int,int>
#define re register
using namespace std;
const int N =7e5+5;
const int inf=1e18;
const int mod=998244353;
const double eps=1e-8;
int a,b,d;
int ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int gcd=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return gcd;
}
int Cal(int a,int b,int c)  //a*x+b*y=c
{
    int x,y;
    int gcd=ex_gcd(a,b,x,y);
    if(c%gcd) return -1;
    x*=c/gcd;
    b/=gcd;
    if(b<0) b=-b;
    int ans=x%b;
    if(ans<=0) ans+=b;
    return ans;
}
void solve()
{
    cin>>a>>b>>d;
    int k=a|b;
    int r=d-k%d;
    if(r==0)
    {
        cout<<k<<endl;return;
    }
    int ans=Cal(1<<30,d,r);
    if(ans!=-1)
        cout<<(k|(ans*(1<<30)))<<endl;
    else
        cout<<-1<<endl;
}
signed main()
{
    //ios;
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61