2.15 周总结

又是飞起来的一周。
1.
ABC 444：

C 快速注意到答案只可能是 max⁡ai\max a_i 或 max⁡ai+min⁡ai\max a_i + \min a_i

D 高精度，写的时候感觉跟吃屎差别不大。

E 双指针+ multiset 冲了过去。

较简单。

ABC 445：

C 简单题。

D 读题读了 55 遍才发现题目讲了个啥。随后发现一个性质，就是巧克力切两块肯定有一块根原来巧克力的长宽相同。

然后就做完了。

太石了！！！！！！

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
struct node1
{
    int h,w;
    int id;
    bool friend operator<(node1 a,node1 b)
    {
        return a.h<b.h;
    }
};
struct node2
{
    int h,w;
    int id;
    bool friend operator<(node2 a,node2 b)
    {
        return a.w<b.w;
    }
};
priority_queue<node1> q1;
priority_queue<node2> q2;
int n;
int x[N],y[N];
int del[N];
int posx[N],posy[N];
void solve(int h,int w,int x,int y)
{
    // cout<<h<<' '<<w<<' '<<x<<' '<<y<<'\n';
    while(q1.size()&&del[q1.top().id])
    {
        q1.pop();
    }
    while(q2.size()&&del[q2.top().id])
    {
        q2.pop();
    }
    if(q1.size())
    {
        if(q1.top().h==h)
        {
            del[q1.top().id]=1;
            posx[q1.top().id]=x;
            posy[q1.top().id]=y;
            int nw=w-q1.top().w;
            int ny=y+q1.top().w;
            q1.pop();
            solve(h,nw,x,ny);
            return;
        }
    }
    if(q2.size())
    {
        if(q2.top().w==w)
        {
            del[q2.top().id]=1;
            posx[q2.top().id]=x;
            posy[q2.top().id]=y;
            int nh=h-q2.top().h;
            int nx=x+q2.top().h;
            q2.pop();
            solve(nh,w,nx,y);
            return;            
        }
    }
    return;
}
int main()
{
    int h,w;
    cin>>h>>w>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
        q1.push(node1{x[i],y[i],i});
        q2.push(node2{x[i],y[i],i});
    }
    solve(h,w,1,1);
    for(int i=1;i<=n;i++)
    {
        cout<<posx[i]<<' '<<posy[i]<<'\n';
    }
    return 0;
}

很难相信一个人的代码能这么难看。

E 是简单题，2 min 糊了个思路，就是所有数质因数分解后转化成了一个显然的结论。

就是考虑 lcm 在质因数分解时产生的一系列问题。

然后 O(nn)O(n\sqrt{n}) 试图冲过去，但常数写的比山东煎饼还大，飞起来了。

代码放在这，以后调吧

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
const int M = 5e7+10;
const int Mod = 998244353;
long long qpow(long long x,long long y)
{
    long long res=1;
    while(y)
    {
        if(y&1) 
        {
            res*=x;res%=Mod;
        }
        x*=x;x%=Mod;y/=2;
    }
    return res;
}
int a[N];
int n;const int V = 1e7+10;
int b[2][V],c[2][V];
vector<long long> p;

long long ans;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int tmp=a[i];
        for(auto j:p)
        {
            if(j*j>a[i]) break;
            int cnt=0;
            while(tmp%j==0)
            {
                cnt++;
                tmp/=j;
            }
            if(cnt>b[0][j])
            {
                b[1][j]=b[0][j];
                c[1][j]=c[0][j];
                b[0][j]=cnt;
                c[0][j]=i;
            }
            else if(cnt>b[1][j])
            {
                b[1][j]=cnt;
                c[1][j]=i;
            }
        }
        int j=tmp,cnt=1;
        if(j==1) continue;
        if(cnt>b[0][j])
        {
            b[1][j]=b[0][j];
            c[1][j]=c[0][j];
            b[0][j]=cnt;
            c[0][j]=i;
        }
        else if(cnt>b[1][j])
        {
            b[1][j]=cnt;
            c[1][j]=i;
        }
    }ans=1;
    for(auto i:p) ans=ans*qpow(i,b[0][i])%Mod;
    // cout<<ans<<' ';
    for(int i=1;i<=n;i++)
    {
        long long tmp=ans;
        int k=a[i];
        for(auto j:p)
        {
            if(j*j>a[i]) break;
            while(k%j==0) k/=j;
            if(c[0][j]==i)
            {
                long long res=qpow(j,b[0][j])%Mod;
                res=qpow(res,Mod-2);
                tmp*=res;tmp%=Mod;
                tmp*=qpow(j,b[1][j]);
                tmp%=Mod;
            }
        }
        int j=k;
        if(j>1&&c[0][j]==i)
        {
            long long res=qpow(j,b[0][j])%Mod;
            res=qpow(res,Mod-2);
            tmp*=res;tmp%=Mod;
            tmp*=qpow(j,b[1][j]);
            tmp%=Mod;            
        }
        cout<<tmp<<' ';
    }
    for(int i=1;i<=n;i++)
    {
        long long tmp=ans;
        int k=a[i];
        for(auto j:p)
        {
            if(j*j>a[i]) break;
            while(k%j==0)
            {
                b[0][j]=b[1][j]=c[0][j]=0;
                k/=j;
            }
        }
        if(k!=1) b[0][k]=b[1][k]=c[0][k]=0;
    }
    cout<<'\n';
}
int _;

bool vis[V];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    for(int i=2;i<=1e7;i++)
    {
        if(!vis[i]) p.push_back(i);
        for(auto j:p)
        {
            if(j*i>1e7) break;
            vis[j*i]=1;
            if(i%j==0) break;
        }
    }
    // cout<<p.size();
    cin>>_;
    while(_--) solve();
    return 0;
}
  1. 2.9 号才放假的人看着接下来的集训留下了欣慰的泪水。

虽然说就是被强制按着上了 33 天自习。

发现我有大量的典题没做。

被黄色数论 小凯的疑惑 撞了。

我恨数论。

  1. 得到了一些很奇奇怪怪的结论。

比如我发现线段树吧每个节点信息封到一个结构体里，再重载一下加法运算符出奇的好写。神秘。

  1. exkmp 太神秘了。

不如叫 ex马拉车。

感觉还得再想想。

  1. 复习了一下树链剖分。

主要是被一道树剖套可持久化线段树给整死了。

  1. 被勒令写笔记了。

于是调试了一下博客园。

现在开张了：sundingjia.github.io

祝新春快乐！

周总结
#个人记录
2.15 周总结
http://sundingjia.github.io/2026/02/15/2-15-周总结/
作者
sundingjia
发布于
2026年2月15日
许可协议