补题：河南萌新联赛2024第（二）场：南阳理工学院

目录

D-A*BBBB

C-小w和大W的决斗

E-"好字符"

G-lxy的通风报信

---

D-A*BBBB

思路：b的每一位都相同，所以b可以表示成x*111111...，先将a*x，再根据b的位数将相前移动，该过程可以使用前缀和数组维护。

#include<bits/stdc++.h>
using namespace std;
using ll =long long ;
#define INF 0x3f3f3f3f
const int N=2e6+5;
const int mod=998244353;
ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1){ans*=a;ans=ans%mod;}a=a*a;a%=mod;b>>=1;}return ans;}
ll gcd(ll a,ll b){ll t=a%b;while(t){a=b;b=t;t=a%b;}return b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll get_inv(ll x){return ksm(x,mod-2);}
int pre[N];
void solve()
{
	string a,b;cin>>a>>b;int x=b[0]-'0';
    if(a[0]=='0'||b[0]=='0')
    {
        cout<<0<<endl;return ;
    }
    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());//反转v，从低位开始记录
    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();
    for(int i=1;i<=n+m-1;i++)
    {
        int r=min(n+m-i,n);
        int l=max(0,n-i);
        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 i:ans) cout<<i;
    cout<<endl;
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int _;cin>>_;while(_--)
    solve();
}

C-小w和大W的决斗

思路：Nim游戏的一种，ai<=100，直接暴力求解sg函数，数组的sg函数的xor值为0则先手必败，否则先手必胜。

#include<bits/stdc++.h>
using namespace std;
using ll =long long ;
#define INF 0x3f3f3f3f
const int N=1e5+5;
const int mod=998244353;
ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1){ans*=a;ans=ans%mod;}a=a*a;a%=mod;b>>=1;}return ans;}
ll gcd(ll a,ll b){ll t=a%b;while(t){a=b;b=t;t=a%b;}return b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll get_inv(ll x){return ksm(x,mod-2);}
int sg[105];
int mex(set<int> v)
{
    unordered_set<int> s;
    for(auto i:v) s.insert(i);
    for(int i=0;;i++)
    {
        if(s.find(i)==s.end())//s中没有即mex为i
            return i;
    }
}
void solve()
{
	for(int i=1;i<=100;i++)
    {
        set<int>v;
        for(int j=0;j<i;j++) v.insert(sg[j]);
        if(i>=3)
        {
            for(int a=1;a<i;a++)//将大于3的数拆成三个正整数
            {
                for(int b=a;b<=i-a-b;b++)
                v.insert(sg[a]^sg[b]^sg[i-a-b]);
            }
        }
        sg[i]=mex(v);
    }
    int ans=0;
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;cin>>x;ans^=sg[x];
    }
    if(ans!=0) cout<<"w win";
    else cout<<"W win";
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//     int _;cin>>_;while(_--)
    solve();
}

E-"好字符"

思路：将a，b倍长，构造循环同构，计算每个字符的哈希值，有哈希值相同的子串，数量就加一。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull P = 131, N = 1e6 + 10;
ull h1[N * 2], h2[N*2], p[N * 2] = {1};
void geth(string &s, char c, ull *h)//初始化
{
	for (int i = 1; i <  s.size(); i++)
		h[i] = h[i - 1] * P + (s[i] == c);	//相当于将字符串s转化为01串处理
}
 
ull get(ull *h, int l, int r)//计算哈希值
{
	return h[r] - h[l - 1] * p[r - l + 1];
}
void solve()
{
	int n;cin>>n;string a,b;cin>>a>>b;
    set<char>st(a.begin(),a.end());
    a=" "+a+a,b=" "+b+b;
    for(int i=1;i<N*2;i++) p[i]=p[i-1]*P;
    int ans=0;
    for(auto c:st)
    {
        geth(a,c,h1),geth(b,c,h2);
        for (int i = 1; i <= n; i++)
		{
			if (get(h1, i, i + n - 1) == get(h2, 1, n))
			{
				ans++;
				break;
			}
		}
    }
    cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//     int _;cin>>_;while(_--)
    solve();
}

G-lxy的通风报信

思路：先bfs求各个军队的距离判断是否能够合并，再跑最小生成树得到最短天数。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cout << #x << " = " << x << endl;
const int N = 2e5 + 5;
int a[1005][1005], step[1005][1005];
char tu[1005][1005];
int num, n, m, ts;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
void bfs(int i, int j)
{
    queue<pair<int, int>> q;
    q.push({i, j});
    vector<vector<int>> dist(1001, vector<int>(1001, 0));
    vector<vector<int>> st(1001, vector<int>(1001, 0));
    dist[i][j] = 0;
    st[i][j] = 1;
    ts = 1;
    while (!q.empty())
    {
        auto [x, y] = q.front();
        q.pop();
        if (a[x][y])
        {
            step[a[i][j]][a[x][y]] = dist[x][y];
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && tu[nx][ny] != '#' && !st[nx][ny])
            {
                st[nx][ny] = 1;
                q.push({nx, ny});
                if (tu[nx][ny] == '*')
                {
                    ts++;
                }
                dist[nx][ny] = dist[x][y] + 1;
            }
        }
    }
}
int prim()
{
    vector<int> vis(1001);
    vector<int> dis(1001, 0x3f3f3f3f);
    dis[1] = 0;
    int ans = 0;
    for (int i = 1; i <= num; i++)
    {
        int t = -1;
        for (int j = 1; j <= num; j++)
        {
            if ((t == -1 || dis[j] < dis[t]) && !vis[j])
            {
                t = j;
            }
        }
        ans += dis[t];
        vis[t] = 1;
        for (int j = 1; j <= num; j++)
        {
            if (dis[j] > step[t][j])
            {
                dis[j] = step[t][j];
            }
        }
    }
    return ans;
}
void slove()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> tu[i][j];
            if (tu[i][j] == '*')
            {
                a[i][j] = ++num;
            }
        }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j])
            {
                bfs(i, j);
                if (ts < num)//说明无法合并
                {
                    cout << "No\n";
                    return;
                }
            }
        }
    }
    cout << prim()  << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    slove();
}