8/11 二分图染色+KM算法变型+后缀数组+图论

P6185 [NOI Online #1 提高组] 序列

又因为一个小错误浪费了1个半小时。。。我是真的sb啊！
题意：将数组a经过两种操作使得和b数组相等：
操作1：将a数组中，i和j两个下标的数同时加1或者减1.
操作2：将a数组上两个下标值一个加1一个减一，或者一个减1一个加1
思路：
1.操作2一个加1一个减1，但两个数总和不变，由于该操作的传递性，可形成一个连通块，在此连通块内可任意调整值。可理解为缩点操作
2.操作1对数组a同时加1或减1，可转化为a部点加1，b部点减1，或相反。
若是二分图，则a部点值之和要等于b部点权值之和
若非二分图，则此时只对数组a操作，不涉及操作2，要保证操作前前后奇偶行相同，因为每次操作都是加2或者减去2.

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
int n,m,a[N],b[N],f[N],p[N],q[N],g,sz[N],num[3],col[N];
vector<int>e[N];
int r_find(int r)
{
    return r==f[r]?r:(f[r]=r_find(f[r]));
}
bool dfs(int x,int c)
{
    col[x]=c,num[c]+=sz[x];
    int flag=1;
    for(int i=0;i<e[x].size();i++)
    {
        int y=e[x][i];
        if(col[y]==col[x]) flag=0;
        if(!col[y]&&!dfs(y,3-c))
            flag=0;
    }
    return flag;
}
int solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    g=0;
    for(int i=1;i<=n;i++)
        f[i]=i,col[i]=sz[i]=0,e[i].clear();
    for(int i=1,op,x,y;i<=m;i++)
    {
        cin>>op>>x>>y;
        if(op==2) f[r_find(x)]=r_find(y);
        else p[++g]=x,q[g]=y;
    }
    for(int i=1;i<=n;i++)
        sz[r_find(i)]+=b[i]-a[i];
    for(int i=1;i<=g;i++)
    {
        int x=r_find(p[i]),y=r_find(q[i]);
        e[x].push_back(y),e[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(i==r_find(i)&&!col[i])
        {
            num[1]=num[2]=0;
            bool flag=dfs(i,1);
            if(flag && num[1]!=num[2]) return 0;
            if(!flag && ((num[1]^num[2])&1)) return 0;
        }
    }
    return 1;
}
signed main()
{
    int t;cin>>t;
    while(t--)
    {
        if(solve())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    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

P3967 [TJOI2014]匹配

题意：求出男女生间的求出最大匹配和最小匹配
最大匹配：带入模板求出最大完美匹配。
最小匹配：将权值取为负值，最后将答案进行取反操作

#include
#define int long long
#define endl '\n'
#define For(i,a,b) for(i=(a);i<=(b);++i)
#define ios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
using namespace std;
const int N=5e2+5;
const int inf=0x3f3f3f3f;
int match[N];       //右部点匹配了哪个左部点
int va[N],vb[N];    //标记是否在交替路中
int la[N],lb[N];    //左顶标、右顶标的值
int w[N][N],d[N];   //维护更新的delta值
int n,a[N][N];
bool dfs(int x)
{
    va[x]=1;
    for(int y=1;y<=n;y++)
    {
        if(!vb[y])
        {
            if(la[x]+lb[y]-w[x][y]==0)
            {
                vb[y]=1;
                if(!match[y]||dfs(match[y]))
                {
                    match[y]=x;return 1;
                }
            }
            else //不是相等子图则记录i最小的d[y]
                d[y]=min(d[y],la[x]+lb[y]-w[x][y]);
        }
    }
    return 0;
}
int KM()
{
    //预处理
    for(int i=1;i<=n;i++) la[i]=-inf;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        la[i]=max(la[i],w[i][j]);
    for(int i=1;i<=n;i++)
        lb[i]=0;
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            fill(va+1,va+n+1,0);
            fill(vb+1,vb+n+1,0);
            fill(d+1,d+n+1,inf);
            if(dfs(i)) break;
            int delta=inf;
            for(int j=1;j<=n;j++)
                if(!vb[j]) delta=min(delta,d[j]);
            for(int j=1;j<=n;j++)
            {
                if(va[j]) la[j]-=delta;
                if(vb[j]) lb[j]+=delta;
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
        res+=w[match[i]][i];
    return res;
}

void solve()
{
    memset(w,-inf,sizeof w);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j],a[i][j]=w[i][j],w[i][j]=-w[i][j];
    cout<<-KM()<<endl;
    memset(match,0,sizeof match);
    memset(w,-inf,sizeof w);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            w[i][j]=a[i][j];
    cout<<KM()<<endl;
}
signed main()
{
    //ios;
    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

P6140 [USACO07NOV]Best Cow Line S

属于范围0~2000，n^2的方法可以，但若是1e5就得用后缀数组了qaq
直接贪心即可。贪心策略真的太典了，不说了

#include
#define int long long
#define endl '\n'

using namespace std;
const int N=7e5+10;
const int inf=0x3f3f3f3f;
int n;
string s;
void solve()
{
    cin>>n;
    string s1=" ";
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        s1+=s;
    }
    string s2="";
    for(int i=1,j=n;i<=j;)
    {
        if(i==j)
        {
            s2+=s1[i];break;
        }
        if(s1[i]<s1[j]) s2+=s1[i],i++;
        else if(s1[i]>s1[j]) s2+=s1[j],j--;
        else
        {
            int a1=i,a2=j;
            while(s1[a1]==s1[a2]&&a1<a2)
                a1++,a2--;
            if(s1[a1]<s1[a2]) s2+=s1[i],i++;
            else if(s1[a1]>s1[a2]) s2+=s1[j],j--;
            else
                s2+=s1[i],i++;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(i%80==0&&i!=0)
            cout<<endl;
        cout<<s2[i];
    }
    cout<<endl;
}
signed main()
{
    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

P2870 [USACO07DEC]Best Cow Line G

数据范围5e5次方，应使用后缀数组来解决问题了。
得换一个模板了，此模板复杂度有点高，最后一组样例卡住了。
思路：
由于需要比较由前后字母向中间延申直至不同字符的字符串大小，因此想到构造一个新的字符串。
AACBAA —> AACBAA#AABCAA
(一个非常重要而技巧，将前缀转化为后缀)
比较rk[l]和rk[2*(n+1)-r]

#include
#define endl '\n'
#define re register
using namespace std;
const int N=7e6+10;
const int inf=0x3f3f3f3f;
int n,k;
int rk[N],rk2[N];   //以i开头后缀的排名
char s[N],s1[N],str[N];
int sa[N];   //表示sa[i]表示排名i的后缀的开头下标

//求解各个以i为起始下标的后缀字符串的排名
inline bool cmp(re int i,re int j)
{
    if(rk[i]!=rk[j])
        return rk[i]<rk[j];
    int ri=(i+k<=n ? rk[i+k]:-1);
    int rj=(j+k<=n ? rk[j+k]:-1);
    return ri<rj;
}
inline void getsa(int n,char *str)
{
    for(re int i=1;i<=n;i++)
        sa[i]=i,rk[i]=s[i];  //利用ASCLL码
    for(k=1;k<=n;k*=2)
    {
        sort(sa+1,sa+1+n,cmp);
        rk2[sa[1]]=1;
        for(int i=2;i<=n;i++)
            rk2[sa[i]]=rk2[sa[i-1]]+cmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++)
            rk[i]=rk2[i];
    }
}


inline void solve()
{
    scanf("%d",&n);
    for(re int i=0;i<n;i++)
        scanf("%s",str+i);
    for(re int i=0;i<n;i++)
        s[2*(n+1)-i-1]=s[i+1]=str[i];
    s[n+1]='#';
    n=2*n+1;
    getsa(n,s);
    n=(n-1)/2;
    int l=1,r=n,g=0;
    while(l<r)
    {
        if(s[l]<s[r]) s1[++g]=(char)(s[l]),l++;
        else if(s[l]>s[r]) s1[++g]=(char)(s[r]),r--;
        else
        {
            if(rk[l]>rk[2*(n+1)-r])
                s1[++g]=(char)(s[r--]);
            else
                s1[++g]=(char)(s[l++]);
        }
    }
    s1[++g]=(char)(s[l]);
    n=strlen(s1+1);
    for(re int i=1;i<=n;i++)
    {
        printf("%c",s1[i]);
        if(i%80==0) putchar('\n');
    }
}
signed main()
{
    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

P1155 [NOIP2008 提高组] 双栈排序

给定两个栈和一个数组，四个基本操作，要求输出一个字典序最小的操作序列
思路：
1.通常情况下只用一个栈进出a、b，字典序最小。那么什么情况下必须用到两个栈呢？
即： x 2.此时将x和y连一条直线，表示x和y不可放到同一个栈中，利用二分图，若出现奇数环，则不满足题意
3.组后调整字典序b和c、d和a。

#include
#define endl '\n'
#define re register
using namespace std;
const int N=5e3+10;
const int inf=0x3f3f3f3f;
int n,a[N],col[N],g;
char s[N];
vector<int>e[N];
stack<int>s1,s2;
int dfs(int x,int c)
{
    col[x]=c;
    for(int j:e[x])
    {
        if(!col[j])
            dfs(j,3-c);
        else if(col[j]==col[x])
            return 0;
    }
    return 1;
}

inline void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n-1,x=a[n];i>1;i--)
    {
        for(int j=1;j<i;j++)
            if(x<a[j]&&a[j]<a[i])
            {
                e[a[i]].push_back(a[j]);
                e[a[j]].push_back(a[i]);
            }
        x=min(x,a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(!col[a[i]])
        {
            int flag=dfs(a[i],1);
            if(flag==0)
            {
                cout<<0<<endl;return;
            }
        }
    }
    int k=1;
    for(int i=1;i<=n;i++)
    {
        if(col[a[i]]==1)
            s1.push(a[i]),s[++g]='a';
        else
            s2.push(a[i]),s[++g]='c';
        while((!s1.empty()&&s1.top()==k) || (!s2.empty()&&s2.top()==k))
        {
            if(!s1.empty()&&s1.top()==k)
                s1.pop(),s[++g]='b',k++;
            else
                s2.pop(),s[++g]='d',k++;
        }
    }
    for(int i=1;i<g;i++)
    {
        if(s[i]=='c'&&s[i+1]=='b'||s[i]=='d'&&s[i+1]=='a')
            swap(s[i],s[i+1]);
    }
    for(int i=1;i<=g;i++)
        cout<<s[i]<<" ";
    cout<<endl;
}
signed main()
{
    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