大一第六次周赛题解

大一第六次周赛题解

Lionlnuc
Lionlnuc Lv4
  2025-12-22 2025-12-22 创建   2025-12-22 2025-12-22 更新      

A - 冬

知识点： 思维
题意：找到另一个整点 C，使顶点组成的三角形任意两边之和大于第三边，且所组成的三角形面积是正整数。
分析：要使面积是整数那就让底乘高为偶数。可以去构造一个与坐标轴平行的边且长度为偶数作为底边
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e5+5;
const int mod=998244353;
void solve()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    if(x1==x2){
        cout<<x1+2<<" "<<y1<<endl;
    }else{
        cout<<x1<<" "<<y1+2;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

B - 至

知识点： 贪心
题意：给一个偶数，要拆解成尽可能多的偶数。
分析：遇到偶数就切割，遇到奇数就和它右边遇到的第一个偶数结合。麻烦的是进行排序。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string s;
vector<string> v;
bool cmp(string &a,string &b)
{
    if(a.size()==b.size()) return a<b;//长度相同时按字典序排
    else return a.size()<b.size();//长度小的放前面
}
void solve()
{
    cin>>s;
    for(int i=0,j=0;i<s.size();i++)
    {
        if((s[i]-'0')%2==0)//偶数
        {
            v.push_back(s.substr(j,i-j+1));
            j=i+1;
        }//如果为奇数，j会停下来，直到遇到下一个偶数一起放入数组中。
    }
    sort(v.begin(),v.end(),cmp);
    for(auto c:v)
    {
        cout<<c<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

C - 记

知识点： 构造
题意：
分析：相邻两集合有且只有一个值重复，对于示例，更容易发现规律的结果应该是

1
2
3
1 2 3
2 4 5
3 5 6

也就是说构造这样的对称矩阵就能满足题意
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=505;
int a[N][N];
void solve()
{
    int n;
    cin>>n;
    int cnt=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)a[i][j]=cnt++;
        for(int j=1;j<=i;j++)a[i][j]=a[j][i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cout<<a[i][j]<<" ";
        cout<<endl;
    }
}
signed main(){
	IOS
	int t=1;
	while(t--)
	{
		solve();
	}
}

D - 得

知识点： 贪心
题意：所有拉雪橇的驯鹿的力量总和必须大于或等于所有坐在雪橇上的驯鹿的体重总和，最多有多少只驯鹿能坐在雪橇上。
分析：
很简单的一个要求就是让拉雪橇的鹿的力量大于等于坐雪橇的鹿的体重。
是所有鹿的力量和。 是坐雪橇驯鹿的力量和
两者相减就是拉雪橇的总力量。
是坐雪橇驯鹿的体重和;
要求
即
贪心一点，我们在选择时选择代价小的（排个序从第一个开始选）。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=3e5+5;

void solve()
{
    int n;
    cin>>n;
    vector<int> a;
    int power=0;
    for(int i=1;i<=n;i++)
    {
        int w,p;
        cin>>w>>p;
        power+=p;
        a.push_back(w+p);
    }
    sort(a.begin(),a.end());
    int sum=0,cnt=0;
    for(int i=0;i<n;i++)
    {
        if((sum+a[i])<=power)
        {
            cnt++;
            sum+=a[i];
        }else break;
    }

    cout<<cnt<<endl;

}
signed main(){
	IOS
	int t;
    cin>>t;
	while(t--)
	{
		solve();
	}
}

E - 吃

知识点： 思维
题意：给出一个排列的前缀最小值数组，求有多少个排列满足要求。
分析：
长度为 n 的排列是从 1~n 这个 n 个整数按任意顺序组成的数组。
我们先来模拟一下，假如这个数组为{1,2,3}

1
2
3
min{p[1]}=1;
min{p[1],p[2]}=2;
min{p[1],p[2],p[3]}=3;

可以发现上面是绝对错误的，所以对于这个前缀最小值数组是非递增的(因为后面的前缀必然包含当下前缀的最小值，超过的话这个数组就是错误的)。此时排列数量为 0。
如何计算这个变化，对于一个完全不同的数组{3,2,1}。我们可以推出结果只有一种那就是{3,2,1}。排列的数量的更新其实是取决于前缀数组中相同的数。
比如：{2,2,1} 此时的排列可以是{2,2,1}也可以是{2,3,1}。
所以当前前缀最小值等于之前的前缀最小值时可以选择的放置数量为 。（PS: 注意因为是排列所以不能有重复数字，需要减去之前用过的 i 个数）
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
const int N=2e5+5;
const int mod=998244353;
void solve()
{
    int n;
    cin>>n;
    int a[N];//前缀的最小值数组
    for(int i=0;i<n;i++) cin>>a[i];
    int ma=a[0];
    int ans=1;
    for(int i=1;i<n;i++)
    {
        if(a[i]==ma)ans=ans*(n-ma-i+1)%mod;
        else if(a[i]>ma){
            cout<<"0"<<endl;
            return;
        }else ma=a[i];
    }
    cout<<ans%mod<<endl;
}
signed main(){
	IOS
	int t;
	cin>>t;
	//int t=1;
	while(t--)
	{
		solve();
	}
}

F - 饺

知识点： 01 BFS (双端队列)
来源于 BFS（图论） - OI Wiki 的惯用伪代码

1
2
3
4
5
6
7
8
9
10
11
while (队列不为空) {
  int u = 队首;
  弹出队首;
  for (枚举 u 的邻居) {
    更新数据
    if (...)
      添加到队首;
    else
      添加到队尾;
  }
}

题意：有一个 N × M 的矩阵 a，a 中的元素可能是 / 或 \ ，左上角是电源，右下角是灯。要得到亮灯的最少操作次数。
分析：
我们要搜索从开关到灯的最短路径。我们把交叉点视为格点，每个格点会有四个对角格点, 出界的不能选择，无法达到更优结果的也能不选。此时就有两种状态：连通路径和不连通路径，为了使操作次数最少，优先选连通的。具有两端性 (0 和 1) 对于更优的从双端队列队头入队，不优的从队尾入队。
每个状态可能入队多次，但是只使用一次。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define x first
#define y second
int dx[]={-1,-1,1,1};
int dy[]={-1,1,1,-1}; //要扩展的点的偏移量
int ex[]={-1,-1,0,0};
int ey[]={-1,0,0,-1};//当前节点对应的四个方格在输入的字符串中的偏移量
char s[5] = "\\/\\/";//注意\为转义字符所以需要输入两次
const int N=505;
char mp[N][N];
int dis[N][N];//储存操作步数
bool vis[N][N];//用来判重

int bfs(int n,int m)
{
    memset(dis,0x3f,sizeof dis);
    dis[0][0]=0;
    deque<PII> q;
    q.push_back({0,0});//电源入队
    while(q.size())
    {
        PII u=q.front();
        q.pop_front();
        int xx=u.x,yy=u.y;
        if(vis[xx][yy])continue;//如果已出过队，已经最小。
        vis[xx][yy]=true;
        for(int i=0;i<4;i++)//枚举周围子格点
        {
            int a=xx+dx[i],b=yy+dy[i];
            if(a<0||a>n||b<0||b>m)continue;//判断出界
            int ea=xx+ex[i],eb=yy+ey[i];
            int d=dis[xx][yy]+(mp[ea][eb]!=s[i]);//不连通时取一
            if(d<dis[a][b]) //可以更新最少次数
            {
                dis[a][b]=d;
                if(mp[ea][eb]!=s[i]) q.push_back({a,b});//加到队尾
                else q.push_front({a,b}); //加到队头
            }
        }
        
    }
    return dis[n][m];
}

void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)cin>>mp[i][j];
    }
    int d=bfs(n,m);
    if(d==0x3f3f3f3f)cout<<"NO SOLUTION";
    else cout<<d;
    
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

