上学期末打完比赛后就没再练了，这次参赛就是来玩的感觉心态都不一样了哈哈哈哈哈哈，还好没掉出奖牌区。

由于实力有限，所以只给出一点点的题解。

以下题目顺序按照我主观认为的题目难度顺序。

H 讨论组

作者 JMU_ACM

小Z 是一个老师。

小Z 所教的班级有 n 个学生。有一天，小Z 要把班级的学生分成若干小组，每个小组讨论一些主题。

小Z 认为由两个或更少的学生组成的小组无法进行有效的讨论，因此你希望尽可能多地由三个或更多的学生组成小组。

小 Z 想对学生进行分工，使由三名或三名以上学生组成的小组数量达到最大。你能帮助他吗？

输入格式:

第一行给出一个整数 n(1≤n≤1000)，表示学生人数。

输出格式:

输出一个正整数，表示至多能分成的三个人以上小组的个数。

输入样例:

5

输出样例:

1

 题解

明显的签到题，为了使小组数达到最大，那么每个小组的人就要尽量少，刚好卡线的人数就是最小的人数，总人数除这个人数就是最多的小组。

ps:但是问题的意思（三人以上）难道不是4个人嘛？

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll n;
ll ans;
int main()
{cin>>n;ans=n/3;cout<<ans<<endl;return 0;} 

B 矩阵的拆解之谜

作者 JMU_ACM

给定一个 n×n 的矩阵 A，我们想知道这个知道矩阵是否能表示成对称阵和反对称阵的和。如果能表示，请输出对称阵与反对称阵。可以证明，如果所求的两个矩阵存在，则这两个矩阵唯一。题目数据保证如果所求的两个矩阵存在，则对称阵与反对称阵内的元素必然为整数。

以下是一些名词的定义以及解释。

对称阵

定义：如果一个矩阵的转置等于自身，即  AT=A  ，那么这个矩阵就是对称矩阵。

• 数学表示：对于任意的  i 和  j ，有  Aij​=Aji​。
• 简单理解：对称阵关于主对角线对称。
  例子：

在这个矩阵中，A12​=A21​=2，A13​=A31​=3  ，所以它是对称阵。

反对称阵

定义: 如果一个矩阵的转置等于它的负矩阵，即  AT=−A  ，那么这个矩阵就是反对称矩阵。

• 数学表示: 对于任意的  i  和  j  ，有  Aij​=−Aji​，并且所有对角线上的元素都为 0 ，即  Aii​=0。
• 简单理解：反对称阵关于主对角线反号对称。
  例子:

在这个矩阵中，A12​=−A21​=2，A13​=−A31​=−1，并且主对角线元素 A11​=A22​=A33​=0，所以它是反对称阵。

矩阵加法

设有两个矩阵 A 和 B，它们的大小都是 n×m，即每个矩阵都有 n 行和 m 列。矩阵加法的规则是将对应位置的元素相加，得到一个新的矩阵 C，其中：
Cij​=Aij​+Bij​

输入格式:

第一行给出一个整数 n(1≤n≤500)，表示矩阵的大小。
接下来有 n 行,每行给出 n 个正整数。其中第 i 行第 j 列为 Aij​(−109≤Aij​≤109)，即矩阵的第 i 行第 j 列的值。

输出格式:

如果所求的对称阵与反对称阵存在，第一行输出 YES，否则输出 NO。
如果存在，则接下来输出 2n 行，每行 n 个正整数，其中第 1∼n 行输出要求的对称阵，第 n+1∼2n 行输出要求的反对称阵。

输入样例:

2
1 2
4 3

输出样例:

YES
1 3
3 3
0 -1
1 0

样例解释

题解

赛前说是两道签到题，但我半小时了都没找到第二道明显的签到，那么且认为这个是签到吧，因为其实就是纯模拟。

虽然题目说了一大堆看似很复杂，但其实只要判断目标矩阵的Aij和Aji之和是否是偶数，因为这样平分之后可以给出一加一减同样的数使得存在反对称矩阵。

接着就算出这个差值是多少，然后按样例输出就行。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll n;
int flag=1;
ll a[505][505];
ll temp[505][505];
ll b[505][505];
ll c[505][505];
int main()
{cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];if(i==j){b[i][j]=a[i][j];}}}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if((a[i][j]+a[j][i])%2!=0){flag=0;//不存在的情况}else{b[i][j]=(a[i][j]+a[j][i])/2;b[j][i]=b[i][j];c[i][j]=a[i][j]-b[i][j];c[j][i]=a[j][i]-b[j][i];}}}if(flag){cout<<"YES"<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<b[i][j]<<" ";}cout<<endl;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<c[i][j]<<" ";}cout<<endl;}}else{cout<<"NO"<<endl;}return 0;
}

