JZTXT

模拟五

发布时间 2023-11-02 09:56:33作者: zhuwen

收官之战！！！

模拟赛五补题报告

日期：\(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;
}