SCP-J A、C题求优化，悬关

DGFLSzfd @ 2024-10-13 14:20:05

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int T;
    cin >> T;
    while (T--) 
    {
        long long n, k,ans=0;
        cin>>n>>k;
        if (k==0) 
        {
            cout<<1<<endl; 
            continue;
        }
        for(long long q=n/(k+1);q*k<=n;q++) 
        {
            long long r=n-(q*k);
            if(r<0) break;
            if (r<q) 
            {
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int f(const string &S, int &pos, int x) 
{
    int result=0;
    while (pos<S.length() and isdigit(S[pos])) 
    {
        result=result*10+(S[pos]-'0');
        pos++;
    }
    if (pos == S.length() || S[pos] != 'x') 
    {
        return result;
    }//算尽了 

    //嵌套了下一个三目 
    bool greater=(S[pos + 1] == '>');
    pos += 2;  

    int con = 0;
    while (isdigit(S[pos])) 
    {
        con=con*10+(S[pos]-'0');
        pos++;
    }
    pos++;

    int truee = f(S, pos, x);
    pos++;
    int falsee = f(S, pos, x);
    if ((greater and x > con) or (!greater and x < con)) 
    {
        return truee;
    } 
    else 
    {
        return falsee;
    }
}

int main() 
{
    int m,q;
    cin >>m>>q;
    string S;
    cin>>S;
    while(q--) 
    {
        int x;
        cin>>x;
        int pos=0; 
        cout<<f(S,pos,x)<<endl;
    }
    return 0;
}

by luojingjie @ 2024-10-13 14:24:55

@DGFLSzfd

T1不能暴力，可以试着去找规律。

by 0Io_oI0 @ 2024-10-13 14:29:40

@DGFLSzfd T1是可以找到规律的这样就有O(1)的代码，T3我觉得是暴力递归

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
template<typename TP> inline TP read(TP &num)
{
    TP x=0;
    int f=0;
    char ch=getchar();
    while(ch<48||ch>57) f|=ch=='-',ch=getchar();
    while(48<=ch&&ch<=57) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return num=f?-x:x;
}
template<typename ...Args> inline void read(Args &...args)
{
    (read(args),...);
}
template<typename TP> inline void write(TP x)
{
    (x<0)?(putchar('-'),x=-x):0;
    (x>9)?(write(x/10),0):0;
    putchar((x%10)^48);
}
template<typename TP> inline void writeln(TP x)
{
    write<TP>(x);
    puts("");
}
int ans[1600001],m,q,l[1600001],r[1600001],idx=1;
int sval[1600001],Lb[1600001],Ub[1600001],mxans;
string s;
inline void read_str(string &s)
{
    char ch=getchar();
    s="";
    while(ch=='\n'||ch=='\r'||ch==' ') ch=getchar();
    while(ch!='\n'&&ch!='\r'&&ch!=' ') s+=ch,ch=getchar();
}
int dfs(int pos,int depth,int id,int lb,int ub)
{
    if(s[pos]=='x')
    {
        int p=pos+2,val=0,finpos;
        while(p<(int)s.size()&&isdigit(s[p])) val=val*10+s[p]-48,++p;
        if(s[pos+1]=='>')
        {
            int nxt=dfs(p+1,depth+1,l[id]=++idx,max(lb,val+1),ub);
            finpos=dfs(nxt+2,depth+1,r[id]=++idx,lb,min(val,ub));
        }
        else
        {
            int nxt=dfs(p+1,depth+1,l[id]=++idx,lb,min(val-1,ub));
            finpos=dfs(nxt+2,depth+1,r[id]=++idx,max(lb,val),ub);
        }
        return finpos;
    }
    else
    {
        int p=pos,val=0;
        while(p<(int)s.size()&&isdigit(s[p])) val=val*10+s[p]-48,++p;
        if(lb<=ub)
        {
            sval[id]=val;
            Lb[id]=lb,Ub[id]=ub;
        }
        return p-1;
    }
}
signed main()
{
    read(m,q);
    read_str(s);
    memset(sval,-1,sizeof sval);
    dfs(0,1,1,1,1000000);
    rep(i,1,1600000) if(sval[i]!=-1)
    {
        rep(j,Lb[i],Ub[i]) ans[j]=sval[i];
        if(Ub[i]==1000000) mxans=sval[i];
    }
    while(q--)
    {
        int num;
        read(num);
        if(num>1000000) writeln(mxans);
        else writeln(ans[num]);
    }
    return 0; 
}

by dear_deer_land @ 2024-10-13 14:30:29

T1的正解（忽略我的快读快写）
一定要开longlong
关我

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
        if (c == '-') flag = true;
    else
        num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
int t,a,b,c,d,ans;
signed main(){
    t=read();
    while(t--){
        a=read();
        b=read();
        if(b==0){
            puts("1");
        }
        else{
            c=a/b;
            d=a/(b+1);
            ans=c-d;
            write(ans);
            puts("");
        }
    }
    return 0;
}

by DGFLSzfd @ 2024-10-13 14:31:24

@0Io_oI0 T3这么长？！！！不会吧

by 0Io_oI0 @ 2024-10-13 14:33:30

@DGFLSzfd 我不知道，反正我这个代码可以A，应该还有更有解

by DGFLSzfd @ 2024-10-13 14:34:05

@dear_deer_land 楼上 O(1)是正解吧我觉得……

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int T;
    cin >> T;
    while (T--) 
    {
        long long n, k,ans=0;
        cin>>n>>k;
        if(k==0) 
        {
            cout<<1<<endl;
            continue;
        }
        cout<<(n/k)-(n/(k+1))<<endl; 
    }
    return 0;
}

by 0Io_oI0 @ 2024-10-13 14:35:28

@DGFLSzfd 能给个关注吗

by DGFLSzfd @ 2024-10-13 14:36:15

@0Io_oI0

rep(i,1,1600000) if(sval[i]!=-1)
    {
        rep(j,Lb[i],Ub[i]) ans[j]=sval[i];
        if(Ub[i]==1000000) mxans=sval[i];
    }

能不能解释一下这个，谢谢！

by DGFLSzfd @ 2024-10-13 14:38:26

@0Io_oI0 已关求解释

by dear_deer_land @ 2024-10-13 14:40:57

@DGFLSzfd
我这个也是O(1)。。。
一个式子分开算和合在一起算复杂度一样，而且我用快读快写会比他更快。。。