收官之战！！！
模拟赛五补题报告
日期：\(2023\)—\(10\)—\(6\) 学号：\(S11390\)
一、总分：
\(T1\) 重复判断:\(100\)分
\(T2\) 歪果仁学乘法:\(100\)分
\(T3\) 去重求和:\(40\)分
\(T4\) 点集操作:\(0\)分
共：\(240\) 分
二、比赛过程
-
在第一题中，我在考试中通过遍历字符串的方式，一个一个向下遍历，找到了就接着向下遍历，只要有一个字符不同就跳出遍历，输出 \(NO\)。通过这种简单的思路，也是做对了这道题，成功 \(AC\)。
-
在第二题中，思路也是很简单，将这个图一画就能够想出思路，也是做对了，成功 \(AC\)。
-
在第三题中，想不出好的思路，就只能往前几个测试点考虑，得部分分，通过双层循环和前缀和的优化，过了前 \(8\) 个样例，得了 \(40\) 分。
-
在第四题中，读了几遍后，没有啥思路，就放弃了，没有得分。
三、题目分析
\(T1\) 重复判断
给定两个字符串 \(s,c\) 看看 \(s\) 是否是又 \(c\) 复制而来的，就如果是输出 \(YES\)，反之输出 \(NO\)。
我们就可以遍历 \(s\) 字符串，与 \(c\) 字符串相判断，如果有不同那么就输出 \(NO\)。
但要注意：如果 \(s\) 字符串的长度不是 \(c\) 字符串的长度的倍数的话，那么也要输出 \(NO\)。
若前两种情况都满足的话，就输出 \(YES\)。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int t;
signed main()
{
//freopen("repeat.in","r",stdin);
//freopen("repeat.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while(t--)
{
int h=0;
bool flag=1;
string s,c;
cin>>s>>c;
for(int i=0;i<s.size();i++)
{
if(s[i]!=c[h])
{
flag=0;
break;
}
else
{
if(h==c.size()-1)
{
h=0;
}
else
{
h++;
}
}
}
if(flag&&s.size()%c.size()==0) // s 字符串必须是 c 字符串长度的倍数
//所以才可能是重复若干次得到的
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
// fclose(stdin);
//fclose(stdout);
return 0;
}
\(T2\) 歪果仁学乘法
如图
给定不超过 \(99\) 的两个数，按照以下方法进行计算。
-
\(a\) 的十位用 \(x1\) 表示，各位用 \(x2\) 表示；\(b\) 的十位用 \(y1\) 表示，各位用 \(y2\) 表示。
-
间隔一定距离朝同一方向（斜向）画 \(x1\) 和 \(x2\)。
-
向垂直方向画出 \(y1\) 和 \(y2\)。
-
数出交点即为答案。
我们可以根据图来看出本题的答案就是将一个公式：
x1*y1 + x2*y1 + x1*y2 + x2*y2;
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
int a,b;
signed main()
{
// freopen("multiplication.in","r",stdin);
// freopen("multiplication.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>b;
int x1=a/10,x2=a%10,y1=b/10,y2=b%10;
// 2*3 3*3 2*2 3*2
int sum= x1*y1 + x2*y1 + x1*y2 + x2*y2;
cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T3\) 去重求和
本题就是让我们求出区间 \([l,r]\) 的数去重后的和，
\(\begin{aligned} \sum _ {i = 1} ^ n \end{aligned}\) \(\begin{aligned} \sum _ {j = 1} ^ i \end{aligned}\) \(sum(i,j)\)
对 \(1e9+7\) 取余的结果。
如果没有去重条件的话，则答案为。
\(sum(1,1)\)
\(sum(1,2)\) \(sum(2,2)\)
\(sum(1,3)\) \(sum(2,3)\) \(sum(3,3)\)
\(\dots\dots\)
\(sum(1,n-1)\) \(sum(2,n-1)\) \(sum(3,n-1)\) \(\dots\) \(sum(n-1,n-1)\)
\(sum(1,n)\) \(sum(2,n)\) \(sum(3,n)\) \(\dots\) \(sum(n,n)\)
此时我们就可以得出公式：
f[i]=f[i-1]+a[i]*i
但这是没去重的情况，加入去重后，需要加入几个条件：我们在遍历数组时，通过 \(map\) 记录一下该数出现的位置，每个重复的元素只累加第一次出现的值。
有了这一条件，我们可以将以 \(i\) 结尾的区间 \(a_i\) 的值进行累加，具体来说，对于一个区间 \([i,x]\)，如果出现不止一次 \(a_x\) 那么后面这个 \(a_x\) 控制的只是对于后面出现的与前面出现的这一区间有影响， 区间 \([i,x]\) 中最后一次出现的 \(a_x\) 一定影响了最多的贡献值，并且包含了此前出现的所有 \(a_x\) 带来的影响。
这样说不好理解，我来画个图。
前面的 \(4\) 管前面的区间，后面的 \(4\) 管两个 \(4\) 之间的区间，所以递推公式就找出来了。
f[i]=f[i-1]+a[i]*(i-mp[a[i]])
最后将 \(f_i\) 加起来即为最后的答案。
正解
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define swap(a, b) a ^= b, b ^= a, a ^= b
#define pb push_back
const int N = 1e6 + 10;
const int mod = 1e9+7;
map<int ,int > mp;
int a[N];
int n;
int s[N];
int res;
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i]*(i-mp[a[i]]);
//每出现一个数就记录一下位置
mp[a[i]]=i;
}
for(int i=1;i<=n;i++)
res=(res+s[i])%mod;
cout<<res<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T4\) 点集操作
哎呀，经典的图论题，经典的爆零，也是没有一点思路啊，骗分都不会骗。那我就顺着思路来试着说说这道题。
这道题要通过规律来找到最优解。
-
对于入度为 \(0\) 的点，那些点一定是能够留下的。
-
对于由于有入度和出度的点，我们要将它指向的点删除。
-
对于有多种路径能够到达的点，我们要求到达这个点的最大值，通过最大值看看是否能保留。我们来定义一个广义的深度。如果当前结点的深度 \(>=2\) 时，这个点就删除，否则的话就保留。
最少的点一共有 \(3\) 个，就通过这样的方式减少能够减少的点，最后剩下的就是最少的点。
正解
#include<iostream>
#include<vector>
#include<queue>
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]){//第i个点的入度为0，那就是起始点，计数
v.push_back(i);//然后把入度为0的点记下来 ，放到v里
ans++;//计数
}
}
for(int i=1;i<=m;++i){//遍历输入的m条边
if(in[x[i]])//如果这条边的起点的入度不为0，你们这条边的终点一定不是处于第二层的点，最少也得是第三层 x-->y x入度不为0，还有点，你们y最少也得在第三层
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;
}