G 三点共线

作者 JMU_ACM

在二维无限坐标平面上有 n 个点。

第 i 个点在 (xi​,yi​) 处。

在 n 个点中，是否有三个不同的点位于同一条直线上？

输入格式:

第一行给出一个正整数 n(3≤n≤10^2)，表示点的数量。

接下来有 n 行，每行有两个整数 xi​,yi​(∣xi​∣,∣yi​∣≤103)，表示第 i 个点的坐标。

输出格式:

如果存在三个点在同一条直线上，输出 Yes ， 否则输出 No。

输入样例 1:

14 
5 5
0 1
2 5 
8 0 
2 1 
0 0 
3 6
8 6 
5 9 
7 9 
3 4 
9 2 
9 8
7 2

输出样例1:

No

输入样例 2:

4
0 1
0 2
0 3
1 1

输出样例2:

Yes

题解 

由于n的范围最大才100，所以枚举所有点是可以的。

用for循环固定两个点，去寻找第三个点，注意判断是否是不同的点。

三点共线说明斜率相等。

坑点在于不能直接用斜率，因为算的不准。所以要用乘法。

因为(Ya-Yb)/(Xa-Xb)=(Ya-Yc)/(Xa-Xc)

所以(Ya-Yb)*(Xa-Xc)=(Ya-Yc)*(Xa-Xb)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll n;
int flag;
//用结构体存x和y
struct node{double x,y;
}s[10005];
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>s[i].x>>s[i].y;}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){for(int k=j+1;k<=n;k++){if((s[j].y==s[i].y && s[j].x==s[i].x) || (s[k].y==s[i].y && s[k].x==s[i].x) || (s[k].y==s[j].y && s[k].x==s[j].x))//判断是否是不同的点{continue;}if(((s[i].y-s[j].y)*(s[i].x-s[k].x))==((s[i].y-s[k].y)*(s[i].x-s[j].x))){flag=1;break;}}}}if(flag==1){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}return 0;} 

I 市场

作者 JMU_ACM

在一个热闹的市场中，有 n 个摊位，编号为 1,2,…,N。第 i 个摊位位于坐标 ai​ 的位置，所有摊位都在 x 轴上。你从坐标 0 的入口出发，依次前往各个摊位购物。从坐标 a 到坐标 b 所需要的行走距离为 ∣a−b∣。

你原本计划在一天内访问所有这些摊位，按编号顺序逐一购物，最后再返回入口。然而，由于突然出现的促销活动，你发现自己无法按计划访问所有的摊位，因此决定取消对某个摊位 i 的访问。

在调整行程后，你将继续按顺序访问剩余的摊位，并依然从坐标 0 出发，最后返回入口。

请你计算在取消对每个摊位 i 的访问时行走的总距离。对于每个 i=1,2,…,n，给出相应的距离计算结果。

输入格式:

第一行给出一个整数 n(2≤n≤10^5)，表示摊位的数量。

第二行给出 n 个整数 ai​(−5000≤ai​≤5000)，表示 第 i 个摊位的坐标。

输出格式:

输出 n 个正整数，用空格隔开。其中第 i 个数表示少访问第 i 个摊位的答案。

输入样例:

3
3 5 -1

输出样例:

12 8 10

题解

这题可能很多新生看到会使用暴力的方法，但是观察数据量，n最大是10^5，显然使用O（n^2）的算法会超时，所以要考虑能够单次判断的。

因为要考虑每一个点被删掉后这段路怎么办，所以可以用一个变量s来标记a点到b点的距离，变量ss标记a点到c点的距离，这样如果b点被删掉了，那么a->b->c距离可以直接替换成a->c。

因为原本a->c要经过a->b，b->c，即Sab+Sbc；但是去掉b点后，a->c变成SSac

所以一开始记录总的距离sum，再遍历每一个点去掉的情况，减去原本的距离，加上新的距离，最终得到的就是答案。sum-(Sab+Sbc)+SSac。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll n;
ll a[100005];
ll b[100005];
ll s[100005];
ll ss[100005];
ll sum;
ll ans;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){sum+=abs(a[i]-a[i-1]);//先记录不删点的总距离s[i]=abs(a[i+1]-a[i]);//i->i+1的距离ss[i]=abs(a[i+2]-a[i]);//i->i+2的距离//用来判断i+1这个点被删掉的情况}//开始和结尾特判一下sum+=abs(a[n]-0);s[0]=abs(a[1]-0);ss[0]=abs(a[2]-0);s[n]=abs(a[n]-0);ss[n]=0;//遍历每一个删掉的点for(int i=1;i<=n;i++){ll temp=sum;temp-=s[i-1];temp-=s[i];temp+=ss[i-1];cout<<temp<<" ";}return 0;} 

C 因子数小于等于4的个数

作者 JMU_ACM

给定区间 [l,r]，你需要求出 [l,r] 中因子个数小于等于 4 的正整数个数。

输入格式:

本题包含多组测试数据。
第一行给出一个整数 T(1≤T≤10^5)，表示测试数据的组数。
接下来有 T 行,每行给出两个正整数 l,r (1≤l≤r≤10^6)，具体意义如题目所示。

输出格式:

输出 T 行，每行 1 个整数，其中第 i 个数表示第 i 个数据的答案。

输入样例:

1
1 6

输出样例:

6

样例解释

当 x=6 时，它有 {1,2,3,6} 这4 个因子。

 题解

看数据范围，显然不能在t次询问里用暴力来跑，可能是太多人都用暴力结果死活过不去，通过率低得离谱。

观察题目发现，一个数如果有小于等于4个因子的条件如下:

1.这个数是质数（因为只有1和本身两个因子）

2.这个数是质数的三次方（因为只有1 质数 质数平方 本身 四个因子）

3.这个数除了1和本身外还是两个质数的乘积（因为只有1和本身还有两个质数作为因子）

所以用素数筛筛出范围内的所有质数，在询问前就找到所有符合条件的数，并用前缀和统计，在询问的时候用前缀和给出答案即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
bool isPrime[10000005];
ll Prime[6000005];
ll cnt;
ll sum[2000005];
ll t;
//素数筛模板
void getPrime(int n)
{memset(isPrime,1,sizeof(isPrime));isPrime[1]=0;for(int i=2;i<=n;i++){if(isPrime[i]){Prime[++cnt]=i;}for(int j=1;j<=cnt && i*Prime[j]<=n;j++){isPrime[i*Prime[j]]=0;if(i%Prime[j]==0){break;}}}
}
void zb()
{getPrime(1000005);sum[1]=1;//枚举所有情况，并用前缀和统计for(ll i=2;i<=1000000;i++){if(isPrime[i])//是否是质数{//	cout<<i<<" ";sum[i]=sum[i-1]+1;continue;}int bj=0;for(ll j=1;j<=sqrt(i);j++){if(i%Prime[j]==0 && isPrime[i/Prime[j]]==0){if(Prime[j]*Prime[j]*Prime[j]==i)//是否是质数的三次方{sum[i]=sum[i-1]+1;//	cout<<i<<" ";bj=1;}break;}if(i%Prime[j]==0 && isPrime[i/Prime[j]]==1)//是否是两个质数的乘积{//	cout<<i<<" ";sum[i]=sum[i-1]+1;bj=1;break;}}if(bj==0)//不满足的数前缀和不变{sum[i]=sum[i-1];}}
}
int main()
{//关流加个速ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);zb();//在询问前就要算好cin>>t;while(t--){ll l,r;cin>>l>>r;cout<<sum[r]-sum[l-1]<<endl;}return 0;
}

J 区间缩小

作者 JMU_ACM

给定一个正整数 n，我们初始设定两个变量 l 和 r，其中 l=1，r=n。我们将执行以下步骤：

1. 如果 l=r，则结束操作；否则，执行步骤 2。

2. 从区间 [l,r] 中等概率地选取一个正整数 x。然后，以下两种情况互斥地发生：以概率 p 将 l 更新为 x，以概率 1−p 将 r 更新为 x。接着返回步骤 1。

经过上述操作，最终必然会有 l=r。设随机变量 X 为最终得到的数字（即 l），求 X 的数学期望。

答案对 998244353 取模。

输入格式:

第一行给出两个正整数 n,x(1≤n≤106,0≤x≤100)，其中 n 的具体意义如题意所示。令 p=100x​。其中 p 的意义如题意所示。

输出格式:

输出一个整数，表示答案。

输入样例:

234 10

输出样例:

898419942

 题解

根据经验，这个应该是会用到逆元。

那想不出好的做法怎么办？猜测大法！

首先，假设p=1，此时X必然=n

假设p=0，此时X=1

那么就要寻找一个公式使得结果成立，且因为等概率，很可能是什么(n-1)之类的

所以猜一个1+(n-1)*p 然后就能过了（好神奇）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n' 
const ll mod=998244353; 
ll n,x;
//快速幂模板
ll qpow(ll a,ll b)
{ll res=1;while(b){if(b&1){res=res*a%mod; }a=a*a%mod;b>>=1;}return res;
}
//逆元模板
ll inv(ll a,ll p)
{return qpow(a,p-2);
}
int main()
{cin>>n>>x;cout<< 1+(n-1)*x*inv(100,mod)%mod<<endl;return 0;
}