退役后的咸鱼生活

本来应该有一个退役(游记)总结贴,不过临近期末考了,还是能拖就拖吧

当然刷题还是会接着刷下去的,虽然很菜但还是喜欢啊

(另外自己搞的blog程序希望能在寒假内完成QAQ)

(另另外旧的题解blog应该是不会再更新了)

Codeforces - 671B

题意

给出$n$个人,第$i$人有$a[i]$块钱,共有$k$次操作,每次操作把任意的$max\lbrace a[i]\rbrace$减一,然后把任意的$min\lbrace a[i]\rbrace$加1,求$k$次后的极差,既$max\lbrace a[i]\rbrace-min\lbrace a[i]\rbrace$

范围

$n\le5\cdot10^5,k\le10^9$

分析

显然,当$k​$足够大时,所有人的钱肯定徘徊在$avg=\frac{\sum_{i=1}^{n}a[i]}{n}​$之间

不止如此,可以看出$k$其实是单调的,就是$k$越大,极差越小,并且$max$越小,$min$越大

那就意味着可以根据$k$(可以把加减分开处理)来二分两个答案$max$和$min$,二分的范围分别是$[avg+[sum \mod \ n≠0],max\lbrace a[i]\rbrace]$ 和$[min\lbrace a[i]\rbrace,avg]$

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5+11;
int a[MAXN],n,k;
bool C1(int mid){
    ll res=0;
    for(int i=1;i<=n;i++) res+=max(0,a[i]-mid);
    return res<=k;
}
bool C2(int mid){
    ll res=0;
    for(int i=1;i<=n;i++) res+=max(0,mid-a[i]);
    return res<=k;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    while(~scanf("%d%d",&n,&k)){
        int mx=0,mn=INT_MAX;
        ll sum=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            mx=max(mx,a[i]);
            mn=min(mn,a[i]);
            sum+=a[i];
        }
        int avg=sum%n==0?sum/n:sum/n+1;
        int lo=avg,hi=mx;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(C1(mid)) hi=mid;
            else lo=mid+1;
        }
        int res1=lo;
        lo=mn,hi=sum/n;
        while(lo<hi){
            int mid=lo+(hi-lo+1)/2;
            if(C2(mid)) lo=mid;
            else hi=mid-1;
        }
        int res2=lo;
        printf("%d\n",res1-res2);
    }
    return 0;
}

Codeforces - 1070F

题意

$n$个人为两个人进行选举,每个人有选票$a_i$和影响力$b_i$

$a_i=\lbrace 00,01,10,11\rbrace$,00表示两个均不选,$01$表示投第二个人,$10,11$同理

现在要求从$n$个人中挑选子集,使得$\sum_i b_i$最大且选两个人的票数均超过一半人数

范围

$n\le4\cdot10^5$

分析

首先$11$全都要,比如已经挑了$m$个人,选票情况是$\frac{x}{m}$和$\frac{y}{m}$,选了$11$后$\frac{x+1}{m+1}$和$\frac{y+1}{m+1}$,明显更划算

然后对$01$和$10$讨论,一个保底的策略是一开始就两个分别挑$min\lbrace01,10\rbrace$的数目,这样保证了两边都是$\frac 1 2​$(可以看出两边多一个少一个都不行)

剩下的比如只剩$\lbrace01,00\rbrace$,设$11$的票数是$i$,$10$的票数是$j$,$01$的票数是$j+k$,目前挑了$j$

假设剩下的$01$挑$x$个,$00$挑$y$个,

第一个人变为$\frac{i+j}{i+2\cdot j+x+y}$

第二个人变为$\frac{i+j+x}{i+2\cdot j+x+y}$

现在要求$2(i+j)\ge i+2\cdot j+x+y$ 且$2(i+j+x) \ge i+2\cdot j+x+y$

既$i \ge x+y$

也就是说只要从$\lbrace01,00\rbrace$中不论种类从大到小挑$x+y \le i$个即可

$10​$搭配$00​$的情况同理

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 5e5+11;
int a[MAXN],b[MAXN],n,k;
struct QAQ{
    int val,type,block;
    bool operator < (const QAQ &orz) const{
        return val>orz.val;
    }
}c[MAXN];
string str;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n){
        for(int i=1;i<=n;i++){
            cin>>str;
            if(str=="00") a[i]=0;
            else if(str=="01") a[i]=1;
            else if(str=="10") a[i]=10;
            else a[i]=11;
            cin>>b[i];
        }
        ll ans=0,cnt11=0,cnt10=0,cnt01=0,cnt00=0,cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]==11){
                ans+=b[i];
                cnt11++;
                continue;
            }else if(a[i]==10) cnt10++;
            else if(a[i]==1) cnt01++;
            else cnt00++;
            c[++cnt]=(QAQ){b[i],a[i],0};
        }
        sort(&c[1],&c[cnt]+1);
        int choose=min(cnt01,cnt10),cur01=0,cur10=0;
        for(int i=1;i<=cnt;i++){
            if(cur01>=choose and cur10>=choose) break;
            if(c[i].type==1){
                if(cur01>=choose) continue;
                ans+=c[i].val;
                cur01++;
            }else if(c[i].type==10){
                if(cur10>=choose) continue;
                ans+=c[i].val;
                cur10++;
            }
            else continue;
            c[i].block=1;
        }
        int cur=0;
        for(int i=1;i<=cnt;i++){
            if(cur>=cnt11) break;
            if(c[i].block) continue;
            ans+=c[i].val;
            c[i].block=1;
            cur++; 
        }
        cout<<ans<<endl;
    }
    return 0;
}