G - 子

知识点： 枚举
题意：从数组里面选一些数字使得被选中的数字构成一个等比数列，要求选的数字个数最多
分析：
可以枚举每个数，把它当作等比数列首项，再从 2 开始枚举公比。为避免超时要进行优化，如果当前需求的值超过数组最大值直接结束或者当前最多相同数字个数已经超出该数所能实现的时也 break。
代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
const int N=2e5+5;
int a[N],b[N];
void solve()
{
    int n;
    cin>>n;
    int ans=1;//个数
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        b[a[i]]++;
        ans=max(ans,b[a[i]]);
    }
    sort(a,a+n);
    for(int i=2;i<=a[n-1];i++)//从2开始枚举公比，不会超过a[n]
    {
        //枚举n个元素
        for(int j=0;j<n;j++)
        {
            if(pow(i,ans)*a[j]>a[n-1])break;
            int res=a[j],cnt=1;
            //下来寻找符合要求的元素
            //成倍增加
            while(res*i<=a[n-1]&&b[res*i])
            {
                res*=i;
                cnt++;
            }
            ans=max(ans,cnt);
        }
    }
    cout<<ans;
}
signed main(){
	IOS
	//int t;
	//cin>>t;
	int t=1;
	while(t--)
	{
		solve();
	}
}

欢迎关注我的微信公众号呀微信公众号文章链接

  • 标题: 大一第六次周赛题解
  • 作者: Lionlnuc
  • 创建于 : 2025-12-22 00:00:00
  • 更新于 : 2025-12-22 00:00:00
  • 链接: https://lionlnuc.github.io/2025/12/22/大一第六次周赛题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
大一第六次周赛题解
  1. A - 冬
  2. B - 至
  3. C - 记
  4. D - 得
  5. E - 吃
  6. F - 饺
  7. G - 子