2020银川K(字典树)牛客小白61C，，等

银川K
题意：给定n个字符串，保证每个字符串都不会是其他字符串的前缀，现在想要找到k个字符串，使得这k个字符串是前a个字符串的前缀并且不能是后面n-a个字符串的前缀，k的最小值是F(a)的值。

请你求出f(1) f(2)…f(n)

思路：字典树。
找出能够代表前a个字符串的前缀是比较好实现的。可以在构建字典树的同时用sum数组标记每个节点被走了多少次，然后再顺序在字典树上查找这n个字符串，查找过程中，每走到一个节点就使得这个节点对应sum数组中的值-1，当sum数组中这个节点值为0说明从根一直到这个节点代表的字符串就可以作为答案并且是优的。

较为困难的是后续合并的处理方案。有如下例子

hcx
hxd
h
显然我们一次要用hcx当前缀，第二次多用一个hxd。但是当到了第三个的时候，发现直接用h就可以了，所以可以视为字典树的c x d节点合并，并且用他们的父/祖节点h来表示。

考虑回溯操作。每次添加前缀的时候都记录下来相应路径上的节点被选了多少次，当用到路径上的节点当前缀时就可以直接从当前累计的前缀数目中减去。

这样的实现思路既可以用回溯，也可以用逆向遍历，也可以建立两颗字典树

#include
using namespace std;
#define endl '\n'
const int N=3e6+10;
int tire[N][30],sum[N],con[N],cnt,ans;
inline int get(char c)
{
    if(c<='z'&&c>='a')
        return c-'a'+1;
    if(c=='.')
        return 27;
    return 28;
}
void ins(string s)
{
    int p=0;
    for(int i=0;i<(int)s.length();i++)
    {
        int id=get(s[i]);
        if(tire[p][id]==0)
        {
            tire[p][id]=++cnt;
        }
        sum[tire[p][id]]++;
        p=tire[p][id];
    }
}
void tfind(string s)
{
    int p=0;
    vector<int> v;
    for(int i=0;i<(int)s.length();i++)
    {
        int id=get(s[i]);
        sum[tire[p][id]]--;
        if(sum[tire[p][id]]==0)
        {
            int dis=1-con[tire[p][id]];
            ans+=dis;
            for(auto x:v)
            {
                con[x]+=dis;
            }
            return ;
        }
        v.push_back(tire[p][id]);
        p=tire[p][id];
    }
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<string> str;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        ins(s);
        str.push_back(s);
    }
    for(int i=0;i<n;i++)
    {
        tfind(str[i]);
        cout<<ans<<'\n';
    }
    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

2020绵阳K（数论）
属于自己玩一会儿，手推一推就能会的题。

题意：给定一个数x，现在要求你选择k个数，使得k个数的和等于x并且所有数都大于1而且所有数两两互质，请你求出这k个数最大值和最小值的差值的最小值。

思路：
奇数情况的话n/2和n/2+1就可以，显然最优

偶数的话通常是分为n/2是奇数和n/2是偶数的

如果n/2是偶数，显然也好弄，n/2-1和n/2+1就可以了

比较容易错的就是n/2是奇数的情况，n/2是奇数的情况最坏情况是4，但是如果不手推几组大概率是会错的。
发现10是3，18是2，说明n/2是奇数的情况下，可能会有些不太对劲的东西，分解一下发现其实他可以找到2 3 4三种不同方案。

#include 

