Znzryb's Blog
0%

Posted on Edited on

AC代码

不难发现，只要知道该点能够跳到的最远点，就能够顺利求出答案。

1
2
3
4
5
// upA[i]表示i位置之前（包括i位置）出现的最大的height。
// upj[i]表示i位置能跳到的最远位置
for(int i=1;i<=n;++i)
      cout<<upA[upj[i]]<<" ";
cout<<endl;

那问题就变成了怎么求 i 位置能跳到的最远位置

我们使用记忆化搜索

1
2
3
for(ll i=1;i<=n;++i) {
      upj[i]=max(upI[upA[i]-1],i);
}

upj[i]的初始化是指我们先给upj[i]赋上一个跳一次或者两次（一定往前跳）的值

1
2
3
4
5
6
7
ll dfs(ll x) {
    if(vis[x])
        return upj[x];
    vis[x]=true;
    upj[x]=dfs(upj[x]);
    return upj[x];
}

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e5)+10;
ll n,T,A[N],upI[N],upA[N],upj[N];   // upj is max idx you can jump to in this pos
bool vis[N];

ll dfs(ll x) {
    if(vis[x])
        return upj[x];
    vis[x]=true;
    upj[x]=dfs(upj[x]);
    return upj[x];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        for(int i=1;i<=n;++i)   // initialize
            upI[i]=0,vis[i]=false;
        for(int i=1;i<=n;++i) {
            cin>>A[i];
        }
        for(int i=1;i<=n;++i) {
            // upI[x] means the max index of x, in other words, farthest x's idx
            upI[A[i]]=i;
        }
        ll maxUpi=0;
        for(int i=1;i<=n;++i) {
            // 大的点肯定能跳到小的点最远的位置
            maxUpi=max(upI[i],maxUpi);
            upI[i]=maxUpi;
        }
        ll maxA=0;
        for(int i=1;i<=n;++i) {
            // upA[i]表示i位置之前（包括i位置）出现的最大的height。
            maxA=max(maxA,A[i]);
            upA[i]=maxA;
        }
        for(ll i=1;i<=n;++i) {
            upj[i]=max(upI[upA[i]-1],i);
        }
        for(int i=1;i<=n;++i) {
            if(vis[i])
                continue;
            upj[i]=dfs(i);
        }
        for(int i=1;i<=n;++i)
            cout<<upA[upj[i]]<<" ";
        cout<<endl;
    }
    return 0;
}
// AC https://codeforces.com/contest/2031/submission/291771622

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

Posted on Edited on

AC代码

就是要再深想一步，其实也没有那么复杂
27’s situation → odd num ≥ 27

1
2
ans[1]=1,ans[10]=1,ans[26]=1;
ans[27]=2,ans[23]=2;

就是这样构建27的情况

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

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,ans[N];
bool perf[N];   // is perfect square ?
vector<ll> P;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    for(int i=1;i<=N;++i) {
        if(i*i>N)
            break;
        perf[i*i]=true;
        P.push_back(i*i);
    }
    for(int i=0;i<P.size();++i) {

    }
    while (T--) {
        cin>>n;
        for(int i=1;i<=n;++i)
            ans[i]=0;
        if(n==3 || n==1) {
            cout<<-1<<endl;
            continue;
        }
        if(n%2==0) {
            for(int i=1;i<=n/2;++i)
                cout<<i<<" "<<i<<" ";
            cout<<endl;
            continue;
        }else if(n<=25){
            cout<<-1<<endl;
            continue;
        }
        // 27's situation -> odd num >= 27
        ans[1]=1,ans[10]=1,ans[26]=1;
        ans[27]=2,ans[23]=2;
        ll kind=3,cnt=0;
        for(int i=1;i<=n;++i) {
            if(ans[i])
                continue;
            if(cnt%2==0)
                ++kind;
            ans[i]=kind;
            ++cnt;
        }
        for(int i=1;i<=n;++i)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
}
// AC https://codeforces.com/contest/2031/submission/291725770

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

赛时我在想我要找到全部的完全平方数相加等于另一个完全平方数的这种，但后来发现根本不需要

详见上面

Posted on Edited on

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>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N= 1010;
ll n,sum[N],ans[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n-1;++i) {
        cout<<"? 1 "<<n-i+1<<endl;
        cin>>sum[n-i+1];
    }
    cout<<"? 2 3"<<endl;
    ll temp;
    cin>>temp;
    for(int i=n;i>=3;--i) {
        ans[i]=sum[i]-sum[i-1];
    }
    ans[1]=sum[3]-temp;
    ans[2]=sum[2]-ans[1];
    cout<<"! ";
    for(int i=1;i<=n;++i) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
// AC https://codeforces.com/problemset/submission/1425/291200157

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

Posted on Edited on

AC代码

加了一段这个// 两个点都已经已知，就不需要继续找了

然后找的次数少了，就AC了。

1
2
if(vis[a] && vis[b])    // 两个点都已经已知，就不需要继续找了
        return;

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

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T;
bitset<N> vis;
bool ans[N][N];


void solve(ll a,ll b) {
    if(ans[a][b])
        return;
    if(vis[a] && vis[b])    // 两个点都已经已知，就不需要继续找了
        return;
    cout<<"? "<<a<<" "<<b<<endl;
    ll ret;
    cin>>ret;
    if(ret<0)   // 如果读入-1 需立即终止程
        exit(0);
    if(ret==a) {
        vis[a]=true,vis[b]=true;
        ans[a][b]=true;
    }else {
        solve(a,ret);
        solve(ret,b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vis.reset();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                ans[i][j]=false;
        for(int i=2;i<=n;++i) {
            if(vis[i])
                continue;
            solve(1,i);
        }
        cout<<"! ";
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                if(ans[i][j])
                    cout<<i<<" "<<j<<" ";
            }
        }
        cout<<endl;
    }
}
// WA on test 5 https://codeforces.com/contest/2001/submission/291518387
// AC https://codeforces.com/contest/2001/submission/291568701

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

WA on test 5

Probably, the solution is executed with error ‘out of bounds’ on the line 24

我也不太理解为什么会越界数组，除非他给我输入-1

image

好像还真是。

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

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(1e3)+10;
ll n,T;
bitset<N> vis;
bool ans[N][N];


void solve(ll a,ll b) {
    if(ans[a][b])
        return;
    cout<<"? "<<a<<" "<<b<<endl;
    ll ret;
    cin>>ret;
    if(ret==a) {
        vis[a]=true,vis[b]=true;
        ans[a][b]=true;
    }else {
        solve(a,ret);
        solve(ret,b);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n;
        vis.reset();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                ans[i][j]=false;
        for(int i=2;i<=n;++i) {
            if(vis[i])
                continue;
            solve(1,i);
        }
        cout<<"! ";
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                if(ans[i][j])
                    cout<<i<<" "<<j<<" ";
            }
        }
        cout<<endl;
    }
}
// WA on test 5 https://codeforces.com/contest/2001/submission/291518387