Znzryb's Blog
0%

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……）

Posted on Edited on

AC代码

本来不是想做这题的，但想不到赛氪竟然连补题都不支持，离谱。

这题和赛氪的题还不完全一样，两者螺旋矩阵的顺序有稍许不同

然后比赛的时候不要光想，笔也要动起来，比赛完后我造了个数据6 3 3，结果输出了38，就发现问题了，但赛中没造6的数据。只能说不要停下来呀！！！

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 <vector>
#include <deque>
#include <cstdio>
#include <cctype>

// https://oj.saikr.com/problem/detail/1854
using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+2-2*i)-4;
    }
    for(int j=cen;j<=n+1-cen;++j) {   // 从左上走到右上
        if(I!=cen) {
            cnt+=(n+1-cen)-(cen)+1;
            break;
        }
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=cen+1;i<=n+1-cen;++i) {   // 从右上走到右下
        if(J!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=n-cen;j>=cen;--j) {     // 从右下走到左下
        if(I!=n+1-cen) {
            cnt+=(n-cen)-(cen)+1;
            break;
        }
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=n-cen;i>=cen+1;--i) { // 从左下走到左上
        if(J!=cen) {
            cnt+=(n+1-cen)-cen+1;
            break;
        }
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    return 0;
}
// AC https://www.luogu.com.cn/record/188066061

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

还是声明一下，下面的WA代码不是此题的

主要这段代码出问题了

1
2
3
for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
 }

应该写成这样

1
2
3
for(int i=1;i<cen;++i) {
        cnt+=4*(n+2-2*i)-4;
    }

