# Codeforces Round #549（div1）简析

A 1800 数论

```const int maxn = 1e5 + 5;
ll n, k, a, b, aa, minn = INF, maxx = -1;
set<ll> bb;

ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}

int main() {
cin >> n >> k >> a >> b;
ll T = n * k;
rep(i, 0, n - 1) {
ll p = (ll)i * k + 1;
bb.insert((p + b) % T);
bb.insert((p - b + T) % T);
}
aa = (1 + a) % T;
for(set<ll>::iterator it = bb.begin(); it != bb.end(); it++) {
ll t = *it;
ll ans = T / gcd(T, (t - aa + T) % T);
minn = min(minn, ans);
maxx = max(maxx, ans);
}
cout << minn << " " << maxx << endl;
return 0;
}```

B 2300 倍增

1.先预处理出在循环中某数前面的数是谁。

2.读入a数列时贪心选取最晚的父亲。

3.链上倍增预处理二进制祖先。

4.对于每个位置，预处理第n-1个祖先位置最早要从哪里开始，技巧上再顺手与前一位的最早位置取max，尽量缩小区间。

5.查询已经可做。

```const int maxn = 2e5 + 5;
int n, m, q, permu[maxn], pre[maxn], a[maxn], f[maxn][25], late[maxn], L[maxn];

int Find(int pos, int n) {
irep(i, 20, 0)
if (n >= 1 << i) {
n -= 1 << i;
pos = f[pos][i];
}
return pos;
}

int main() {
scanf("%d%d%d", &n, &m, &q);

rep(i, 0, n - 1)
scanf("%d", &permu[i]);
rep(i, 0, n - 1)
pre[permu[i]] = permu[(i - 1 + n) % n];

rep(i, 1, m) {
scanf("%d", &a[i]);
f[i][0] = late[pre[a[i]]];
late[a[i]] = i;
}
rep(i, 1, 20)
rep(j, 1, m)
f[j][i] = f[f[j][i - 1]][i - 1];
rep(i, 1, m)
L[i] = max(Find(i, n - 1), L[i - 1]);

while (q--) {
int l, r;
scanf("%d %d", &l, &r);
printf("%d", L[r] >= l);
}

return 0;
}```

C 2800 凸包

```#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 5;
int n;
struct Point {
ll x, y;

Point(){}
Point(ll x, ll y):x(x), y(y) {}

friend ll operator * (const Point &a, const Point &b) {
return a.y * b.x - b.y * a.x;
}

friend Point operator - (const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
}

bool operator < (const Point &rhs) const {
if (x != rhs.x)    return x < rhs.x;
return y < rhs.y;
}
};

vector<Point> v, st;

cin >> n;

for (int i = 0; i < n; i++) {
ll x, y;
cin >> x >> y;
y = y - x * x;
v.push_back({x, y});
}
}

void convex() {
sort(v.begin(), v.end());//按坐标排序

for (int i = n - 1; ~i; --i)
v[i] = v[i] - v[0];

for (int i = 0; i < n; i++) {
int tot = st.size();
while (tot > 1 && (v[i] - st[tot - 2]) * (st[tot - 1] - st[tot - 2]) >= 0)    tot--, st.pop_back();
st.push_back(v[i]);
}
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

convex();

int ans = 0;
for (int i = 1; i < st.size(); i++)
if (st[i].x != st[i - 1].x)//x相同无法构成二次函数
ans++;
cout << ans << endl;

return 0;
}```

D 2700 dp

https://www.cnblogs.com/AlphaWA/p/10665100.html

```#include <cstdio>
#include <cstring>

const int maxn = 1e5 + 5;
char S[maxn];
__int64_t ans, dp[maxn][15];//以第i个位置、以rankj的数拓展出去的方案数

int main() {
scanf("%s", S + 1);
int len = strlen(S + 1);

for (int i = len; i; --i) {
int d = S[i] - '0';

for (int j = 0; j <= 10; ++j) {
dp[i][j] = 1;//自己独立成一个方案
if (i < len) {
int t = S[i + 1] - '0';
if (j > t) {//与后面联合,当前rank只会转移到更小的数字
dp[i][j] += dp[i + 1][(j * (j - 1) / 2 + t + 10) % 11];//事实上只有两位数的转移也可以直接打表
}
}
}

if (d)  ans += dp[i][d];//题目限制从1～9为起点
}

printf("%lld\n", ans);
return 0;
}```

E 3100 图论、交互

```#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

const int maxn = 1e5 + 5;
int n, m, used[maxn], indeg[maxn];
queue<int> Q;

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
}

function<void(int)> dfs = [&](int cur) {
if (used[cur])  return;
used[cur] = 1;
vector<int> tmp;
for (int son : adj[cur]) {
if (used[son] == 1) continue;
dfs(son);
tmp.push_back(son);
indeg[son]++;
}
used[cur] = 2;
};

for (int i = 1; i <= n; i++)    dfs(i);

for (int i = 1; i <= n; i++) {
if (!indeg[i]) {
Q.push(i);
}
}

while (Q.size() >= 2) {
int a = Q.front(); Q.pop();
int b = Q.front(); Q.pop();

cout << "? " << a << ' ' << b << '\n' << flush;

for (int i : adj[b]) {//delete b
if (!--indeg[i]) {
Q.push(i);
}
}
Q.push(a);
}

cout << "! " << Q.front() << endl;
return 0;
}```

0 条评论

• ### 水果Fruit（母函数） - HDU 2152

转眼到了收获的季节，由于有TT的专业指导，Lele获得了大丰收。特别是水果，Lele一共种了N种水果，有苹果，梨子，香蕉，西瓜……不但味道好吃，样子更是好看。 ...

• ### 力扣 526.优美的排序（next_permutation?)

链接：https://leetcode-cn.com/problems/beautiful-arrangement

• ### leetcode 周赛155 | 项目管理之拓扑排序算法

今天看了下leetcode周赛的题目，没怎么做，第四题是一道Hard题目，看了下题意感觉要用拓扑排序，但是这道题除了依赖关系，还有一个分组的变量，导致这道题处理...

• ### 程序员必须掌握的8大排序算法

分类： 1）插入排序（直接插入排序、希尔排序） 2）交换排序（冒泡排序、快速排序） 3）选择排序（直接选择排序、堆排序） 4）归并排序 5）分配排序（基数排序）...

• ### 桶排序

3. 桶排序        桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值（当然也可以装入若干个值），...

• ### Codeforces Round #621 (Div. 1 + Div. 2)（无比自闭的一夜）

菜到自闭自闭~~ 欲哭无泪~ 深夜一人伤悲~ 掉了~ rank– 明天要多刷水题，体验AC快感… 真几把自闭

• ### 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元，D,模拟，E,前缀和，F,LCS，H,Prim算法，I,胡搞，J,树状数组)

A-------------------------------------------------------------------------------...

• ### POJ Test for Job(DAG上拓扑排序)

题意是给了n个点，m条边(单向边)，然后每个点都有一个点权(存在负权)，问从入度为0的点开始到出度为0的点，最大的权值和为多少。

• ### 1751:分解因数

1751:分解因数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述给出一个正整数a，要求分解成若干个正整数的乘积，即a = ...