2023/10/16考试

ccrui · 2023-10-16 14:25:36 · 个人记录

注意分配时间，以及思路要更清晰。

T1 friends

pro

link

sol

考场

分配时间：\le 60

考场思路：dp_{i,j,k}=\max{dp_{i-1,j,k},dp_{i-1,j-C_i+t,k-t\times X_i}}\to O(n^4)

复盘

分配时间：\le 50

思路：

先按 X_i 排序，然后倒着做一遍 01 背包，

预处理有 i 个哞尼时，从后往前找到的第 j 个朋友的最大的受欢迎度是多少。

从后往前进行一次 dp，枚举有 b 个冰激凌时最大的受欢迎度是多少。

因为保证了单调性，所以可以不断将此个朋友的 C_i 降为 0，直到 b 不能降完 C_i 为止

注意：

dp 要证明正确性。
合理分配时间。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,aa,bb;
struct node{
    int p,c,x;
    bool operator <(const node &a)const{
        return x<a.x;
    }
}a[2005];
int dp[2005][2005],f[2005][2005],ans;
signed main(){
    cin>>n>>aa>>bb;
    for(int i=1;i<=n;i++){
        cin>>a[i].p>>a[i].c>>a[i].x;
    }
    sort(a+1,a+n+1);
    for(int i=n;i;i--){
        for(int j=0;j<=aa;j++){
            dp[i][j]=dp[i+1][j];
        }
        for(int j=a[i].c;j<=aa;j++){
            dp[i][j]=max(dp[i][j],dp[i+1][j-a[i].c]+a[i].p);
        }
    }
    for(int i=n;i;i--){
        for(int j=0;j<=bb;j++){
            f[i][j]=f[i+1][j];
            int nn=j-min(a[i].c,j/a[i].x)*a[i].x;
            if(min(a[i].c,j/a[i].x)==a[i].c)f[i][j]=max(f[i][j],f[i+1][nn]+a[i].p);
            else f[i][j]=max(f[i][j],dp[i+1][aa-(a[i].c-min(a[i].c,j/a[i].x))]+a[i].p);
            ans=max(ans,f[i][j]);
        }
    }
    cout<<ans;
    return 0;
}

T2 replace

pro

link

sol

考场

分配时间：\ge 60

考场思路：模拟。

复盘

分配时间：\le 60

思路：

图论建模。

拓扑排序找环，环上的点可以通过多改成一个点而破环，所以每找到一个环 ans 就要加一，ans 初始为边数。

如：ABC \to BAB 可以建模为

点	to
A	B
B	A
C	B

可以发现我们可以这样拆环：

设环上的点位 v_1\to v_2\to \dots\to v_k\to v_1，

则可以操作v_1\to x,v2\to v_1,v3\to v_2,\dots,v_k\to v_{k-1},x\to v_k 即可破环，操作次数为 \text{边数}+1。

总括起来操作次数为 \text{边数}+\text{环数}。

至于求环，拓扑排序再 dfs 即可。

还有无解的情况，有两种情况要输出 -1：

所有字母再 a 中均存在，这是只有两个字符串完全相等才输出 0，否则输出 -1；
字符串 a 中有一个点连了两条边，及一种字符要拆成两种。

#include<bits/stdc++.h>
using namespace std;
int qs;
string a,b;
int v[55];
int bb[55],ru[55],xu=0;
queue<int>q;
set<int>bs;
int chcc(char c){
    if(c>='a'&&c<='z')return c-'a'+1;
    else return c-'A'+27;
    //return c;
}
void illl(){
    xu=0;
    for(int i=0;i<53;i++){
        ru[i]=bb[i]=0;
        v[i]=0;
    }
    while(!q.empty())q.pop();
    bs.clear();
}
void topu(){
    for(int i=1;i<53;i++){
        if(!ru[i])q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        bb[u]=1;
        //cout<<u<<endl;
        q.pop();
        int nn=v[u];
        if(!bb[nn]){
            ru[nn]=0;
            q.push(nn);
        }
    }
}
bool strp(string a,string b){
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i])return 0;
    }
    return 1;
}
void dfs(int x){
    bb[x]=1;
    if(!bb[v[x]])dfs(v[x]);
}
int run(){
int ans=0;
    int n=a.size();
    for(int i=0;i<n;i++){
        if(!v[chcc(a[i])]||v[chcc(a[i])]==chcc(b[i])){
            v[chcc(a[i])]=chcc(b[i]);
        }else return -1;
        bs.insert(chcc(b[i]));
        //cout<<b[i]<<endl;
    }
    if(bs.size()==52){
        if(strp(a,b))return 0;
        else return -1;
    }
    memset(v,0,sizeof(v));
    for(int i=0;i<n;i++){
        if(v[chcc(a[i])]==0&&a[i]!=b[i]){
            v[chcc(a[i])]=chcc(b[i]);
            ru[chcc(b[i])]++;
            ans++;
        }
        //cout<<v[chcc(a[i])]<<endl;
    }
    topu();
    //cout<<bb[0]<<" "<<bb[1]<<" "<<bb[2]<<" "<<bb[3]<<endl;
    for(int i=1;i<53;i++){
        //cout<<i<<endl;
        if(!bb[i]){     
            ans++;
            dfs(i);
            //cout<<i<<endl;
        }
    }
    return ans;
}
signed main(){
    cin>>qs;
    while(qs--){
        illl();
        cin>>a>>b;
        cout<<run()<<endl;
    }
    return 0;
}