Codeforces - 551C

题意

给出$n$堆石头,$m$个人,第$i$堆石头有$a[i]$个石头,且与第$i-1$堆石头$x$轴相比多一,所有人一开始都在原点,每个人能在1秒内要么移动1坐标,要么减少对应坐标下的一个石头,求最少时间使得所有石头被消灭

范围

$1\lt n,m \lt 10^5,0 \le a[i] \le 10^9$

分析

首先要知道时间越长就能消灭越多石头,所以可以二分答案

对于枚举出来的答案,我们去check消灭石头用到的人的最少个数,没用满就意味着可以进一步压缩时间

时间消耗来自两个方面:跑路时间和捡石头时间,只需分别令两方面都最优即可

对于每个人,贪心考虑消灭最远自己能到达的石头个数(因为要捡的石头总数是恒定的),如果富余时间,那就先消灭最接近的几个石头,再跑去消灭目前最后的所有石头(实现上是倒过来完成的),这样比先拿最后再回来耗费跑路时间明显更划算

同时这样能减少下一个人跑路多消耗的最后一段路(前一个人能到达且全灭的最远距离)的时间,也就是越早消灭那段路越省劲,那就是两方面都达到最优

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5+11;
int a[MAXN],b[MAXN],n,m,first,last;
ll sum;
bool C(ll mid){
    ll tot=sum;
    memcpy(a,b,(n+2)*sizeof(int));
    ll cur,used=0,pos=last;
    while(tot>0&&pos>=first){
        used++;
        cur=mid-pos;
        while(cur>0&&pos>=first){
            if(used>m) return 0; //剪枝
            if(cur>=a[pos]){
                tot-=a[pos];
                cur-=a[pos];
                a[pos]=0;
                while(pos>=first&&a[pos]==0) --pos;
            }else{
                a[pos]-=cur;
                tot-=cur;
                cur=0;
            }
        }
    }
    return used<=m;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    while(~scanf("%d%d",&n,&m)){
        sum=0,last=n,first=1;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
            sum+=a[i];
            if(a[i]) last=i;
        }
        for(int i=n;i;--i) if(a[i]) first=i;
        ll lo=last+1,hi=LONG_LONG_MAX;
        while(lo<hi){
            ll mid=lo+(hi-lo)/2;
            if(C(mid)) hi=mid;
            else lo=mid+1;
        }
        printf("%lld\n",lo);
    }
    return 0;
}

last update:2018.11.15

Codeforces - 893E

题意

给出$x,y$,求$\prod_{i=1}^{y}F_i=x$的方案数,其中$F$任取

范围

多组询问$T \le 10^5$

$1 \le x,y \le 10^6$

分析

对$x$进行质因子分解$\prod_i p_i^{k_i}$,那么对于每个$p_i$只需令$F$的质因子指数和对应$k_i$即可

把问题再抽象一点就是求$k_i$个不可区分的球放入$y$个可以为空的盒子的方案数

这个可以用隔板法求得为$k_i+y-1 \choose y-1$

别忘了数值是可以取负数的,所以总方案数还需乘上${y \choose 0} + {y \choose 2} + {y \choose 4} + \cdots$

也就是$2^{y-1}$

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6+11;
const int MOD  = 1e9+7;
bool isprime[MAXN];
int prime[MAXN],cnt;
ll jie[MAXN<<1];
int x,y;
vector<int> p[MAXN],k[MAXN];
void sai(){
    for(int i=2;i<MAXN;i++) isprime[i]=1;
    for(int i=2;i*i<MAXN;i++){
        if(isprime[i]){
            for(int j=2*i;j<MAXN;j+=i){
                isprime[j]=0;
            }
        }
    }
    for(int i=2;i<MAXN;i++){
        if(isprime[i]){
            prime[++cnt]=i;
        }
    }
}
void chai(int val){
    if(p[val].size()) return;
    ll t=val;
    int sqr=sqrt(val+1);
    for(int i=1;i<=cnt&&prime[i]<=sqr;i++){
        if(val%prime[i]==0){
            p[t].push_back(prime[i]);
            k[t].push_back(1);
            val/=prime[i];
            while(val%prime[i]==0){
                val/=prime[i];
                k[t][(int)k[t].size()-1]++;
            }
        }
    }
    if(val!=1){
        p[t].push_back(val);
        k[t].push_back(1);
    }
}
ll fpw(ll a,ll n){
    ll res=1;
    while(n){
        if(n&1) res=res*a%MOD;
        a=a*a%MOD;
        n>>=1;
    }
    return res;
}
inline ll inv(ll a){
    return fpw(a,MOD-2);
}
inline ll C(int all,int choose){
    return jie[all]*inv(jie[choose])%MOD*inv(jie[all-choose])%MOD;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    jie[0]=1;
    for(int i=1;i<MAXN*2;i++) jie[i]=jie[i-1]*i%MOD;
    sai();
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        chai(x);
        ll ans=1;
        for(int i=0;i<p[x].size();i++){
            ans*=C(y+k[x][i]-1,y-1);
            ans%=MOD;
        }
        ans*=fpw(2,y-1);
        ans%=MOD;
        printf("%lld\n",ans);
    }
    return 0;
}

Codeforces - 401D

题意

给出$n,m$,求任意排列$n$各位的数字使得形成的新的数模$m$为$0$的方案数

范围

$1 \le n \le 10^{18}, 1 \le m \le 18$

分析

