Znzryb's Blog
0%

Posted on Edited on

AC代码

回文数生成算法

前面搞半天没过，原来是pow的问题，pow只会返回int，导致int溢出了。

自己手搓了一个lpow就过了。

主要原理是经过观察

image

那么i位回文数就有9*10**((i-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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;
ll lpow(int a,int b) {
    return {b==0 ? 1: lpow(a,b-1)*a};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n==1) {
        cout<<0<<endl;
        return 0;
    }
    ll cnt=0;
    n-=1;
    bool isOdd=true;
    for(int i=1;i<=n;++i) {
        cnt+=9*lpow(10,(i-1)/2);
        if(cnt>=n) {
            cnt-=9*lpow(10,(i-1)/2);
            ll ten;ten= lpow(10,(i-1)/2);
            ten-=1;
            ll remain=ten+n-cnt;
            // 把remain存入ans数组
            while (remain) {
                ans.push_back(remain%10);   // 900 存入后是 0 0 9
                remain/=10;
            }
            if(i%2==0)
                isOdd=false;
            break;
        }
    }
    if(isOdd) {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=1;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }else {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=0;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }
}
// AC https://atcoder.jp/contests/abc363/submissions/59551360

心路历程（WA，TLE，MLE……）

虽然样例吧都过不了，但我百思不解为何WA，对拍程序生成的都没WA呀。

搞半天原来是pow的问题，pow只会返回int，导致int溢出了。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef unsigned long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n;
vector<ll> ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n==1) {
        cout<<0<<endl;
        return 0;
    }
    ll cnt=0;
    n-=1;
    bool isOdd=true;
    for(int i=1;i<=n;++i) {
        cnt+=9*pow(10,(i-1)/2);
        if(cnt>=n) {
            cnt-=9*pow(10,(i-1)/2);
            ll ten;ten= pow(10,(i-1)/2);
            ten-=1;
            ll remain=ten+n-cnt;
            // 把remain存入ans数组
            while (remain) {
                ans.push_back(remain%10);   // 900 存入后是 0 0 9
                remain/=10;
            }
            if(i%2==0)
                isOdd=false;
            break;
        }
    }
    if(isOdd) {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=1;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }else {
        for(int i=ans.size()-1;i>=0;--i)
            cout<<ans[i];
        for(int i=0;i<=ans.size()-1;++i)
            cout<<ans[i];
        cout<<endl;
    }
}

Posted on Edited on

AC代码

这题思路就是二分答案，二分可能的dis并检验

在复杂的就是check()函数必须在logn的级别，写的时候也比较复杂，这边简单阐述一下

1
2
3
ll l=lower_bound(A.begin(),A.end(),obl)-A.begin();
ll r=upper_bound(A.begin(),A.end(),obr)-A.begin();
// 这种方法找到的应该是该dis能包括的最多点数

这个代码是用来找到该dis可以包含的最多点数，详见下面图解

image

b=2 , dis=3，包含的最多点数就是-1，-1，5，5，即4个点，在图上很清楚，upper_bound-lower_bound就是4。

然后我们知道，最多点≥k是可能满足条件的（可能最少点符合条件），但最多点<k，那么一定不符合条件

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e5)+10;
ll n,q,rangeA;
vector<ll> A;

inline bool check(ll b,ll dis,ll k) {
    ll obl=b-dis,obr=b+dis;
    // 这种方法找到的应该是该dis能包括的最多点数
    ll l=lower_bound(A.begin(),A.end(),obl)-A.begin();
    ll r=upper_bound(A.begin(),A.end(),obr)-A.begin();
    if(r-l<k)      // 如果最多点数都<k 不用多说，铁不符合
        return false;
    return true;
}

