CFhM xjb training 题解

发表于 | 分类于 | | 阅读次数:

A-Number Busters-推公式

  • 当b<xb<x时，aa和cc都会减小，c−ac - a不会改变，所以只有在b≥xb \geq x的时候，才会使aa和cc之间的距离缩短，所以我们知道b≥xb \geq x这个状态共出现c−ac - a秒。
  • 再来看b < x​的时间，假设有k​秒，且易知使c = a​这个临界点出现的状态必然是b \geq x​，此时（更新之后）b​的值为b - x * (c - a) + k * (w - x)​，那么这个值还原回去（加上x​）必须大于等于x​。
  • 由此得出方程b−x∗(c−a)+k∗(w−x)+x≥xb - x * (c - a) + k * (w - x) + x \geq x
  • 解出kk，再加上b≥xb \geq x的时间c−ac - a，就是最终的答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    ll a, b, w, x, c;
    scan(a, b, w); scan(x, c);
    ll ans = 0LL;
    if(c > a) ans = ceil(1.0 * ((c - a) * x - b) / (w - x)) + c - a;
    dbg(ans);
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

B-ZYB loves Xor I-分治

  • 这里的lowbit(x)lowbit(x)的定义和我们以前知道的那个一样
  • 网上的题解都是字典树，然而学艺不精
  • 刘庆晖老师教导的分治的思维，让我看到了希望
  • 对于一个数组aa，我们考虑它的最低位是否为1，可以分为两个集合，这两个集合中任意两个数做异或的结果的lowbitlowbit，都是1。
  • 对于第一个集合，由于最低位相同（都是1），那么考虑第二位（次低位），按照上面的描述再次分为两个集合，那么这两个集合中任意两个数的异或的lowbitlowbit都是2。
  • 对于第二个集合同理。
  • 之后对于再次划分的集合我们发现依然可以这样分治下去。
  • wow~
  • 最后我们构造的就是一棵2n−12^n - 1个节点的解答树
  • 复杂度是O(nlogn∗T)O(nlogn * T)
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
void gao(vi &vec, int pos, ll &ans) {
    vi vec1, vec2;
    for(auto v : vec) {
        if(v & (1 << pos)) vec1.pb(v);
        else vec2.pb(v);
    }
    ans += (ll)(1LL << pos) * vec1.size() * vec2.size() % MOD;
    if(pos >= 28) return;
    if(vec1.size() > 0) gao(vec1, pos + 1, ans);   //剪枝很重要
    if(vec2.size() > 0) gao(vec2, pos + 1, ans);
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    int T; scan(T);
    rep(i, 0, T)
    {
        vi vec;
        int n, x; scan(n);
        while(n--) {
            scan(x);
            vec.pb(x);
        }
        ll ans = 0LL;
        gao(vec, 0, ans);
        ans = ans * 2LL % MOD;
        printf("Case #%d: %lld\n", i + 1, ans);
    }
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

C-Wavy numbers-Q神代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int MAXQ=10000000;
const int MAXL=14;
int vis[MAXQ],num[MAXL];
int change(int t)
{
    int now=0;
    while(t)
    {
        num[now++]=t%10;
        t/=10;
    }
    return now;
}
unordered_map<ll,int>mp[2][10];
void solve_right(ll n,ll &k)
{
    for(int i=1;i<MAXQ;i++)
    {
        int t=change(i),ok=1;
        if(t==2)ok&=(num[0]!=num[1]);
        for(int j=1;j<t-1;j++)
            ok&=((num[j]>num[j-1] && num[j]>num[j+1])
               ||(num[j]<num[j-1] && num[j]<num[j+1]));
        if(!ok)continue;
        vis[i]=1;
        k-=(i%n==0);
        if(k==0)
        {
            printf("%d",i);
            exit(0);
        }
        if(t==6 && num[t-1]>num[t-2])mp[0][0][i%n]++;
        else if(t==7)mp[num[t-1]>num[t-2]][num[t-1]][i%n]++;
    }
}
void get_res(ll n,ll &k,ll Mod,int lef)
{
    int len=7;
    while(lef)
    {
        num[len++]=lef%10;
        lef/=10;
    }
    for(int i=1;i<MAXQ;i++)
    {
        if(!vis[i])continue;
        int t=change(i),ok=1;
        while(t<7)num[t++]=0;
        t=len;
        for(int j=1;j<t-1;j++)
            ok&=((num[j]>num[j-1] && num[j]>num[j+1])
               ||(num[j]<num[j-1] && num[j]<num[j+1]));
        if(!ok)continue;
        k-=(i%n==Mod);
        if(k==0)
        {
            printf("%07d",i);
            exit(0);
        }
    }
}
void solve_left(ll n,ll &k)
{
    for(int i=1;i<MAXQ;i++)
    {
        if(!vis[i])continue;
        int t=change(i),ok=1;
        if(t==2)ok&=(num[0]!=num[1]);
        for(int j=1;j<t-1;j++)
            ok&=((num[j]>num[j-1] && num[j]>num[j+1])
               ||(num[j]<num[j-1] && num[j]<num[j+1]));
        if(!ok)continue;
        ll m=(n-1LL*i*MAXQ%n)%n,cnt=0;
        if(t==1)
        {
            for(int j=0;j<num[0];j++)
                if(mp[0][j].find(m)!=mp[0][j].end())
                    cnt+=mp[0][j][m];
            for(int j=num[0]+1;j<10;j++)
                if(mp[1][j].find(m)!=mp[1][j].end())
                    cnt+=mp[1][j][m];
        }
        else
        {
            int go=(num[1]>num[0]);
            if(go==0)for(int j=0;j<num[0];j++)
                if(mp[0][j].find(m)!=mp[0][j].end())
                    cnt+=mp[0][j][m];
            if(go==1)for(int j=num[0]+1;j<10;j++)
                if(mp[1][j].find(m)!=mp[1][j].end())
                    cnt+=mp[1][j][m];
        }
        if(k<=cnt)
        {
            printf("%d",i);
            get_res(n,k,m,i);
        }
        else k-=cnt;
    }
}
int main()
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    solve_right(n,k);
    solve_left(n,k);
    return 0*printf("-1");
}

