銀川選拔賽補題

我菜得很抱歉，，

A、查詢區間眾數出現次數
運用離線查詢的思想，莫隊演算法模版題，可以作為莫隊演算法板子，代碼上有備注～

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define pb push_back
#define endl '\n'
using namespace std;
const int maxn=1e5+7;
struct Q{
    int l,r;
    int idx;
}q[maxn];
int pos[maxn];//分組編號
int a[maxn];//查詢陣列
int ans[maxn];//最終結果記錄
bool cmp(Q a,Q b){
    if(pos[a.l]!=pos[b.l]){
        return pos[a.l]<pos[b.l];
    }
    else{
        return a.r<b.r;
    }
}
int res=0;
int numcnt[maxn];//某個數的出現次數
int cntcnt[maxn];//區間內出現某個次數的數的個數
void add(int pos){
    //加入一個元素
    int t=a[pos];
    numcnt[t]++;//當前數的出現次數++
    cntcnt[numcnt[t]]++;//出現次數的次數++
    if(numcnt[t]>res){
        res=numcnt[a[pos]];
    }
}
void sub(int pos){
    int t=a[pos];
    cntcnt[numcnt[t]]--;//被刪去的元素的出現次數的出現次數
    if(res==numcnt[t]&&cntcnt[numcnt[t]]==0){
        res--;//如果當前答案的出現次數變成0了，就讓它--
    }
    numcnt[t]--;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].idx=i;
    }
    int siz=sqrt(n);
    for(int i=1;i<=n;i++){
        pos[i]=i/siz;
    }
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(q[i].l<l) add(--l);
        while(q[i].r>r) add(++r);
        while(q[i].l>l) sub(l++);
        while(q[i].r<r) sub(r--);

        ans[q[i].idx]=res;
    }
    for(int i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }   
}

B、pc玩游戲
wuwuwu這個題是個挺好想的二分，

可以看出，隨著查詢次數的變多，抽屜合法能放下的娃娃越來越少，
所以考慮二分答案，查詢最早在什么位置合法放下的娃娃小于k，（要注意放娃娃不能相鄰）

代碼實作如下：
（我本來用set做的結果tle了（2000ms左右），用陣列排序直接過了而且只跑了300ms左右）

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define endl '\n'
using namespace std;
const int maxn=2e5+7;
int a[maxn];
int tp[maxn];
int main(){
   // FAST;
    int n,k,L,m;
    scanf("%d%d%d%d",&n,&k,&L,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&a[i]);
    }
    int temp1=n;
    int temp2=0;
    if(temp1>=L){
        temp1-=L;
        temp2++;
    }
    temp2+=temp1/(L+1);
    if(temp2<k){
        cout<<0<<endl;
        return 0;
    }
    //二分
    int l=1;
    int r=m;
    int temp=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        tp[0]=0;
        for(int i=1;i<=mid;i++){
            tp[i]=a[i];
        }
        tp[mid+1]=n+1;
        sort(tp,tp+mid+2);
        int putin=0;
        for(int i=1;i<=mid+1;i++){
            int nn=tp[i-1];
            int nexx=tp[i];
            int d=nexx-nn-1;
            if(d>=L){
                d-=L;
                putin++;
                putin+=d/(L+1);
            }
        }
        if(putin<k){
            temp=mid;
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<temp<<endl;
}

C、pc買禮物

這是個dp，算方案數的dp（之前寫過類似的，只不過那個是一維的而已，，），因為方案不同的判定條件為路徑不同/攜帶禮物不同，所以dp陣列記錄到達的某點編號和當前禮物價值，（因為給出的單向邊都是小節點指向大節點，直接按節點編號dp就行，不然還得拓撲序），

思考一下，只需要記錄當前總價值和當前所在節點就可以確定方案數，

代碼實作：

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define pb push_back
#define endl '\n'
using namespace std;
//在圖上dp
const int maxn=2e3+7;
const int mod=998244353;
vector<int> mp[maxn];
ll dp[maxn][maxn];
ll w[maxn];
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        //a->b有一條有向邊
        //只要記錄某個點從哪來
        mp[b].pb(a);
    }
    dp[1][0]=1;
    dp[1][w[1]]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<mp[i].size();j++){
            int t=mp[i][j];
            for(int x=0;x<=k;x++){
                dp[i][x]=(dp[i][x]+dp[t][x])%mod;
                if(x-w[i]>=0){
                    dp[i][x]=(dp[i][x]+dp[t][x-w[i]])%mod;
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=k;i++){
        ans=(ans+dp[n][i])%mod;
    }
    cout<<ans<<endl;
}

D、game
sb思維題，直接判斷奇偶，就不放代碼了，

E、median
這也是水題，
比賽的時候沒看懂這“排列”的意思，，，，，原來v只會出現一次，，b瞎寫了好久，絕了，一開始第一眼的思路就是對的，

因為要形成一個v是中位數的陣列，那么陣列中大于v和小于v的數量必須相等，

直接在陣列中找到v的位置，看v之前任一段序列中有多少大于v的，多少小于v的，記錄每個點到v形成的序列大于v和小于v的個數的差值，然后記錄這個差值出現的次數，（別忘了前后各自有個位置是0，0）
v之后的序列一樣處理，

然后前后組合就好了，

代碼實作：

#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define endl '\n'
using namespace std;

const int maxn=1e5+7;
int a[maxn];
map<int,ll> mp1,mp2;//分別記錄前后綴差值資訊
int main(){
    int n,v;
    scanf("%d%d",&n,&v);
    int i0=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==v){
            i0=i;
        }
    }
    int cntb=0;
    int cnts=0;
    mp1[0]++;
    mp2[0]++;
    for(int i=i0-1;i>=1;i--){
        if(a[i]<v){
            cnts++;
        }
        else{
            cntb++;
        }
        mp1[cnts-cntb]++;
    }
    cntb=0;
    cnts=0;

    for(int i=i0+1;i<=n;i++){
        if(a[i]<v){
            cnts++;
        }
        else{
            cntb++;
        }
        mp2[cnts-cntb]++;
    }
    ll ans=0;
    for(int i=0;i<=n;i++){
        //cout<<mp1[i]<<' '<<mp[-i]<<endl;
        ans+=mp1[-i]*mp2[i];
        if(i!=0)
            ans+=mp1[i]*mp2[-i];
    }
    printf("%lld\n",ans);
}

