526互联

训练round1题解

发布时间 2023-03-24 23:47:09作者: WW爆米花

SMU Spring 2023 Trial Contest Round 1

A.

大意：
给出一个仅由0，1组成的字符串，该字符串是多次在首位各加0或1得到，问最短的原始字符串的长度。

思路：
一次操作增加两个字符，
特判字符串长度为1直接输出1.
首尾双指针进行判断，满足条件同时移动，不满足则退出，答案为原长-2乘以指针移动的次数。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s;cin>>s;
        if(s.size()==1){
            cout<<1<<endl;
            continue;
        }
        int l=0,r=s.size()-1;
        while(l<r){
         if((s[l]=='0'&&s[r]=='1')||(s[l]=='1'&&s[r]=='0')){
             l++;r--;
         }else break;
        }
        cout<<s.size()-l*2<<endl;
    }
    return 0;
}

B.

大意：
给定一个字符串，把它分成两部分，使每部分重复的字母最少，计算出两部分不重复字母数之和。

思路：
用map记录字母是否重复，
向右扫一遍，向左扫一遍，两个数组记录在每个位置断开后重复的字母数。
最后遍历一遍找出左右重复字母数和最小的那个位置，输出字符串长度-和。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5+10;
vector<int> l(N),r(N);
map<char,int> mp;
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s;cin>>s;
        for(int i=0;i<s.size()-1;i++){
            if(!mp[s[i]]){
                mp[s[i]]=1;
                if(i==0)l[i]=0;
                else l[i]=l[i-1];
            }else{
                l[i]=l[i-1]+1;
            }
        }
        mp.clear();
        for(int i=s.size()-1;i>0;i--){
            if(!mp[s[i]]){
                mp[s[i]]=1;
                if(i==s.size()-1)r[i]=0;
                else r[i]=r[i+1];
            }else{
                r[i]=r[i+1]+1;
            }
        }
        //for(int i=s.size()-1;i>0;i--)cout<<r[i]<<endl;
        int mi=1e7;
        for(int i=0;i<s.size()-1;i++){
            mi=min(l[i]+r[i+1],mi);
        }
        cout<<s.size()-mi<<endl;
        mp.clear();
        l.clear();r.clear();
    }
    return 0;
}

C.

大意：
给出一组数，一次操作可以将相邻两个数符号取反，问经过数次操作后整组数和最大是多少。

思路：
等价于可以任意选两个数取相反符号。
1.若负数个数为偶数，则答案为整组数取正之和。
2.若负数个数为奇数，则看它与最小正数的绝对值，若负数绝对值大则进行操作。
在输入时可以将所有数取正求和，记录负数个数，
若负数个数为奇数，把数排序，删除最小数的2倍。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5+10;
int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        ll sum=0;
        int cnt=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]<0){
                cnt++;
                sum-=a[i];
                a[i]=-a[i];
            }else sum+=a[i];
        }
        if(cnt&1){
            sort(a+1,a+1+n);
            cout<<sum-2*a[1]<<endl;
        }else{
            cout<<sum<<endl;
        }
    }
    return 0;
}

E.

思路：
判断数n是否大等于两个最低需求之和，若是，输出一个最低需求和n-该最低需求。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5+10;
int a[10][10];
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            cin>>a[i][j];
        }
    }
    int x,y;
    x=min(a[1][1],a[1][2]);
    y=min(a[1][3],a[1][4]);
    if(x+y<=n){
        cout<<1<<' '<<x<<' '<< n-x;
        return 0;
    }
    x=min(a[2][1],a[2][2]);
    y=min(a[2][3],a[2][4]);
    if(x+y<=n){
        cout<<2<<' '<<x<<' '<< n-x;
        return 0;
    }
    x=min(a[3][1],a[3][2]);
    y=min(a[3][3],a[3][4]);
    if(x+y<=n){
        cout<<3<<' '<<x<<' '<< n-x;
        return 0;
    }
    x=min(a[4][1],a[4][2]);
    y=min(a[4][3],a[4][4]);
    if(x+y<=n){
        cout<<4<<' '<<x<<' '<< n-x;
        return 0;
    }
    cout<<-1;
    return 0;
}

