算法进阶-深度优先搜索

High33 迷宫寻路

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH33 迷宫寻路
//https://www.nowcoder.com/practice/0c8930e517444d04b426e9703d483ed4
/*
 *DFS模版题
 *dxdy转方向，递归找路线
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

bool ans=false;
ll n,m;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(vector<vector<char>> &grid, int i, int j) {
    grid[i][j]='#';
    if (ans==true||i==n&&j==m) {
        ans=true;
        return;
    }
    for (int k=0;k<4;k++) {
        if (grid[i+dx[k]][j+dy[k]]=='#') continue;
        dfs(grid, i+dx[k], j+dy[k]);
    }
}


void solve() {
    cin>>n>>m;
    vector<vector<char>> grid(n+2, vector<char>(m+2,'#'));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin>>grid[i][j];
        }
    }
    dfs(grid,1,1);
    if (ans==true) {
        cout<<"Yes";
    }else {
        cout<<"No";
    }
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High34 数水坑

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH34 数水坑
//https://www.nowcoder.com/practice/0c8930e517444d04b426e9703d483ed4
/*
 *DFS简单题
 *遍历整个地图，遇到水坑就ans++，并用dfs/bfs找到所有相连位置，并把对应位置改成空地
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

ll ans=0;
ll n,m;
int dx[8]={1,1,1,0,0,-1,-1,-1};
int dy[8]={-1,0,1,1,-1,-1,1,0};
void dfs(vector<vector<char>> &grid, int i, int j) {
    if (grid[i][j] == '.') return;
    grid[i][j]='.';
    for (int k=0;k<8;k++) {
        if (grid[i+dx[k]][j+dy[k]]=='.') continue;
        dfs(grid, i+dx[k], j+dy[k]);
    }
}


void solve() {
    cin>>n>>m;
    vector<vector<char>> grid(n+2, vector<char>(m+2,'.'));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            cin>>grid[i][j];
        }
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (grid[i][j] == 'W') {
                ans++;
                dfs(grid, i, j);
            }
        }
    }
    cout<<ans;
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High35 全排列

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH35 全排列
//https://www.nowcoder.com/practice/1d1fe38275da44b5848add89f9e223b1
/*
 *DFS简单题
 *有全排列函数也可以用其实
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}
ll n;
vi have;
vi visited(10,0);
void dfs() {
    if (have.size() == n) {
        for (const auto &i : have) {
            cout << i << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            have.push_back(i);
            visited[i] = 1;

            dfs();
            visited[i] = 0;
            have.pop_back();
        }
    }

}

void solve() {
    cin >> n;
    dfs();
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High37 模意义下最大子序列和（Easy Version）

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH36 模意义下最大子序列和（Easy Version）
//https://www.nowcoder.com/practice/540ed4ee356c434bb3f96c67521b6671
/*
 *感觉是按下标递增dfs全排列找最大值
 *
 *思路没毛病好吧，对了
 */

ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}

ll ans=0;
ll n,m;
void dfs(vll& a,ll pos,ll sum) {
    ans=max(ans,sum%m);
    for (int i=pos+1;i<=n;i++) {
        dfs(a,i,sum+a[i]);
    }

}

