发表于 | 分类于

C(数据结构:区间加减、查询最值线段树)

大致题意:一个人在一个城市旅游，旅程有其开始时间和结束时间，给定n个任务，每个任务有其开始时间和结束时间，任务完成后会有奖励p，每在该城市待一天，都会花费k，现求旅程的开始时间和结束时间，使完成任务的奖励之和-花费之和最大(若最大值小于0则输出0，否则输出达到最大值时的开始、结束时间、所完成的任务的编号)

题解:可以将所有任务抽象成小区间，小区间被完全包含时，对答案有贡献，求小区间贡献和-k*区间长度的最大值

区间问题+数据范围2e5，很明显是枚举区间的R，找到最佳的L，再根据此时区间值判断是否更新答案，而对每个R找L时，往往需要借助线段树等数据结构达到log(并且往往是边枚举R边更新L的值)

首先化简问题，固定L为1，则很明显能预处理出一个前缀和数组RR。

而当L不为1时，则要将1~L-1区间对答案的影响消去(一部分来自k、一部分来自左端点<=L-1，右端点<=R的小区间)。

故先将小区间按右端点从小到大重新排列，设所有任务的右端点最大值为MAX，则枚举R从1到MAX，当枚举到i时，将所有右端点<=i的任务的影响插入线段树，将k的影响插入线段树(k这部分在建立线段树时就可预处理好)，然后在1~i区间内查询最小值,(RR[i]-最小值)则为区间的右端点固定为R时，所能取到的最大值。