F、重建網路

這個題挺有意思的，開始和學長討論還以為這個是個假題，后來看了題解的解釋，才發現這個題的妙處，

思路就是對給出的無向圖跑一次最大生成樹，如果用到的邊有小于k的，那么答案sum（小于k的且用到的邊-k），
如果用到的邊都大于k，答案就是所有的邊與k最小的差值，（為什么呢？）
通過思考可以發現，當前已經形成樹了，如果與k差值最小的那個邊不在樹上，可以直接替換上去，（刪去換上去的邊兩節點（a，b）任意點與集合相連的那個邊即可）

（非主流最大生成樹寫法，，，堆優化prim，邊權全部取負數）

代碼實作：

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define pb push_back
#define endl '\n'
using namespace std;

const int maxn=1e5+7;
const int maxm=2e5+7;

struct edge{
    int to;
    ll w;
};
vector<edge> mp[maxn];

typedef pair<ll,int> P;//first為距離，second為編號

bool vis[maxn];
ll dis[maxn];

int n,m;
ll k;
ll cntedge[maxn];
ll ed[maxm];

int cnt=0;

void prim(){
    //最大生成樹
    priority_queue<P,vector<P>,greater<P> >q;
    q.push({0,1});//隨便讓一個點入隊；
    while(q.size()){
        P t=q.top();
        q.pop();
        ll w0=t.first;
        ll v0=t.second;
        //cout<<"w0="<<w0<<endl;
        if(vis[v0]) continue;
        vis[v0]=1;
        if(w0!=0)
            cntedge[++cnt]=-w0;
        for(int i=0;i<mp[v0].size();i++){
            edge e=mp[v0][i];
            q.push({e.w,e.to});
        }
    }
    
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int a,b;
        ll c;
        cin>>a>>b>>c;
        mp[a].pb({b,-c});//建圖用負邊權
        mp[b].pb({a,-c});
        ed[i]=c;
    }
    prim();
    ll ans=0;
    int flag=0;
    ll minn=1e15;
    for(int i=1;i<=cnt;i++){
        //cout<<"cntedge="<<cntedge[i]<<endl;
        if(cntedge[i]<k){
            flag=1;
            ans+=abs(k-cntedge[i]);
            //cout<<"abs="<<abs(k-cntedge[i])<<endl;;
        }
    }
    
    //cout<<"flag="<<flag<<endl;
    if(flag==1){
        cout<<ans<<endl;
    }
    else{
        for(int i=1;i<=m;i++){
            minn=min(minn,abs(k-ed[i]));
        }
        cout<<minn<<endl;
    }
}

G

H、pc要出題

對不起對不起對不起我以為1e7陣列會爆硬是用了map查詢，然后把我tle到傻，又被容器坑了一把，
問了大佬同學，他說如果map用下標查詢原本不存在的節點，會現場建一個節點，時間成本較大，所以建議用find查詢map，
要兩個數的和能除盡k，那么就是兩個數取模和等于k，就是個sb題，
（這里分享兩種寫法）

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <stdlib.h>
#include <time.h>
#include <vector>
#define FAST ios::sync_with_stdio(false);
#define INF 0x3f3f3f3f
#define ll long long
#define endl '\n'
using namespace std;
ll cnt[10000007];
int a[1000007];
bool vis[100000007];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll temp;
        scanf("%lld",&temp);
        temp%=k;
        //a[i]=k;
        cnt[temp]++;
    }
    for(int i=0;i<k;i++){
        if(vis[i]==1) continue;
        if(i==0|k-i==i){
        //記得特判
            ans+=cnt[i]*(cnt[i]-1)/2;
            vis[i]=1;
        }
        else{
            ans+=cnt[i]*cnt[k-i];
            vis[i]=1;
            vis[k-i]=i;
        }
    }
    printf("%lld\n",ans);
}

int cnt[10000007];
int a[1000007];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    ll temp;
    ll ans=0;
    while(n--){
        scanf("%lld",&temp);
        temp%=k;
        if(temp==0){
            ans+=cnt[0];
        }
        else{
            ans+=cnt[k-temp];
        }
        cnt[temp]++;
    }
    printf("%lld\n",ans);
    return 0;
}

（還有一個dp沒寫，寫完馬上補上題解）