D-Bear and Floodlight-计算几何

  • 只有20盏灯，所以可以考虑用状压dp，dp[i]dp[i]表示ii代表的状态（1表示亮）能走的最远距离
  • 转移就是枚举剩下的未亮的灯，点亮后能走的距离。
  • 对于状态dp[i]dp[i]点亮灯jj之后的状态分两种情况：
    • 由dp[i]dp[i]的终点开始向rr照亮θj\theta_j的范围，那么有dp[i∣(1<<j)]=(arctan((dp[i]−xj)/yj)+θj)∗yj+xj−ldp[i | (1 << j)] = (arctan((dp[i] - x_j) / y_j) + \theta_j) * y_j + x_j - l
    • 若该角度超过r，则取r−lr - l
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
double l, r;
struct point {
    double x, y, ang;
    point() {}
    point(double _x, double _y, double _ang) {
        x = _x - l;
        y = fabs(_y);
        ang = _ang * pi / 180.0;
    }
}p[maxn];
double dp[maxn];
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    int n; scan(n); scan(l, r);
    r -= l;
    rep(i, 0, n) {
        double x, y, ang;
        scan(x, y, ang);
        p[i] = point(x, y, ang);
    }
    rep(i, 0, (1 << n)) {
        rep(j, 0, n) {
            if((i & (1 << j)) == 0) {
                double tmp = atan((r - p[j].x) / p[j].y);
                tmp = min(tmp, atan((dp[i] - p[j].x) / p[j].y) + p[j].ang);
                dp[i | (1 << j)] = max(dp[i | (1 << j)], p[j].x + p[j].y * tan(tmp));
            }
        }
    }
    printf("%.9f\n", dp[(1 << n) - 1]);
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