void solve() {
    cin >> n >> m;
    vll a(n+1,0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        dfs(a,i,a[i]);
    }
    cout<<ans;
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High38 数组分组

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH38 数组分组
//https://www.nowcoder.com/practice/9af744a3517440508dbeb297020aca86
/*
 *显然a和b数组的和是固定的
 *所以我们只要看剩下的数加或减是否能把sum从abs（a-b）变成0
 *每个“其他元素”都有+或-两种可能，dfs从数组第一个开始找
 *当找到最后一个时sum==0就把全局变量ans改成true
 *然后全速return退出>>>>>>>>GOGOGO
*/
ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}
ll num=-1;
bool ans= false;
void dfs(vll& have,ll sum,ll pos) {
    if (pos>num){
        if (sum==0) ans=true;
        return;
    }
    dfs(have,sum+have[pos],pos+1);
    if (ans==true) return;
    dfs(have,sum-have[pos],pos+1);
}
void solve() {
    ll n;
    cin >> n;
    ll a=0,b=0;
    vll have;
    for (ll i = 1; i <= n; i++) {
        ll temp;
        cin >> temp;
        if (!(temp%5)) {
            a+=temp;
        }else if (!(temp%3)) {
            b+=temp;
        }else {
            have.push_back(temp);
            num++;
        }
    }
    dfs(have,abs(a-b),0);
    cout<<(ans?"true":"false")<<endl;

}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High39 实现字通配符*

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH39 实现字通配符*
//https://www.nowcoder.com/practice/bab19e5b95b54744aa824e0d7be51487
/*
 *
*/
ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}
string p,s;
set<pll> ans;
void dfs(ll initPos,ll Ppos,ll Spos) {
    if (Ppos >= p.length()) {   //p匹配到头了，说明这是一个答案
        if (Spos-initPos==0) return;//子串长度为0，说明不是答案，退出
        ans.insert({initPos,Spos-initPos});//否则就是答案，进入到答案集合
        //cout<<initPos<<" "<<Spos-initPos<<'\n';
    }
    if (Spos >= s.length()) return;//s不够长了：直接退出
    if (p[Ppos]!='*'&&s[Spos]!=p[Ppos]) return;//不是通配符且字符不匹配，直接退出

    if (p[Ppos]!='*') {
        dfs(initPos,Ppos+1,Spos+1);//操作：同时向前继续尝试匹配
    }else {
        dfs(initPos,Ppos+1,Spos+1);//操作：同时向前继续尝试匹配
        dfs(initPos,Ppos,Spos+1);//操作：因为*忽略s中的这个字符
        dfs(initPos,Ppos+1,Spos);//操作：忽略这个*
    }
}
void solve() {
    string p1;
    cin>>p1>>s;
    for (char c : p1) {         //很关键！一定要优化p，把p所有连续的*删除到只剩一个，不然dfs会重复非常多次！
        if (c == '*' && !p.empty() && p.back() == '*')
            continue;
        p += c;
    }

    for (int i=0; i<s.size(); i++) {    //比较s中和p[0]相同的字符，作为dfs的起点
        if (s[i]==p[0]||p[0]=='*') {
            dfs(i,0,i);
        }
    }
    if (ans.empty()) {//答案集合为空输出-1 0
        cout<<"-1 0";
    }else {
        for (const auto & i:ans) {  //输出答案，用集合是为了去重，肯定有更好做法，可以再研究一下
            cout<<i.first<<" "<<i.second<<'\n';
        }
    }
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High40 kotori和素因子

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH40 kotori和素因子
//https://www.nowcoder.com/practice/7b1c858a3e7a41ed8364178979eaae67
/*
 *n的范围非常非常小，所以可以直接dfs！
 *记得用欧拉筛预处理所有质数就行
*/
ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}


void EulerSieve(ll n, vector<int>& primes,  vector<bool>& isNotPrime) {
        // if (n >= 1) minPrime[1] = 1;

        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                primes.push_back(i);
                // minPrime[i] = i;
            }

            for (int j = 0; j < (int)primes.size(); j++) {
                int p = primes[j];
                long long next = 1LL * i * p;
                if (next > n) break;

                isNotPrime[next] = true;
                // minPrime[next] = p;

                if (i % p == 0) {
                    break;
                }
            }
        }
    }
