视频题解

---

A. 字符串操作

- 30pts：

模拟即可

- 100pts

注意到每轮操作字符串的长度会翻倍，原串 $i$ 位置会计算出新串的 $2\times i-1,2\times i$ 两个位置。所以当前轮所求的 $k$ 位置由上一轮的 $\frac{k+1}2$ 的位置决定。

用 012 分别代表 ABC，同时观察到 A->BC,B->CA,C->AB，每次新生成的第一个字符是原字符 $(+1)mod\; 3$，第二个字符是原字符 $(+2)mod\;3$。所以如果 $k$ 为奇数，当前轮的第 $k$ 字符是上一轮第 $\frac{k+1}2$ 个字符 $(+1) mod\;3$ 而来，否则为 $+2$。

同时注意当 $k=0$ 时，$t$ 也可能很大。首字母一定也是 ABCABCABC... 的循环，根据规律即可找到第 $t$ 轮的首字母。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s[100001];//0A
int sovle(int t,int k){
	if(k==1){
		return (s[1]+t%3)%3;
	}
	if(t==0)return s[k];
	int p=sovle(t-1,(k+1)>>1);
	if(k&1)return(p+1)%3;
	return(p+2)%3;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	string a;
	cin>>a;
	const int LLL=a.length();
	for(int i=0;i!=LLL;++i){
		s[i+1]=a[i]-'A';
	}
	int q;
	cin>>q;
	while(q--){
		int t,k;
		cin>>t>>k;
		cout<<char(sovle(t,k)+'A')<<'\n';
	}
	return 0; 
} 

B. 数格子

- 90pts：

边长为 $1$ 的正方形有 $n\times n$ 个；边长为 $3$ 的正方形有 $(n-2)\times(n-2)$ 个；边长为 $5$ 的正方形有 $(n-4)\times(n-4)$ 个...循环累加即可。

- 100pts:

额外的 $10$pts 帮助同学们进行数学推导：

前 $n$ 个数字平方和： $1^2+2^2+3^2...+n^2=\frac{n\times(n+1)\times(2n+1)}{6}$

前 $n$ 个偶数平方和：

$(1\times2)^2+(2\times2)^2+(3\times2)^2+...(n\times 2)^2$

$=2^2\times(1^2+2^2+3^2...+n^2)$

$=4\times\frac{n\times(n+1)\times(2n+1)}{6}$

$=2\times\frac{n\times(n+1)\times(2n+1)}{3}\;①$

又 ∵ 前 $2n$ 个数字总和为：

$\frac{2n\times(2n+1)\times(4n+1)}{6}\;②$

∴ 前 $n$ 个奇数和为 $②-①$

化简得 $\frac{n\times(4n^2-1)}3$

#include "bits/stdc++.h"
#define int long long
using namespace std;

signed main() {
    int t;cin >> t;
    while(t--) {
        int n; cin >> n;
        if(n & 1) {
            int k = n / 2 + 1;
            cout << k * (4*k*k-1) / 3 << endl;
        } else {
            int k = n / 2;
            cout << 2 * k * (k+1) * (2*k+1) / 3 << endl;
        }
    }
}

C. bug

- 60pts:

记 $dp[i][j][k]$ 为考虑了前 $i$ 个人，总共写了 $j$ 行代码，出现了 $k$ 个bug的方案数。

$dp[i][j][k] = \sum_{0\le t\le j, t\times a_i\le k}dp[i-1][j-t][k-t\times a_i]$

复杂度 $O(m^2nb)$

- 80pts:

利用完全背包的思路进行优化：第 $i$ 人不写、至少写了一行：

$dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k-a_i]$

空间复杂度 $O(nmb)$

- 100pts:

滚动数组优化：

$dp[j][k]=dp[j][k]+dp[j-1][k-a_i]$

最后所求：$\sum_{0\le t\le b} dp[m][t]$

初始状态 $dp[0][0] = 1$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int dp[550][550], a[550];

signed main()
{
    int n, m, b, mod = 998244353;
    scanf("%d %d %d", &n, &m, &b);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = a[i]; k <= b; k++)
                dp[j][k] = (dp[j][k] + dp[j-1][k-a[i]]) % mod;
    int ans = 0;
    for(int i = 0; i <= b; i++) ans = (ans + dp[m][i]) % mod;
    printf("%lld\n", ans);
    return 0;
}

