A. Shape Perimeter
难度(个人感觉)★☆☆☆☆
思考:
考虑平移
Code:
for(int i = 0; i < N; i++){
std::cin >> dx >> dy;
if(i){
cnt_dx += dx; cnt_dy += dy;
}
}
ans = (m + cnt_dx + m + cnt_dy) * 2;
B. Find the Permutation
难度(个人感觉)★☆☆☆☆
思考:
可以直接拓扑排序,但是这只是 \(b\) 题,可以用比较简单的方法
做法
任意几个点的相对关系是确定的。那么我们每次插入一个点即可。
Code:
bool ok(int x, int y){//能不能把 x 放在 y 左边
if(x < y){
return a[x][y] == '1';
} else{
return a[x][y] == '0';
}
}
std::vector<int> ans;
for(int x = 0; x < N; x++){
auto p = ans.begin();
while(p != ans.end() && !ok(x, *p)){ p++; }
ans.insert(p, x);
}
C. Palindromic Subsequences
难度(个人感觉)★☆☆☆☆
思考:
所有数不同可以做到 \(n\)。只要再大一点就行,考虑使用乘法原理。
做法
前 \(n - 2\) 个是是 \(1\),\(2\),\(3\),... \(n - 2\)。之后是两个 \(1\)。
那么最左边的 \(1\) 必须和最右边的其中一个匹配。
枚举中间数,有 \(2(n - 3)\) 种情形。实际上 \(1\; 1\; 1\) 也是一种方案。因此是\(2(n - 3) + 1\)
当 \(n \ge 6\),$2(n - 3) + 1 = 2n - 5 > n $
Code:
std::vector<int> ans;
for(int i = 0; i < N - 2; i++){
ans.push_back(i);
}
ans.push_back(0);
ans.push_back(0);
D. Unique Median
难度(个人感觉)★★★☆☆
思考:
考虑枚举位置或值。枚举位置不太有规律,因此通过值计数。
对于偶数,可行的情况是两个中位数相同。对一个区间,中位数可能有很多,很难找到两个特殊位置的。考虑不可行的情况。
做法:
用区间个数减去不可行的情况,不可行即长度偶数且两个中位数不同。可以枚举较大的那个,记作 \(M\)。若一个区间里有多个 \(M\),不妨枚举最后一个。
当且仅当 区间中比\(M\)小的数个数和大于等于\(M\)的数个数相等时,不合法。具体实现时,前者贡献 \(-1\),后者贡献 \(+1\),那么 \(pre[l-1] = pre[r]\) 。
限制是,由于它是区间最后一个 \(M\),设它的位置 \(p\),那么 \([p + 1, r]\) 里没有 \(M\)。
Code:
i64 ans, dec;
int pre[MAXN + 1];
int cnt_l[MAXN * 2 + 1], cnt_r[MAXN * 2 + 1];
void work(int x){
pre[0] = 0;
std::vector<int> pos{-1};
for(int i = 0; i < N; i++){
pre[i + 1] = pre[i] + (a[i] < x ? -1 : 1);
if(a[i] == x) pos.push_back(i);
}
pos.push_back(N);
memset(cnt_l + MAXN - N, 0, sizeof(int) * (N * 2 + 1));
memset(cnt_r + MAXN - N, 0, sizeof(int) * (N * 2 + 1));
for(int i = 1; i < (int)pos.size() - 1; i++){
int min = INF, max = 0;
for(int p = pos[i - 1] + 1; p <= pos[i]; p++){ cnt_l[pre[p] + MAXN]++; }
for(int p = pos[i] + 1; p <= pos[i + 1]; p++){ cnt_r[pre[p] + MAXN]++; chmin(min, pre[p] + MAXN); chmax(max, pre[p] + MAXN); }
for(int k = min; k <= max; k++){
dec += 1ll * cnt_l[k] * cnt_r[k];
}
memset(cnt_r + min, 0, (max - min + 1) * sizeof(int));
}
}
void get(){
ans = 1ll * N * (N + 1) / 2;
dec = 0;
for(int x = 0; x < 10; x++) work(x);
}
void output(){
std::cout << ans - dec << "\n";
}