inline ll bsearch(ll b,ll k) {
    ll l=0,r=rangeA;
    while (l<r) {
        ll mid= l+r >>1;
        if(check(b,mid,k))
            r=mid;
        else
            l=mid+1;
    }
    return l;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        ll a;
        cin>>a;
        A.push_back(a);
    }
    sort(A.begin(),A.end());
    for(int i=1;i<=q;i++) {
        ll b,k;
        cin>>b>>k;
        // 其实应该叫rangeDis最好，即二分查找的范围，不会超过b点与两端点之间的最大距离
        rangeA=max(abs(b-A[0]),abs(b-A[n-1]));
        cout<<bsearch(b,k)<<'\n';
    }
}
// AC https://atcoder.jp/contests/abc364/submissions/59526172

心路历程（WA，TLE，MLE……）

Posted on Edited on

AC代码

总体思路其实就是对于暴力dp的优化，其实很多时候一些做法就是对暴力做法的优化，所以就算知道时间复杂度较高，也可以写一写试试，看看能不能优化。

思路就是C[i][isE]里面存的是从i点以是否是偶数进入，最优的v。

当然，把之前的全部遍历一遍肯定超时了，所以maxC[2]就登场了。

直接存的就是之前最优的奇数偶数情况，直接调用就行，当然记得更新。

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,A[N];
ll C[N][3],maxC[2];     // C 即 cache
ll ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>A[i];
    }
    for(int i=n;i>=1;--i) {
        ll isE=0;
        ll currMax[2];      // 搞一个local变量，避免互相影响在更新时
        currMax[0]=maxC[0];currMax[1]=maxC[1];
        C[i][isE]=A[i]+currMax[1-isE];
        maxC[isE]=max(maxC[isE],C[i][isE]);
        isE=1;
        C[i][isE]=A[i]*2+currMax[1-isE];
        maxC[isE]=max(maxC[isE],C[i][isE]);
    }
    C[1][1]-=2*A[1];    // 1是even的情况是不可能的，所以要减去1的双倍经验
    cout<<max(C[1][1],C[1][0])<<endl;
}

// AC https://atcoder.jp/contests/abc369/submissions/59513452

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

https://www.bilibili.com/video/BV1SGsfeKExw/?vd_source=4350e5f2584d2f27c848b347ea11b675

image

树的重心是指以该点为根，其最大子树最小

AC代码

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
#include <iostream>
#include <vector>
#include <bitset>
#define ll long long
using namespace std;
const int maxn = static_cast<int>(1e5) + 7;
const long long MAXSON=1e18+7;
int n,a,b,l,core;
int c[maxn];
long long maxSonTree[maxn],minSon=MAXSON;
bitset</*100007*/ maxn> vis;
vector<pair<int,int> > g[maxn];
long long ans,sumN;
long long dfs(ll x,ll dis) {
    long long accSon=0,maxSon=0,treeSon;
    for(int i=0;i<g[x].size();i++) {
        ll son=g[x][i].first,len=g[x][i].second;
        if(!vis[son]) {
            vis[son]=true;
            treeSon=dfs(son,dis+len);
            accSon+=treeSon;
            maxSon=max(maxSon,treeSon);
        }
    }
    // 这个节点过来的这颗子树我们没法直接统计，但可以用总的通过相减得到
    maxSon = max(maxSon,sumN-accSon-c[x]);   //accSon>sumN-accSon-c[x] ? accSon:sumN-accSon-c[x];
    maxSonTree[x]=maxSon;
    return accSon+c[x];
}