ll ans=LINF;
void dfs(ll pos,vll& a,vector<bool>& isNotPrime,vector<int>& primes,ll sum) {
    if (pos >= a.size()) {
        ans=min(ans,sum);
        return;
    }
    for (int i = 0; i < primes.size(); i++) {
        //cout<<a[pos]<<' '<<primes[i]<<' '<<!isNotPrime[primes[i]]<<' '<<a[pos]%primes[i]<<'\n';
        if (a[pos]>=primes[i]&&!isNotPrime[primes[i]]&&a[pos]%primes[i]==0) {
            isNotPrime[primes[i]]=true;
            dfs(pos+1,a,isNotPrime,primes,sum+primes[i]);
            isNotPrime[primes[i]]=false;
        }
    }
}
void solve() {
    vector<int> primes;
    ll n,ma=-1;
    cin >> n;
    vll a(n);
    for (ll i=0;i<n;i++) {
        cin >> a[i];
        ma=max(ma,a[i]);
    }
    vector<bool> isNotPrime(ma+1, false);
    EulerSieve(ma,primes,isNotPrime);
    dfs(0,a,isNotPrime,primes,0);
    if (ans==LINF) cout<<-1;
        else cout<<ans;

}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High41 火车进站

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH41 火车进站
//https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
/*
 *n的范围依旧非常非常小，所以可以直接dfs！
 *dfs递归只有两个操作：
 *1.进栈一个，指向进栈顺序数组的下标pos++
 *2.出栈一个，把出栈的放到答案数组，pos不变
 *每次dfs都要还原现场！
 *当答案数组大小等于n时，把本轮答案用字符串保存到另一个数组
 *最后排序整个数组，输出即可！
 *
*/
ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}
vector<string> allAnswers;
vll ans;
ll n;
stack<ll> s;
void dfs(vll& a,ll pos) {
    if (ans.size()==n) {
        allAnswers.emplace_back("");
        for (const auto& i : ans) {
            allAnswers.back() += (to_string(i)+' ');
        }
        return;
    }
    if (!s.empty()) {
        ans.pb(s.top());
        s.pop();
        dfs(a,pos);
        s.push(ans.back());
        ans.pop_back();
    }
    if (pos<=n) {
        s.push(a[pos]);
        dfs(a,pos+1);
        s.pop();
    }
}

void solve() {
    cin >> n;
    vll a(n+1);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dfs(a,1);
    sort(allAnswers.begin(),allAnswers.end());
    for (const auto& i : allAnswers) {
        cout << i << "\n";
    }
}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

High42 小A的线段（easy version）

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back
#define m_p make_pair
#define fi first
#define se second
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
inline ll addmod(ll a, ll b ,ll mod) { return (a + b) % mod; }
inline ll submod(ll a, ll b ,ll mod) { return (a - b + mod) %mod; }
inline ll mulmod(ll a, ll b ,ll mod) { return a * b % mod; }
//HIGH42 小A的线段（easy version）
//https://www.nowcoder.com/practice/03950e31758643d2924601b6dd466c24
/*
 *因为这道题简单版本答案最大也就1024所以可以直接用1024大小的数组模拟
 *dfs回溯一下就行了，没有很难
 *
*/
ll fastPower(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) res = (res * a) % mod;
        a = a * a % mod;
    }
    return res%mod;
}

ll divmod(ll a, ll b, ll mod) {
    if (b == 0) return a;
    if (mod == 0) return b;
    ll inv = fastPower(b, mod-2, mod);
    return mulmod(a, inv ,mod);
}
ll n,m;
ll ans=0;
vector<ll> r;
vector<pii> v;
bool check() {
    ll sz=r.size();
    for (int i = 1; i <= n; i++) {
        if (r[i]<2) return false;
    }
    return true;
}
void change(ll pos) {
    for (int i = v[pos].fi; i <= v[pos].se; i++) {
        r[i]++;
    }
}
void dfs(ll pos) {
    if (pos>=m) {
        if (check()) {
            ans++;
        }
        return;
    }
    dfs(pos+1);
    vll temp=r;
    change(pos);
    dfs(pos+1);
    r=temp;
}
void solve() {
    cin >> n >> m;
    v.resize(m);
    for (int i = 0; i < m; i++) {
        cin>>v[i].first>>v[i].second;
    }
    r.resize(n+1,0);
    dfs(0);
    cout << ans;

}




int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}