河南萌新联赛2024第（二）场 ADEFGHIJ

A-国际旅行Ⅰ

思路：因为都是连通的，所以直接排序就行了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n,m,q; 
int a[N],fa[N];
int b[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>q;
    int cnt = 0;
    for(int i = 1;i <= n; i++){
        cin>>a[i];
    }

    for(int i = 1;i <= m; i++)
    {
        int u,v; cin>>u>>v;
    }

    sort(a+1,a+1+n);
    
    while(q--)
    {
        int k; cin>>k;
        cout<<a[k]<<"\n";

    }

    
    return 0;
}

D-A*BBBB

思路：长度是\(1e6\),普通的高精度肯定是不行了。我们观察一下这个题，发现\(b\)每一位都相同，这肯定是突破口,我们发现：\(a\times b = a \times x \times(1111...) = c\times(1111...)\)

而对于\(c\times 1111...\)怎么办呢？

我们手玩样例看看：

12345*1111

    12345
   12345
  12345
 12345
 ————————————
 [1] [1,2] [1,2,3] [1,2,3,4] [2,3,4,5] [3,4,5] [4,5] [5]

我们竖着看，发现每一位都是有规律的。我们可以预处理出前缀和，然后一位一位算贡献即可。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;

int pre[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        memset(pre,0,sizeof(pre));
        //a * b = a * x * (11111...)
        string a,b; cin>>a>>b; int x = b[0]-'0';
        if(a[0] == '0' || b[0] == '0')
        {
            cout<<0<<"\n";
            continue;
        }

        reverse(a.begin(),a.end());//从低位开始
        vector<int>v;
        int p = 0;//进位
        for(int i = 0;i < a.size(); i++)
        {
            int t = p + (a[i]-'0')*x;
            v.push_back(t % 10);
            p = t/10;
        }

        while(p)
        {
            v.push_back(p%10);
            p/=10;
        }

        reverse(v.begin(),v.end());//算完之后正回来
   
        for(int i = 1;i <= v.size(); i++)//预处理前缀和
            pre[i] = pre[i-1] + v[i-1];
        vector<int>ans;
        p = 0;
        int n = v.size(),m = b.size();
        //12345*1111
        //   12345
        //  12345
        // 12345
        //12345

        for(int i = 1;i <= n+m-1; i++)
        {
            int l = max(0,n-i);
            int r = min(n,n+m-i);
            // cout<<l<<" "<<r<<"\n";
            int t = p + pre[r] - pre[l];
            ans.push_back(t%10);
            p = t/10;
        }

        while(p)
        {
            ans.push_back(p%10);
            p/=10;
        }

        reverse(ans.begin(),ans.end());
        for(auto x : ans)
            cout<<x;
        cout<<"\n";
    }


    return 0;
}

E-“好”字符

思路：我们肯定是一个字母一个字母来考虑。当考虑其他字母的时候，这个字母可以当作是没有。那么我们可以转化为类似01串的形式。

具体来说：比如\(acabxb\)，当我们只关注\(a\)的时候就变成\(101000\)

因为循环同构也是可以的，我们考虑把\(b\)串double一下，这样就能有所有的情况了。

每次对一个字母进行01串的哈希，如果有一样的说明就可以。

举例来说：

a: acabxb
b: eababf -> eababfeababf

'a'：
a: 101000
b: 0[10100]010100

'b':
a: 000101
b: 00101[000101]0

类似这样子，以此类推。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;

ll P = 131;
ll pm[N],ha1[N],ha2[N];

void Hash(string s,char c,ll *ha)
{
    for(int i = 1;i <= s.size(); i++)
        ha[i] = ha[i-1]*P+(s[i]==c);
}


ll get(ll ha[],int l,int r)
{
    return ha[r]-ha[l-1]*pm[r-l+1];
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int n; cin>>n;
    string s,t; cin>>s>>t;
 
    set<char>se(s.begin(),s.end());//只用考虑a中存在的字母就行了
    s = "?"+s;
    t = "?"+t+t;
    pm[0] = 1;
    for(int i = 1;i <= N; i++)
        pm[i] = pm[i-1]*P;
    int ans = 0;
    for(auto c : se)
    {
        Hash(s,c,ha1);
        Hash(t,c,ha2);

        for(int i = 1;i <= n; i++)
        {
            if(get(ha1,1,n) == get(ha2,i,i+n-1)){
                ans++;
                break;
            }
        }
    }

    cout<<ans<<"\n";

    return 0;
}

F-水灵灵的小学弟

