跳转至

ATC & CF 选做(22Sep,22Oct)

九、十月 CF 丢人做题记录ψ(｀∇´)ψ

ZJK 给的建议是多想，也许之后会从 ARC104 开始倒着做，锻炼思维，或者说让自己平复心态多去想。

而且 OI 和 CF 不一样，OI 不是速度竞赛，所以 OI 和 CF 的策略往往是不一致的，CF 这种紧张的氛围容易让人不清醒，而且 CF 没有部分分。

HFY 说可以把题拿出来，定 4h/3h 直接当模拟赛做，习惯那种感觉也防止走神。

Edu1 - Vpψ(｀∇´)ψ

CF598C - Nearest vectorsψ(｀∇´)ψ

极角排序模板，沙卵卡精度题。

暂时咕掉了。

Edu2 - Vpψ(｀∇´)ψ

CF600E Lomsat gelralψ(｀∇´)ψ

神秘线段树合并 / dsu on tree 题。

暂时咕掉了。

Global Round 23ψ(｀∇´)ψ

评价是下饭 + 小丑。

想了大半天 E1 不会。

CF1746D Path on the Treeψ(｀∇´)ψ

有意思的树形 dp。

暂时咕掉了。

ABC274ψ(｀∇´)ψ

Dψ(｀∇´)ψ

你在坐标系的原点，你要去 \((x,y)\) （正负 \(1e4\) 级别），你有 \(n\) 次机会走格子。

第 \(i\) 次走格子必须走 \(a_i\) 步，且和上一次走的路径呈 90°角，初始必须向右走 \(a_1\) 步。

问是否可能走到 \((x,y)\)。

\(2\le n \le 10^3, 1\le a_i \le 10\)

首先按奇偶性分组，这个比较显然。

所以问题主要就是看能否用 \(+a_1, ±a_3, ±a_5\) 凑出 \(x\)，能否用 \(±a_2,±a_4,±a_6\) 凑出来 \(y\)。

这个就是经典的背包模型了（硬币凑整的问题），但现在的主要问题是负数咋搞。

发现其实可以挪一下位，把负数往前挪，挪到 \(0 \sim 1e4\)，然后正数挪到 \(1e4 \sim 2e4\)。

然后实现应该比较简单， Bool DP 即可，这里用到了赛时的一血 tabr 代码里的一个小技巧，直接拿 bitset 位移做 dp。

Code 
 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
// author : black_trees

#include <cmath>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
using i64 = long long;

const int si = 1e4 + 10;

int n, x, y, a[si];
std::bitset<20000>dp;
std::vector<int> b, c;

bool solve(std::vector<int> v, int target) {
    dp.reset(); dp[10000] = true;
    for(auto i : v) dp = (dp << i) | (dp >> i);
    return dp[target + 10000];
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit bitor cin.badbit);

    cin >> n >> x >> y;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 1; i < n; ++i)
        if(i % 2 == 0) b.push_back(a[i]);
        else c.push_back(a[i]);
    x -= a[0], x = abs(x), y = abs(y);
    if(solve(b, x) && solve(c, y)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

// thanks tabr : https://atcoder.jp/contests/abc274/submissions/35864370

Eψ(｀∇´)ψ

给你一个平面直角坐标系，平面上有 \(n\) 个 town 和 \(m\) 个 chest，坐标分别为 \((x_i,y_i),(p_i,q_i)\)（正负 \(1e9\) 级别的整点）。

你必须访问所有的 \(n\) 个town，并回到你的起点 \(1\) 号 town，你不必走过所有 chest，但是每个 chest 里有一个加速器，拿到后会让你的速度乘二，你的初始速度是 \(1\)，请问走完全程的最短时间是多少？

\(1 \le n \le 12, 0 \le m \le 5\)，没有 town 和 chest 处于原点。

板板状压 dp，设 \(dp(msk,sta,i)\) 表示当前 town 的状态为 \(msk\)，chest 的状态为 \(sta\)，当前正在第 \(i\) 个点（可能是 chest，也可能是 town）的最短时间。

然后枚举上一个位置从哪里来的，最后再对所有合法状态 （\(msk = 2^n - 1\)）算一下它到原点此时所需的速度，取 min 即可，初始化 \(dp(1,0,1) = 0\)，其余 \(\infty\)。

Code 不写了，直接贺贺 std。

std 
 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
#include<stdio.h>
#include<math.h>
#define bit(x,i)(((x)>>(i))&1)

double x[20],y[20];
double dp[17][1<<17];
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n+m;i++)scanf("%lf%lf",x+i,y+i);
    for(int i=0;i<n+m;i++)for(int s=0;s<1<<(n+m);s++)dp[i][s]=1e18;
    for(int i=0;i<n+m;i++)dp[i][1<<i]=hypot(x[i],y[i]);

    for(int s=1;s<1<<(n+m);s++){
        double coef=pow(0.5,__builtin_popcount(s>>n));
        for(int i=0;i<n+m;i++)if(bit(s,i)){
            for(int j=0;j<n+m;j++)if(!bit(s,j)){
                dp[j][s^(1<<j)]=fmin(dp[j][s^(1<<j)],dp[i][s]+hypot(x[i]-x[j],y[i]-y[j])*coef);
            }
        }
    }

    double ans=1e18;
    for(int i=0;i<n+m;i++)for(int s=(1<<n)-1;s<1<<(n+m);s+=1<<n)ans=fmin(ans,dp[i][s]+hypot(x[i],y[i])*pow(0.5,__builtin_popcount(s>>n)));
    printf("%.10f\n",ans);
}

CF Round #829ψ(｀∇´)ψ

下午，连着两场 CF，小溪了。

暂时咕掉了。

CF Round #830ψ(｀∇´)ψ

没打，暂时咕掉了。

最后更新: May 9, 2023