升级版:若小区间的端点范围开到1e12，小区间个数仍是2e5，易知最佳区间的R一定是某个任务的右端点，L一定是某个任务的左端点，故我们可以先将小区间的左右端点坐标离散化成4e5的范围，再开个4e5的pos数组记录离散化后的坐标和离散化之前的坐标的对应关系以计算k的影响，其他均与上述做法一致。

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 1e6 + 5;
const ll INF = 0x7fffffff;
ll tmp, T, n, m, k;
struct node
{
    ll l, r, p;
    ll id;
    bool operator<(const node &b)
    {
        return r < b.r;
    }
};
node a[maxn];
ll RR[2 * maxn];
// ll lsh[2 * maxn];
ll num;
struct seg_node
{
    pair<ll, ll> val;
    ll lazy;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = min(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void pushdown(ll rt, ll ln, ll rn)
{
    if (segtree[rt].lazy)
    {
        segtree[rt << 1].lazy += segtree[rt].lazy;
        segtree[rt << 1 | 1].lazy += segtree[rt].lazy;
        segtree[rt << 1].val.first += segtree[rt].lazy;
        segtree[rt << 1 | 1].val.first += segtree[rt].lazy;
        segtree[rt].lazy = 0;
    }
}
void build(ll left = 1, ll right = num, ll rt = 1)
{
    segtree[rt].lazy = 0;
    if (left == right)
    {
        segtree[rt].val.first = 0;
        segtree[rt].val.second = left;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
pair<ll, ll> part_query(ll l, ll r, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val; //+segtree[rt].lazy;
    }
    if (l > right || r < left)
    {
        return {INF, INF};
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    return min(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}
void part_update(ll l, ll r, ll value, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        segtree[rt].val.first += value;
        segtree[rt].lazy += value;
        return;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    if (l <= mid)
    {
        part_update(l, r, value, left, mid, rt << 1);
    }
    if (r > mid)
    {
        part_update(l, r, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    // cin >> T;
    while (T--)
    {
        cin >> n >> k;
        num = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r >> a[i].p;
            a[i].id = i;
            num = max(num, a[i].r);
        }
        memset(RR, 0, sizeof(RR));
        for (ll i = 1; i <= n; i++)
        {

            RR[a[i].r] += a[i].p;
        }
        for (ll i = 1; i <= num; i++)
        {
            // LL[i] += LL[i - 1];
            RR[i] += RR[i - 1];
        }
        for (ll i = 1; i <= num; i++)
        {
            RR[i] -= k * (i);
            // LL[i] -= k * (pos[i] - 1);
        }
        sort(a + 1, a + 1 + n);
        // pos[0] = 0;
        //  LL[num] = 0x7fffffff;
        // pos[0] = 0;
        // deque<ll> qq;
        ll ans = 0;
        ll ansl = -1, ansr = -1;
        build();
        ll tot = 1;
        pair<ll, ll> tmp;
        for (ll i = 1; i <= num; i++)
        {
            
            while (tot <= n && a[tot].r <= i)
            {
                if (a[tot].l + 1 <= num)
                part_update(a[tot].l + 1, num, a[tot].p);//选取到l时，右端点为l的任务仍能完成，故加入时要写l+1
                tot++;
            }
            if (i > 1)
            {
                part_update(i, num, -k);
            }
            tmp = part_query(1, i);
            //cout << i << " " << tmp.first << " " << tmp.second << "!!!\n";
            if (ans < RR[i] - tmp.first)
            {
                ans = RR[i] - tmp.first;
                ansl = tmp.second;
                ansr = i;
            }
        }
        if (ans == 0)
        {
            cout << ans << "\n";
        }
        else
        {
            cout << ans << " " << ansl << " " << ansr << " ";
            vector<ll> ret;
            for (ll i = 1; i <= n; i++)
            {
                if (a[i].l >= ansl && a[i].r <= ansr)
                {
                    ret.push_back(a[i].id);
                }
            }
            cout << ret.size() << "\n";
            for (auto &e : ret)
            {
                cout << e << " ";
            }
            cout << "\n";
        }
        // cout << ans << " " << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

场后反思:

  1. 场上看错了数据范围，以为要离散化，浪费的时间++
  2. 明明思路想好了，code的时候忘记考虑小区间的R的影响，导致最后没写出来
  3. 再考虑L的影响区间时过于混乱(一部分也是开了离散化的锅)，浪费了太多时间在瞎改code上，在code前就应该明确细节

G(博弈论、尺取法)

大致题意:给出、…，、…

现规定第i轮给两位选手分别加上,，规定谁先达到k谁输，若一同达到k或n轮之后都没达到k，则平局，选手1可在每轮结束后选择是否按下reset，若按下，记按下之前选手1的值为x，选手2的值为y，则按下后选手1的值为max(0,x-y)，选手2的值为max(0,y-x)

求选手1能否获胜，若不能，输出-1，若能，则求选手1最少需要按几次reset才能获胜，并求出按下reset的对应回合

题解:观察reset操作，可看出reset操作后双方分数差值不变，相当于双方都减去双方分数的最小值，而不考虑k的限制时，多次reset操作都可看作在最后按reset的位置按一次reset，故可枚举获胜的位置(由后文贪心思路可知，越靠前所需按reset次数越少)，得出获胜的最靠前位置，和其对应的最后一次按reset的位置，再枚举前面的回合，只有在即将到达k时才按reset，即可贪心得出最少按reset的次数

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
138
139
140
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 2e5 + 5;
ll tmp, T, n, m, k;
ll a[maxn], prea[maxn], b[maxn], preb[maxn];

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        prea[0] = preb[0] = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i];
            prea[i] = prea[i - 1] + a[i];
        }
        for (ll i = 1; i <= n; i++)
        {
            cin >> b[i];
            preb[i] = preb[i - 1] + b[i];
        }
        ll tot = 0; //最后一次按reset位置，随获胜回合的位置单增
        ll ans = -1;
        vector<ll> ret;
        for (ll i = 1; i <= n; i++) //枚举获胜回合
        {
            while (tot <= i && prea[i] - min(prea[tot], preb[tot]) >= k)//找到满足a不会输的最小tot下标
            {
                tot++;
            }
            if (tot != i && prea[i] - min(prea[tot], preb[tot]) < k && preb[i] - min(prea[tot], preb[tot]) >= k)//计算b是否会输
            {
                ans = i;
                break; //得到最靠前的获胜回合
            }
        }
        if (ans == -1)
        {
            cout << "-1\n";
            continue;
        }
        else if (tot == 0)
        {
            cout << "0\n\n";
            continue;
        }
        else
        {
            bool flag = 1;
            ll pos = 0; //上次按reset位置
            for (ll i = 1; i < tot; i++)
            {
                if (prea[i + 1] - min(prea[pos], preb[pos]) >= k)
                {
                    pos = i; //在i-1回合结束后必须按
                    ret.push_back(i);
                    if (prea[i + 1] - min(prea[pos], preb[pos]) >= k)//按reset后仍可能失败
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            if (!flag)
            {
                cout << "-1\n";
                continue;
            }
            else
            {
                cout << ret.size() + 1 << "\n";
                for (auto &e : ret)
                {
                    cout << e << " ";
                }
                cout << tot << "\n";
            }
        }
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

发表于 | 分类于

B(多阶段dp)

大致题意:有若干个任务，有x、t、y、r四个属性(y<=x,r<=t)，有两个阶段，到达第一阶段需要s1经验值，到达第二阶段需要s2经验值，任务属性中，x表示在到达第一阶段前完成该任务所奖励的经验值，y表示在到达第一阶段后完成该任务所奖励的经验值，t表示在在到达第一阶段前完成该任务所花费的时间，r表示在到达第一阶段后完成该任务所花费的时间，先求到达第二阶段需要花费的最少时间

题解:最少时间+二维变量，一看很像背包，但两个阶段所需经验不同、任务数完成情况繁多，明显无法用背包来维护状态

故用dp[i][j]来表示状态，表示第一阶段前所获经验值=i，第一阶段后所获经验值=j时，所花费的最少时间

则dp[i][j]=min{dp[i][j],dp[i-a[k].x][j]+a[k].t,dp[i][j-a[k].y]+a[k].r}(即分别考虑第k个任务是在第一阶段前还是第一阶段后完成还是不完成，取最小值)

细节:任务的处理顺序—若不是从按x的从小到大顺序，会有什么问题?

在同一个阶段内状态转移时，类似于背包，任务的顺序不会产生影响，而overflow时，任务的顺序会产生影响

假设最佳方案时第一阶段的完成任务，按其x值递增排列是(1,2,3,4,5,6)，任务6完成第一阶段并将部分经验值转移到第二阶段，前5个任务随意打乱顺序都不会影响结果(都不会完成第一阶段，相当于一个类似背包的普通dp)，但如果将第6个任务提前，比如(6,5,4,3,2,1)，有可能提前完成第一阶段而导致不是最佳结果。

故将任务按x的顺序从小到大排，确保第一阶段完成前任务的完成顺序按递增顺序排列

下列代码根据j、k的情况分三类讨论:

  1. j<=s1，不会overflow，按正常dp方程处理
  2. j大于s1,此时会发生overflow，k需减去第一阶段转移来的多余值
  3. k不存在跨阶段问题，故按普通dp方程处理
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
138
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 500 + 5;
ll dp[2*maxn + 5][2*maxn + 5];
struct node
{
    ll x, t, y, r;
    bool operator<(const node &b)
    {
        return x < b.x;
    }
};
node a[maxn];
ll tmp, T, n, m, s1, s2;
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> s1 >> s2;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].x >> a[i].t >> a[i].y >> a[i].r;
        }
        sort(a + 1, a + 1 + n);
        for (ll i = 2*maxn; i >= 0; i--)
        {
            for (ll j = 2*maxn; j >= 0; j--)
            {
                dp[i][j] = 6e12;
            }
        }
        // memset(dp, 0x3f, sizeof(dp));
        ll noans = dp[1][1];
        // cout << noans << "\n";
        dp[0][0] = 0;
        for (ll i = 1; i <= n; i++)
        {
            for (ll j = 2*maxn; j >= 0; j--)
            {
                for (ll k =2* maxn; k >= 0; k--)
                {
                    if (j <= s1 && j - a[i].x >= 0)
                    {
                        dp[j][k] = min(dp[j - a[i].x][k] + a[i].t, dp[j][k]);
                        // if(dp[j][k]<noans)
                        // {
                        //    cout << j << " " << k << " "<<dp[j][k] << "!!!!\n";
                        //}
                    }
                    if (j >= a[i].x && j - a[i].x < s1 && j > s1 && k - j + s1 >= 0)
                    {
                        dp[j][k] = min(dp[j][k], dp[j - a[i].x][k - (j - s1)] + a[i].t);
                        // if(dp[s1][k]<noans)
                        // cout << j << " " << k << " "<<dp[s1][k] << "!!!!\n";
                    }
                    if (k - a[i].y >= 0)
                    {
                        dp[j][k] = min(dp[j][k - a[i].y] + a[i].r, dp[j][k]);
                        // if(dp[j][k]<noans)
                        // {
                        // cout << j << " " << k <<" "<< dp[j][k] << "!!\n";
                        // }
                    }
                }
            }
        }
        ll ans = noans;
        for (ll i = s1; i <= 2*maxn; i++)
        {
            for (ll j = s2; j <= 2*maxn; j++)
            {
                ans = min(ans, dp[i][j]);
            }
        }
        if (ans != noans)
            cout << ans << "\n";
        else
            cout << "-1\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

《关于我因为数组大小没开对wa了半天这件事》

F(博弈论+图论+树上问题)

大致题意:给定一颗树，在树上进行游戏，游戏规则如下：

  1. A可选定一个节点作为chip出发点，之后由B开始游戏
  2. 当轮到本人操作时，可选择将chip移至当前节点的子节点或父节点处(即与之相邻的节点)，但同一节点不能多次到达，若无法继续移动，则判本人负

题解:

在场上想的是所有的路径只能分为3类，只上、只下和先上后下，如果只下很容易处理，套用博弈论中的必胜点和必输点+树形dp就行，只上的情况根据每个节点的深度也可得出，但先上后下的情况过于复杂

引入图论中完全匹配的概念:

  1. 完全匹配是数量最多的一组边集，满足每条边的左右节点都只出现一次
  2. 若所有节点都在该边集出现过一次，则称该图完美匹配

将树看成图，结论:若图是完美匹配图，则Bob必胜，否则Alice必胜

证明如下：

  1. 若图是完美匹配图，则可将所有点划分成(s1,s2),(s3,s4)…若干个二元组，则当Alice选定任意个节点，Bob都可将其移动到其对应节点上，由于不能多次到达同一节点，Alice只能选择其他二元组的节点，Bob仍可重复上述操作直至所有节点都被遍历完毕，Bob胜利
  2. 若图不是完美匹配，设存在最大匹配(s1,s2),(s3,s4)…若干个二元组，有t个点不在该点集内，则Alice可选择不在该点集内的点开始游戏，Bob只能移动到该点集内的一个点(否则两个不在点集内的点也能匹配，与最大匹配相悖)，此时Alice可重复1中Bob操作，Bob输。若Bob可移动到不在该点集内的点，注意，，一开始时通过一个集外节点进入匹配点集，若再次从匹配点集到达集外节点，可将二元组重新分配且匹配数+1(画个图就很好理解)，与最大匹配定义相悖。

按正常图的方法求最大匹配，时间复杂度过大，而本题是特殊的树形结构，运用树形dp可在O(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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 100005;
vector<ll> g[maxn];
ll dp[maxn];
ll T, n;
void dfs(ll x,ll fa)
{
    ll cnt = 0;
    for (auto&e:g[x])
    {
        if(e==fa)
        {
            continue;
        }
        dfs(e, x);
        cnt += dp[e];
    }
    if(cnt==0)
    {
        dp[x] = 1;
    }else
    {
        dp[x] = cnt - 1;
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        ll x, y;
        for (ll i = 1; i <= n - 1;i++)
        {
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        dfs(1, 0);
        if(dp[1]==0)
        {
            cout << "Bob\n";
        }else
        {
            cout << "Alice\n";
        }
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

dp[i]表示以i为根的子树其不匹配的点数量，为0表示该子树完美匹配

今天被博弈论爆打的教训:1.不要纠结于每个人如何作出最佳操作，有时候只看结果思路更简单;2.图和博弈论可以根据完美匹配的定义结合，多留意一下

E

坑位预定

发表于 | 分类于

B(图论+贪心dp)

给定一张节点数小于1e5的无环无向图，有以下规定:

  1. 你可以强制monitor任意节点
  2. 被强制monitor的节点，其相邻节点和对应的连边都会被monitor
  3. 若一条边被monitor，则其对应的节点也被monitor
  4. 若一个边的对应两个节点都被monitor，则该边也被monitor
  5. 若一个节点和k条边相连，若k-1条边都被monitor，则剩下一条边也被monitor

现要求所有的节点和边都被monitor，求最少需要强制monitor多少个节点

正解:复杂的规则+图，考虑用dfs+贪心转移解决

考虑当前节点和其所有子节点、父节点，假设未被monitor子节点数为k

若k>=2,则对当前节点强制monitor能monitor所有子节点和父节点，若不对当前节点强制monitor，则在当前节点不为强制monitor的情况下，想要monitor其子节点，必须强制monitor子节点本身(因为k>=2不能满足规则5使边被monitor)，由于k>=2，故此时强制monitor当前节点花费最小且成效最大(父节点也被monitor)

若k==1，则依据规则3、4可知，该子节点的其他边都未被monitor，该子节点和当前节点的连边也未被monitor，当前节点与其父节点的连边monitor后，则该子节点与当前节点的连边也被monitor，则该子节点和该节点的所有边都会被monitor，故我们延后处理(即不做任何处理)

若k==0，则所有子节点都被monitor，如果当前节点也被monitor，则当前节点与父节点的连边，根据规则5，也被monitor，再根据规则3，当前节点的父节点也一定会被monitor；如果当前节点没被monitor，则无事发生

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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 100005;
ll tmp, T, n, m;
bool vis[maxn];
ll ans = 0;
vector<ll> g[maxn];
void dfs(ll x,ll fa)
{
    for(auto&e:g[x])
    {
        if(e!=fa)
        {
            dfs(e, x);
        }
    }
    ll cnt = 0;
    ll tmp;
    for(auto&e:g[x])
    {
        if(e!=fa)
        {
            if(!vis[e])
            {
                cnt++;
                tmp = e;
            }
        }
    }
    if(cnt>=2)
    {
        vis[x] = 1;
        vis[fa] = 1;
        ans++;
    }else if(cnt==0&&vis[x]==1)
    {
        vis[fa] = 1;
    }
}
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    //cin >> T;
    while (T--)
    {
        cin >> n;
        ll x, y;
        
        for (ll i = 1; i < n;i++)
        {
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        memset(vis, 0, sizeof(vis));
        ans = 0;
        dfs(1, 0);
        if(!vis[1])
        {
            ans++;
            vis[1] = 1;
        }
        cout << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

在场上的时候没读懂规则3和规则4

发表于 | 分类于

A(数据结构:区间更新、查询最值线段树)

大致题意：给定n个闭区间，求两个点，使包含这两个点的总数最多

题解:

很明显是离散化后用数据结构维护，想了个先找被包含区间数最大的点，去掉该点后找第二个点的错误贪心

正解:首先，我们规定，选取的第一个点始终位于第二个点的左侧。

离散化后将所有区间按左端点从大到小排列，再从大到小用i枚举点，将所有左端点大于i的区间加入，记录此时的最大值作为f[i]，则此时f[i]表示不包含左端点小于等于i的区间的情况下，能找到一个点，满足包含这个点的最多的区间数。

当所有区间都加入后，用i遍历所有点，f[i]+包含i的区间总数则为可能答案

证明:包含i的区间总数很好理解，即枚举第一条直线的位置，而f[i]则表示消除包含该条直线后的区间后，第二条直线能达到的最大区间数（其他区间要么对答案根本没贡献—完全位于i点左侧，要么包含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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
ll n, m, T;
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
struct node
{
    ll leftx, lefty, rightx, righty;
    friend bool operator<(node &a, node &b)
    {
        return a.righty < b.righty;
    }
};
node a[100005];
ll tmp;
ll lsh[200005];
const ll maxn = 200005;
ll num;
ll ans[200005];
struct seg_node
{
    ll val;
    ll lazy;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = max(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void pushdown(ll rt, ll ln, ll rn)
{
    if (segtree[rt].lazy)
    {
        segtree[rt << 1].lazy += segtree[rt].lazy;
        segtree[rt << 1 | 1].lazy += segtree[rt].lazy;
        segtree[rt << 1].val +=  segtree[rt].lazy;
        segtree[rt << 1 | 1].val +=  segtree[rt].lazy;
        segtree[rt].lazy = 0;
    }
}
void build(ll left = 1, ll right = num, ll rt = 1)
{
    segtree[rt].lazy = 0;
    if (left == right)
    {
        segtree[rt].val = 0;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
ll part_query(ll l, ll r, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val; //+segtree[rt].lazy;
    }
    if (l > right || r < left)
    {
        return 0;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    return max(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}
void part_update(ll l, ll r, ll value, ll left = 1, ll right = num, ll rt = 1)
{
    if (l <= left && r >= right)
    {
        segtree[rt].val += value;
        segtree[rt].lazy += value;
        return;
    }
    ll mid = (left + right) >> 1;
    pushdown(rt, mid - left + 1, right - mid);
    if (l <= mid)
    {
        part_update(l, r, value, left, mid, rt << 1);
    }
    if (r > mid)
    {
        part_update(l, r, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}

int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        //ll ans = 0;
        for (ll i = 1; i <= n; i++)
        {
            cin >> a[i].leftx >> a[i].lefty >> a[i].rightx >> a[i].righty;
            lsh[i] = a[i].righty;
            lsh[i + n] = a[i].lefty;
        }
        sort(lsh + 1, lsh + 1 + 2 * n);
        // memset(tree, 0, sizeof(tree));
        num = unique(lsh + 1, lsh + 1 + 2 * n) - lsh - 1;
        for (ll i = 1; i <= n; i++)
        {
            a[i].lefty = lower_bound(lsh + 1, lsh + 1 + num, a[i].lefty) - lsh;
            a[i].righty = lower_bound(lsh + 1, lsh + 1 + num, a[i].righty) - lsh;
        }
        sort(a + 1, a + 1 + n);
         //reverse(a + 1 + n, a + 1);
         //cout << a[n].righty << "!!!\n";
        // build(1, num, 1);
        build(1,num,1);
        ll now = n;
        for (ll i = num; i >= 1; i--)
        {
            while (now>=1&&a[now].righty > i)
            {
                part_update(a[now].righty, a[now].lefty, 1,1,num,1);
                now--;
            }
            ans[i] = part_query(i, num,1,num,1);
        }
        while (now >= 1)
        {
            part_update(a[now].righty, a[now].lefty, 1,1,num,1);
            now--;
        }
        ll mx = 0;
        for (ll i = 1; i <= num; i++)
        {
            ans[i] += part_query(i, i,1,num,1);
            mx = max(ans[i], mx);
        }

        cout << mx << "\n";

#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

这个线段树写法是硬改的。。不怎么优雅，而且常数很大

B(图论、Floyd)

题意:给定m个物品，n个人对所有物品进行喜好度分级(可能多个物品同一级)，先规定d(x,y)为比起y更喜欢x的人数，现有路径,满足条件d(t,t+1)>d(t+1,t)(即路径中相邻两项中，比起右项更喜欢左项的人数要严格大于比起左项更喜欢右项的人数)，在所有d(t,t+1)中，取最小值作为S(x,y)的预备值，在所有预备值中，取最大值作为S(x,y)，若不存在路径，则规定S(x,y)=0,若S(x,y)>=S(y,x)，当y为除了x的任意值时，都成立，则输出x，要求找出所有x(m<500,n<500)

题解:

图论题，用d[x,y]存储比起y更喜欢x的人数后，将所有不能形成路径的d消去(避免影响后续计算)，类似Floyd算法，规定dp[k,x,y]表示x、y之间路径不包含编号超过k的节点时，S(x,y)的最大值，当k=0时，dp[0,x,y]=d[x,y]/(前提是d[x,y]有意义，即能形成路径)，之后枚举k进行计算，得到S值，再枚举所有S值得到答案。

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
138
139
140
141
142
143
144
145
146
147
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 505;
const ll INF = 0x7fffffff;
ll T, n, m;
//ll S[maxn][maxn];
ll d[maxn][maxn];
ll a[maxn];
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> m >> n;
        /*if(m==1)
        {
            cout << "\n";
            continue;
        }*/
        memset(d, 0, sizeof(d));
        //memset(S, 0, sizeof(S));
        for (ll i = 1; i <= n;i++)
        {
            for (ll j = 1; j <= m;j++)
            {
                cin >> a[j];
                if(a[j]==0)
                {
                    a[j] = INF;
                }
                for (ll k = 1; k < j;k++)
                {
                    if(a[j]!=0&&a[j]<a[k])
                    {
                        d[j][k]++;
                    }else if(a[k]!=0&&a[k]<a[j])
                    {
                        d[k][j]++;
                    }
                }
            }
        }
        for (ll i = 1; i <= m;i++)
        {
            for (ll j = 1; j < i;j++)
            {
                if(d[i][j]==d[j][i])
                {
                    d[i][j] = 0;
                    d[j][i] = 0;
                }else if(d[i][j]>d[j][i])
                {
                    d[j][i] = 0;
                }else if(d[i][j]<d[j][i])
                {
                    d[i][j] = 0;
                }
                d[i][i] = 0;
            }
        }
        for (ll k = 1; k <= m;k++)//类似Floyd
        {
            for (ll i = 1; i <= m;i++)
            {
                for (ll j = 1; j <= m;j++)
                {
                    d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));
                }
            }
        }
        for (ll i = 1; i <= m;i++)
        {
            bool flag = 1;
            for (ll j = 1; j <= m;j++)
            {
                if(i==j)
                {
                    continue;
                }
                if(d[i][j]<d[j][i])
                {
                    flag = 0;
                    break;
                }
            }
            if(flag)
            {
                cout << i << " ";
            }
        }
        cout << "\n";
    }
    return 0;
}

E(二分+贪心)

题意:给定n组数据(x,y)，根据题意求出误差最小值

题解:小数二分误差值，check使用贪心

check具体流程:将所有点按x坐标从左到右排好之后，先找到pos满足pos前的所有值都小于等于给定值，之后到达第二阶段；易知同一分段内的最大值最小值之差不能大于2给定值，根据最大最小值更新第二阶段可能的最小值，直至不满足条件，将其作为pos；之后所有点都归为第三个分段，而第三个分段满足的条件是:1.最大值、最小值之差不能大于2给定值2.最小值+给定值必须大于第二阶段值

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 3e5 + 5;
ll n;
const ll INF = 0x7fffffff;
const double eps = 1e-2;
struct node
{
    ll x;
    ll y;
    friend bool operator < (node&a,node&b)
    {
        return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x);
    }
};
node a[maxn];
bool check(double err)
{
    ll pos = 1e9 + 5;
    ll id1=1, id2;
    for (ll i = 1; i <= n;i++)//1 1 1 2 2
    {
        if(abs(a[i].y)>err)
        {
            pos = a[i].x-1;
            break;
        }
        if(i!=n&&a[i].x!=a[i+1].x)
        {
            id1 = i + 1;
        }
    }
    if(pos==-1)
    {
        //cout << "1!!\n";
        return false;
    }
    if(pos==1e9+5)
    {
        return true;
    }
    ll mx = -1e9-5, mn = 1e9+5;
    ll pos2 = 1e9 + 5;
    double val2;
    for (ll i = id1; i <= n;i++)
    {
        if(a[i].y>mx||a[i].y<mn)
        {
            if(2*err<max(a[i].y,mx)-min(a[i].y,mn))
            {
                pos2 = a[i].x - 1;
                val2 = min(mx - err, mn + err);
                //val2 = max(val2, 1.0*0);
                //cout << i << "debug!!\n";
                break;
            }else
            {
                mx = max(mx, a[i].y);
                mn = min(mn, a[i].y);
            }
        }
        if(i!=n&&a[i].x!=a[i+1].x)
        {
            id2 = i + 1;
        }
    }
    if(pos2==pos)
    {
        //cout << val2<<"!"<<"!"<<"!\n";
        return false;
    }
    if(pos2==1e9+5)
    {
        return true;
    }
    mx = -1e9 - 5, mn = 1e9 + 5;
    for (ll i = id2; i <= n;i++)
    {
        mx = max(mx, a[i].y);
        mn = min(mn, a[i].y);
    }
    if(1.0*(mx-mn)>2*err)
    {
       // cout << "3!!\n";
        return false;
    }
    if(1.0*mn+err<val2||1.0*mn+err<0)
    {
       // cout << "3!!\n";
        return false;
    }
    return true;
}
int main()
{
    ll T = 1;
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n;
        double l = 0, r;
        for (ll i = 1; i <= n;i++)
        {
            scanf("%lld %lld", &a[i].x, &a[i].y);
            r = max(abs(1.0*a[i].y), r);
        }
        //r = INF;
        sort(a + 1, a + 1 + n);
        double mid;
        while(r-l>eps)
        {
            mid = (r + l) / 2;
            //cout << mid << "\n";
            if(check(mid))
            {
                r = mid+1e-3;
            }else
            {
                l = mid-1e-3;
            }
        }
        printf("%.1lf",(r + l) / 2);
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

发表于 | 分类于

F(数据结构:点更新、查询最值线段树)

给定N个正整数，N<=400000，数字会重复，但每个数都小于等于N，求字典序最小的A、B满足：该数列中含有A、B、A、B子序列(不一定连续)

题解:第一眼能猜到是个数据结构题，但不会推(

思路1：A、B、A、B，是一个交错结构，可以先想查询ABA子序列，则只需要知道下一个A的位置(预处理中能得到)，在两个位置之间查询最小值即为B，可在NlogN内完成，如果替换成ABAB的情况，则我们需要保证查询到的最小值B，其在两个A的间隔之后，仍存在一个B，很麻烦。

故转化思路，在遍历到时，将其看作B，查询BAB中的A，而A是遍历到之前插入线段树的，故在两个B之前必定存在一个A

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int maxn = 400005;
const int INF = 0x3f3f3f;
int tmp;
int n;
int a[400005];
int nxt[400005];
int lst[400005];
struct seg_node
{
    int val;
} segtree[maxn << 2];
void pushup(ll rt)
{
    segtree[rt].val = min(segtree[rt << 1].val, segtree[rt << 1 | 1].val);
}
void build(ll left = 1, ll right = n, ll rt = 1)
{
    if (left == right)
    {
        segtree[rt].val = INF;
        return;
    }
    ll mid = (left + right) >> 1;
    build(left, mid, rt << 1);
    build(mid + 1, right, rt << 1 | 1);
    pushup(rt);
}
void point_update(int point, int value, int left = 1, ll right = n, ll rt = 1)
{
    if (left == right)
    {
        segtree[rt].val = min(segtree[rt].val, value);
        return;
    }
    int mid = (left + right) >> 1;
    if (point <= mid)
    {
        point_update(point, value, left, mid, rt << 1);
    }
    else
    {
        point_update(point, value, mid + 1, right, rt << 1 | 1);
    }
    pushup(rt);
}
int part_query(int l, int r, int left = 1, int right = n, int rt = 1)
{
    if (l <= left && r >= right)
    {
        return segtree[rt].val;
    }
    if (l > right || r < left)
    {
        return INF;
    }
    int mid = (left + right) >> 1;
    return min(part_query(l, r, left, mid, rt << 1), part_query(l, r, mid + 1, right, rt << 1 | 1));
}

int main()
{
    n = read();
    memset(lst, 0, sizeof(lst));
    memset(nxt, 0, sizeof(nxt));
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
    }
    for (int i = n; i >= 1; i--)
    {
        nxt[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    build(1, n, 1);
    int tmp, A = INF, B = INF;
    for (int i = 1; i <= n; i++)
    {
        if (nxt[i] == 0)
        {
            continue;
        }
        tmp = part_query(i+1, nxt[i]-1);
        if (tmp != INF)
        {
            if (tmp < A)
            {
                A = tmp;
                B = a[i];
            }
            else if (tmp == A)
            {
                B = min(B, a[i]);
            }
        }
        point_update(nxt[i], a[i]);
    }
    if (A == INF || B == INF)
    {
        write(-1);
        putchar('\n');
    }
    else
    {
        write(A);
        putchar(' ');
        write(B);
        putchar('\n');
    }
    return 0;
}

思路2：题目要求字典序最小，故我们找出满足题目条件的A，在A之间再找B，略复杂

G(数学、排列组合计数问题)

题意:给定RxC的方格，给定整数K(1<=K<=R*C)，在方格上找到N个矩形，满足所有矩形的共有区域的格数大于等于K，求矩形有多少种摆放方式(注意:矩形的顺序也有影响)

题解:预处理出共有区域大小刚好为i的摆放方式，最后枚举i从K到MAX的和

问题:如何预处理以至于不漏、不重复?可以看出共有区域必定是个矩形，故我们从矩形的row和column两方面考虑，若i块矩形，其row的位置有m种可能，column的位置有n种可能，则一共有m*n种摆放方式。故我们只需处理出共有区域的row的长度为1~R时，其所对应的可能数，column的长度从1~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
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/
inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll mod = 1e9 + 7;
ll T, n, r, c, k;
ll pr[5005], pc[5005];
ll p[5006];
ll ksm(ll x, ll y)
{
    if (x == 0)
    {
        return 0;
    }
    ll ret = 1;
    while (y)
    {
        if (y & 1)
        {
            ret = (ret * x) % mod;
        }
        x = (x * x) % mod;
        y /= 2;
    }
    return ret;
}
void pre()
{
    ll cnt;
    for (ll len = 1; len <= r; len++)
    {
        cnt = 0;
        for (ll l = 1; l + len - 1 <= r; l++)
        {
            cnt += (p[l] - p[l-1])* (p[r - (l + len - 1) + 1] - p[r - (l + len - 1)]) % mod;
            // cout << cnt << "!!\n";
            cnt %= mod;
        }
        pr[len] = cnt;
        // cout << "pr" << len << "==" << pr[len] << "\n";
    }
    for (ll len = 1; len <= c; len++)
    {
        cnt = 0;
        for (ll l = 1; l + len - 1 <= c; l++)
        {
            cnt += (p[l]-p[l-1]) * (p[c - (l + len - 1) + 1] - p[c - (l + len - 1)]) % mod;
            cnt %= mod;
        }
        pc[len] = cnt;
        // cout << "pc" << len << "==" << pc[len] << "\n";
    }
}
int main()
{
    T = 1;
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> r >> c >> k;
        for (ll i = 0; i < 5005; i++)
        {
            p[i] = ksm(i, n);
        }
        pre();
        ll ans = 0;
        for (ll i = 1; i <= r; i++)
        {
            for (ll j = 1; j <= c; j++)
            {
                if (i * j >= k)
                {
                    ans += pr[i] * pc[j];
                    ans %= mod;
                }
            }
        }
        cout << (ans+mod)%mod << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

D(环型贪心、二倍环展开)

题意:给定N个数组成的圆环，求将圆环上的数分割成K组后，每组的OR值的AND值最大

题解:位运算很容易想到从高到低位考虑，当第i位为1的数不足k个，或将其分为k组的分法与更高位的分法相悖时，第i位对答案没有贡献。

我们就考虑1位时，很明显若当前位出现1时，将其划分到一组，最后看能划分出的组数大于等于k，即存在答案

而若考虑2位时，先将最高位按上述处理，若最高位对答案有贡献，则当前位和最高位都为1时，才将其划分到一组，最后也是看划分出的组数是否大于等于k

环问题，则将其转化成2n的序列，则划分出的组数要大于等于2k-1(将环变成二倍环，展开后最多减少1个组数，即2k-1满足条件—如果不扩展成二倍环，无法区分最后组数是否收到展开的影响而-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
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

inline int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}

inline void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 100005;
ll tmp;
ll n, m, T, k;
ll a[1000005];
int main()
{
    T = 1;
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (T--)
    {
        cin >> n >> k;
        for (ll i = 1; i <= n;i++)
        {
            cin >> a[i];
            a[i + n] = a[i];//将环展开
        }
        ll ans = 0;
        for (ll i = 30; i >= 0;i--)//从高位枚举到低位贪心
        {
            ll cnt = 0, tmp = 0;
            for (ll j = 1; j <=2* n;j++)
            {
                tmp |= a[j];
                if(((ans|(1<<i))&(tmp))==(ans|(1<<i)))//此时的值满足成组条件
                {
                    cnt++;
                    tmp = 0;//重置
                }
            }
            if(cnt>=2*k-1)
            {
                ans |= (1 << i);
            }
        }
        cout << ans << "\n";
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

发表于 | 分类于

课程视频:https://www.bilibili.com/video/BV1iW411d7hd?share_source=copy_web

Lecture02:Bits,Bytes,and Integer

浮点数的二进制表示:100010.101=1*2^5+1*2^1+1*2^(-1)+1*2^(-3)

4个bit分为一组—>十六进制

x86-64上的数据类型:

  1. char 1字节—8位
  2. short 2字节—16位
  3. int 4字节—32位
  4. long 8字节—64位
  5. float 4字节—32位
  6. double 8字节—64位
  7. long double 10/16字节(只使用10个字节，当在64位机器上使用时，额外6字节被浪费—保证了一切以16字节对齐)

64位机器、32位机器:地址是64位或32位(即pointer的大小)

位移操作(shift)

左移(left shift):将bit-vector向左移动,将溢出位舍弃,在右边填0

右移(right shift):将bit-vector向右移动,将多余位舍弃

signed的逻辑右移(logic shift):在左边填0

signed的算术右移(Arithmetic shift):在左边复制符号位(为什么没有算术左移?左移相当于执行了一次可能会溢出的乘法)

注意:移动<0的数或大于等于数据字节长度的行为,都是UB

二进制到unsigned,signed的转换(T表示two’s complement,即二进制补码形式):

即最高位取负数,其他不变,若最高位为1,则一定是负数(最大为-1)

|TMin|=TMax+1

UMax=2*TMax+1

B2U,U2B(对同一个bit-vector,建立从signed到unsigned的映射)

注意:在C中,默认常量都是signed,如要使用unsigned需要添加后缀”U”,如0U,4294967259U

当signed,unsigned被混合运算时(如大小比较),signed总被转化成unsigned(bit-vector保持不变,仅仅是转换方式变化)

signed extension(如32位拓展到64位):signed在左边复制符号位(类似算术右移),即从符号位开始的一连串1,可等价于将这串1中,最低位作为符号位

Lecture03:Bits,Bytes,and Integers cont

Unsigned Addition :相加后无论”多出”的一位是什么,都舍弃掉,可理解为模运算,即

Two’s complement Addition:等价于将两个数都转化为unsigned计算后再转化为signed(即按位相加)

正溢出(positive):两个较大正数加在一起使符号位变成1,即得到负数

负溢出(positive):两个较小负数加在一起使符号位变成0,即得到正数

.png)

Unsigned Multiplication:相乘后多余位舍弃,可理解为模运算,即

Signed Multiplication:当作unsigned相乘后舍弃多余位,剩下的首位作为符号位,如55=25—>11001—>1001—>-7,若相乘后的数字可以用目前位数表示,则结果正常(注意,这里相乘后的数字指的是*signed相乘结果,而不是转化成unsigned后的相乘结果)

注意,负数算术右移时,结果会向负无穷舍入,而不是零(即左侧,事实上这就是二分中通常用>>1的原因),如果想要向零舍入,需要添加一个偏移量(添加偏移量的操作,编译器会在使用除法时自动添加,然后在实施右移)

??C语言对signed的右移是算术还是逻辑右移没有明确规定,绝大多数情况下是算术右移

移位操作消耗1计算周期,而乘法操作消耗3个计算周期(通过各种硬件优化),除法操作消耗30个计算周期

signed取相反数(x—>-x):将所有位取反,再+1,故Tmin=-Tmin

数据是如何存储的:在64位机器中,地址有64位,可以将内存系统理解为一个巨大的char数组,每一个char占据一字节,64位地址能表示的下标从0~2^64,故最多存储2^64字节数据(实际上目前能使用的最大内存地址是47位,对应的内存大小大约是128TB),实际上,只是程序认为它可以使用这么大的空间,当程序运行时,系统会规定其能访问的内存区域,如果程序试图访问其他区域,将报错(即segementation fault)

一般情况下,数据类型的地址取其占有的bytes的最低位地址,如64位地址占据了0000~0007这8个byte,这该地址是0000,类比0008~0015是0008;而32位地址同理,0000~0004是0000,0005~0007是0005(地址表示一般情况下使用十六进制)

字长(Word Size):没有明确规定,当我们提及64位机器时,指的是其pointer/地址大小是64位(尽管只使用了47位)

使用GCC编译时,可以指定它是64位还是32位,会生成两种不同类似的object code,即硬件本身不一定定义字节大小,是硬件和编译器一起决定(64位的代码也可兼容32位机器)

multi-byte word是如何在内存中排序的?

小端序(little endian):最低有效byte拥有最低位地址(x86,IOS,Windows,ARM processors running Android)

大端序(big endian):最低有效byte拥有最高位地址(PPC MAC,Internet)

如15213=3B6D(十六进制)

在小端序中:6D 3B 00 00

在大端序中:00 00 3B 6D

例外:无论是小端序还是大端序,char数组的存储顺序都是相同的,即都符合大端序,’/0’放在最高位

实际上,ARM的硬件配置为既能处理小端序也能处理大端序

Lecture04:Floating Point

小数/分数的二进制表示:(小数点左侧0~i,右侧-1~-j)

如果是分数—>依次减1/2,1/4,1/8判断该位是否为1

如果固定位数,将point左移,则能表示的最大值变小了,精度变大;将point右移,则精度变小,能表示的最大值变小了,故采用floating point,即浮点来表示小数

IEEE(电气电子工程师学会) floating point:

形式:

Sign bit 表示了该数是正是负;Significand/Mantissa表示一个介于[1.0,2.0)之间的值;而Exponent表示了该值要乘上2的多少次方

单精度浮点数(32位):s占一位,exp占8位,frac占23位;双精度浮点数(64位):s占一位,exp占11位,frac占52位;80位浮点数(Intel only):s占1位,exp占15位,frac占63位或64位(所以为什么不直接取64位呢?)

Normalized values:

exp域(阶码字段)决定了E,但不等于E,同时,exp域不能全为0或全为1.exp域视作一个unsigned number,exp域的值-bias(偏移量,值为)后才是E.(example:exp占8位,则bias为127,exp域本身的范围是1~254,加上偏移量后是-126~127).

注意,为何不用exp域不使用signed number的标准—>便于浮点数之间比较

significand域(尾数域/frac)决定了M,但不等于M,其采用隐含编码法.即假设M=1.xxxxxx始终成立,可以省去一位来表示小数点前的1,所以尾数域全0时尾数最小为1,尾数域全1时尾数最大,极其接近2.0

Denormalized values:

来源:当我们想表示0or非常接近0的数时,尾数域隐含的1限制了我们

解决措施:当exp全为0时,其值不是0-bias,而是1-bias.同时,尾数域隐含的1变为0,即0.xxxxxx

example:

  1. exp全为0,frac全为0,则此时值为0,但注意有(+0和-0的区别)
  2. exp全为0,frac不全为0,则此时值很接近0(0.xxxxx的-126次方)

Special values:

当exp全为1时:

  1. 若frac全为0,则表示一个,如,
  2. frac不为0,表示Not-a-Number(NaN),表示无法确定的值,如sqrt(-1),,

.png)

.png)

相关性质:比较浮点数的大小时,除了NaN,都可以将其视作unsigned number比较(即从高到低依次相比):正数总是比负数大;当exp不全为0时,exp域大的数总是比exp域小的数大(最高位是隐含的1);当exp全为0时,尾数域大的总是比尾数域小的数大

Floating Point Operations(addition,multiplication)

rounding(舍入):

  1. towards zero(向零舍入)
  2. round down(向负无穷舍入,即舍入后的值<=舍入前的值)
  3. round up(向正无穷舍入,即舍入后的值>=舍入前的值)
  4. default:nearest even(向最靠近的值舍入,偶数优先,如1.4-1,1.6-2,1.5-2,2.5-2,-1.5—2)

为什么采用IEEE采用nearest even作为默认舍入规则:当给定足够多数据时,这些数据有50%的概率增加或减少,故平均值保持不变(可能不够严谨,但至少能说明为什么该规则较优)

而应用到二进制数上:偶数即有效位的最低位是0,而中间值(即’0.5’)是10000….,其他都同理

Floating Point Multiplication:

符号位取异或,exp域相加,尾数域相乘

如果尾数域>=2,右移,增加exp

如果exp超出范围,overflow

对尾数域相乘结果进行舍入以对应尾数域精确度

Floating Point Addition:

首先对齐小数点(即exp域取二者中较大值),然后相加

若尾数域>=2,右移,增加exp

若尾数域<1,左移k位使其>=1,exp减少k

如果exp超出范围,overflow

对尾数域相加结果进行舍入以对应尾数域精确度

注意,浮点数的加法,乘法均不满足结合律,如(1e20+3.14)-1e20=0,(1e20-1e20)+3.14=3.14

(1e20*1e20)*1e-20=inf,1e20*(1e20*1e-20)=1e20

在”自然”条件中,值通常是连续的,即不会相差太大,浮点数的该性质通常不会产生影响.但是在非自然条件中,如金融行业中的计算,需要注意该性质对结果的影响.

C语言中的浮点数

当浮点数和int之间发生类型转化时,不能保持bit-vector不变而只改变翻译方式

double/float—>int:

  1. 截去小数(效果如同向0舍入)
  2. 当浮点数的值超出范围或者为NaN时,没有定义,通常情况下会设置为TMin

int—>double:

  1. 如果int的位数小于等于53(double的尾数域长度),值将不会改变

int—>float:

  1. 同理double,若尾数域长度小于int位数,将会发生舍入

Lecture05:Machine-Level Programing I:Basics

一般说machine program有两种含义,一是计算机实际运行的object code(是一系列代表着实际操作的字节);二是汇编代码(编译器的目标便是将代码转化成汇编代码).二者是一一对应的.

x86机器有两种汇编语言,一种是Intel和Microsoft使用的,一种是Linux使用的(本课程使用).二者参数顺序不同.

本课程采用的是英特尔64位processors(处理器)的指令集

英特尔processors的历史:

x86是对英特尔processer的一个口头称呼,因为芯片名字都含有86

x86的特性总是不断进化\重叠,其指令集或许不是最清晰易懂的,却是最uesful的

80年代的RISC(reduced instructions set computer,即精简指令集计算机)和CISC(complex instructions set computer,复杂指令计算机.实际上,CISC是RISC派给以前的处理器起的名,带有贬义色彩,乐)大战

英特尔采用CISC架构

8086:1978年推出,是第一个16位Intel processor,有1MB的内存空间,其一个变种是IBS和DOS的基础

386:1985年推出,也被称作IA32,因为其是第一个32位Intel processor.添加了”flat addressing”,能运行Unix或Lunix

Pentium 4E:2004年推出,也被称作x86-64,因为其是第一个64位Intel processor(其也可运行32位代码,避免了software从32位到64位的长久迭代)(到这一代为止,Intel processor的性能都在逐步提升,但面对着功耗过高的问题,引出了多核processor(可以理解为在一个芯片上塞多个处理器))

Core 2:2006年推出,是第一个multi-core(多核)Intel Processor

Core i7:2008年推出,其拥有4个core

Processors有Desktop Model(一般功率更高)和Server Model(Cores一般更多)两种

.png)

DDR:processor链接到主存储器的方式,即DRAM/动态RAM

PCI是与外部设备的连接

SATA是与不同类型盘的连接

Ethernet(以太网接口)连接到一个网路

这些逻辑单元和处理器一起组成了芯片

Advanced Micro Decvices:AMD(Intel的对手,和Intel之间吵过专利,结果是AMD被允许生产x86处理器)

AMD提出了64位英特尔扩展程序

2001年,Intel投入大量资金,试图从IA32转变到IA64,在市场上没有成功

而AMD将寄存器变大,只是将东西从32位变成64位,并获得了成功,于是Intel跟随其脚部继续推出x86

ARM(Acorn RISC Machine),一家公司推出的自家芯片,然后公司华丽丽的破产了,但是其指令集非常高效且简单,可以设置在芯片上,且可定制

所以ARM现在是一家位于英国剑桥的公司,向其他公司出售使用其设计的许可权利(其比x86机器功耗更低)

如前言所说,编译器的目标是将你的code转化成电脑操作的指令,但有些指令更简单,却需要更多硬件,有些指令很繁琐,但不需要什么硬件条件,而如何最好的实现指令集,是硬件研究者的工作

.png)

pc:Program counter,存储下一条指令的地址,在x86-64中被称作”RIP”

register:存储数据(有各自的名字,如%rbx,%rdx等等)

condition code:存储操作的状态信息,在branching(“分支”)中使用

Memory:可以视作一个巨大的字节数组,实际上是操作系统和硬件协调产生的一种”虚拟内存”,每个软件都有自己独立的字节数组,而在物理意义上,所有软件都共享这些字节数组(cache指的是多次访问同一位置的内存总是更快,但注意,在指令层面,你无法直接操作cache)

将C 转变成object code:

.png)

第一步是将C代码变成汇编代码(gcc -Og -S,-Og是对编译器进行什么优化的规范,O是指Optimize,如果不加,将不会进行任何优化,;-S意思是Stop,只做第一部分,即将C代码变成汇编代码)

第二步是通过汇编程序(Assembler)运行它,将文本形式的代码转化成字节形式

第三步是通过链接器(Linker),将不同的文件融合在一起

(你的各个代码文件和库代码)

实际上,当真正开始运行这个程序上时,有些库是在首次启动时动态导入

1.将C转化成Assembly(汇编代码)

.png)

pushq:将某个数据压入栈中

movq:将某个数据移动位置

call:调用某个procedure(操作序列)

ret:从一个特定的函数返回

汇编代码中的数据类型:

.png)

Integer类型:存储整数(不区分signed,unsigned,C中的pointer等数据类型也以该形式存储)

Floating point类型:以不同的方式处理,使用不同的寄存器组

Code:定义了一系列操作的字节序列

结构体等数据类型,都不存在于机器代码中,都由编译器来定义

2.将汇编代码变成object code

.png)

.png)

一些指令可能只有1byte,但也有些指令有15bytes(不同指令所代表byte长度不一定)

变量的所有名称,在汇编代码,机器代码级别完全丢失(变成了寄存器和内存中的某个位置)

.png)

disassembler/反汇编(顾名思义,将object code逆推成汇编代码)

.png)

gdb:强大的debugger,可以在存在source code的情况下进行调试,不存在source code时,也可进行调试,其也具有反汇编功能(disassemble xxxx)

x/14xb sumstore—显示从sumstore地址开始的14个十六进制byte

更多的汇编基础知识:

.png)

注意:如果你使用%r版本,使用的是64位register;如果你使用%e版本,使用的是32位register(实际上,%e版本只是使用了%r版本的低32位,同理,8位,16位都可取到)

rsp是特殊的寄存器,被称为栈指针(stack point)

左半部分寄存器(除rsp)的命名来自其原始用途,现在这些名字只是历史遗留问题,在大多数情况下,他们都可用于保存数据

.png)

注意,从IA32到64位处理器,寄存器数量增加了一倍

movq operation:

.png)

注意,不能将内存中的数据直接移动到内存中的另一个地方,需要两次操作(Mem-Reg,Reg-Mem)

.png)

(%xxx)表示对该寄存器所存储的地址解引用

D(%xxx),D是一个数字,表示对该寄存器所存储的地址加一个偏移量后解引用

.png)

swap函数示例

对地址解引用的更多操作:

.png)

.png)

leaq(load effective address):地址操作

有些乘法操作可以转化成leaq,如*12—>*3再*4

.png)

