NOIP2023 国庆集训 A 组 Day3

A. 最短路上（count）

• 使用 Floyed 算法预处理最短路，查询时枚举中间点判断即可。

~~考试Floyed写挂了，只有30pts~~

#include 
using namespace std;
const int inf=1000001;
int n,m,q;
int a,b;
int mp[1001][1001];
int dis[1001][1001];
pair que[6001];
int main() {
    freopen("count.in", "r", stdin);
    freopen("count.out", "w", stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            dis[i][j]=inf;
    for(int i=1; i>a>>b;
        mp[a][b]=mp[b][a]=1;
        dis[a][b]=dis[b][a]=1;
    }

    cin>>q;
    for(int i=1; i>que[i].first>>que[i].second;
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(i!=j && i!=k && j!=k)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1; i<=q; i++) {
        int ans=2;
        for(int j=1; j<=n; j++)
            if(j!=que[i].first && j!=que[i].second)
                if(dis[que[i].first][j]+dis[j][que[i].second]==dis[que[i].first][que[i].second])
                    ans++;
        cout<<ans<<endl;
    }
    return 0;
}

B. 古老谜题（puzzle）

• 考试暴力砸出53pts

#include 
using namespace std;
int idx,n;
string s;
long long qwq;
long long ans;
long long num;
long long sum[1000001][3];
int main() {
    freopen("puzzle.in", "r", stdin);
    freopen("puzzle.out", "w", stdout);
    cin>>idx>>n>>s;
    for(int i=0; i<n; i++) {
        if(i!=0) {
            sum[i][0]=sum[i-1][0];
            sum[i][1]=sum[i-1][1];
        }
        if(s[i]=='1')
            num++;
        sum[i][num&1]++;
    }
    qwq=num;
    num=0;
    for(int i=0; i<n; i++) {
        if(s[i]=='1') {
            if(num!=0)
                ans+=sum[n-1][num&1]-sum[i][num&1];
            num++;
            continue;
        }
        ans+=sum[n-1][(num+1)&1]-sum[i][(num+1)&1];
        if(num<qwq)
            ans--;
    }
    cout<<ans;
    return 0;
}

C. 礼物购买（present）

• 二分查找，考试写挂了，TLE，20pts
  附上自己20pts代码：

#include 
using namespace std;
int n,m;
struct note {
    long long v;
    long long x;
    long long sum;
    long long as;
} g[100001];
bool cmp(note x,note y) {
    return x.v>y.v;
}
long long w,now;
long long ans;
bool f;
int l,r,mid;
int main() {
    freopen("present.in", "r", stdin);
    freopen("present.out", "w", stdout);
    cin>>n>>m;
    for(int i=1; i>g[i].v>>g[i].x;
    sort(g+1,g+n+1,cmp);
    for(int i=1; i>w;
        now=0;
        ans=0;
        f=0;
        while(w>=g[n].v && now<=n) {
            if(!f) {
                l=0,r=n;
                while(l<r) {
                    mid=(l+r+1)/2;
                    if(g[mid].sum<=w)
                        l=mid;
                    else
                        r=mid-1;
                }
                w-=g[l].sum;
                ans+=g[l].as;
                now=l+1;
                f=1;
            } else {
                l=0,r=g[now].x;
                while(l<r) {
                    mid=(l+r+1)/2;
                    if(g[now].v*mid<=w)
                        l=mid;
                    else
                        r=mid-1;
                }
                w-=g[now].v*l;
                ans+=l;
                now++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

In a word

• 改题后第一题、第二题AC，第三题改不动，220收尾