这种涉及所有东西推导的代码还是不能够仅靠观察，理性论证也很重要

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 <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
    }
    for(int i=n+1-cen;i>=cen;--i) {
        if(J!=cen) {
            cnt+=(n+1-cen)-cen+1;
            break;
        }
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=cen+1;j<=n+1-cen;++j) {
        if(I!=cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int i=cen+1;i<=n+1-cen;++i) {
        if(J!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    for(int j=n-cen;j>=cen+1;--j) {
        if(I!=n+1-cen) {
            cnt+=(n+1-cen)-(cen+1)+1;
            break;
        }
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    return 0;
}

注意！！！TLE不仅代表算法时间复杂度过高，还有可能是死循环（特别是你觉得TLE不可思议时，相信自己的判断，大概率是死循环）

1
2
3
4
5
6
7
for(int j=n+1-cen;j>=cen+1;++j) {
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

像这段代码，是 —j 的，写成了++j，就会死循环TLE

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=3010;
ll n,I,J;
// 行号，列号

int main()
{
    cin>>n>>I>>J;
    ll cen=min(min(I,n+1-I),min(J,n+1-J));
    if(cen==(n/2+1)) {
        cout<<n*n<<endl;
        return 0;
    }
    ll cnt=0;
    for(int i=1;i<cen;++i) {
        cnt+=4*(n+1-i)-4;
    }
    for(int i=n+1-cen;i>=cen;--i) {
        ++cnt;
        if(I==i && J==cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int j=cen+1;j<=n+1-cen;++j) {
        ++cnt;
        if(I==cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int i=cen+1;i<=n+1-cen;++i) {
        ++cnt;
        if(I==i && J==n+1-cen) {
            cout<<cnt<<endl;
            return 0;
        }
    }
    for(int j=n+1-cen;j>=cen+1;++j) {
        ++cnt;
        if(I==n+1-cen && J==j) {
            cout<<cnt<<endl;
            return 0;
        }
    }

    return 0;
}

Posted on Edited on

AC代码

赛时AC，主要就是记录一下

主要思路就是通过一次遍历得到以1位置为准的到达所需魔法数cntK[N]以及魔法数最远到达点ktomax[N]

由于都是相对于一位置的，魔法数可以互相加减。

从i点能够到达的最远点即是ktomax[k+cntK[i]]（前提是s[i]==‘想统计的字符’），那么长度就是ktomax[k+cntK[i]]-i+1，这就是lans（local ans）的由来

核心代码就是这一段，其他的代码就是重复，初始化，以及防止加出去=0了

1
2
3
4
5
6
7
if(s[i]=='i') {
    ll lans=ktomax[k+cntK[i]]-i+1;
    ans=max(ans,lans);
}else {
    ll lans=ktomax[k+cntK[i]-1]-i+1;
    ans=max(ans,lans);
}
1
2
3
for(int i=chK+1;i<=2*k;++i) {   // 你说你有更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
 }

cntI是没有用的变量，不过因为

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <cstdio>
#include <cctype>

using namespace std;
typedef long long ll;
const ll N=2e5+7;
string s;
ll k,ans;
ll ktomax[N],cntK[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    cin>>k;
    ll chK=0,cntI=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='i') {
            ++cntI;
        }else {
           chK+=1;
            ++cntI;
        }
        ktomax[chK]=i,cntK[i]=chK;
    }
    for(int i=chK+1;i<=2*k;++i) {   // 你说你有更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
    }
    for(int i=0;i<s.size();++i) {
        if(s[i]=='i') {
            ll lans=ktomax[k+cntK[i]]-i+1;
            ans=max(ans,lans);
        }else {
            ll lans=ktomax[k+cntK[i]-1]-i+1;
            ans=max(ans,lans);
        }
    }

    memset(ktomax,0,sizeof(ktomax));    // 重置
    memset(cntK,0,sizeof(cntK));
    chK=0,cntI=0;

    for(int i=0;i<s.size();++i) {   //判断e序列
        if(s[i]=='e') {
            ++cntI;
        }else {
            chK+=1;
            ++cntI;
        }
        ktomax[chK]=i,cntK[i]=chK;
    }
    for(int i=chK+1;i<=2*k;++i) {   // 你说你需要更多的k？没问题，但是到达距离是一样的
        ktomax[i]=ktomax[chK];
    }
    for(int i=0;i<s.size();++i) {
        if(s[i]=='e') {
            ll lans=ktomax[k+cntK[i]]-i+1;
            ans=max(ans,lans);
        }else {
            ll lans=ktomax[k+cntK[i]-1]-i+1;
            ans=max(ans,lans);
        }
    }
    cout<<ans<<endl;
    return 0;
}
// AC https://oj.saikr.com/problem/detail/1851

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

之前的做法只想了从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
#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;
string s;
ll k;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    cin>>k;
    ll ans=0;
    ll chK=k,cntI=0,cntE=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='i') {
            ++cntI;
            ans=max(ans,cntI);
        }else {
            if(chK<=0) {
                ans=max(ans,cntI);
                cntI=0,chK=k;
            }else {
                chK-=1;
                ++cntI;
                ans=max(ans,cntI);
            }
        }
    }
    chK=k,cntI=0,cntE=0;
    for(int i=0;i<s.size();++i) {   //判断i序列
        if(s[i]=='e') {
            ++cntE;
            ans=max(ans,cntE);
        }else {
            if(chK<=0) {
                ans=max(ans,cntE);
                cntE=0,chK=k;
            }else {
                chK-=1;
                ++cntE;
                ans=max(ans,cntE);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Posted on Edited on

AC代码

赛中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
#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 query;
ll curt,lastHar;
vector<pair<ll,ll> > pot;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>query;
    for(int _=1;_<=query;++_) {
        ll op,t,h;
        cin>>op;
        if(op==1) {
            if(pot.empty() || pot.back().first!=curt)
                pot.push_back(make_pair(curt,1));
            else
                pot.back().second+=1;
        }else if(op==2) {
            cin>>t;
            curt+=t;
        }else {
            cin>>h;
            if(curt-h<lastHar) { // 种植时间在 lastHar 之前的植物 都被收割了
                cout<<0<<endl;
                continue;
            }
            ll l=lower_bound(pot.begin(),pot.end(),make_pair(lastHar,0LL))-pot.begin();
            ll r=upper_bound(pot.begin(),pot.end(),make_pair(curt-h,N))-pot.begin()-1;
            if(r>pot.size())
                r=pot.size()-1;
            ll ans=0;
            for(int i=l;i<=r;++i) {
                ans+=pot[i].second;
            }
            lastHar=curt-h+1;     // 种植时间在 curt-h+1 之前的植物 都被收割了
            cout<<ans<<'\n';
        }
    }
}
// AC https://atcoder.jp/contests/abc379/submissions/59614741

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