.png)

.png)

.png)

Lecture06:Machine-Level Programing II:Control

Condition codes:

.png)%rip:指令指针(instruction pointer,在IA32中中叫%eip),包含正在执行指令的地址,无法通过正常方式操作(可通过技巧获取它的值)

condition codes一共有8个,图中只展示了4个,都只有1bit

.png)

CF:在二进制加法时,表示是否进位(翻译为溢出更恰当?)

ZF:当计算结果为0时被置位

SF:计算结果最高位为1时(signed)被置位

OF:当signed计算溢出时被置位(包括加,乘?)

注意,lea不会操作这4个condition code

专门操作condition code的指令:

.png)

.png)

获取condition code的手段:

.png)

setX根据condition code的状态,将目标寄存器的低位,置1或置0,以此来知道最近的指令做了什么

sete,setne表示上次指令的结果是相等或为零

sets,setns表示上次指令的结果的正负性(没有考虑溢出)

setg,setge表示上次指令的结果是大于(大于或等于),这里用了~(SF^OF)表示大于或等于,即考虑了正溢出和负溢出,保证了比大小不会因为溢出出错

setl,setle同理

setb表示上次指令结果是否溢出(unsigned)

.png)

%xxl表示寄存器的最后一位(l—low)

setX示例:

.png)

