8.15test

kamikuQAQ · 2025-08-15 23:24:39 · 个人记录

T1

签到题没什么好讲的，我的做法是将所有的可能用数组存起来然后一个一个对比

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 15;
int ans[maxn];
int a[maxn];
int solve(int n) {
    for(int i=1;i<=3;i++) {
        ans[i]=a[i];
    }
    int cnt=3;
    for(int i=1;i<=3;i++) {
        for(int j=i+1;j<=3;j++) {
            ans[++cnt]=a[i]+a[j];
        }
    }
    ans[7]=a[1]+a[2]+a[3];
    int minn=INT_MAX;
    sort(ans+1,ans+1+7);
    for(int i=1;i<=7;i++) {
        if(n<ans[i]) {
            break;
        }
        minn=min(minn,n-ans[i]);
    }
    if(minn==INT_MAX) {
        minn=n;
    }
    return minn;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        int k;
        cin>>k;
        for(int i=1;i<=3;i++) {
            cin>>a[i];
        }
        sort(a+1,a+1+3);
        cout<<solve(k)<<"\n";
    }
    return 0;
}//100pts

T2

没注意要蛇型走位挂了35pts（）
其实这题50分超级好拿，对于n<=20,可以选择全部走边上的一，然后性质A的意思就是将从一到某一层全部拿满就行
正解思路是可以看到2^60大于1e18所以直接空出来，然后进行二进制分解去填前面的空，不够填空的说明可以用1来填

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
const int mod1 = 1e18+1;
const int mod = 99824353;
const int maxn = 505;
int dp[maxn][maxn];
struct point {
    int x,y;
};
vector<point>op;
int mul(int a,int b) {
    return ((a%mod)*(b%mod))%mod;
}
void init() {
    dp[1][1]=dp[2][1]=dp[2][2]=1;
    for(int i=1; i<=60; i++) {
        for(int j=1; j<=i; j++) {
            if(j==1||j==i) {
                dp[i][j]=1;
            } else {
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }
    }
    return ;
}
int n;
signed main() {
    init();
    cin>>n;
    if(n<=60) {
        cout<<n<<'\n';
        for(int i=1; i<=n; i++) {
            cout<<i<<' '<<1<<"\n";
        }
        cout<<n<<' '<<1<<"\n";
        return 0;
    }
    int tmp=n-60;
    int cnt=1;
    int ans=1;
    int dir=0;
    int num=60;
    int sum=0;
    while(tmp) {
        if (tmp % 2 == 1) {
            if (dir == 1) {
                for (int i = 1; i <= cnt; i++) {
                    op.push_back({cnt, i});
                    ans = mul(ans, dp[cnt][i]);
                    sum += dp[cnt][i];
                }
            } else {
                for (int i = cnt; i >= 1; i--) {
                    op.push_back({cnt, i});
                    ans = mul(ans, dp[cnt][i]);
                    sum += dp[cnt][i];
                }
            }
            dir = !dir;
        } else {
            num--;
            if (dir == 0) {
                op.push_back({cnt, cnt});
            } else {
                op.push_back({cnt, 1});
            }
            sum += 1;
        }
        cnt++;
        tmp /= 2;
    }
    sum+=num;
    for(int i=1;i<=num;i++) {
        if(dir==0) {
            op.push_back({cnt,cnt});
        } else {
            op.push_back({cnt,1});
        }
        cnt++;
    }
    cout<<op.size()<<endl;
    for(int i=0;i<op.size();i++) {
        cout<<op[i].x<<' '<<op[i].y<<"\n";
    }
    cout<<sum<<' '<<ans<<'\n';
    return 0;
}

T3

dfs可以骗30pts（）
思路是既然w范围大价值范围小，我们反其道而行之，设能在j价值内获得最小容量来进行背包 状态转移方程

dp[i][j] = dp[i - 1][j - v[i]] + w[i] // 装入
dp[i][j] = dp[i - 1][j]//不装入

#include<bits/stdc++.h>
using namespace std;
int dp[105][100005];
int v[105],w[105];
int main() {
    int n,W;
    cin>>n>>W;
    int sum=0;
    for(int i=1;i<=n;i++) {
        cin>>w[i]>>v[i];
        sum+=v[i];
    }
    for(int i=1;i<=sum;i++) {
        dp[0][i]=1e9;
    }
    int ans=0;
    dp[0][0]=0;
    for(int i=1;i<=n;i++) {
        for(int j=0;j<=sum;j++) {
            dp[i][j]=dp[i-1][j];
            if(j>=v[i]) {
                dp[i][j]=min(dp[i-1][j-v[i]]+w[i],dp[i][j]);
            }
        }
    }
    for(int i=0;i<=sum;i++) {
        if(dp[n][i]<=W) {
            ans=i;
        }
    }
    cout<<ans;
    return 0;
} 

T4

首先要让一个一段亲密度最大，自然地我们就会想到使用二分答案，二分找出上限之后，我们使亲密度大于k的段数严格小于k，最后枚举就行
至于验证二分，将所有人分为两部分，1到n-x和n-x+1到n后面的部分让他们两两配对若亲密度小于k说明合法反之不合法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
vector<int>num[maxn];
long long a[maxn],n,k;
long long calc(int x)
{
    long long sum = (n - x) * x + x * (x - 1) / 2;
    for (int i = 1; i <= n; i++)
    {
        int l = 0;
        for (int j = 0; j < num[i].size(); j++)
        {
            while (l < num[i].size() && num[i][j] - num[i][l] > x)
            {
                l++;
            }
            sum = sum - (j - l);
        }
    }
    return sum;
}
int main() {
    cin>>n>>k;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        num[a[i]].push_back(i);
    }
    if(calc(n)<k) {
        cout<<-1;
        return 0;
    }
    int l=0-1,r=n+1;
    while(l+1<r) {
        int mid=(l+r)/2;
        if(calc(mid)<k) {
            l=mid;
        } else {
            r=mid;
        }
    }
    int d=l+1;
    long long cnt=calc(l);
    for(int i=1; i<=n-d; i++) {
        if(a[i]!=a[i+d]) {
            cnt++;
        }
        if(cnt==k) {
            cout<<i<<' '<<i+d;
            return 0;
        }
    }
    return 0;
}