Cheeeeen the Cute Cat

题目大意

给定一个二分图，两边有个点，求二分图的最大匹配。

解题思路

模板题，直接（）跑一边二分图即可。

参考代码

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
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define ri register int
using namespace std;
#define gc getchar
template<class T>void read(T&x){
    ri f=1,c;while(c=gc(),c<48||57<c)if(c=='-')f=-1;x=c^48;
    while(c=gc(),47<c&&c<58)x=(x<<3)+(x<<1)+(c^48);x*=f;
}
const int N = 1000010, INF = 0x3f3f3f3f;
vector<int> G[N];
int Nx,Ny,k;

int Mx[N],My[N];
int dx[N],dy[N];
int dis,u,v;
bool used[N];
bool searchP(){
    queue<int> Q;
    dis = INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(int i = 0;i < Nx;++i)
    if(Mx[i] == -1)    Q.push(i), dx[i] = 0;
    while(!Q.empty()){
        int u = Q.front();Q.pop();
        if(dx[u] > dis) break;
        int sz = G[u].size();
        for(int i = 0;i < sz;++i){
            int v = G[u][i];
            if(dy[v] == -1) {
                dy[v] = dx[u] + 1;
                if(My[v] == -1) dis = dy[v];
                else dx[My[v]] = dy[v] + 1, Q.push(My[v]);
            }
        }
    }
    return dis != INF;
}
bool DFS(int u){
    int sz = G[u].size();
    for(int i = 0;i < sz;++i){
        int v = G[u][i];
        if(!used[v] && dy[v] == dx[u] + 1){
            used[v] = true;
            if(My[v] != -1 && dy[v] == dis) continue;
            if(My[v] == -1 || DFS(My[v])){
                My[v] = u;
                Mx[u] = v;
                return true;
            }
        } 
    }
    return false;
}
int MaxMatch(){
    int res = 0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(searchP()){
        memset(used,false,sizeof(used));
        for(int i = 0;i < Nx;++i)
        if(Mx[i] == -1 && DFS(i)) ++res;
    }
    return res;
}
int main(){
    int n;  read(n);
    Nx=Ny=n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            int x;  read(x);
            if(x)  G[i-1].push_back(j+n-1);
        }
    }
    printf("%d\n",MaxMatch());
}

Cirno’s Perfect Equation Class

题目大意

给定，问你所有满足以下条件的二元组的个数：

解题思路

试除法求约数，求出所有c的约数，然后暴力枚举每个约束是否符合上述条件，符合则计数。

时间复杂度：

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;

vector<int> divs;
void get_divisors(int n){
    for(int i=1;i<=n/i;i++)
    {
        if(n%i==0){
            divs.push_back(i);
            if(n/i!=i) divs.push_back(n/i);
        }
    }
}

