21st UESTC Programming Contest - Preliminary except BCGIKMNPR

OK,那么长的except那我到底写了什么呢 （悲，太菜啦）

A. 能量采集

dp+组合数的应用

用dp[i] [j] [p] 表示在(i,j)这个点以连续个p结尾的路径数

1.首先对于每一个A 到达这个格子的方案数是 {n-i+m-j \choose n-i}

2.对于每一个A的p状态 都可以从上方和左方的p-1状态转移得到

遍历dp的k状态数组 对答案的贡献就是这个dp[i] [j] [p]的值*{n+m-2 \choose n-1}

时间复杂度为 O(nmk+nlogn)

#define ll long long
char a[N][N];
int dp[N][N][N*2],fact[N*2],infact[N*2];
int qmi(int a, int k, int p)  {
    int res = 1;
    while (k){
        if (k & 1) res =res * a % p;
        a =a * a % p;
        k >>= 1;
    }
    return res;
}
void solve(){
    int n=read(),m=read(),k=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='A'){
                dp[i][j][1]=fact[i+j-2]*infact[i-1]%mod*infact[j-1]%mod;
                for(int h=2;h<=k;h++){
                    dp[i][j][h]=(dp[i-1][j][h-1]+dp[i][j-1][h-1])%mod;
                }
            }
        }
    }
    int fenzi=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            (fenzi+=(dp[i][j][k]*fact[n+m-i-j]%mod*infact[n-i]%mod*infact[m-j]%mod))%=mod;
        }
    }
    cout<<fenzi*infact[n+m-2]%mod*fact[n-1]%mod*fact[m-1]%mod<<'\n';
}

signed main(){
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N*2; i ++ ){
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int t=1;
    while(t--){
        solve();
    }
}

D. 小美爱画鱼

void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i].x=read(),a[i].y=read(),a[i].xx=read(),a[i].yy=read();
        a[i].k=a[i].x+a[i].y;
    }
    sort(a+1,a+1+n);
    int ans=1,sum=0,last=0;
    sum+=a[1].xx-a[1].x;
    last=a[1].xx;
    for(int i=2;i<=n;i++){
        if(a[i-1].k==a[i].k&&last>a[i].x){
            ans=-1;
            sum+=max(0,a[i].xx-last);
            last=max(a[i].xx,last);
        }
        else {
            sum+=a[i].xx-a[i].x;
            if(a[i-1].k!=a[i].k){
                last=a[i].xx;
            }else last=max(a[i].xx,last);
        }
    }
    puts(ans>0?"YES":"NO");
    cout<<sum<<'\n';
}

E. 小团来打字

map<int,int>mp;
void solve(){
    int n=read(),k=read();
    vector<PII>a;
    for(int i=1;i<=n;i++){
        int x=read();
        int y=read();
        if(a.size()&&x==a.back().first){
            a.back().second+=y;
        }else {
            a.push_back({x,y});
        }
    }
    for(auto x:a){
        mp[x.first]+=x.second+(x.second-1)/k*k;
    }
    cout<<mp.size()<<'\n';
    for(auto i=mp.begin();i!=mp.end();i++){
        cout<<i->first<<" "<<i->second<<'\n';
    }
}

F. 炸弹鸭

离线处理 将询问和输入的边都按照k值排序 处理询问时只将k值小于询问k值的边加入图 记录各度数的顶点数 量 如果度数大于炸弹数就可以逃脱 所以答案就是[0,d]的前缀和

用树状数组对每次加边的两个端点的度数统计进行修改 两个点原本的度数都要-1 新度数都要+1

时间复杂度小于等于 O((m+q)logn)