F.

大意：
给定一组数，（循环式），可选任一个位置开始，给出间隔k，一轮总量是这几个位置上的值相加，问从哪个位置开始使得值最小。

思路：
枚举可以开始的位置：0-k，
数组下标从0开始，这样把位置取个数的模达到循环的作用，
一轮取的个数：n/k

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll mi=1e9;
    int f=0;
    ll sum,tt;
    for(int i=0;i<k;i++){
        sum=0;
        tt=i;
      //  cout<<"i="<<i<<endl;
      //  cout<<"n/k-1="<<n/k-1<<endl;
       // cout<<"tt="<<tt<<endl;
        sum+=a[tt];
       // cout<<"sum="<<sum<<endl;
        for(int j=1;j<=n/k-1;j++){
            tt+=k;
            sum+=a[tt%n];
         //   cout<<"tt%n="<<tt%n<<endl;
           // cout<<"sum="<<sum<<endl;
        }
        if(sum<mi) {
            mi = sum;
            f = i;
        }
    }
    cout<<f+1;
    return 0;
}

G.

大意：
有n种水果，每种水果有对应的taste和cal，要求选m种水果后taste之和除以cal之和等于k。
问taste之和最大是多少。

思路：
把公式变形，得到（taste-k * cal）之和为0。
将（taste-k * cak)看作体积，
taste看作价值，
装满背包，求最大价值。
正负数分开作两个背包，
相同体积的则满足条件（相减为0）。
最后遍历一遍求最大值。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=2e5+10;
const int mod=1e9;
#define inf 0x3f3f3f3f;
int dp[2][100010];
int x,j,ans,n,k,i,a[110],b[110];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    for(i=0;i<2;i++)
        for(j=1;j<100010;j++)
            dp[i][j]=-1*inf;
    dp[0][0]=dp[1][0]=0;
    cin>>n>>k;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<n;i++){
        cin>>b[i];b[i]=a[i]-b[i]*k;
    }
    for(i=0;i<n;i++){
        if(b[i]>0){
            for(j=100005;j>=b[i];j--){
                dp[0][j]=max(dp[0][j],dp[0][j-b[i]]+a[i]);
            }
        }else{
            x=-1*b[i];
            for(j=100005;j>=x;j--){
                dp[1][j]=max(dp[1][j],dp[1][j-x]+a[i]);
            }
        }
    }
    ans=0;
    for(i=0;i<=100005;i++)ans=max(ans,dp[0][i]+dp[1][i]);
    if(ans==0)cout<<-1;
    else cout<<ans;
    return 0;
}

H.

大意：
给出一个n个点m条边的无向图，每条边有区间l-r，求从1到n路径组成的边集，使该边集中所有区间的交内的正整数元素个数最多。

思路：
dfs深搜，要剪枝。
每个结点结构体存区间信息。
剪枝1：已经更新过的区间比现区间大，不合理过了，剪掉。
剪枝2：现区间比已知答案还小，不是最优解，剪掉。
剪枝3：已经访问过的节点剪掉。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e3+10;
const int mod=1e9;
int n,m;
struct node{
    int v,le,ri;
};
vector<node> g[N];
int ma;
int vis[N],vx[N],vy[N];
void dfs(int u,int l,int r){
    if(u==n){
        ma=max(ma,r-l+1);
        return ;
    }
    for(auto t:g[u]){
        int vv=t.v,left=t.le,right=t.ri;
        if(vis[vv])continue;
        vis[vv]=1;
        int lll=max(l,left),rrr=min(r,right);
        if(vx[vv]<=lll&&vy[vv]>=rrr){
            vis[vv]=0;
            continue;
        }
        if(lll<=rrr&&rrr-lll+1>ma) {
            vx[vv] = lll;vy[vv] = rrr;
            dfs(vv, lll, rrr);
        }
        vis[vv] = 0;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int a,b,l,r;
    while(m--){
        cin>>a>>b>>l>>r;
        g[a].push_back({b,l,r});
        g[b].push_back({a,l,r});
    }
    dfs(1,1,1e9);
    if(ma==0)cout<<"Nice work, Dima!";
    else cout<<ma;
    return 0;
}