Solutions to CSP-S 2021 Programming Competition Problems

Problem 1 Solution

The problem involves resource allocation between two regions. If we precompute f₁, f₂, ..., fₘ₁ where fᵢ represents the maximum number of resources allocated to the domestic region with i resources, then fᵢ₊₁ will always include the resources selected in fᵢ. Similarly, we define gᵢ for the international region.

The solution is then max(fᵢ + gₙ₋ᵢ) for i ∈ [0, n].

The task now is to compute f and g arrays. Since fᵢ₊₁ includes all resources from fᵢ, we can use a greedy approach with binary search to select intervals.

Time complexity: O(n log n)

Problem 3 Solution

This problem is simpler than problem 2. I initially considered a greedy approach that was incorrect but still scored 96 points. The approach was based on the false assumption that there would always be a sequence of consecutive numbers 1, 2, 3, ..., n appearing in the result, and if a solution exists, it would be on the right side.

After analyzing the problem, I noticed that the first operation has only two possible choices. Although this might seem counterintuitive as it could lead to nested structures, this problem doesn't follow that pattern. After the first operation, the remaining sequences are separated and can only be operated on from both ends.

I'll only discuss the case where we initially choose the left end. We use two double-ended queues to record numbers that pair with a specific value, then check the front and back of these queues while paying attention to the order of checks.

#include 
#define debug puts("Algorithm implemented successfully");
#define pb push_back
using namespace std;
template inline void read(T& t){
    t=0; register char ch=getchar(); register int fflag=1;
    while!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
    while(('0'<=ch&&ch<='9')){t=t*10+ch-'0'; ch=getchar();} t*=fflag;
}
template  inline void read(T& t, Args& ...args){read(t);read(args...);}
const int MAXN=3000086;
int n,d[MAXN],a[MAXN],b[MAXN],t[MAXN];
dequeq1,q2;
bool check(int pos){
    string ans="",ans1="L";
    ans+=(pos==1)?'L':'R';
    while(!q2.empty())q2.pop_back();
    while(!q1.empty())q1.pop_back();
    if(pos==1){
        for(int i=2;it[1];--i) q2.pb(i);
    }else{
        for(int i=1;it[2*n];--i) q2.pb(i);
    }
    while(!q1.empty()||!q2.empty()){
        int x=0,y=0,xx=0,yy=0;
        if(!q1.empty()) x=q1.front(),xx=q1.back();
        if(!q2.empty()) y=q2.front(),yy=q2.back();
        if(x&&xx==t[x]){
            q1.pop_front(); 
            q1.pop_back();
            ans+='L';ans1+='L';
            continue;
        }
        if(x&&yy==t[x]){
            q1.pop_front(); 
            q2.pop_back();
            ans+='L';ans1+='R';
            continue;
        }
        if(y&&xx==t[y]){
            q2.pop_front(); 
            q1.pop_back();
            ans+='R';ans1+='L';
            continue;
        }
        if(y&&yy==t[y]){
            q2.pop_front(); 
            q2.pop_back();
            ans+='R';ans1+='R';
            continue;
        }
        return 0;
    }
    cout<=0;--i) cout<

#include
const int A=360000,B=1210000,INF=1000000000; 
using namespace std;
int n,m,s,t,T,to[A][2],is[A],hd[A],hu[A],lvl[A],qwq[A],tl,van;
struct edge
{
    int to,nt,cap;
}e[B];
void add(int u,int v,int w)
{
    e[tl].to=v,e[tl].nt=hd[u],e[tl].cap=w;
    hd[u]=tl++;
}
bool bfs()
{
    for(int i=0;i0&&lvl[u]+10&&lvl[u]+1==lvl[v])
        {
            int c=dfs(v,min(e[z].cap,f));
            e[z].cap-=c,f-=c,e[z^1].cap+=c,res+=c;
            if(!f)break; 
        }
    }
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for(int i=0,ti=0;i+1=0;--i)hd[i]=-1;
        for(int i=0,ti=0;i+1