E-Subway Innovation-前缀和优化+数学推导

  • 如果这nn个点是按照xx坐标排好序的，那么我们很容易知道，两两距离之和最短的kk个点一定是连续的（反证一下即可）
  • 首先用前缀和处理一下xx坐标的和，即sum[i]sum[i]表示前ii个点的xx坐标之和
  • 令f(i)f(i)表示从ii开始的kk个点两两之间的距离之和，我们先求出f(0)f(0)
  • 添加辅助函数h(i)h(i)表示前ii个点两两间的距离之和，有h(i)=h(i−1)+xi∗i−sum[i−1]h(i) = h(i - 1) + x_i * i - sum[i - 1](ii从00开始)
  • 我们令f(0)=h(k−1)f(0) = h(k - 1)
  • 接下来推导ff的转移关系，可以看出f(i)f(i)到f(i−1)f(i - 1)，多出了xi+k−1x_{i + k - 1}到xi...xi+k−2x_i...x_{i + k - 2}的距离，减少了xi−1x_{i - 1}到xi...xi+k−2x_i...x_{i + k - 2}的距离
  • f(i)=f(i−1)−(sum[i+k−2]−sum[i−1]−xi−1∗(k−1))+xi+k−2∗k−sum[i+k−1]+sum[i−1]f(i) = f(i - 1)-(sum[i + k - 2] - sum[i - 1] - x_{i - 1} * (k - 1)) + x_{i + k - 2} * k - sum[i + k - 1] + sum[i - 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
struct point {
    int id;
    ll x;
    bool operator<(const point &b) const {
        return x < b.x;
    }
}p[maxn];
ll sum[maxn], dp[maxn];
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    int n, k; scan(n);
    rep(i, 0, n) {
        scan(p[i].x);
        p[i].id = i;
    }
    sort(p, p + n);
    sum[0] = p[0].x;
    rep(i, 1, n) sum[i] = sum[i - 1] + p[i].x;
    scan(k);
    rep(i, 1, k) dp[i] = dp[i - 1] + p[i].x * i - sum[i - 1];
    dp[0] = dp[k - 1];
    ll ans = dp[0], l = 0;
    rep(i, 1, n - k + 1) {
        dp[i] = dp[i - 1] - (sum[i + k - 2] - sum[i - 1] - p[i - 1].x * (k - 1)) + (p[i + k - 1].x * (k - 1) - (sum[i + k - 2] - sum[i - 1]));
        if(ans > dp[i]) {
            ans = dp[i];
            l = i;
        }
    }
    rep(i, l, l + k) printf("%d%c", p[i].id + 1, i == l + k - 1 ? '\n' : ' ');
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

F-Dexterina’s Lab-矩阵优化+概率dp

  • dp[i][j]=∑k=0127dp[i−1][k]∗p[j∧k]dp[i][j] = \displaystyle{\sum_{k = 0}^{127}dp[i-1][k]*p[j\wedge k]}
  • (dp[i][0]dp[i][1]...dp[i][127])=(p[0][0]p[0][1]...p[0][127]p[1][0]p[1][1]...p[1][127]..................p[127][0]p[127][1]...p[127][127])(dp[i−1][0]dp[i−1][1]...dp[i−1][127])\begin{pmatrix} dp[i][0] \\ dp[i][1]\\.\\.\\.\\dp[i][127]\end{pmatrix} = \begin{pmatrix}p[0][0] &&p[0][1]&&...&&p[0][127]\\p[1][0] &&p[1][1]&&...&&p[1][127]\\.&&.&&...&&.\\.&&.&&...&&.\\.&&.&&...&&.\\p[127][0] &&p[127][1]&&...&&p[127][127]\\\end{pmatrix}\begin{pmatrix} dp[i-1][0] \\ dp[i-1][1]\\.\\.\\.\\dp[i-1][127]\end{pmatrix}
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
int n, K;
struct Matrix{
	double x[128][128];
}A,B,ans;
Matrix operator * (const Matrix &k1, const Matrix &k2) {
	mem(B.x, 0);
	rep(i, 0, n + 1)
		rep(j, 0, n + 1)
			rep(k, 0, n + 1)
				B.x[i][j] += k1.x[i][k] * k2.x[k][j];
	return B;
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    scan(K, n);
	rep(i, 0, n + 1) {
		double k1; scan(k1);
		rep(j, 0, 128) A.x[j][i^j]=k1;
	}
	n = 127;
	ans=A; K--;
	while (K) {
		if (K & 1) ans = ans * A; A = A * A; K >>= 1;
	}
	printf("%.11lf\n",1 - ans.x[0][0]);
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

G-Count Good Substrings-机智

  • 根据描述最后的串一定是abababa这个样子
  • 若是回文串那么首尾字母一定相同
  • 偶数长度的回文串的来源
    • 一个奇数位置的a和一个偶数位置的a之间
    • 一个奇数位置的b和一个偶数位置的b之间
  • 奇数长度的回文串来源
    • 任意位置的奇偶性相同的两个a或两个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
ll gao(ll n) { return n * (n - 1) / 2LL; }
char s[maxn];
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    scan(s);
    int n = strlen(s);
    ll oa = 0LL, ea = 0LL, ob = 0LL, eb = 0LL;
    rep(i, 0, n) {
        if(i & 1) {
            if(s[i] == 'a') oa++;
            else ob++;
        } else {
            if(s[i] == 'a') ea++;
            else eb++;
        }
    }
    dbg(oa * ea + ob * eb);
    dbg(gao(oa) + gao(ob) + gao(ea) + gao(eb) + n);
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

H-Divisors-模拟

  • 先O(x)O(\sqrt x )预处理出xx的所有因子并且排序，再根据题目描述dfs模拟一下就行
  • 注意对因子去重什么的，免得平方根因子不好搞
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
int cnt = 0, mnt = 0;
ll fac[maxn];
void gao(ll x, ll k) {
    if(cnt > 99999) return;
    if(x == 1LL || k == 0LL) { dbg(x); cnt++; return; }
    rep(i, 0, mnt) {
        if(x < fac[i]) break;
        if(x % fac[i] == 0) gao(fac[i], k - 1);
    }
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    ll x, k; scan(x, k);
    for(ll i = 1LL; i * i <= x; i++) {
        if(x % i == 0) {
            fac[mnt++] = i;
            fac[mnt++] = x / i;
        } 
    }
    mnt = unique(fac, fac + mnt) - fac;
    sort(fac, fac + mnt);
    gao(x, k);
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

I-Painting Fence-分治

  • 一个问题的定义，就是找到这个区间中的最短板，把这个长度以下部分横着刷，剩下的以他为中心分为两个区间，每个区间又是相同的子问题
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
int a[maxn];
int gao(int l, int r, int minn) {
    if(l > r) return 0;
    if(l == r) return a[l] > minn;
    int m = min_element(a + l, a + r + 1) - a;
    return min(r - l + 1, gao(l, m - 1, a[m]) + gao(m + 1, r, a[m]) + a[m] - minn);
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        long _begin_time = clock();
    #endif
    
    int n; scan(n);
    rep(i, 1, n + 1) scan(a[i]);
    dbg(gao(1, n, 0));
    
    #ifndef ONLINE_JUDGE
        long _end_time = clock();
        printf("time = %ld ms\n", _end_time - _begin_time);
    #endif
    
    return 0;
}

头文件

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
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define MP(A, B) make_pair(A, B)
#define pb push_back
#define gcd __gcd
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i > b; i--)
typedef long long ll;
typedef unsigned long long ulls;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef map<pii, int> mpi;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const ll MOD = 998244353;
const double pi = acos(-1.0);
const double eps = 1e-6;
const int maxn = 1e6 + 5;
const int maxm = 1e6 + 5;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
inline int scan(int &a) { return scanf("%d", &a); }
inline int scan(int &a, int &b) { return scanf("%d%d", &a, &b); }
inline int scan(int &a, int &b, int &c) { return scanf("%d%d%d", &a, &b, &c); }
inline int scan(ll &a) { return scanf("%I64d", &a); }
inline int scan(ll &a, ll &b) { return scanf("%I64d%I64d", &a, &b); }
inline int scan(ll &a, ll &b, ll &c) { return scanf("%I64d%I64d%I64d", &a, &b, &c); }
inline int scan(double &a) { return scanf("%lf", &a); }
inline int scan(double &a, double &b) { return scanf("%lf%lf", &a, &b); }
inline int scan(double &a, double &b, double &c) { return scanf("%lf%lf%lf", &a, &b, &c); }
inline int scan(char &a) { return scanf("%c", &a); }
inline int scan(char *a) { return scanf("%s", a); }
template<class T> inline void mem(T &A, int x) { memset(A, x, sizeof(A)); }
template<class T0, class T1> inline void mem(T0 &A0, T1 &A1, int x) { mem(A0, x), mem(A1, x); }
template<class T0, class T1, class T2> inline void mem(T0 &A0, T1 &A1, T2 &A2, int x) { mem(A0, x), mem(A1, x), mem(A2, x); }
template<class T0, class T1, class T2, class T3> inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) { mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x); }
template<class T0, class T1, class T2, class T3, class T4> inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) { mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x); }
template<class T0, class T1, class T2, class T3, class T4, class T5> inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) { mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x), mem(A5, x); }
template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void mem(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) { mem(A0, x), mem(A1, x), mem(A2, x), mem(A3, x), mem(A4, x), mem(A5, x), mem(A6, x); }
template<class T> inline T min(T a, T b, T c) { return min(min(a, b), c); }
template<class T> inline T max(T a, T b, T c) { return max(max(a, b), c); }
template<class T> inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d)); }
template<class T> inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d)); }
template<class T> inline T min(T a, T b, T c, T d, T e) { return min(min(min(a,b),min(c,d)),e); }
template<class T> inline T max(T a, T b, T c, T d, T e) { return max(max(max(a,b),max(c,d)),e); }
template<class T> inline void dbg(T a[], int n) { rep(i, 0, n) cout << a[i] << (i == n - 1 ? "\n" : " ");}
template<class T> inline void dbg(T a) { cout << a << " "; }
template<class T> inline void dbg(T a[][maxn], int n, int m) { rep(i, 0, n) rep(j, 0, m) cout << a[i][j] << (j == m - 1 ? "\n" : " "); }
本博客收到的所有打赏均将用于博主女朋友的化妆品购买及养胖计划