void dfs2(ll x,ll dis) {   // 统计不方便值的
    ans+=(c[x]*dis);
    for(int i=0;i<g[x].size();i++) {
        ll son=g[x][i].first,len=g[x][i].second;
        if(!vis[son]) {
            vis[son]=true;
            dfs2(son,dis+len);
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) {
        cin>>c[i];
        sumN+=c[i];
    }
    for(int i=1;i<=n-1;i++) {
        cin>>a>>b>>l;
        // sumN+=l;
        g[a].push_back(make_pair(b,l));
        g[b].push_back(make_pair(a,l));
    }
    vis[1]=true;
    dfs(1,0);
    for(int i=1;i<=n;i++) {
        if(maxSonTree[i]<minSon)
            core=i,minSon=maxSonTree[i];
    }
    vis.reset(),ans=0;
    vis[core]=true;
    dfs2(core,0);
    cout<<ans<<endl;
    return 0;
}
// 30pts https://www.luogu.com.cn/record/178572159
// 40pts https://www.luogu.com.cn/record/178576100  删除了边权，但好像有点不对
// 遇到都read 0的情况大概率不是算法有问题，很有可能是某个min变量的初始值设小了
// 90pts https://www.luogu.com.cn/record/178578870 接近了

心路历程（WA，TLE，MLE……）

Posted on Edited on

AC代码

image

我判断这道题是一道树状dp问题

以上是树状dp问题的基本思路（说白了就是递归，dfs嘛，简单）

当然我这个做法和树上dp可能还是有点不同，但都是靠子树返回的值进行计算

注释应该足够清楚，主要思路就是通过下面的节点传递上来的可传播validS进行求解，然后用dfs2打了一下链状数据结构的补丁

AC

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,ans,recAns;    // recAns,即rectify ans
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要求解包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

void dfs2(ll x) {   // 把链状数据剪掉，即打补丁的dfs
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        if(g[fx].size()==2 && g[x].size()==2)
            recAns+=1;
        dfs2(fx);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vis[1]=true;
    dfs(1);
    vis.reset();
    vis[1]=true;
    dfs2(1);
    ans-=recAns;
    cout<<ans<<endl;
}
// AC https://atcoder.jp/contests/abc378/submissions/59465360

心路历程（WA，TLE，MLE……）

没过样例，主要问题在这里

degree==2的点也会阻隔validS传播

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return res+1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}

这个代码样例过了，但是全错

主要问题在于输入链状数据，答案一定为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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>

using namespace std;
typedef long long ll;
const ll N = static_cast<ll>(2e5)+10;
vector<ll> g[N];
ll n,dp[N],ans;
bitset<N> vis;

// dp最重要的就是分解问题，一整颗树的求解不会，小子树的求解会不会？拼起来会不会？都会，那树上dp也就好做了
ll dfs(ll x/*,ll validS*/) {    // validS即valid start的简称，即合法的开始节点数
    // 我发现validS不需要向下传递，因为我们的求解按照遍历序，下面的点只要包含自己的子树就行，
    // res 表示返回值（返回的）
    ll res=0,forAns=0;      // forAns 是为了degree==3的点搞出来的
    for(int i=0;i<g[x].size();i++) {
        ll fx=g[x][i];
        if(vis[fx])
            continue;
        vis[fx]=true;
        ll acc=dfs(fx);
        if(g[x].size()==3)  // 只有degree为3的点需要考虑包含这点的环数量
            forAns+=res*acc;   // 每一个之前的合法start点都可以与acc结合，那不就是res*acc种
        res+=acc;
        // 无需回退 有一些dfs需要回退是因为怕之前的探索路径阻碍到现在的，树因为没有环，不需要担心这个问题
        // if(g[fx].size()>3 || g[fx].size()<=1)
        //     res+=dfs(g[fx][i]/*,0*/);       // 不符合validS传播条件的点，阻断传播
        // else if(g[fx].size()==3)
        //     res+=dfs(g[fx][i]/*,validS*/);      // g[fx].size()==3，degree为3，可正常传播
        // else if(g[fx].size()==2)
        //     res+=dfs(g[fx][i]/*,validS+1*/);
    }
    if(g[x].size()==2) {
        ans+=res;
        return 1;
    }
    if(g[x].size()==3) {
        ans+=forAns;
        return res;
    }
    return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;i++) {
        ll u, v ;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // for(int i=1;i<=n;i++) {
    //     dp[i]=-1;
    // }
    for(int i=1;i<=n;i++) {     // 防止图不联通
        // // 我凭感觉应该是只能从degree为1的点进入，即只连了一条边点
        // if(g[i].size()>1)
        //     continue;
        if(vis[i])
            continue;
        vis[i]=true;
        dfs(i);
    }
    cout<<ans<<endl;
}