考虑到$n$的位数$log_{10}n+1$很小,可以直接状压求出来,

设$dp[S][r]$:状态为$S$的数模$m$得到$r$的方案数,每次枚举一个位作为最低位

求出后要对重复的数字进行一次全排列去重

注意要特判前导0

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6+11;
const int MOD  = 1e9+7;
ll jie[233],n,m;
int cnt[233],val[233];
ll dp[1<<18|1][103];
void chai(ll x){
    int tot=0;
    while(x){
        val[tot++]=x%10;
        x/=10;
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    jie[0]=1;
    for(int i=1;i<20;i++) jie[i]=jie[i-1]*i;
    while(~scanf("%lld%lld",&n,&m)){
        memset(cnt,0,sizeof cnt);
        int num=log10(n)+1;
        int S=1<<num;
        chai(n);
        for(int i=0;i<num;i++) cnt[val[i]]++;
        memset(dp,0,sizeof dp);
        dp[0][0]=1;
        for(int i=0;i<S;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<num;k++){
                    if(i>>k&1){
                        if((i^(1<<k))==0&&val[k]==0) continue;
                        dp[i][(j*10+val[k])%m]+=dp[i^(1<<k)][j];
                    }
                }
            }
        }
        ll ans=dp[S-1][0];
        for(int i=0;i<10;i++) ans/=jie[cnt[i]];
        printf("%lld\n",ans);
    }
    return 0;
}

Codeforces - 895C

题意

给定一个数组$a[1 \ldots n]$,从中选定一个可重复元素子集,使得子集内元素的乘积是个平方数,求满足该条件的方案数

范围

$1 \le n \le 10^5, 1 \le a[i] \le 70$

分析

很显然平方数的质因子次数必然是偶数次,且70内的质因子个数只有19个,我们可以枚举19个质因子的次数

需要注意到一个套路是每选定一个元素,其实只影响若干个质因子次数的奇偶性,这样就可以维护了

设$dp[i][S]$,前$i$种元素质因子次数奇偶性状态为$S$的方案数

挑选第$i$种元素需要分别转移选奇数个和偶数个的方案数

答案为$dp[70][0]$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5+11;
const int MOD  = 1e9+7;
int n,a[MAXN],b[233],s[233];
bool isPrime[233];
int prime[233],cnt;
ll dp[2][1<<19|1],_2[MAXN];
void sai(){
    for(int i=2;i<233;i++) isPrime[i]=1;
    for(int i=2;i*i<233;i++){
        if(isPrime[i]){
            for(int j=2;j*i<233;j++){
                isPrime[j*i]=0;
            }
        }
    }
    for(int i=2;i<=70;i++){
        if(isPrime[i]){
            prime[++cnt]=i;
        }
    }
}
void init(int n){
    int tmp=n;
    for(int i=1;i<=cnt;i++){
        while(n%prime[i]==0){
            n/=prime[i];
            s[tmp]^=1<<i-1;
        }
    }
}
#define add(a,b) (a%MOD+b)%MOD
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    sai();
    _2[0]=1;
    for(int i=1;i<MAXN;i++) _2[i]=_2[i-1]*2%MOD;
    for(int i=1;i<=70;i++) init(i);
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(b,0,sizeof b);
        for(int i=1;i<=n;i++) b[a[i]]++;
        memset(dp,0,sizeof dp);
        int S=1<<19; dp[0][0]=1;
        for(int i=1;i<=70;i++){
            if(b[i]==0){
                memcpy(dp[i&1],dp[i-1&1],sizeof dp[0]);
                continue;
            }
            memset(dp[i&1],0,sizeof dp[0]);
            for(int j=0;j<S;j++){
                dp[i&1][j^s[i]]=add(dp[i&1][j^s[i]],dp[i-1&1][j]*_2[b[i]-1]%MOD);
                dp[i&1][j]=add(dp[i&1][j],dp[i-1&1][j]*_2[b[i]-1]%MOD);
            }
        }
        printf("%lld\n",(dp[0][0]-1+MOD)%MOD);
    }
    return 0;
}

Codeforces - 998D

题意

一个特殊的数字系统,每一位只有$\lbrace 1,5,10,50\rbrace$四种可能,且数值为每一位的和,现在给出一个$n$,问一个$n$位数能凑出多少个值

范围

$1 \le n \le 10^9$

分析

(完全没想法orz,%别人的题解)

比较微妙的一点是其实$\lbrace 1,5,10,50\rbrace$和$\lbrace 0,4,9,49\rbrace$的方案数是一样的,并且微妙在于后面3个数是互质的,这就方便讨论

如果只有$\lbrace 0,4,9\rbrace$,可以看出9个4和4个9是可以互为替换的,这样就可以在大于等于9个4时贪心把每9个4换成4个9,剩余的位可用0填充,这就得到方案数,也就是暴力枚举0到$min(8,n)$个4,然后任取9和0

现在再看$\lbrace 0,4,9,49 \rbrace$,也就是解$4 \cdot x+9 \cdot y = 49 \cdot z, x \le 49,y \le 49$,得到$(1,5,1)$,可以用49贪心替换掉然后填5个0

这意味着取至少1个4时,9的个数不得超过4个,当取0个4时,9的个数不得超过48个,剩下任选49和0