PS:x86-64的小特性:当你操作32位寄存器时,会将寄存器的其余32位置为0.

而byte(如short)操作不动其他位(更低位也如此)

Conditional branches:

if和else

传统的实现方法:jump instruction

unconditional jump(无条件跳跃)

conditonal jump(有条件跳跃)

.png)

示例:

.png)

.XXX:label,在object code中并不存在(代表了指令的地址?)

优化:Conditional Moves(类似于先将if的结果和else的结果都算出来,根据条件值判断使用哪个)

先猜测条件结果(大部分情况下都能猜对),并直接开始计算

.png)

可以类比工厂的工作流水线,可以同一时间处理多条指令,而不是卡在条件指令,使之更有效率

示例:

.png)

注意,conditional move仅在分支计算都很简单的时候能提高效率,在某些情况下甚至有风险(如解引用NULL指针),有时计算结果影响条件判断

.png)

loops:

.png)

.png)

dowhile循环的实现

-Og级别的while:

.png)

-O1级别的:

.png)

for循环

.png)

类似while循环

.png)

采用O1优化时,会删除初始化之后的一个test(因为一定对)

switch:

.png)

switch会生成一个类似于数组的jump table,以快速定位提高效率

.png)

.png)

注意,从0到x的最大值均有其标签(如果出现负数,会添加一个bias使下标从0开始)

