NOIP2023 国庆集训 A 组 Day4

A. 石子合并(gouli)

• 优先队列，记得ull。
  考试看错题了

#include 
using namespace std;
unsigned long long ans;
priority_queue q;
unsigned long long a, b, n;
int main() {
    freopen("gouli.in", "r", stdin);
    freopen("gouli.out", "w", stdout);
    cin >> n;
    for(int i=1; i>a;
        q.push(a);
    }
    n--;
    while (n--) {
        a = q.top();
        q.pop();
        b = q.top();
        q.pop();
        ans += a * b;
        q.push(a + b);
    }
    cout << ans;
    return 0;
}

B. 货物收集(aia_iai)

二分答案Ans,O(n)判断即可。

#include 
using namespace std;
int n,u,v,no;
long long W,w,sum;
long long l=1,r,mid;
struct note {
    int v;
    long long w;
} now;
vector mp;
vector f;
vector adj;
queue q;
bool bfs(long long as) {
    f.clear();
    f.resize(n+3);
    sum=0;
    f[1]=1;
    q.push(1);
    while(!q.empty()) {
        no=q.front();
        q.pop();
        for(int i=adj[no].size()-1; i>=0; i--) {
            if(adj[no][i].w=W)
    return true;
    else
    return false;
}
int main() {
    freopen("aia_iai.in", "r", stdin);
    freopen("aia_iai.out", "w", stdout);
    cin>>n>>W;
    mp.resize(n+3);
    adj.resize(n+3);
    for(int i=2; i>mp[i];
    for(int i=1; i>u>>v>>w;
        r=max(r,w);
        now.v=v;
        now.w=w;
        adj[u].push_back(now);
        now.v=u;
        adj[v].push_back(now);
    }
    while(l>1;
        if(bfs(mid))
            r=mid;
        else
            l=mid+1;
    }
    cout<<l;
    return 0;
}

D. 雨中池塘(pool)

• 暴力

#include 
using namespace std;
int n,q;
long long now,ans;
long long qwq;
vector l;
int main() {
    freopen("pool.in", "r", stdin);
    freopen("pool.out", "w", stdout);
    cin>>n>>q;
    for(long long i=1; i<=n; i++)
        l.push_back(0);
    while(q--) {
        scanf("%lld",&now);
        ans=0;
        for(int i=0; i<n; i++) {
            l[i]+=now;
            qwq=i+1;
            if(l[i]<0)
                l[i]=0;
            else
                l[i]=min(l[i],qwq);
            ans+=l[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

In short

• 多练，认真审题