void solve(){
    divs.clear();
    int k,c,n;
    cin>>k>>c>>n;
    get_divisors(c);
    int ans=0;
    for(int i=0;i<divs.size();i++){
        int b=divs[i];
        if((c-b)%k!=0) continue;
        int a=(c-b)/k;
        if(a==0) continue;
        if(__gcd(a,b)>=n){
            ans++;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Red and Blue and Green

题目大意

给定m个区间，这些区间要么包含要么不相交，每个区间包含一个表示下方构造的排列区间的逆序对数量的奇偶性为(0/1表示偶/奇)。现在要你构造一组排列，使得满足上述所有区间的限制。

解题思路

（以下奇偶性均指区间逆序对的奇偶性）

因为这个区间要么包含要么不交，所以被包含的区间可以作为大区间的子树，不交的两个区间可以作为一个大区间的两个子树或作为两棵树，即我们可以构造出一个树形结构（去掉重复区间）。

我们可以按照区间大小排序，然后建图对每个小区间找到一个包含它的大区间连一条大区间向小区间的边。

通过对树形结构dfs，利用异或的性质，对于一个大区间的奇偶性异或上所有它的子树的奇偶性后若不为0则不合法，不可能构成符合题意的情况。

首先，最初默认pos[i]=i，逆序对数量为偶，在dfs的过程中，如果这个区间奇偶性异或上所有子树的区间奇偶性后为0，则当前区间可以不需要操作，如：为奇，它的子树为奇，，那么当前区间奇偶性已经满足无需操作。反之不符，我们可以通过交换来使逆序对奇偶性改变。

考虑以下几种情况：

首先，要满足每个子树的奇偶性不变的同时使得大区间的奇偶性改变。那么我们可以分类讨论。

①当子树为空时，直接交换当前区间最小的两个数的位置。

②当子树中最左边的区间的左端点与当前树的区间的左端点重合，交换最左边区间的最大值和右边区间的最小值的位置。（因为这里记录得是值为i的位置在哪，所以直接交换和即可。

③剩下的情况也就是最左边的区间的左端点不与当前树这个大区间的左端点重合时，交换子树最左边区间的最小值的位置和{这个最小值-1}的位置。

参考代码

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
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=0;

const int N = 1e3 + 10;

struct Seg {
    int l, r, k;
};
int n, m, a[N], pos[N], deg[N];
vector<Seg> s;
vector<int> G[N];
map<pair<int, int>, int> mp;//记录区间的逆序对奇偶性

void op(int k) { swap(pos[k], pos[k + 1]); }

void dfs(int u) {
    int w = s[u].k;
    //对u区间包含的所有子区间按照左端点排序。
    sort(G[u].begin(), G[u].end(), [&](int a, int b){ return s[a].l <s[b].l; });
    for(auto v: G[u]) {
        dfs(v);
        w ^= s[v].k;//异或判断奇偶性是否统一
    }
    if(!w) return;
    if(G[u].empty()) op(s[u].l);//叶子节点直接交换当前区间最左边两个
    else if (s[G[u][0]].l == s[u].l) op(s[G[u][0]].r);
    else op(s[G[u][0]].l - 1);
    
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        pos[i] = i, mp[{i, i}] = 0;//区间大小为1的逆序对数量必然只能为偶数。
    }
    while(m--){
        int l, r, k;
        cin >> l >> r >> k;
        if(mp.count({l, r}) && mp[{l, r}] != k){//与之前设定的逆序对数量奇偶性不同，出现矛盾，无解。
            cout << -1 << '\n';
            return;
        }
        if(mp.count({l, r})) continue;
        mp[{l, r}] = k;
        s.push_back({l, r, k});
    }
    m = s.size();//此时的m是去掉了相同区间。
    sort(s.begin(), s.end(),[](Seg a, Seg b) { return a.r - a.l < b.r - b.l; });
    for(int i = 0; i < m; i++){//找到所有大区间包含小区间，并从大区间向小区间连边，建立树形结构。
    //因为前面按照区间大小排序，所有j从大于i开始枚举，只有大于i的部分长度才比i大，才有可能包含i区间。
        for(int j = i + 1; j < m; j++){
            if(s[j].l <= s[i].l && s[i].r <= s[j].r){
                G[j].push_back(i), ++deg[i];
                break;
            }
        }
    }

    for(int i = 0; i < m; i++){
        if(!deg[i])
            dfs(i);
    }
    for(int i = 1; i <= n; i++){
        a[pos[i]] = i;
    }
    for(int i = 1; i <= n; i++){
        cout << a[i] << " \n"[i == n];
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Go to Play Maimai DX

题目大意

给定一个只有1，2，3，4的指针，求最短区间满足这个区间内包含1，2，3，4四个数且4这个数的数量至少为k。

题目保证该区间至少有一个1，2，3且至少有k个4

解题思路

双指针，两个指针分别表示此时区间的左右端点，右端点从右边不断加数，左端点判断去掉左端数去掉是否仍满足题意，每次直到左端点右移后不符合含k个4的好区间为止。

时间复杂度：

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;
int n,k;
const int N=1e5+10;
int a[N];
vector<int> cnt(5);
int tot=0;
int cnt4=0;
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=1e9;
    int l=1;
    for(int i=1;i<=n;i++){
        if(!cnt[a[i]]){
            tot++;
        }
        cnt[a[i]]++;
        while(1){
            if(a[l]!=4&&cnt[a[l]]>1||a[l]==4&&cnt[a[l]]>k){
                cnt[a[l]]--;
                l++;
            }else{
                break;
            }
        }
        if(tot==4&&cnt[4]>=k){
            ans=min(ans,i-l+1);
        }
    }
    
    cout<<ans<<endl;

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Nazrin the Greeeeeedy Mouse

题目大意

给定n个奶酪按顺序从左往右放成一条线，每个奶酪有它的重量和体积，有m个袋子，每次Nazrin按顺序拿一个袋子装从左往右装奶酪，如果这个奶酪装不了要么破坏这个要么回去拿下一个袋子，如果奶酪被破坏则不能再拿这个奶酪。

解题思路

观察到，那么我们只需要保留最后min{200,n}个即可。

这里我们规定i=1为用最后min{200,n}中的第一个背包

定义为用前第i个背包，拿到第j个奶酪，且第i个背包已经装的体积为k时的获得的最大重量。

它可以从用前i-1个背包，拿到j-1时的最大重量转移过来，如下：

1
2
3
4
5
6
for(int k=0;k<=sz[i-1];k++){//mx为上一轮拿到j-1的所有状态中的最大值
    mx=max(mx,dp[i-1][j-1][k]);
}
if(k>=v[j]){
	dp[i][j][k]=max({dp[i][j][k],max(mx,dp[i][j-1][k-v[j]])+w[j]});
}

最后的答案是每一轮中拿到最后一个且装的体积最大时的最大值。

时间复杂度： i\le r$$

参考代码

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;
int n,m;
const int N=210,M=1e5+10;
int v[N],w[N],sz[M];
int dp[N][N][N];

void solve(){
    cin>>n>>m;
    for(int i=n;i>=1;i--){
        cin>>v[i]>>w[i];
    }
    for(int i=m;i>=1;i--){
        cin>>sz[i];
    }
    int r=min(m,200LL);
    int ans=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=n;j++){
            int mx=0;
            for(int k=0;k<=sz[i-1];k++){//mx为上一轮拿到j-1的所有状态中的最大值
                mx=max(mx,dp[i-1][j-1][k]);
            }
            for(int k=0;k<=sz[i];k++){
                dp[i][j][k]=max(mx,dp[i][j-1][k]);
                if(k>=v[j]){
                    dp[i][j][k]=max({dp[i][j][k],max(mx,dp[i][j-1][k-v[j]])+w[j]});
                }
            }
        }
    }
    for(int i=1;i<=r;i++){
        ans=max(ans,dp[i][n][sz[i]]);
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}