若是x的范围过大且相对稀疏(如x为0和1000000,会使用二分优化成if else)

.png)

break代码块:

.png)

注意,switch后即为return w,故将ret写在代码块内

.png)

.png)

只有case3中的指令需要w初始化,故将w初始化放在case3中.

case2fall-through到case3中,故在初始化后添加merge标签供case2跳转

发表于 | 分类于

题面:https://codeforces.com/contest/1698/problem/E

大致题意:给定a排列、b排列的部分、数值s，规定可对a排列进行如下操作:在第i次操作时，可选定下标范围在i~i+s的两个数值，进行交换(若选定的两个下标相同，则排列不变，可视为跳过一次操作)

求通过若干次操作，能使a排列变为b排列的b排列总数

题解:易想到，先求解怎样的b排列符合条件，即假定一个特定的b排列，判断是否满足条件。先上结论:若，则符合条件

证明如下:

  1. 证明:将b按大小与a一起重排后，按照新的排列考虑问题不影响结果(因为a数组已经固定，故可以理解为对a数组进行重新”投射”)
  2. 按的大小从小到大考虑问题，若=m,大于m，则前几次操作不会涉及(因为其大于m,与前面的b不会对应);若，则不需移动，且第i次操作可直接放弃而不造成影响;若，此时a中的m所对应b大于m，则在考虑中，已将其调到另外一个b处，必定可以完成操作
  3. 欲证明，若=m,大于m，则使a归位需要的s最少为a、b之差，按b大小重排后则所需，等效到原排列中s不变
  4. 已知s，对每个未知b，可知道其可能值的个数(可能值从小到大排)，故从可能值个数较小的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
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
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <time.h>
#include <unordered_set>
#include <vector>
using namespace std;
using ll = int64_t;
/*head*/