还有一点是$4 \cdot x + 49 \cdot y = 9 \cdot z$解得$(2,1,9)$,意味着取0个4时,其实9的个数不超过8个

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    while(~scanf("%d",&n)){
        ll ans=0;
        for(int i=0;i<=min(8,n);i++){
            for(int j=0;i+j<=n;j++){
                if(i==0 and j>8) break;
                if(i>0 and j>4) break;
                ans+=n-i-j+1;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

BZOJ - 1050

题意

给出$n$个点$m$条无向带权边,以及出发点$s$和终点$t$,求$s \to t$路径上的最大值/最小值的最小可能

范围

$n\le500,m\le5000$

分析

睡觉时想到一个too young的想法,$O(n^3)$预处理连通性后,再$O(m^2)$枚举最大值和最小值的所有可能,只需对两条边上的点进行连通性判断更新答案即可,然而只能过样例(我也不知道哪里有问题),这里贴出WA的代码

一个通俗的方法是利用最小生成树的性质,如果固定一条边作为最小边的前提下生成MST,那么MST中最大边权的权值会是最小的,那么显然$O(m^2)$就可以解决这道题

hzwer给出的题解是,首先边权排序,那么只需枚举其中一个最值,比如最小值

从sta=0开始枚举下标,初始化并查集,不断往右联通直到s与t联通,记此时下标为r,此时得到最小的最大边权$cost[r]$

再初始化并查集,枚举另一边从r开始往左连接,直到s与t联通,记下标为l,此时得到最大的最小边权$cost[l]$

比较两种MST的解得到[l,r]的最优解,然后sta=l+1重复上述过程

复杂度...$O(很快)$

实现

$O(m^2)$版本

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+11;
struct Edge{
    int from,to,cost,next;
    Edge(){}
    Edge(int u,int v,int w,int nxt):from(u),to(v),cost(w),next(nxt){}
    bool operator<(const Edge &rhs)const{return cost<rhs.cost;}
}edge[MAXN<<1];
int head[MAXN],tot;
void init(){memset(head,-1,sizeof head),tot=0;}
void add(int u,int v,int w){edge[tot]=Edge(u,v,w,head[u]);head[u]=tot++;}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int p[503];
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
int n,m,s,t,u,v,w;
int main(){
    while(~scanf("%d%d",&n,&m)){
        init();
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        sort(edge,edge+tot);
        scanf("%d%d",&s,&t);
        int ans1,ans2,flag=0;
        for(int i=0,j;i<tot;i++){
            for(j=0;j<=n;j++) p[j]=j;
            for(j=i;j<tot;j++){
                u=find(edge[j].from),v=find(edge[j].to);
                if(u<v) swap(u,v); p[u]=v;
                if(find(s)==find(t)) break;
            }
            if(find(s)==find(t)){
                if(flag==0||ans1*edge[i].cost>ans2*edge[j].cost){
                    ans1=edge[j].cost,ans2=edge[i].cost;
                    flag=1;
                }
            }
        }
        if(!flag) printf("IMPOSSIBLE\n");
        else if(ans2==gcd(ans1,ans2)) printf("%d\n",ans1/gcd(ans1,ans2));
        else printf("%d/%d\n",ans1/gcd(ans1,ans2),ans2/gcd(ans1,ans2));
    }
    return 0;
}

BZOJ - 1052

题意

给出$n$个点,求用3个正方形覆盖所有点的最小边长

范围

$n\le20000$

分析

从边界出发,构造一个把所有的点包起来的矩形

很显然至少有一个正方形要包在四个边的其中一端,枚举四个角,然后二分一下边长看剩下两个能否完全覆盖剩余所有点

很naive的想法,没有代码(据说能$O(n)$?)

last update: 2018/12/01

BZOJ - 3680 / 2018Nanjing - D

题意

BZOJ - 3680:二维坐标系下给出$n$个点$p_i$和权重$w_i$,找到一个点$best$使得$\sum_{i=1}^ndis(best,p_i)\cdot w_i$最小

NanjingOnsite:三维坐标下给出$n$个点$p_i$,找到一个点$best$使得$max_{i=1}^ndis(best,p_i)$最小

范围

BZOJ - 3680:$n\le1000$

NanjingOnsite:$n\le100$

要求输出精度比较低

分析

稍微入门一下模拟退火就知道这水的不行

实现

这里只给出南京D题的实现,马老板得背锅

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 103;
const double PI = acos(-1);
const double EPS = 1e-6;
int n;
double ans;
struct Point{
    double x,y,z;
}p[MAXN],now,best;
double dis(Point &a,Point &b){
    return sqrt(
        (a.x-b.x)*(a.x-b.x)
        +(a.y-b.y)*(a.y-b.y)
        +(a.z-b.z)*(a.z-b.z)
    );
}
double rand01(){
    return (rand()%1000+1.0)/1000.0;
}
double lambda(Point cur){
    double res=0;
    for(int i=1;i<=n;i++){
        res=max(dis(cur,p[i]),res);
    }
    if(res<ans) best=cur,ans=res;
    return res;
}
int main(){
    //freopen("stdin.txt","r",stdin);
    srand(19260817);
    while(~scanf("%d",&n)){
        double nx=0,ny=0,nz=0;
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
            nx+=p[i].x/n;
            ny+=p[i].y/n;
            nz+=p[i].z/n;
        }
        best=now=(Point){nx,ny,nz};ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,dis(best,p[i]));
        }
        double T=2e6;
        while(T>EPS){
            double dx=now.x+T*(rand01()*2-1);
            double dy=now.y+T*(rand01()*2-1);
            double dz=now.z+T*(rand01()*2-1);
            Point tmp=(Point){dx,dy,dz};
            double t1=lambda(now),t2=lambda(tmp);
            double de=t1-t2;
            if(de>=0||exp(de/T)>=rand01()){
                now=tmp;
            }
            T*=0.99;
        }
        int times=2e6;
        while(times--){
            double dx=best.x+rand01()*(rand01()*2-1);
            double dy=best.y+rand01()*(rand01()*2-1);
            double dz=best.z+rand01()*(rand01()*2-1);
            lambda((Point){dx,dy,dz});
        }
        printf("%.5lf\n",lambda(best));
    }
    return 0;
}