#define int long long
struct node{
    int x,y,k;
    friend bool operator<(const node&a,const node&b){
        return a.k<b.k;
    }
}edge[N];
struct edon{
    int d,k,id;
    int ans;
    friend bool operator<(const edon&a,const edon&b){
        return a.k<b.k;
    }
}que[N];
int cnt[N],tr1[N];
int n;
int lowbit(int x){
    return x & -x;
}
void add(int tr[], int x, int c){
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
int sum(int tr[], int x){
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
bool cmp(edon a,edon b){
    return a.id<b.id;
}
void solve(){
    n=read();
    int m=read(),q=read();
    for(int i=1;i<=m;i++){
        edge[i].x=read(),edge[i].y=read(),edge[i].k=read();
    }
    for(int i=1;i<=q;i++){
        que[i].d=read(),que[i].k=read(),que[i].id=i;
    }
    sort(edge+1,edge+1+m);
    sort(que+1,que+1+q);
    add(tr1,1,n);
    int now=0;
    for(int i=1;i<=q;i++){
        int d=que[i].d,k=que[i].k;
        for(int j=now+1;edge[j].k<=k&&j<=m;j++){
            now=j;
            int x=edge[j].x,y=edge[j].y;
            add(tr1,cnt[x]+1,-1);
            add(tr1,cnt[y]+1,-1);
            cnt[x]++;
            cnt[y]++;
            add(tr1,cnt[x]+1,1);
            add(tr1,cnt[y]+1,1);
        }
        que[i].ans=sum(tr1,d+1);
    }
    sort(que+1,que+1+q,cmp);
    for(int i=1;i<=q;i++){
        cout<<que[i].ans<<'\n';
    }
}

H. 约瑟夫问题

加强后的传统问题 可以构造一个线段树 每次处理前缀和（活着是1 死了修改为0）用二分寻找到最小位置的前缀和符合要求就可以了

时间复杂度大概在 O(nlog^2n)

int n, m, w[N];
struct Node{
    int l, r;
    int sum, lmax, rmax, tmax;
}tr[N * 4];
void pushup(Node &u, Node &l, Node &r){
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}                     
void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r){                          
    if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else{
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int x, int v){   
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}
Node query(int u, int l, int r){
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else{
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}
bool check(int x,int k) {
    if(query(1,1,x).sum>=k)return true;
    else return false;
}
int bs1(int l, int r,int k){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid,k)) r = mid;    
        else l = mid + 1;
    }
    return l;
}
void solve(){
    n=read(),m=read();
    int cnt=n;
    for (int i=1;i<=n;i++) w[i]=1;
    build(1, 1, n);
    int last=1;
    while(m--){
        int k=(read()-1+last-1)%n+1;
        last=k;
        int ans=bs1(1,cnt,k);
        ans=(ans-1)%cnt+1;
        cout<<ans<<'\n';
        modify(1,ans,0);
        n--;
    }
}

J. 数矩形

考虑穷举对角线 如果两个对角线的长度和中点相同就可以构成矩形 用map计数

pair<double,double> d[N];
map<pair<pair<double,double>,double>,int>mp;
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
       cin>>d[i].first>>d[i].second;
    }
    sort(d+1,d+1+n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            double x=(d[j].first+d[i].first)/2;
            double y=(d[j].second+d[i].second)/2;
            double len=fabs(fabs(d[i].first-d[j].first)*fabs(d[i].first-d[j].first)+fabs(d[i].second-d[j].second)*fabs(d[i].second-d[j].second));
            mp[{{x,y},len}]++;
        }
    }
    int ans=0;
    for(auto [y,x]:mp){
        ans+=(x-1)*x/2;
    }
    cout<<ans<<'\n';
}

L. 树边重排

从n开始dfs 记录每个点的父亲即可

int h[N], e[N], ne[N], idx, ans[N];
bool st[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u){
    st[u] = true; 
    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];
        if(!st[j]) ans[j]=u,dfs(j);
    }
}
void solve(){
    int n=read();   
    idx = 0;    memset(h, -1, sizeof h);
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(n);
    for(int i=1;i<n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<'\n';
}

O. 爬塔

#define int long long
int sum[N],a[N];
void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
    }
    int ans=0,now=1;
    for(int i=1;i<=n;i++){
        if(now<a[i]){
            ans+=(a[i]-1-now)/(1+sum[i-1])+1;
            now=now+(1+sum[i-1])*((a[i]-1-now)/(1+sum[i-1])+1)+a[i];
        }
        else now+=a[i];
    }
    cout<<ans<<'\n';
}

Q. Du Cuo Ti Le

void solve(){
    int n=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read();
    }
    cout<<"1 "<<2*n-1<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}