T1

link

Đây là một bài toán khá đơn giản, có thể giải ngay bằng phương pháp quét đường, nhưng đáng tiếc là cách tiếp cận đó gây ra TLE, chỉ đạt được 80 điểm. Giải pháp thực sự lại đơn giản đến bất ngờ.

Có thể giải bài này bằng cách duyệt từ cuối về đầu một vòng lặp 1e7, mỗi lần cộng thêm giá trị lớn nhất.

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define benh now<<1
#define phai now<<1|1
const ll N=20000005,MAX=1919810,inf=1145141919;
ll n,maxn[N];
struct diem{
    ll x,y;
}a[N];
int main(){
    //freopen("bai1.in","r",stdin);
    //freopen("bai1.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i].x>>a[i].y,a[i].x/=2,a[i].y/=2,maxn[a[i].x]=max(maxn[a[i].x],a[i].y);
    ll ketqua=0,y=0;
    for(int i=1e7;i>=1;--i)
        y=max(y,maxn[i]),ketqua+=y;
    cout<<ketqua*4;
    return 0;
}

T2

link

Trong cuộc thi, tôi đã đưa ra một giả định sai và chỉ được 15 điểm. Sau này nhận ra đây là một bài toán tập hợp hợp lệ rất đơn giản!

Bài toán có thể chuyển thành điều kiện \(dis_u \oplus dis_v=x\), với \(dis_i\) là tổng tiền tố XOR từ nút i đến gốc.

Tập hợp hợp lệ duy trì các nút chứ không phải các cạnh như tôi nghĩ. Cuối cùng, số lượng gốc trong tập hợp hợp lệ chính là \(2^{n-1}\). Cần lưu ý trường hợp không có lời giải.

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define caphe make_pair
const ll N=1145140,MAX=1919810,modulo=1e9+7;
ll n,Q;
ll mu(ll a,ll b){
    ll ketqua=1;
    while(b){
        if(b&1) ketqua=ketqua*a%modulo;
        a=a*a%modulo;
        b>>=1;
    }
    return ketqua%modulo;
}
ll f[N],dis[N];
ll find(ll x){
    if(x==f[x]) return x;
    else{
        ll pos=f[x];
        f[x]=find(f[x]);
        dis[x]=dis[x]^dis[pos];
        return f[x];
    }
}
void hopnhat(ll x,ll y,ll z){
    ll a=find(x),b=find(y);
    f[b]=a;
    dis[b]=dis[x]^dis[y]^z;
}
int main(){
    freopen("bai2.in","r",stdin);
    freopen("bai2.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll ketqua=0,dem=0;
    cin>>n>>Q;
    for(int i=1;i<n;++i){
        ll a,b;
        cin>>a>>b;
    }
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=Q;++i){
        ll u,v,w;
        cin>>u>>v>>w;
        ll x=find(u),y=find(v);
        if(x==y&&dis[u]!=(dis[v]^w)){
            cout<<0;
            return 0;
        }
        if(x!=y) hopnhat(u,v,w);
    }
    for(int i=1;i<=n;++i)
        if(find(i)==i) ++dem;
    cout<<mu(2,dem-1);
    return 0;
}

T3

link

Bài toán quy hoạch động, tôi không thể giải được. Đây thực sự là vấn đề về năng lực, cần phải luyện tập nhiều bài và làm kỹ từng bài.

Quay lại bài toán, trước hết thảo luận về giải pháp DP 70 điểm. Đặt \(dp_{i,j,k}\) là thời gian làm việc nhỏ nhất khi đã xử lý xong i công việc, máy 1 còn j thời gian, máy 2 còn k thời gian.

Chuyển trạng thái: công việc thứ i chuyển từ \(dp_{i-1,j,k}\), khi đặt trên máy 1 thì chuyển thành \(dp_{i,t1,t2}=\min(dp_{i,t1,t2},dp_{i-1,j,k}+cost)\).

Nếu máy 1 cần nhiều thời gian hơn, cần xem xét trường hợp đặc biệt: if(j>=k) cost=a[i],t1=a[i],t2=0;

Hoặc nếu máy 2 cần nhiều thời gian hơn: if(j+a[i]<=k) cost=0,t1=j+a[i],t2=k;

Chuyển trạng thái thông thường là: cost=j+a[i]-k,t1=j+a[i]-k,t2=0;

Trường hợp đặc biệt: nếu thời gian hoàn thành máy 1 đã muộn hơn máy 2, khi vẫn giao việc cho máy 1, hiệu suất thời gian giữa hai máy sẽ trở thành \(a_i\), không phải cộng \(a_i\) vào \(j\) ban đầu, vì cần đợi công việc trước trên máy 1 hoàn thành rồi mới bắt đầu trên máy 2.

Chuyển trạng thái cho máy 2 tương tự. Độ phức tạp tổng thể là \(O(nm^2)\), với \(m\) là thời gian hoàn thành tối đa của một công việc.

30 điểm còn lại yêu cầu độ phức tạp \(O(nm)\), cần nén hai chiều sau thành một chiều bằng cách sử dụng mối quan hệ giữa chúng.

Có thể đặt: \(dp_{i,j}\) là thời gian làm việc nhỏ nhất của máy 1 khi đã xử lý xong i công việc, thời gian còn lại của máy 1 hơn máy 2 là j. Thời gian làm việc của máy 2 có thể tính bằng \(dp_{i,j}+j\).

Lưu ý j có thể âm, nên khi chuyển trạng thái cần cộng thêm thời gian tối đa M.

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define trum make_pair
const ll N=3003,MAX=1919810,modulo=1e9+7;
ll n;
struct congviec{
    ll may1,may2;
}a[N];
ll dp[N][2*MAX+5];
int main(){
    freopen("bai3.in","r",stdin);
    freopen("bai3.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i].may1>>a[i].may2;
    memset(dp,63,sizeof(dp)); dp[0][MAX]=0;
    for(int i=1;i<=n;++i)
        for(int j=0;j<=2*MAX;++j){
            if(j>=MAX){
                dp[i][MAX+a[i].may1]=min(dp[i][MAX+a[i].may1],dp[i-1][j]+a[i].may1);
                dp[i][j-a[i].may2]=min(dp[i][j-a[i].may2],dp[i-1][j]);
            }
            else{
                dp[i][MAX-a[i].may2]=min(dp[i][MAX-a[i].may2],dp[i-1][j]+(MAX-j));
                dp[i][j+a[i].may1]=min(dp[i][j+a[i].may1],dp[i-1][j]+a[i].may1);
            }
        }
    ll ans=modulo;
    for(int i=0;i<=2*MAX;++i) ans=min(ans,dp[n][i]+max(0ll,MAX-i));
    cout<<ans;
    return 0;
}

T4

link

Thật lòng không muốn làm tiếp nữa. Ban đầu tôi thậm chí không thể mô phỏng được ví dụ mẫu. Giải pháp là sử dụng băm, nhưng tôi lại không biết cách băm, nên tạm thời bỏ qua.

Để đó, chuyển sang làm đồ thị thôi.