#define fi first
#define se second
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
//#define DE_BUG
/*define*/

ll T, n, m, k, tt = 0, ss;
ll tmp, a[300005], b[300005];
const ll mod = 998244353;
// 1 0
// 2 0
// 3 1
// 4 1
// 5 2
// 6 2
// 7 3
void solve()
{
    ll ans = 1;
    bool flag = 1;
    cin >> n >> ss;
    set<ll> s;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i];
        s.insert(i);
    }
    for (ll i = 1; i <= n; i++)
    {
        cin >> b[i];
        if (b[i] != -1)
        {
            if (a[i] - b[i] > ss)
            {
                flag = 0;
            }
            s.erase(b[i]);
        }
    }
    if(!flag)
    {
        cout << "0\n";
        return;
    }
    vector<ll> cnt;
    vector<ll> s2(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    for (ll i = 1; i <= n;i++)
    {
        if(b[i]==-1)//b>=a[i]-s
        {
            ll tmp = s2.end()-lower_bound(s2.begin(), s2.end(),a[i]-ss);
            //cout << tmp << "\n";
            cnt.push_back(tmp);
        }
    }
    ll tmp = 0;
    sort(cnt.begin(), cnt.end());
    for(auto e:cnt)
    {
        ans = ans * ((e - tmp)%mod);
        ans %= mod;
        tmp++;
        tmp %= mod;
    }
    cout << (ans+mod)%mod << "\n";
}
int main()
{
    T = 1;
    cin >> T;
    while (T--)
    {
        solve();
#ifdef DE_BUG
        cout << "TIME==" << (ll)(clock()) - tt << "\n";
        tt = (ll)clock();
#endif
    }
    return 0;
}

