10.13OI集训营普及组第五场题解

T1 复读

考察基础的字符串匹配， $j$ 表示当前匹配到 $t$ 字符串的第 $j$ 位， $i$ 表示当前匹配到 $s$ 字符串的第 $i$ 位，两两比较，如果 $t$ 等于 $t.size()$ ，说明一遍已经复制完了，从零开始重新匹配（题解中用取模表示这一效果）

#include<bits/stdc++.h>
using namespace std;

string s, t;

int main() {
    int T;
    cin >> T;
    while(T--) {
        bool flag = 0;
        cin >> s >> t;
        for(int i = 0, j = 0; i < s.size(); ++i) {
            if(s[i] != t[j]) flag = 1;
            ++j; j %= t.size();
        }
        if(flag) puts("NO"); else puts("YES");
    }
}

T2 学习乘法

注意到本题的乘法都是最多两位数相乘，所以我们只需要将读入的 $a,b$ 拆分成个位和十位两个数字，然后两位之间两两计算交点数量即可。

#include<cstdio>
int ans(int a, int b){
	int a1 = a/10, a2 = a%10, b1 = b/10, b2 = b%10;
	return a1 * b1 + a1 * b2 + a2 * b1 + a2 * b2;
}
int main(){
	int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", ans(a, b));
}

T3 求和

如果 $a_i$ 互不相同，那么就有
$\text{sum}(l,r)=\sum_{i=l}^ra_i$
此时，考虑枚举每个 $a_i$ 算贡献，那么答案就是
$\sum_{i=1}^na_i\times(n-i+1)\times i$
这是因为对于每个 $a_i$ ，满足 $1\le l\le i\le r\le n$ 的区间 $[l,r]$ 会将其计入贡献。

而这样的区间共有 $i\times (n-i+1)$ 个，因此就得到了上面的式子。

去重后怎么做呢？考虑换一种方式解释去重：我们只计算每个数第一次出现时产生的贡献。

设 $p_i$ 为最大的 $j<i$ 使得 $a_j=a_i$ （不存在则为 $0$ ），即 $p_i=\max\{j|j<i,a_j=a_i\}$ 。

那么在这种方式下， $a_i$ 在答案中的系数就是 $(i-p_i)(n-i+1)$ 。

计算 $p_i$ 可以使用 hash 或者 map 做到 $O(n\log n)$ ，那么算法的时间复杂度就是 $O(n\log n)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
const int mod = 1e9 + 7;
int n, a[N];
map<int,int>mp;
int l[N], r[N];
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        mp[a[i]] = 1;
    }
    mp.clear();
    for(int i = 1; i <= n; ++i) {
        l[i] = mp[a[i]] + 1;
        mp[a[i]] = i;
    }
    mp.clear();
    for(int i = n; i; --i) {
        if(!mp.count(a[i])) {
            r[i] = n;
        } else r[i] = mp[a[i]] - 1;
        mp[a[i]] = i; 
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += 1ll * a[i] * (i - l[i] + 1) % mod * (n - i + 1) % mod;
        ans %= mod;
    }
    cout << ans << endl;
}

T4 点集操作

可以使用模拟暴力拿到一些分，正解还是较思维。

正解：

发现在一个单向链上，只需要让链头的两个点进行一次操作就可以将整个链变成两个点。

所以每次操作可以在一条所含点数超过 $2$ 的单向链上进行，直至不能继续操作，剩下的点的个数即为图中剩余的最小点数。

由上面操作的特殊性可以知道所有入度为 $0$ 的点删不掉，所有满足“所有入边对应点入度为 $0$ “的点也删不掉，可以将这些点（所有满足“所有入边对应点入度为 $0$ “的点）看成新点。

统计这些点个数即可。

复杂度： $O(n+m)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int n,m,x[MAXN<<1],y[MAXN<<1],in[MAXN];
int head[MAXN],num,ans;
bool b[MAXN],vis[MAXN];
vector<int>v;
queue<int>q;
struct node{
	int to,next;
}e[MAXN<<1];

void add(int u,int v){
	e[++num].to=v;
	e[num].next=head[u];
	head[u]=num;
}

int main(){
	cin >> n >> m;
	for(int i=1;i<=m;++i){
		cin >> x[i] >> y[i];
		add(x[i],y[i]);
		in[y[i]]++;//统计入度 
	}
	for(int i=1;i<=n;++i){
		if(!in[i]){//如果入度为零 
			v.push_back(i);//记录入度为零的点 
			ans++;//这些点肯定不能被删去 
		}
	}
	for(int i=1;i<=m;++i){
		if(in[x[i]])b[y[i]]=1;//将入边对应点入度大于零的点标记，这些点都不行 
	}
	for(int i=0;i<v.size();++i){//最外层
		for(int j=head[v[i]];j;j=e[j].next){//第二层
			if(!b[e[j].to]){//若第二层的点的**所有**入边对应点入度等于零（有些点既在第二层又在其它层） 
				b[e[j].to]=1;
				ans++;//这些点虽然会被删除，但是他们可以充当新点，相当于保留 
			}
		}
	}
	cout << ans;
	return 0;
}

全部评论

推荐最新楼层

Try_harder_one

天津仁爱学院 C++

学算法，就上牛客，XCPC铜牌不是梦，心动不如行动，点此下方链接报名立减20元：基础算法入门班：https://www.nowcoder.com/courses/cover/live/724?coupon=ARgGejk 进阶数据结构专题课：https://www.nowcoder.com/courses/cover/live/707?coupon=AQDlsi4

点赞回复分享

发布于 2022-12-02 20:50 天津

shenyibin

广东实验中学

同上， 4 4 1 2 1 3 4 2 4 3 应该输出3，而正解貌似没有处理这种情况。

点赞回复分享

发布于 2022-10-26 18:01 广东

偶尔刷刷题

保密算法工程师

第四题输入： 4 4 1 2 1 3 4 2 4 3 请问选择1和4，是不是可以合并2和3呢？

点赞回复分享

发布于 2022-10-17 13:19 广东