last update:2018/12/05

Codeforces - 767C

题意

给出一棵带$n$个节点的树,每个节点$i$带权$val[i]$,固定根,给出一种方案使得这棵树删掉两条边后可形成三个权值总和相等的子树

范围

$3\le n\le 10^6$

分析

容易看出的一点是分出来的每个块权值和肯定是$sum/3$

而我们又可以看出,肯定有一棵树是完全包揽子树的,那我们可以尝试枚举这个子树的根(不枚举原来树的根)

当子树和为$sum/3$时,可以找出子树外另一个和为$sum/3$的子树,再剩下的就是根的残块

当子树和为$sum/3\cdot2$时,可以找出子树内和为$sum/3$的子树,剩下的外围全部都是根的那块

然后很不熟练地码了1h的树形DP

然而,WA了QAQQQ

见代码

放弃治疗:别人家的题解

实现

我不干了

update.过一天发现在pushDown过程中的$sum-dp[u]==sum/3$的判断是会包括根节点导致分割错误

把它删掉就AC了!

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+11;
int to[MAXN<<1],nxt[MAXN<<1],head[MAXN],tot;
void init(int n){memset(head,-1,(n+2)*sizeof(int)),tot=0;}
void add(int u,int v){to[tot]=v,nxt[tot]=head[u];head[u]=tot++;}
int n,u,v,tmp,tmp2,rt;
int val[MAXN],dep[MAXN],sum[MAXN];
int in[MAXN],out[MAXN],belong[MAXN];
void dfs0(int u,int p,int d){
    in[u]=out[u]=belong[u]=0;
    dep[u]=d; sum[u]=val[u];
    for(int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if(v==p) continue;
        dfs0(v,u,d+1);
        sum[u]+=sum[v];
        if(sum[v]==tmp) in[u]=v,belong[u]=v;
        else if(in[v]) in[u]=in[v],belong[u]=v;
    }
}
void dfs1(int u,int p){
    if(~p&&out[p]&&out[p]!=rt) out[u]=out[p]; //对比这里
    if(~p&&!out[u]){
        if(belong[p]==u) for(int i=head[p];~i;i=nxt[i]){
            int v=to[i];
            if(v==u) continue;
            if(dep[v]<dep[p]) continue;
            if(in[v]&&in[v]!=rt) out[u]=in[v];
            else if(sum[v]==tmp) out[u]=v;
        }else if(in[p]&&in[p]!=rt){
            out[u]=in[p];
        }
    }
    for(int i=head[u];~i;i=nxt[i]){
        int v=to[i];
        if(v==p) continue;
        dfs1(v,u);
    }
}
int main(){
    //freopen("stdin.txt","r",stdin);
    while(~scanf("%d",&n)){
        init(n);
        tmp=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&u,&val[i]);
            tmp+=val[i];
            if(u==0){
                rt=i;
                continue;
            }
            add(i,u);
            add(u,i);
        }
        if(tmp%3!=0){
            printf("-1\n");
            continue;
        }
        tmp/=3; tmp2=tmp*2;
        dfs0(rt,-1,1);
        dfs1(rt,-1);
        int ans1=-1,ans2=-1;
        for(int i=1;i<=n;i++){
            if(i==rt) continue;
            if(sum[i]==tmp2){
                if(in[i]){
                    ans1=i;
                    ans2=in[i];
                    break;
                }
            }else if(sum[i]==tmp){
                if(out[i]){
                    ans1=i;
                    ans2=out[i];
                    break;
                }
            }
        }
        if(~ans1) printf("%d %d\n",ans1,ans2);
        else printf("-1\n");
    }
    return 0;
}

Codeforces - 803C

题意

给出$n$和$k$,构造一个序列满足

  • $a_1+a_2+\cdots+a_k=n$
  • $a_1\lt a_2\lt a_3\cdots \lt a_k$

的前提下使得$gcd(a_1,a_2,\ldots,a_k)$最大

范围

$1\le n,k\le 10^{10}$

分析

一点提示是假设答案是$g$,那就是构造一个$g\cdot b_1,g \cdot b_2,\ldots g\cdot b_k$的序列,$\sum_i b_i=n/g$

枚举$g$只需$O(\sqrt n)$的时间(偷懒排一下序)

那么$n$该怎么凑?这时候只需合法就行了,不够大就往最后一个数硬塞(一时没反应过来)

也就是$\lbrace 1,2,3,\ldots ,k-1,x\rbrace$中只需最后一个数$x=n/g-\sum_{i=1}^{k-1}i>k-1$

输出时别忘了换算回原答案