签到不多说

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int t; cin>>t;
    while(t--)
    {
        int a,b; cin>>a>>b;
        cout<<"DHY\n";
    }

    return 0;
}

G-lxy的通风报信

思路：因为它必须一个点一个点走，即和并一个后再一起走到下一个这样子。那意味着如果所有的军队不是连通的，那么肯定是不行的。如果是连通的，我们可以考虑先求出任意两点的最短距离，然后再用最小生成树把它们都连起来就行了。

那么如何求出任意两个点的最短距离呢？我们考虑bfs。每次对一个军队bfs求他到其他军队的最短距离然后记录下来。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e3 + 10;


int n,m;
char a[N][N];
int mp[N][N];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
bool in(int x,int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int cnt = 0;

bool cmp(array<int,3>a,array<int,3>b)
{
    return a[0] < b[0];
}



int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m;

    for(int i = 1;i <= n; i++){
        for(int j = 1;j <= m; j++){
            cin>>a[i][j];
            if(a[i][j] == '*')mp[i][j] = ++cnt;
        }
    }
    vector<vector<int>>dist2(cnt+1,vector<int>(cnt+1,0));//用于记录任意两个军队的最短距离

    auto bfs=[&](int sx,int sy)->bool{
        queue<array<int,2>>q;
        q.push({sx,sy});
        vector<vector<bool>>vis(n+1,vector<bool>(m+1,false));
        vector<vector<int>>dist(n+1,vector<int>(m+1,0));

        vis[sx][sy] = true;
        dist[sx][sy] = 0;
        int c = 1;
        while(!q.empty())
        {
            auto [x,y] = q.front();
            q.pop();
            if(a[x][y] == '*')
                dist2[mp[sx][sy]][mp[x][y]] = dist[x][y];
            for(int i = 0;i < 4; i++)
            {
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];

                if(in(dx,dy) && !vis[dx][dy] && a[dx][dy] != '#'){
                    vis[dx][dy] = true;
                    dist[dx][dy] = dist[x][y] + 1;
                    if(a[dx][dy] == '*')c++;
                    q.push({dx,dy});
                }
            }
        }
        return c == cnt;//都可达
    };

   
    auto Krusal=[&]->void{
        vector<array<int,3>>e;
        vector<int>p(cnt+1,0);

        for(int i = 1;i <= cnt; i++)
        {
            p[i] = i;
            for(int j = i+1;j <= cnt; j++)
            {
                e.push_back({dist2[i][j],i,j});
            }
        }

        sort(e.begin(),e.end(),cmp);
        function<int(int)> find=[&](int x)->int{
                if(x!=p[x]) p[x]=find(p[x]);
                return p[x];
            };
        

        int ans = 0;
        for(int i = 0;i < e.size(); i++)
        {
            auto [w,u,v] = e[i];

            u = find(u),v = find(v);
            if(u != v){
                p[u] = v;
                ans += w;
            }
        }
        cout<<ans<<"\n";
    };


    bool ok = true;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= m; j++)
        {
            if(a[i][j] == '*')
            {
                if(!bfs(i,j)){
                    ok = false;
                    break;
                }
            }
        }
        if(!ok)break;
    }


    if(ok)Krusal();
    else cout<<"No\n";

    return 0;
}

H-狼狼的备忘录

思路：就是一个模拟题。考虑先按名字分组，然后内部信息后缀暴力判断要不要留。记得要sort就行了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;
map<string,int>mp;
int idx = 1;
vector<string>v[N];
set<string>s;


struct ty 
{
    string name;
    int m;
    vector<string>vx;
};

vector<ty>ans;

void check(string name)
{
    int x = mp[name];
    int m = v[x].size();
    vector<bool>del(m,false);

    for(int i = 0;i < m; i++)
    {
        for(int j = 0;j < m; j++)
        {
            if(i == j)continue;
            if(!del[i] && !del[j])
            {
                int len1 = v[x][i].size(),len2 = v[x][j].size();

                bool ok = true;

                while(1)
                {
                    if(len1 == -1 || len2 == -1)break;
                    if(v[x][i][len1] != v[x][j][len2]){

                        ok = false;
                        break;
                    }
                    len1--,len2--;
                }
                
                if(ok)
                {                    
                    if(len1 == -1)
                        del[i] = true;
                    else if(len2 == -1)
                        del[j] = true;
                }
            }
        }
    }

    int cnt = 0;
    vector<string>stay;
    for(int i = 0;i < m; i++)
    {
        if(!del[i]){
            cnt++;
            stay.push_back(v[x][i]);
        }
    }

    sort(stay.begin(),stay.end());
    ans.push_back({name,cnt,stay});

}

