https://ac.nowcoder.com/acm/discuss/tutorials?tagId=288841
https://ac.nowcoder.com/discuss/1453293

出题人认为的难度排序：

A M F L C

E J K I

G H B D

实际上的通过人数排序：

M A F L C

E G D K

H J I B

A 智乃的博弈游戏

https://ac.nowcoder.com/acm/contest/95335/A

奇数-奇数=偶数

偶数-奇数=奇数

与偶数互质的数一定是奇数，最终胜利时，胜利状态是奇数。所以无论先手还是后手，轮到自己时如果当前的个数是奇数，最优策略都是只拿走111个，而如果轮到自己时是偶数，则说明必败，任何策略都没用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin>>n;
    if(n%2==0)cout<<"No\n";
    else cout<<"Yes\n";   

    return 0;    
}

M 智乃的牛题

https://ac.nowcoder.com/acm/contest/95335/M

简单的排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    ranges::sort(s);
    string s1="nowcoder";
    ranges::sort(s1);
    if(s==s1)cout<<"happy new year\n";
    else cout<<"I AK IOI\n";
    return 0;    
}

F 智乃的捉迷藏

https://ac.nowcoder.com/acm/contest/95335/F

这一题就两个判断条件

  1. sum 不大于两倍的n
  2. sum 不小于 n
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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
void solve(){
    int n,a,b,c;
    cin>>n>>a>>b>>c;
    int sum=a+b+c;
    if(2*n>=sum&&n<=sum)cout<<"Yes\n";
    else cout<<"No\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

L 智乃的三角遍历

https://ac.nowcoder.com/acm/contest/95335/L
这个就是一个很大的模拟，有思路之后敢写就行了。

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
int a[9][9];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    n++;
    cout<<"Yes\n";
    int dix=0;
    for(int i=1;i<=8;i++)
    {
        for(int j=1;j<=i;j++)
        {
            a[i][j]=++dix;
        }
    }
    int x=1,y=1;
    cout<<1<<' ';
    while(!(x==n&&y==1))
    {
        while(x<n)
        {
            x++;
            y++;
            cout<<a[x][y]<<' ';
        }
        while(y>1)
        {
            y--;
            cout<<a[x][y]<<' ';
            if(y>1)
            {
                x--;
                cout<<a[x][y]<<' ';
            }
            else 
            {
                while(x<n)
                {
                    x++;
                    y++;
                    cout<<a[x][y]<<' ';
                }
            }
        }
    }
    while(x>1)
    {
        x--;
        cout<<a[x][y]<<' ';
    }

    return 0;    
}

C 智乃的Notepad(Easy version)

https://ac.nowcoder.com/acm/contest/95335/C

这一题最主要的思路就是 2*idx - 最长的s[i]

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
const int N=1e5+10;
string s[N];
int ne[10*N][26];
int idx=0;
void insert(string &s)
{
    int p=0;
    for(int i=0;i<s.size();i++)
    {
        int shu=s[i]-'a';
        if(!ne[p][shu])ne[p][shu]=++idx;
        p=ne[p][shu];
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    int maxn=0;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        maxn=max(maxn,(int)s[i].size());
    }
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
    }
    for(int i=1;i<=n;i++)
    {
        insert(s[i]);
    }
    int ret=2*idx-maxn;
    cout<<ret<<'\n';
    return 0;    
}

E 智乃的小球

https://ac.nowcoder.com/acm/contest/95335/E

这一题就是把方向向左和向右的小球的位置分别存到pos[0]和pos[1]中，然后二分小球走过的距离，对每一个向右的小球计算他会碰到几个向左的小球，最终求出答案，注意结果可能是x.5，所以我们刚开始存位置的时候将p*2;

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
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>pos[2];
    for(int i=1;i<=n;i++)
    {
        int p,v;
        cin>>p>>v;
        p*=2;
        pos[v==1].push_back(p);
    }
    for(int i=0;i<=1;i++)ranges::sort(pos[i]);
    int l=0,r=INT_MAX;
    auto check=[&](int m)->bool{
        int ans=0;
        for(auto x:pos[1])
        {
            ans+=(upper_bound(pos[0].begin(),pos[0].end(),x+2*m)-lower_bound(pos[0].begin(),pos[0].end(),x));
        }
        return ans>=k;
    };
    while(r-l>1)
    {
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(r==INT_MAX)cout<<"No\n";
    else {
        cout<<"Yes\n";
        cout<<fixed<<setprecision(20)<<r/2.0L<<'\n';
    }

    return 0;    
}

J 智乃画二叉树

https://ac.nowcoder.com/acm/contest/95335/J

这一题是什么玩意，算了先跳了再说

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
```

## K 智乃的逆序数

[https://ac.nowcoder.com/acm/contest/95335/K](https://ac.nowcoder.com/acm/contest/95335/K)

这一题看到数据范围之后确定可以用O(n^2^)的时间复杂度。

因为一个数组冒泡排序的次数就是这个数组的逆序对数。

我们刚开始先将整个二维数组v从小到大分块排序，cal出逆序对数ans，k-=ans，如果k<0，说明结果不存在。

否则逐步对不在同一个组内的数进行冒泡排序，到k=0时停止，输出结果，如果k始终>0，那么输出“No"	

```cpp
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const ll inf = 1e9;
const ll INF = 1e18;
vector<vector<int>>v;
vector<pair<int,int>>a;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    v.resize(n);
    for(int i=0;i<n;i++)
    {
        int l;
        cin>>l;
        for(int j=1;j<=l;j++)
        {
            int x;
            cin>>x;
            v[i].push_back(x);
        }
    }
    sort(v.begin(),v.end(),[&](const vector<int>&A,const vector<int>&B){
        return A[0]<B[0]; 
    });
    for(int i=0;i<n;i++)
    {
        for(auto j:v[i])
        {
            a.emplace_back(i,j);
        }
    }
    int ans=0;
    for(int i=0;i<a.size();i++)
    {
        for(int j=i+1;j<a.size();j++)
        {
            if(a[i]>a[j])ans++;
        }
    }
    k-=ans;
    if(k<0)return cout<<"No\n",0;
    for(int i=0;i<a.size();i++)
    {
        for(int j=0;j+1<a.size();j++)
        {
            if(a[j].first==a[j+1].first)continue;
            if(k>0&&a[j].second<a[j+1].second)
            {
                swap(a[j],a[j+1]);
                --k;
            }
        }
    }
    if(k>0)return cout<<"No\n",0;
    cout<<"Yes\n";
    for(int i=0;i<a.size();i++)
    {
        cout<<a[i].second<<" \n"[i+1==a.size()];
    }
    return 0;    
}

I 智乃的兔子跳

https://ac.nowcoder.com/acm/contest/95335/I

1
2
3
4
5
6
7
8
9
```

## G 智乃与模数

[https://ac.nowcoder.com/acm/contest/95335/G](https://ac.nowcoder.com/acm/contest/95335/G)

[cuppy](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75183859)

```cpp