实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+11;
using ll = long long;
using ld = long double;
ll n,k;
ld sum;
vector<ll> vec;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("stdin.txt","r",stdin);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int kase=0;
    while(cin>>n>>k){
        vec.clear();
        sum=(ld)(k-1)*(k)/2;
        int sqr=sqrt(n)+0.5;
        for(int i=2;i<=sqr;i++){
            if(n%i==0){
                vec.push_back(i);
                if(n/i!=i) vec.push_back(n/i);
            }
        }
        vec.push_back(1);
        sort(vec.begin(),vec.end());
        ll g=-1,x;
        for(int i=0;i<vec.size();i++){
            if((ld)n/vec[i]-sum>k-1){
                x=n/vec[i]-sum;
                g=vec[i];
            }
        }
        if(~g){
            for(int i=1;i<=k-1;i++) cout<<g*i<<" ";
            cout<<g*x<<endl;
        }else{
            cout<<-1<<endl;
        }
    }
    return 0;
}

last update:2018/12/11

Codeforces - 959D

题意

给出一个长度为$n$的数组$a$,要求构造一个等长的数组$b$,满足

  • $b$的字典序比$a$大
  • $b$内元素互质
  • $b_i \ge 2$
  • $b$的字典序尽量小

范围

$1 \le n \le 10^5,2 \le a_i \le 10^5$

分析

要求字典序最小是一个贪心的过程,要求保证考虑第$i$位时要根据前面$1\ldots i-1$的方案得到当前最优

构造的过程其实是修改$a$的过程,可以发现一个$a$数组是由[互质的序列],[与前面不互质的元素],[任意序列]的结构组成

对于第一个发现不互质的元素,要暴力求出第一个与前面的数均互质的最小值,使得满足字典序比$a$大且尽量小的条件

对于剩下的其他序列则贪心使用还没统计到的素数依次同小到大填充(很显然一个合数可以替换成更优的自身的没出现过的质因数,如果出现了任一个那这个合数也是非法的)

实现过程只需用数组记录一下质因数的出现次数即可,复杂度$O(n\sqrt m)$

PS.官方标程是用玄学筛法,实际运行效率有点炸

实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e6+11;
int n,a[MAXN],b[MAXN];
bool isPrime[MAXN];
int prime[MAXN],cnt[MAXN];
void shai(int n=MAXN-1){
    for(int i=2;i<=n;i++) isPrime[i]=1;
    for(int i=2;i*i<=n;i++){
        if(isPrime[i]){
            for(int j=2*i;j<=n;j+=i){
                isPrime[j]=0;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(isPrime[i]){
            prime[++prime[0]]=i;
        }
    }
}
int main(){
    shai();
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>a[i];
        memcpy(b,a,sizeof a);
        memset(cnt,0,sizeof cnt);
        int cur=1;
        for(int i=1;i<=n;i++){
            if(cur!=1) break;
            stack<int> stk;
            for(int j=1;j<=prime[0]&&prime[j]<=a[i];j++){
                if(a[i]%prime[j]==0){
                    if(cnt[prime[j]]==1){
                        cur=i;
                        break;
                    }
                    stk.push(prime[j]);
                    while(a[i]%prime[j]==0){
                        a[i]/=prime[j];
                    }
                }
            }
            if(cur!=1) break;
            if(a[i]!=1){
                if(cnt[a[i]]==1){
                    cur=i;
                    break;
                }
                stk.push(a[i]);
            }
            while(!stk.empty()){
                cnt[stk.top()]++;
                stk.pop();
            }
        }
        vector<int> used;
        for(int i=2;i<MAXN;i++) if(cnt[i]) used.push_back(i);
        if(cur!=1){
            for(int i=b[cur]+1;i<MAXN;i++){
                bool flag=0;
                for(auto j:used){
                    if(i%j==0){
                        flag=1;
                        break;
                    }
                }
                if(flag==0){
                    b[cur]=i;
                    for(int j=1;j<=prime[0]&&prime[j]*prime[j]<=i;j++){
                        if(i%prime[j]==0){
                            cnt[prime[j]]++;
                            while(i%prime[j]==0) i/=prime[j]; 
                        }
                    }
                    if(i!=1) cnt[i]++;
                    break;
                }
            }
            for(int i=cur+1,j=0;i<=n;i++){
                for(int k=j+1;k<=prime[0];k++){
                    if(cnt[prime[k]]) continue;
                    b[i]=prime[k];
                    j=k;break; 
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(i==n) cout<<b[i]<<endl;
            else cout<<b[i]<<" ";
        }
    }
    return 0;
}

Codeforces - 754D

题意

给出$n$个区间$[l_i,r_i]$,从中挑出$k$个区间使得区间的交的长度最大

范围

$1 \le k \le n \le 3 \cdot 10^5,-10^9 \le l_i \le r_i \le 10^9$

分析

这题是真的简单,我果然是菜爆了

考虑枚举$l$,

对于每一个$l_i$,如果能求出合法的且最大的前$k$个$r_j$,那么当前端点下的最优解就是$min \lbrace r_j \rbrace-l_i+1$

然后$n$个答案中取最大的解就是全局最优解

小根堆维护$r_j$表示至少含有$k$个比$top$还大的合法端点,保持堆大小为$k$就能得到当前最优解

只需预处理对左端点排序即可保证前面取到的堆内区间都是合法的(合法是指区间有交集,没交集的话反正答案也是小于0无所谓了)

实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5+11;
struct QAQ{
    int l,r,id;
    bool operator < (const QAQ &rhs) const{
        return r>rhs.r;
    }
}q[MAXN];
bool cmp(const QAQ &a,const QAQ &b){
    return a.l<b.l;
}
priority_queue<QAQ> que;
int n,k; 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n>>k){
        for(int i=1;i<=n;i++){
            cin>>q[i].l>>q[i].r;
            q[i].id=i;
        }
        sort(q+1,q+1+n,cmp);
        int best=0,l,r;
        while(!que.empty()) que.pop();
        for(int i=1;i<=n;i++){
            que.push(q[i]);
            if(que.size()<k) continue;
            QAQ tmp=que.top();
            que.pop();
            int len=tmp.r-q[i].l+1;
            if(len>best){
                best=len;
                l=q[i].l;
                r=tmp.r;
            }
        }
        if(best==0){
            cout<<0<<endl;
            for(int i=1;i<=k;i++){
                if(i==k) cout<<i<<endl;
                else cout<<i<<" ";
            }
        }else{
            cout<<best<<endl;
            for(int i=1;i<=n;i++){
                if(q[i].l<=l&&q[i].r>=r){
                    if(--k){
                        cout<<q[i].id<<" ";
                    }else{
                        cout<<q[i].id<<endl;
                        break;
                    }
                }
            }
        }
    }
    return 0;
}

Codeforces - 767D

题意

给出$n$瓶冰箱里的牛奶和$m$商店里的牛奶的过期日期(当天能喝)以及每天能喝的数目$k​$,求能喝完冰箱牛奶前提下能买到的商店牛奶的最大数目

范围

$1 \le n,m \le 10^6$

分析

显然的贪心,在不影响后面能喝完所有剩余冰箱的牛奶前提下塞入尽量多的商店牛奶即可

实现上我是把两种都混排对比两种策略,对比能不能喝完只需得知下一瓶冰箱的牛奶的日期

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6+11;
int f[MAXN],s[MAXN];
ll bei[MAXN<<1];
struct QAQ{
    int data,flag,id;
    bool operator < (const QAQ &rhs) const{
        if(data!=rhs.data) return data<rhs.data;
        return flag<rhs.flag;
    }
}h[MAXN<<1];
int n,m,k;
vector<int> vec;
int gao(){
    int ans=0,l=k,now=0,j=0;
    for(int i=1;i<=n+m;i++){
        if(!h[i].flag&&l&&h[i].data>=now){
            if(--l==0) now++,l=k;
            ans++;
            j=i;
        }else if(!h[i].flag){
            vec.clear();
            return -1;
        }else if(h[i].data>=now){
            if(j<i) while(h[++j].flag&&j<=n+m);
            if(j<=n+m&&ans+1>bei[j]) continue;
            if(--l==0) now++,l=k;
            ans++;
            vec.push_back(h[i].id);
        }
    }
    return vec.size();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n>>m>>k){
        for(int i=1;i<=n;i++){
            cin>>f[i];
            h[i]=(QAQ){f[i],0,i};
        }
        for(int i=1;i<=m;i++){
            cin>>s[i];
            h[n+i]=(QAQ){s[i],1,i};
        }
        sort(h+1,h+1+n+m);
        bei[0]=1ll<<62;
        for(int i=1;i<=n+m;i++) bei[i]=(ll)h[i].data*k; 
        //b[i]:喝第i瓶牛奶前最多能喝多少
        vec.clear();
        cout<<gao()<<endl;
        sort(vec.begin(),vec.end());
        for(int i=0;i<vec.size();i++){
            if(i==vec.size()-1) cout<<vec[i]<<endl;
            else cout<<vec[i]<<" ";
        }
    }
    return 0;
}

