2022/7/30

D-Jobs (Easy Version)_"蔚来杯"2022牛客暑期多校训练营4 (nowcoder.com)

看了群里大佬的提示，可以预处理出这样的一个数组p[i][j][k]表示iq为i，eq为j在进入第k个公司最低需要多少aq，然后就可以进行o(n）的查询了

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,q,p[500][500][20];
ll seed,lastans;

ll fastpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll solve(ll iq,ll eq,ll aq){
    ll res=0;
    for(ll i=1;i<=n;i++){
        if(aq>=p[iq][eq][i]) res++;
    }
    return res;
}
int main(){
    for(int i=0;i<=405;i++)
    for(int j=0;j<=405;j++)
    for(int k=0;k<=15;k++) p[i][j][k]=1e18;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        ll m;scanf("%lld",&m);
        for(int j=1;j<=m;j++){
            ll x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            p[x][y][i]=min(p[x][y][i],z);
        }
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=400;i++)
    for(int j=1;j<=400;j++){
        p[i][j][k]=min({p[i][j][k],p[i-1][j][k],p[i][j-1][k]});
        //cout<<p[i][j][k]<<" "<<i<<" "<<j<<" "<<k<<endl;
    }
    
    scanf("%lld",&seed);
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1,400);
    ll ans=0;
    lastans=0;
    for (int i=1;i<=q;i++)
    {
        int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
        int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
        int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
        //cout<<IQ<<"  "<<EQ<<" "<<AQ<<endl;
        lastans=solve(IQ,EQ,AQ);  // The answer to the i-th friend
        ans=(ans+lastans*fastpow(seed,q-i)%mod)%mod;
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}

1506E - Restoring the Permutation迭代数组

一开始用的双端队列发现根本不是一回事，然后又选择了二分超时了，然后又改成了while虽然多过了两组但还是超时了，最后看题解才知道可以设一个dis数组表示小于i的最大的数是多少，迭代查找的次数很少，可以通过

Codeforces Round #710 (Div. 3) E. Restoring the Permutation_帅气的伯云的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll t,n,q[200005],visa[200005],visb[200005],mx[200005],mi[200005],vis[200005],dis[200005];
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++) vis[i]=visa[i]=visb[i]=dis[i]=0;
        for(int i=1;i<=n;i++) scanf("%lld",&q[i]);
        ll a=n,b=1;
        for(int i=1;i<=n;i++){
            if(vis[q[i]]){
               a=dis[q[i]];
               while(visa[a]) a=dis[a];
               mx[i]=a;visa[a]=1;dis[q[i]]=a-1;
               while(visb[b]) b++;
               mi[i]=b;visb[b]=1;
            }
            else{
                mx[i]=mi[i]=q[i];
                dis[q[i]]=q[i]-1;
                vis[q[i]]=visa[q[i]]=visb[q[i]]=1;
            }
        }
        for(int i=1;i<=n;i++) printf("%lld ",mi[i]);
        printf("\n");
        for(int i=1;i<=n;i++) printf("%lld ",mx[i]);
        printf("\n");
    }
    system("pause");
    return 0;
}

812C - Sagheer and Nubian Market二分

还以为是dp，想了很久没想出来，题解思路是二分，二分找出k，然后贪心找最小花费

codeforce 812C Sagheer and Nubian Market（二分查找）_China震震的博客-CSDN博客

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,s,a[100005],b[100005];
bool check(ll x){
    for(int i=1;i<=n;i++) b[i]=a[i]+i*x;
    sort(b+1,b+n+1);
    ll res=0;
    for(int i=1;i<=x;i++) res+=b[i];
    return res<=s;
}
int main(){
    scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll l=1,r=n,res=0,ans=0;
    while(l<=r){
        ll mid=l+r>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    for(int i=1;i<=n;i++) b[i]=a[i]+i*res;
    sort(b+1,b+n+1);
    for(int i=1;i<=res;i++) ans+=b[i];
    printf("%lld %lld\n",res,ans);
    system("pause");
    return 0;
}

K-NIO's Sword_"蔚来杯"2022牛客暑期多校训练营4 (nowcoder.com)

假设走第i步需要k次，那么A[i]=A[i-1]*10^k+xi,xi<10^k,从小到大枚举k，只要x在范围内就说明找到了解，最后步数累加起来输出答案

出题人第四场_哔哩哔哩_bilibili

#include <bits/stdc++.h>
#define ll long long
#define lowbit(x) ((x)&(-x))
using namespace std;
const ll MAX=1e6+5;
const ll mod=998244353;
ll n,ten[15];
ll cal(ll x){
    ll res=0;
    if(x==1) return 0;
    for(int i=1;i<=n;i++){
        ll y=i-1;
        for(int j=0;j<=10;j++){
            ll k=y*ten[j];
            k=((i-k)%n+n)%n;
            if(k<ten[j]){
                res+=j;break;
            }
        }
    }
    return res;
}
int main(){
    ten[0]=1;
    for(int i=1;i<=10;i++) ten[i]=ten[i-1]*10LL;
    scanf("%lld",&n);
    printf("%lld\n",cal(n));
    system("pause");
    return 0;
}