D. 传动结构

整体思路：需要维护哪些齿轮已经被连接到一个集合之中，每个集合是否已被卡死。每个集合内的齿轮按照运动方向可以分为 $2$ 类（相邻的齿轮方向相反）

考虑操作 $2$ 合并 $x,y$:

• 如果 $x,y$ 已为同一集合
  • 旋转方向相同：合并会卡死
  • 旋转方向不同：无需合并
• 如果 $x,y$ 不为同一集合
  • 旋转方向相同：所属集合更小的集合的齿轮的方向全部反向再相连（启发式合并保证复杂度）
  • 旋转方向不同：直接合并

考虑操作 $3$ 从 $x$ 计算 $y$ 的速度，中间的齿轮在计算过程中会被约掉，结果仅与起终点有关。

- 30pts:

可使用线性的方法维护集合

- 100pts：

使用并查集维护集合，再为每个集合维护各个方向的具体的齿轮。

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
typedef long long llong;
pair< vector<int>, vector<int> > groups[100111];
int n,m;
int A[100111];
bool blocked[100111];
int groupID[100111];
bool firstPart[100111];

llong gcd(llong a,llong b)
{
    llong r;

    while(b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }

    return a;
}

void connect(int x,int y)
{
    if (groupID[x] == groupID[y])
    {
        if (firstPart[x] == firstPart[y])
        {
            blocked[ groupID[x] ] = true;
        }

        return;
    }

    int G1 = groupID[x];
    int G2 = groupID[y];
    int sz1 = groups[G1].first.size() + groups[G1].second.size();
    int sz2 = groups[G2].first.size() + groups[G2].second.size();
    int i;

    if (sz1 < sz2)
    {
        connect(y,x);
        return;
    }

    blocked[G1] = blocked[G1] || blocked[G2];

    if (firstPart[x] == firstPart[y])
    {
        for (i=0;i<groups[G2].first.size();i++)
        {
            groups[G1].second.push_back(groups[G2].first[i]);
            groupID[ groups[G2].first[i] ] = G1;
            firstPart[ groups[G2].first[i] ] = false;
        }
        for (i=0;i<groups[G2].second.size();i++)
        {
            groups[G1].first.push_back(groups[G2].second[i]);
            groupID[ groups[G2].second[i] ] = G1;
            firstPart[ groups[G2].second[i] ] = true;
        }
    }
    else
    {
        for (i=0;i<groups[G2].first.size();i++)
        {
            groups[G1].first.push_back(groups[G2].first[i]);
            groupID[ groups[G2].first[i] ] = G1;
            firstPart[ groups[G2].first[i] ] = true;
        }
        for (i=0;i<groups[G2].second.size();i++)
        {
            groups[G1].second.push_back(groups[G2].second[i]);
            groupID[ groups[G2].second[i] ] = G1;
            firstPart[ groups[G2].second[i] ] = false;
        }
    }

    groups[G2].first.clear();
    groups[G2].second.clear();

    return;
}

int main()
{
    //freopen("badtest.in","r",stdin);
    //freopen("ans.out","w",stdout);
    int i,j;
    int cm;
    int x,y,v;
    llong top,bot,nod;
    int ctr = 0;

    scanf("%d %d",&n,&m);

    for (i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);

        groups[i].first.push_back(i);
        groupID[i] = i;
        firstPart[i] = true;
    }

    for (i=1;i<=m;i++)
    {
        scanf("%d",&cm);

        if (cm == 1)
        {
            scanf("%d %d",&x,&v);

            A[x] = v;
        }
        else if (cm == 2)
        {
            scanf("%d %d",&x,&y);

            connect(x,y);
        }
        else
        {
            ctr++;

            scanf("%d %d %d",&x,&y,&v);

            if (groupID[x] == groupID[y])
            {
                if (blocked[ groupID[x] ])
                {
                    printf("0\n");
                }
                else
                {
                    top = (llong)A[x] * (llong)v;
                    bot = (llong)A[y];
                    nod = gcd(top,bot);

                    top /= nod;
                    bot /= nod;

                    if (firstPart[x] != firstPart[y])
                        printf("-");
                    printf("%lld/%lld\n",top,bot);
                }
            }
            else
            {
                printf("0\n");
            }
        }
    }

    return 0;
}