bool cmp(ty a,ty b)
{
    return a.name < b.name;
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n;
    for(int i = 1;i <= n; i++)
    {
        string x; int op; cin>>x>>op;
        if(mp[x] == 0)
        {
            mp[x] = idx++;
        } 
        s.insert(x);
        for(int j = 1;j <= op; j++)
        {
            string y; cin>>y;
            v[mp[x]].push_back(y);
        }
    }

    for(auto name : s)
    {
        check(name);
    }

    sort(ans.begin(),ans.end(),cmp);


    cout<<ans.size()<<"\n";
    for(auto [name,op,v] : ans)
    {
        cout<<name<<" "<<op<<" ";
        for(auto x : v)
        {
            cout<<x<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

I-重生之zbk要拿回属于他的一切

思路：暴力判断子串就行了。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    string s; cin>>s;
    
    s = "?" + s;
    string t = "?chuan";
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        if(s[i] == 'c' && i + 4 <= n)
        {
            int idx = 1;
            bool ok = true;
            for(int j = i;j <= i+4; j++)
            {
                if(s[j] != t[idx++]){
                    ok = false;
                    break;
                }
            }
            if(ok)ans++;
        }
    }

    cout<<ans<<"\n";

    return 0;
}

J-这是签到

思路：行列式模板题，套板子秒

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
struct Matrix {
    ll N;
    vector<vector<ll>> A;
    Matrix() { N = 0;}
    Matrix(int n) {
        N = n;
        A.resize(N + 1);
        for (int i = 0; i <= N; i ++)
            A[i].resize(N + 1, 0);
    }
    void init(vector<vector<ll>> a, int n) {
        A = a;
        N = n;
    }
 
    Matrix operator*(const Matrix &b) const {
        Matrix res(b.N);
 
        for (int i = 1; i <= b.N; ++i)
            for (int j = 1; j <= b.N; ++j)
                for (int k = 1; k <= b.N; ++k)
                    res.A[i][j] = (res.A[i][j] + A[i][k] * b.A[k][j]);
        return res;
    }
    Matrix qpow(ll k) {
        Matrix res(N);
 
        //斐波那契数列初始化
        //res.A[1][1] = res.A[1][2] = 1;
        //A[1][1] = A[1][2] = A[2][1] = 1;
 
        //单位矩阵
        for (int i = 0; i <= N; i ++)
            res.A[i][i] = 1;
 
        while (k) {
            if (k & 1) res = res * (*this);
            (*this) = (*this) * (*this);
            k >>= 1;
        }
        return res;
    }
    //求行列式
    ll det() {
        return DET(A, N);
    }
 
    ll DET(vector<vector<ll>> arr1, int n) {
        ll sum = 0;
        //i是第一行的列指标，M是余子式的值，sum是行列式的计算值
        if (n == 1)//一阶行列式直接得出结果
            return arr1[0][0];
        else if (n > 1) {
            for (int i = 0; i < n; i++) {
                //按照第一行展开
                ll M = Minor(arr1, i, n);
                sum += pow(-1, i + 2) * arr1[0][i] * M;
            }
        }
        return sum;
    }
    ll Minor(vector<vector<ll>> arr1, int i, int n) {
        vector<vector<ll>>arr2(n-1,vector<ll>(n-1));
        //以下为构造余子式的过程。
        for (int j = 0; j < n - 1; j++) {
            for (int k = 0; k < n - 1; k++) {
                if (k < i)
                    arr2[j][k] = arr1[j + 1][k];
                else if (k >= i)
                    arr2[j][k] = arr1[j + 1][k + 1];
            }
        }
 
        return DET(arr2, n - 1);
        //构造完后，余子式是一个新的行列式，返回DET函数进行计算。
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, m;
    cin >> n >> m;
 
    vector<vector<ll>>a(max(n,m),vector<ll>(max(n,m),0));


    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];
 
    ll ans = 1e9;
 
    Matrix Ma;
    for (int i = 1; i <= max(n, m); i ++) {
        vector<vector<ll>>ok(i,vector<ll>(i,0));
		//子矩阵
        for (int j = 0; j < i; j ++)
            for (int k = 0; k < i; k ++)
                ok[j][k] = a[j][k];
        Ma.init(ok, i);
        ans = min(ans, Ma.det());
    }
 
    cout << ans << '\n';
 
    return 0;
}