using namespace std;
#define endl '\n'
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    int cnt=0;
    for(cin>>t;t;t--)
    {
        cnt++;
        int x;
        cin>>x;
        int ans=4;
        if(x&1)
            ans=1;
        else
        {
            if((x/2)&1)
            {
                if(x==6)
                {
                    ans=-1;
                }
                else if(x%3==0)
                {
                    ans=2;
                }
                else if(x%3==1)
                {
                    int a=x/3,b=x/3-1,c=x/3+2;
                    if(std::__gcd(a,b)==1&&std::__gcd(a,c)==1&&std::__gcd(c,b)==1)
                        ans=3;
                }
                else
                {
                    int a=x/3+1,b=x/3-1,c=x/3+2;
                    if(std::__gcd(a,b)==1&&std::__gcd(a,c)==1&&std::__gcd(c,b)==1)
                        ans=3;
                }
            }
            else
            {
                ans=2;
            }
        }
        cout<<"Case #"<<cnt<<": "<<ans<<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

2020绵阳D（二分答案）

题意：有n个数，每次你可以选择一个数让其不变然后其他数-1，当有一个数小于0就GG了
问从开始（1）到GG，一共进行了几次

思路：
看着签到就想直接莽上去来着。结果wa了一大片，后来才找到二分答案的思路，其实一开始就有点倾向，但是队友说了个思路我就没在想（）

保留数的操作可以视为+1，但是+1是有前提的，不能有数小于你还在+1.

所以可以试着二分每个数最大能到多少。进而推算出答案，

假设最大到x，那么x-a[i]就是我要进行的操作次数，假如操作的次数都要大于x了，显然是无法维护的

#include 

using namespace std;
#define int long long
#define endl '\n'

const int N = 1e6+1000;

int a[N];
int n;
int sum;
bool check(int x)
{
    int sum1=0;//之前维护了多少次
    x--;//需要变成的数字
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=x)
            continue;
        sum1+=x-a[i];//维护
    }
    return sum1<=x;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>n;
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
        }
        int l=1,r=1e13+100;
        int ans=0;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid))//二分想要的次数
            {
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        cout<<"Case #"<<i<<": "<<ans<<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

牛客小白C
题意：给定二维字符矩阵，‘*’ 代表障碍且不能通过，‘.’代表空且可以通过，一人位于点(x1,y1)，一猫位于点(x2,y2)，当人走到与猫的曼哈顿距离小于r2时人停止走动，此时猫会向人走来。人的活动范围为r1，代表人不能走到与(x1,y1)曼哈顿距离大于r1的点上，注意：当且仅当人走到与(x2，y2)曼哈顿距离小于r2时猫才会向人走来，否则猫处于静止态。请你求出人想与猫汇合的话，人与猫走的步数之和最小是多少。如果无法汇合，请输出-1

思路：

首先，猫的移动范围不受限制，以猫为源点做全局的最短路（BFS）。将猫为源点的最短路记录在mp中

而后以人为源点，在r1和r2的限制条件下BFS出人能到的所有点并且标记出到这些点的最小步数。将人为源点的最短路记录在mp2中

值得注意的是，mp1和mp2初始化为无穷大，以便判断无解的情况。

#include 
using namespace std;
#define endl '\n'
#define int long long 
const int N =1000+100;
int n,m;
char a[N][N];
bool vis[N][N];
int mp[N][N][2];
int r1,r2;
int dir[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int sx,sy,ex,ey;
struct node
{
    int x,y,dis;
};
bool check(int x,int y)
{
    if(x>=1&&x<=n&&y>=1&&y<=m&&!vis[x][y]&&a[x][y]!='*')
        return true;
    return false;
}
void BFS(int xx,int yy,int falg)
{
    queue<node> q;
    q.push({xx,yy,0});
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(a[now.x][now.y]!='*')
            mp[now.x][now.y][falg]=min(mp[now.x][now.y][falg],now.dis);
        if(vis[now.x][now.y]) continue;
        vis[now.x][now.y]=1;
        if(falg==1&&abs(now.x-sx)+abs(now.y-sy)<=r2) continue;
        for(int i=1;i<=4;i++)
        {
            node nex={now.x+dir[i][0],now.y+dir[i][1],now.dis+1};
            if(check(nex.x,nex.y))
            {
                if(falg==1)
                {
                    if(abs(nex.x-ex)+abs(nex.y-ey)<=r1)
                        q.push(nex);
                }
                else
                    q.push(nex);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m>>r1>>r2;
    memset(mp,1e9,sizeof(mp));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            mp[i][j][0]=1e9;mp[i][j][1]=1e9;
            if(a[i][j]=='M')
                sx=i,sy=j;
            if(a[i][j]=='P')
                ex=i,ey=j;
        }
    }
    BFS(sx,sy,0);
    memset(vis,0,sizeof(vis));
    BFS(ex,ey,1);
    int minn=1e9;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(abs(i-sx)+abs(j-sy)>r2||a[i][j]=='*') continue;
            else minn=min(minn,mp[i][j][0]+mp[i][j][1]);
    if(minn==1e9) cout<<-1;
    else cout<<minn;
    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

牛客小白E

题意：求出一个数组在所有排列情况下的所有逆序对的数量。

思路：简单来讲我们这题通过对于每一个逆序对的贡献入手，
一共有n个数，对于一个逆序对，我们其他的n-2个数共有(n-2)！种排列放置方法，现在将选好的两个数放入n个位置中
在保证逆序的情况下有(n-1)*n/2种情况

最后就是 逆序对数量*(n-2)!*(n-1)*n/2

#include 
using namespace std;
#define int long long
#define endl '\n'
const int mod= 1e9+7;
const int N = 1e5+100;
int num[N];
int fac[N];
int fastpow(int n,int a)
{
    int res=1ll;
    while(n)
    {
        if(n&1)
            res=res*a%mod;
        a=a*a%mod;
        n>>=1ll;
    }
    return res%mod;
}
signed main()
{
    int n;
    cin>>n;
    int sum=n;
    fac[0]=1;
    for(int i=1;i<=n;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
    for(int i=1;i<=n;i++)
    {
        int temp;
        cin>>temp;
        num[temp]++;
    }
    int ans=0;
    int x=(n*(n-1))*fastpow(mod-2,2)%mod;
    for(int i=1;i<100000;i++)
    {
        sum-=num[i];
        ans=(ans+sum*num[i]%mod*x%mod*fac[n-2]%mod)%mod;
    }
    cout<<ans;
    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