Acwing.第130场周赛

A.最大数和最小数

思路：

简单模拟，使用max()和min()函数就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int a,b,c;
	cin>>a>>b>>c;
	
	cout<<max(a,max(b,c))<<" "<<min(a,min(b,c))<<endl;
	return ;

}
int main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;

}

B.三元组

题目链接

思路：

如果单纯的模拟肯定会超时5000 * 5000 * 5000这样的时间复杂度一定是会超时的，所以我们再读一遍题意，这时我们就会发现只需要枚举一下y的位置，然后以y的位置为基准，左边枚举x，右边枚举z，这样的时间复杂度就是5000 * 5000了，这样就不会超时了。为了方便，我们还需要再做一个前缀和

代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;
const  int N = 5010;

int n;
int  a[N];
LL s[N];

inline LL getSum(int l, int r)
{
    return s[r-1] - s[l-1];
}


int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", a+i), s[i] = s[i-1] + a[i];

    int x = 1, y = 1, z = 1;
    LL maxSum = -0x3f3f3f3ff3f3f3f;

    for(int yy = 1; yy <= n+1; yy ++)
    {
        LL res1 = -0x1f3f3f3ff3f3f3f, res2 = -0x1f3f3f3ff3f3f3f;
        int tx = 1, tz = 1;
        for(int xx = 1; xx <= yy; xx ++)
        {
            LL tt = getSum(1, xx) - getSum(xx, yy);
            if(res1 < tt)
            {
                res1 = tt;
                tx = xx;
            }
        }

        for(int zz = yy; zz <= n+1; zz ++)
        {
            LL tt = getSum(yy, zz) - getSum(zz, n+1);
            if(res2 < tt)
            {
                res2 = tt;
                tz = zz;
            }
        }

        if(maxSum < res1 + res2)
        {
            maxSum = res1 + res2;
            x = tx, y = yy, z = tz;
        }
    }

    printf("%d %d %d\n", x-1, y-1, z-1);
    //cout << maxSum << endl;

    return 0;
}

C.边的定向

题目链接

思路：

利用搜索，如何能遍历到很多点呢，一定是dfs时候无向边是可以使得u到v的
如何能遍历到最少的点呢，一定是dfs时候无向边是过不去的，也就是说是没有办法使得u到v的

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=300010,M=N*2;
typedef long long ll;
typedef pair<int,int> PII;

int n,m,s;
int h[N],e[M],w[M],ne[M],idx;
std::vector<PII> edge;
bool st[N];
bool st1[N],st2[N];
set<PII> s1,s2;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;

}
void dfs1(int x){
    st1[x]=true;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(st1[j]){
            continue;
        }
        if(w[i]==2){
            s1.insert({x,j});
        }
        dfs1(j);
    }
}
void dfs2(int x){
    st2[x]=true;
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(st2[j]){
            continue;
        }
        if(w[i]==1){
            dfs2(j);
        }
        else if(w[i]==2){
            s2.insert({x,j});
        }
    }
}
void solve(){
    cin>>n>>m>>s;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){
        int f,a,b;
        cin>>f>>a>>b;
        if(f==1){
            add(a,b,1);

        }
        else{
            edge.push_back({a,b});
            add(a,b,2);
            add(b,a,3);
        }
    }
    dfs1(s);
    int cnt=0;
    string res="";
    for(int i=1;i<=n;i++){
        if(st1[i]){
            cnt++;

        }
    }
    for(auto e:edge){
        if(s1.count({e.first,e.second})){
            res+="+";
        }
        else{
            res+="-";
        }
    }
    cout<<cnt<<endl;
    cout<<res<<endl;
    dfs2(s);
    cnt=0;
    res="";
    for(int i=1;i<=n;i++){
        if(st2[i]){
            cnt++;

        }
    }
    for(auto e:edge){
        if(s2.count({e.first,e.second})){
            res+="-";
        }
        else{
            res+="+";
        }
    }
    cout<<cnt<<endl;
    cout<<res<<endl;
    return ;
    
}
int main(){
    int t;
    t=1;
    
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}