last update:2018/12/26

Codeforces - 732E

题意

给出$n$台电脑和$m$个插槽,只有当权值完全匹配时电脑才能与插槽匹配上,有无限个分压器可以使用,使得插槽的权值$x$变为$x/2$的上取整,求最多能匹配的电脑和最少使用的分压器方案

范围

$1 \le n,m \le 2 \cdot 10^5,1 \le x \le 10^9$

分析

权值的分布是树状结构,那就把插槽从小到大排序贪心取即可,因为如果能匹配上小的肯定是次数最小的,否则要么替换大的子节点更亏或者根本匹配不上

PS.作死一次用电脑匹配插槽,分堆里从小到大和从大到小两种贪心策略拿,正确性似乎没问题,但时间不够用了

实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+11;
struct QAQ{
    int val,id;
    bool operator < (const QAQ &rhs) const{
        return val<rhs.val;
    }
}s[MAXN],p[MAXN];
int n,m,cnt,a[MAXN],b[MAXN];
unordered_map<int,int> mp;
vector<int> vec[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n>>m){
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        mp.clear(); cnt=0;
        for(int i=1;i<MAXN;i++) vec[i].clear();
        for(int i=1;i<=n;i++){
            cin>>p[i].val;
            p[i].id=i;
            if(mp.count(p[i].val)==0){
                mp[p[i].val]=++cnt;
                vec[cnt].push_back(i);
            }else{
                vec[mp[p[i].val]].push_back(i);
            }
        }
        for(int i=1;i<=m;i++){
            cin>>s[i].val;
            s[i].id=i;
        }
        int ans1=0,ans2=0;
        sort(s+1,s+1+m);
        for(int i=1;i<=m;i++){
            int x=s[i].val,t=0;
            while(1){
                if(mp.count(x)&&vec[mp[x]].empty()==0){
                    ans1++;
                    ans2+=t;
                    int pos=mp[x];
                    a[s[i].id]=t;
                    b[vec[pos].back()]=s[i].id;
                    vec[pos].pop_back();
                    break;
                }
                if(x==1) break;
                x=(x+1.0)/2.0;
                t++;
            }
        }
        cout<<ans1<<" "<<ans2<<endl;
        for(int i=1;i<=m;i++){
            if(i==m) cout<<a[i]<<endl;
            else cout<<a[i]<<" ";
        }
        for(int i=1;i<=n;i++){
            if(i==n) cout<<b[i]<<endl;
            else cout<<b[i]<<" ";
        }
    }
    return 0;
}