码力太弱哩，就嗯写，时间复杂度大概是nlogn

发表于 | 分类于

适用于mod数较小，而实际计算时需要的阶乘数较大时，只需预处理出mod数范围内的阶乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll Cal(ll u, ll d, ll i)
{
    if (d < u)//注意返回0
        return 0;
    if (d == 0||d==u)
        return 1;
    return ((jc[d][i] * jc_inv[u][i] % mod[i]) * jc_inv[d - u][i])%mod[i];
}
ll Lucas(ll u, ll d, ll i)
{
    if (d < u)//注意返回0
        return 0;
    if (d == 0||d==u)
        return 1;
    
    return ((Lucas(u / mod[i], d / mod[i], i) % mod[i]) * Cal(u % mod[i], d % mod[i], i)) % mod[i];
}

发表于 | 分类于

质数相关:

  1. 一个合数N，一定存在一个质数<=并整除N(用于大范围判断质数—求出的质数表)
  2. 一个合数N(<1e9)最多含有10种不同的质数因子(最小的10种质数相乘已超过1e9)，每种质数因子的指数不超过30(2^31>1e9)
  3. 求N!阶乘的质数分解形式，则统计1~N中各个质数的指数和，即(为何不是—其中一个已统计过)
  4. gcd(n,x)=gcd(n,n-x)，所以与n不互质的数成对出现—与n互质的数也成对出现(平均值为n/2)，故与n互质的数的和=
  5. gcd(a,b)=gcd(a,b-a),gcd(a,b,c)=gcd(a,b-a,c-b),当数目更多时同样成立，即多个数的gcd等价于其等差数组的gcd。如用线段树，区间修改数组，区间查询gcd，可用A数组记录数组初始值，用B数组维护差分数组，每次修改就转化成了两次单点修改，询问就转化成了求gcd(A[l],ask(l+1,r))
  6. 若,若a、n互质,则最小的正整数x为的约数(反证法—若不为约数,则,则r更小且满足条件)
  7. 求a%mod的值，而mod为非质数(如999911658)，可将mod分解成质数积，如999911658=2*3*4679*35617,分别计算a%2,a%3,a%4679,a%35617,这几个数互质,可得出一个线性同余方程组,运用CRT求解得到a%mod的值
  8. 原根、离散对数:给定质数p，若有一个数r满足gcd(r,p)=1,且次方刚好遍历了(即小于p且与p互质的所有数)，则称r是p的原根(dft/idft中，998244353的对应原根是3，其他模数的原根:https://blog.csdn.net/weixin_45697774/article/details/115732914)，而$$r^{e}=a(mod p)$$，则称e是以p为模，以r为底时，a所对应的离散对数。原根具有循环性，被应用于模意义下的fft。
  9. 伪素数:若，且n是合数，则称n是以a为底的伪素数，实践中可通过取多个底来判断n是否是素数(注意，存在合数，满足其是任意底的伪素数，故没法百分百确定)
  10. 若a+b=c,则a与b互质的充要条件是a和c也互质(故a+b=c且a与b互质的对数为phi[c])
  11. 计算阶乘相关时,可能出现分子,分母阶乘mod后均为0,实际结果不为0的情况(因为可能其因数相消将mod数p消去),此时要求出各个阶乘提取p后的结果—根据威尔逊定理((p-1)!==-1 mod p)

约数相关:

  1. 对任意的x<=i<=k/(k/x),k/i结果均相同
  2. 对任意的1<=i<=k,k/i最多有种结果(结合1可快速对k/i区间求和)

排列组合相关:

  1. i个数的错排总数:f[i]=(i-1)*(f[i-1]+f[i-2]),f[1]=0,f[0]=1(例题:https://www.acwing.com/problem/content/description/232/)

  2. 给定一个子串，求长度为m的母串，满足该子串是该母串的不连续子序列的总数：首先，明确如何在母串中规定出“唯一”子串的位置，假设子串为s，母串为p，s[i]与p[j]匹配，s[i+1]与p[k]匹配，则p[j+1]~p[k-1]中，不允许出现s[i](若出现，则该位置才是s[i]匹配位置)，通过该方法，我们可根据子串的字符在母串中的匹配位置(易知匹配位置不同，则母串必不同，故不会重合)，计算该匹配位置有多少种母串(根据上述限制)，而不同的匹配位置可使用dp[i][j]表示母串的第i个字符匹配子串的第j个字符表示，进而递推(来源:https://blog.nowcoder.net/n/aaf4e85f4c7c4c059de3c9c4f2ff91fc)

  6. 范德蒙德恒等式:,进而

  7. (01串中，枚举最后一个1的出现位置从r+1到n+1)