Znzryb's Blog
0%

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

Posted on Edited on

AC代码

image

规律大概就是这么个规律

1
2
3
for(int i=1;i<=n;++i) {
        res[i]=i*(s[i]-'0')+res[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
45
46
47
48
49
50
51
52
53
54
55
#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)+100;
ll res[N],ans[N];
ll n;
char s[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>s[i];
    }
    for(int i=1;i<=n;++i) {
        res[i]=i*(s[i]-'0')+res[i-1];
    }
    //  ans和res顺序是反的
    for(int i=1;i<=n;++i) {
        ans[i]+=res[n+1-i];
        ll temp=ans[i];
        ans[i]=temp%10;
        ll cnt=0;
        while (temp) {
            ++cnt;
            temp/=10;
            ans[i+cnt]+=temp%10;
        }

    }
    bool isPrint=false;
    for(int i=N-1;i>=1;--i) {
        if(ans[i]!=0)
            isPrint=true;
        if(isPrint) {
            cout<<ans[i];
        }
    }
}
// AC https://atcoder.jp/contests/abc379/submissions/59699706

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