Codeforces - 730A

题意

有$n$人,每个人的rating是$w_i$,现在要求每个人rating一致,唯一的方法是降分,你可以选择$2$到$max(5,n)$个人组队降分,也就是选中的这几个人同时降一分,注意当降为0时无论再怎么降也不会变动,求出$rating$一致且最高时的分数,组队次数不做要求,需要输出完整方案

范围

$2 \le n \le 100,0 \le w_i \le 100$

分析

首先$2+2=4,2+3=5,\cdots$,可以发现$2$和$3$是最重要的,且大于$5$时可以用$4\cdot x+2 \cdot y+3 \cdot z$来表示任意一个整数,且$y ,z=\lbrace 0,1 \rbrace$

然后我们枚举答案,每次令最大的多个数靠拢到答案范围(至于为什么挑最大,因为这样可以单次降分后令后来最大的相同的数尽可能多且单次干掉最大的数也是最多的),如果发现有大于等于6个相同的最大值,那就优先干掉4个,其余2到5个尽量塞,其中用平衡树来动态维护这个过程即可(说不定这也是组队次数最少的方案)

代码写的有点挫,因为这个一开始是想着用二分来搞的,实测不可二分(所以越写越乱了)

实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+11;
int n;
struct QAQ{
    int val,id;
    bool operator < (const QAQ &rhs)const{
        return val > rhs.val;
    }
}a[233],b[233];
int rec[MAXN][102],t imes;
bool C(int mid){
    if(n==1&&b[1].val!=mid) return 0;
    multiset<QAQ> st;
    for(int i=1;i<=n;i++) st.insert(b[i]);
    times=0;
    memset(rec,0,sizeof rec);
    while(1){
        if((*st.begin()).val==mid) return 1;
        if((*st.begin()).val<mid) return 0;
        vector<QAQ> vec; 
        for(int i=1;i<=6;i++){
            if(!st.empty()&&((*st.begin()).val>mid||mid==0)){
                vec.push_back(*st.begin());
                st.erase(st.begin());
            }
        }
        if(vec.size()==1) return 0;
        int flag=0,c=0;
        for(int i=0;i<vec.size();i++) if(vec[i].val==vec[0].val) c++;
        if(c==5) flag=4;
        else if(c==6) flag=3;
        else flag=max(1,c-1);
        ++times;
        for(int i=0;i<=flag;i++) vec[i].val=max(0,vec[i].val-1),rec[times][vec[i].id]=1;
        while(!vec.empty()){
            st.insert(vec.back());
            vec.pop_back();
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n){
        int mn=1<<30;
        for(int i=1;i<=n;i++){
            cin>>a[i].val;
            a[i].id=i;
            b[i]=a[i];
            mn=min(mn,a[i].val);
        }
        int lo=0;
        for(int i=0;i<=mn;i++){
            if(C(i)) lo=i;
        }
        C(lo);
        cout<<lo<<endl<<times<<endl;
        for(int i=1;i<=times;i++){
            for(int j=1;j<=n;j++){
                cout<<rec[i][j];
            }
            cout<<endl;
        }
    }
    return 0;
}

Codeforces - 343C

题意

给出$n$个指针的坐标$h_i$,以及$m$个地址的坐标$p_i$,每一秒指针都可以移动一个单位,求最少的时间使得所有地址都被遍历

范围

$1 \le n,m \le 10^5,1 \le h_i,p_i \le 10^{10}$

分析

老实说我当时搞不出来,看了tutorial觉得方法很不错

首先大家都知道的是排序(已省略)并二分答案$mid$,

然后从左到右考虑每一个地址被覆盖的情况(重要)

我们期望枚举过程中做到的是

  • 保留尽可能多的指针
  • 让每个指针跑的尽可能远

对于条件1,显然当该地址存在相对于它的左右边都有指针且可被覆盖时,优先选左端

对于条件2且只剩下右端点可以选择时,找能用的最靠近它的端点,这个时候有两种做法

  • 要么先往左跑,遍历该地址后尽量往右跑
  • 要么先尽量往右跑,最后对该地址踩点即可

依此列出式子然后比较一下选择最优的策略(踩点包含了右端点无法扩展的极端情况)

写起来特简洁,这道题真是喵啊喵啊

实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5+11;
int n,m;
ll p[MAXN],h[MAXN];
bool C(ll mid){
    int i=1,j=1;
    while(j<=m){
        while(h[i]+mid<p[j]&&i<=n) i++;
        if(i>n) return 0;
        if(h[i]<=p[j]){
            while(h[i]+mid>=p[j]&&j<=m) j++;
            i++;
        }else if(mid>=h[i]-p[j]){
            ll t=max(mid-2ll*(h[i]-p[j]),(mid-(h[i]-p[j]))/2)+h[i];
            while(t>=p[j]&&j<=m) j++;
            i++;
        }else return 0;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while(cin>>n>>m){
        for(int i=1;i<=n;i++) cin>>h[i];
        for(int i=1;i<=m;i++) cin>>p[i];
        ll lo=0,hi=2e10;
        while(lo<hi){
            ll mid=lo+(hi-lo)/2;
            if(C(mid)) hi=mid;
            else lo=mid+1;
        }
        cout<<lo<<endl;
    }
    return 0;
}

last update:2018/12/29

标签: none

添加新评论