Educational Codeforces Round 19

A水题，数论都算不上吧，分解一下就行了，看分解的书是不是比k大

B求奇数和，wa了四发。。先把大于0的全部加起来，如果奇数直接输出，如果偶数就找最小的大于0的那个奇数和最大的那个小于0 的奇数，比较和减大于0 和加小于0 谁大就输出谁

复杂度O（n）

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-9;
const int N=100000+10,maxn=100000+10,inf=0x3f3f3f;

int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,sum=0,maxx=-100000,minn=100000;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]>0)
        {
            if(a[i]&1)minn=min(minn,a[i]);
            sum+=a[i];
        }
        else if(a[i]&1)maxx=max(maxx,a[i]);
    }
    if(sum&1)cout<<sum<<endl;
    else
    {
        if(sum==minn)cout<<sum+maxx<<endl;
        else cout<<max(sum+maxx,sum-minn)<<endl;
    }
    return 0;
}

C题比赛时还是没做出来，先从后向前求最小值，用一个栈维护，扫描字符串s，如果当前栈顶元素比s剩下的数全小就输出它

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-9;
const int N=100000+10,maxn=100000+10,inf=0x3f3f3f;

int minn[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int n=s.size();
    minn[n-1]=s[n-1]-'a';
    for(int i=n-2;i>=0;i--)
    {
        minn[i]=min(minn[i+1],s[i]-'a');
    }
    string ans="";
    for(int i=0;i<n;i++)
    {
        string p="";p+=s[i];
        char t=s[i];
        int cur=minn[i];
        while(i+1<n&&cur!=s[i]-'a'){
            i++;
            p+=s[i];
        }
        string q="";q+=s[i];
        while(i+1<n&&t>s[i+1]){
            q+=s[i+1];
            i++;
        }
        ans+=q;
        reverse(p.begin(),p.end());
        p=p.substr(1,p.size()-1);
        ans+=p;
    }
    cout<<ans<<endl;
    return 0;
}

D题不会

E题如果直接模拟会超时，可以分成两段做，如果k够大，直接模拟，如果k小，用数组记录d【k】【p】，如果p+a【p】+k>n,d[k][p]=1;否则d[k][p]=d[k][p+a[p]+k]+1

如果直接用第二个方法会爆内存，所以两个结合起来使用

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

const double g=10.0,eps=1e-9;
const int N=100000+10,maxn=300,inf=0x3f3f3f;

int a[N];
int d[maxn+10][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int k=1;k<=maxn;k++)
    {
        for(int i=n;i>=1;i--)
        {
            if(i+a[i]+k>n)d[k][i]=1;
            else d[k][i]=d[k][i+a[i]+k]+1;
        }
    }
    cin>>m;
    while(m--){
        int p,k,ans=0;
        cin>>p>>k;
        if(k>=maxn)
        {
            while(p<=n){
                p+=(a[p]+k);
                ans++;
            }
            cout<<ans<<endl;
        }
        else cout<<d[k][p]<<endl;
    }
    return 0;
}

F题不会~