T3 bakery

pro

link

sol

考场

分配时间：\ge 70

考场思路：

不等式组推式子：

设 k 为二分 mid，则有：

\begin{cases} (A_1-x)T_c+(B_1-k+x)\le C_1\\ (A_2-x)T_c+(B_1-k+x)\le C_2\\ \dots \\ (A_n-x)T_c+(B_n-k+x)\le C_n \end{cases}

所以

\begin{cases} x \le/\ge\frac{C_1+k\times B_1-T_c\times A_1-T_m\times B_1}{B_1-A_1} \\ x \le/\ge \frac{C_2+k\times B_2-T_c\times A_2-T_m\times B_2}{B_2-A_2} \\ \dots\\ x \le/\ge \frac{C_n+k\times B_n-T_c\times A_n-T_m\times B_n}{B_n-A_n} \end{cases}

解出来不等式组有正整数解可行。

\begin{cases} \min_{x}=\min_{\lceil\frac{C_1+k\times B_1-T_c\times A_1-T_m\times B_1}{B_1-A_1} \rceil}(B_1-A_1<0)\\ \max_{x}=\max_{\lfloor\frac{C_1+k\times B_1-T_c\times A_1-T_m\times B_1}{B_1-A_1}\rfloor}(B_1-A_1>0)\\ x\text{无解}\gets C_1+k\times B_1-T_c\times A_1-T_m\times B_1\neq 0(B_1-A_1=0)\\ \end{cases}

最后判断是否 \max_{x}\le \min_{x} 且无情况 3 即可。

复盘

注意：

特判不等式 B_i-A_i=0 时无解情况（即 C_1+k\times B_1-T_c\times A_1-T_m\times B_1\neq0），返回 false。
小数要在过程中就操作，不然容易掉精度。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010;
int T,n,a,b,na[N],nb[N],nc[N];
bool check(int x){
    int minn=min(x,a-1),maxn=max(0ll,x-b+1);
    for(int i=1;i<=n;i++){
        int ncc=nc[i]+x*nb[i]-a*na[i]-b*nb[i];
        if(na[i]==nb[i]){
            if(ncc<0)return 0;//重要!!!
            continue;
        }
        if(nb[i]-na[i]>0){
            minn=min(minn,(int)floor(1.0*ncc/(1.0*nb[i]-na[i])));//防掉精
        }else{
            maxn=max(maxn,(int)ceil(1.0*ncc/(1.0*nb[i]-na[i])));//防掉精
        }
    }
    return maxn<=minn;
}
signed main(){
    cin>>T;
    while(T--){
        cin>>n>>a>>b;
        for(int i=1;i<=n;i++)cin>>na[i]>>nb[i]>>nc[i];
        int l=-1,r=a+b;
        while(l<r-1){
            int mid=(l+r)>>1;
            if(check(mid))r=mid;
            else l=mid;
        }
        cout<<r<<endl;
    }
    return 0;
}

T4 route

pro

link

sol

考场

分配时间：\le 20

考场思路：针对 n\le2 的数据来回折。

复盘

分配时间：\ge 40

思路：

贪心构造！先尽量往右走，直到值小于 2（这时再折回，因为前面不能折回了），再往左走同理。

注意：

注意做题策略和时间分配！

#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int x=1;
    while(1){
        bool b[100010]={0};
        for(int i=x;i<=n;i++){
            if(a[i]>=2){
                a[i]--;
                x=i+1;
                putchar('R');
            }else break;
        }
        //cout<<x<<endl;
        for(int i=x;;){
            x=i;
            if(i<=n&&(a[i]>1||b[i+1]))b[i]=1;
            if(i>1&&(!b[i]||a[i-1]>1)){
                i--;
                a[i]--;
                putchar('L');
            }else break;
            //cout<<i<<endl;
        }
        if(x==1&&!b[1])break;
    }
    return 0;
}