CF653

2016.03.21 19:50 Mon | 58次阅读 | 旧日oi | 固定链接 | 源码

A

题目大意

给一个长度<=50序列,问是否能选出三个数形如i,i+1,i+2。

mycode

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 100005
int n,a[N];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            for(int k=j+1;k<=n;k++)
            if(a[i]!=a[j]&&a[j]!=a[k]&&a[k]<=a[i]+2)
            {
                puts("YES");
                return 0;
            }
        }
    }
    puts("NO");
    return 0;
}

B

题目大意

给出一些变换,每次可以把一个字符串的头两个字符变成一个新字符,问长度<=6且只能用abcdef的串中,有多少个可以变换成'a'。

题解

爆搜即可

mycode

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 100005
int n,q,ans;
char s1[40][5],s2[40][5],tmp[10];
void dfs(int now)
{
    if(now==n+1)
    {
        char last=tmp[1];
        for(int i=2;i<=n;i++)
        {
            bool flag=0;
            for(int j=1;j<=q;j++)
            if(last==s1[j][0]&&tmp[i]==s1[j][1])
            {
                flag=1;
                last=s2[j][0];
                break;
            }
            if(!flag) return;
        }
        if(last=='a') ans++;
        return;
    }
    for(int i=0;i<6;i++) 
    {
        tmp[now]='a'+i;
        dfs(now+1);
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>q;
    for(int i=1;i<=q;i++)
        scanf("%s%s",s1[i],s2[i]);
    dfs(1);
    cout<<ans<<endl;
}

C

题目大意

给出一个n个数的序列,现在要求你把序列变成如下形式:
奇数位置的数比两边小,偶数位置的数比两边大。
给出的初始序列是不满足条件的,你需要选择一对点交换,使得序列满足条件,问方案数。
n<=150000

题解

我们把不合法的点拎出来,可以发现,如果有超过6个不可行的点,那么不可能存在方案。
我们修改的点一定是不合法的点或其两边的点,枚举这些点,和其它的点交换,验证也只需要验证这些不合法点和被交换的点就可以了。

mycode

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 200005
int n,a[N],pos[N],cnt;
bool vis[N];
bool check(int x)
{
    if(x>n||x==0) return 1;
    if(x%2==1) return a[x]<a[x-1]&&a[x]<a[x+1];
    else return a[x]>a[x-1]&&a[x]>a[x+1];
}
void work()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    if(vis[i]||vis[i+1]||vis[i-1])
    {
        for(int j=1;j<=n;j++)
        if(j!=i)
        {
            if(j<i&&(vis[j-1]||vis[j]||vis[j+1])) continue;
            swap(a[j],a[i]);
            bool flag=1;
            pos[cnt+1]=j;
            for(int k=1;k<=cnt+1;k++)
            if(!check(pos[k])||!check(pos[k]-1)||!check(pos[k]+1)) 
            {
                flag=0;
                break;
            }
            if(flag) ans++;
            swap(a[j],a[i]);
        }
    }
    printf("%d\n",ans);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    a[0]=0x3f3f3f3f;
    if(n%2==1) a[n+1]=0x3f3f3f3f;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        if(i%2==1&&a[i]>=a[i+1]) pos[++cnt]=i,vis[i]=1;
        if(i%2==0&&a[i]<=a[i+1]) pos[++cnt]=i,vis[i]=1;
    }
    if(cnt>6) {puts("0");return 0;}
    work();
}

D

题目大意

给出一幅有向图,有x只熊,每只熊要运相同量的货物从1到n,每条路有总载重上限,问最多能运多少货。
点<=50,边<=500,x<=100000,边容量上限<=1000000

题解

考虑普通的最大流为什么不行,因为熊不能分身,流量不能出现不是单只熊的运量倍数的情况。为了避免这种情况,我们二分答案。设当前答案是mid,那么对于每一条边,用上限w处以mid下取整作为新的边权,这样恰好是有多少头熊可以通过,然后再跑最大流就可以了。
如果二分每只熊的运货量的话精度要高一点,因为最后要乘x

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 55
#define eps 1e-12
#define inf 0x3f3f3f3f3f3f3f3fll
#define ll long long
int h[N],tp=1;
struct edge{int to,next;ll val;}e[2000005];
void ae(int u,int v,ll w=0){e[++tp].to=v;e[tp].next=h[u];e[tp].val=w;h[u]=tp;}
struct MAXFLOW
{
    int S,T,dis[N],q[N],f,t;
    void init(int s,int t){S=s;T=t;memset(h,0,sizeof(h));tp=1;} 
    void add(int u,int v,ll w){ae(u,v,w);ae(v,u,0);}
    int bfs(){
        memset(dis,0,sizeof(dis));dis[S]=1;q[f=t=1]=S;
        while(f<=t){
            int u=q[f++];
            for(int v,i=h[u];i;i=e[i].next) 
            if(e[i].val&&!dis[v=e[i].to]) dis[q[++t]=v]=dis[u]+1;
        }
        return dis[T];
    }
    int dfs(int u,ll l)
    {
        if(u==T) return l;
        ll c=0,t;
        for(int v,i=h[u];i;i=e[i].next)
        if(e[i].val&&dis[v=e[i].to]==dis[u]+1)
        {
            t=dfs(v,min(l-c,e[i].val));
            if(t){e[i].val-=t;e[i^1].val+=t;if((c+=t)==l) break;}
            else dis[v]=-1;
        }
        return c;
    }
    ll dinic(){ll ret=0;while(bfs()) ret+=dfs(S,inf);return ret;}
}g;
int n,m,x;
int u[1005],v[1005];
ll w[1005];
bool check(long double mid)
{
    g.init(1,n);
    for(int i=1;i<=m;i++) 
    {
        ll k=(w[i]+eps)/mid;
        g.add(u[i],v[i],k);
    }
    return g.dinic()>=x;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>m>>x;
    for(int i=1;i<=m;i++)
        scanf("%d%d%I64d",&u[i],&v[i],&w[i]);
    long double l=0,r=1000000.0,mid,ans=0;
    while(r-l>eps)
    {
        mid=(l+r)/2.0;
        if(check(mid)) ans=l=mid;
        else r=mid;
    }
    printf("%.10lf\n",(double)ans*x);
}

E

题目大意

给出一幅完全图,点数300000,有一些边(<=300000)不能用,问是否存在一颗1号点度数恰为k的生成树。

题解

如果不考虑点1的限制,就和BZOJ1098一样了,链表搞一下就行了。
考虑点1的限制的话,我们先求出1号点的最小可能度数,怎么搞?深搜一遍就行了,方法也和1098类似,但是链表不太好搞了,可以换成set。为什么要深搜呢,因为这恰好能保证1号点的度数最小。
1号点的度数最大是多少呢?当然是能和1连的都和1连,连的多不会有坏处嘛。
如果k恰好在最小和最大之间且图连通就有解。否则无解。

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 300005
int n,m,k,ind[N];
bool vis[N];
int u[N],v[N],l[N],r[N];
set<int> s[N],ss;
void del(int x)
{
    r[l[x]]=r[x];l[r[x]]=l[x];
}
int dfs(int u)
{
    int cnt=0,last=0,x=1;ss.erase(u);
    while(x<=n)
    {
        x=(*ss.upper_bound(last));
        if(x>n) return cnt;
        if(!s[u].count(x)) cnt++,dfs(x);
        last=x;
    } 
    return cnt;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>m>>k;
    int tot=n-1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        if(u[i]>v[i]) swap(u[i],v[i]);
        if(u[i]==1) tot--;
        ind[u[i]]++;ind[v[i]]++;
        s[u[i]].insert(v[i]);
        s[v[i]].insert(u[i]);
    }
    if(tot<k)
    {
        puts("impossible");
        return 0;
    }
    for(int i=1;i<=n;i++)
    if(ind[i]==n-1) 
    {
        puts("impossible");
        return 0;
    }
    for(int i=1;i<=n+1;i++) ss.insert(i);
    puts(dfs(1)<=k&&ss.size()==1?"possible":"impossible");
}

F

题目大意

给出一个括号序列,问有多少个本质不同的合法括号序列子串,长度100000.

题解。

先把所有本质不同的子串找到,后缀数组即可。
然后,将(设为1,)设为-1.求前缀和。
那么以i为起点的合法区间就是i后面的sum值和sum[i-1]相同的位置,并且其中不能有<sum[i-1]的位置。
于是我们可以预处理出以每个点开头的有效区间。
然后,我们可以对每一种sum[i]单独处理,从后往前加入每一个位置,同时求出答案,用一个树状数组维护即可复杂度O(nlogn)

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define lowbit(x) (x&(-x))
int v[N],sa[2][N],rk[2][N],h[N],p,q;
int a[N],b[N],sum[N],r[N],c[N],id[N];
char s[N];
long long ans;
set<int> se;
vector<int> son[N];
int n;
void mul(int k,int *sa,int *rk,int *SA,int *RK)
{
    for(int i=1;i<=n;i++) v[rk[sa[i]]]=i;
    for(int i=n;i;i--)
        if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;
    for(int i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i;
    for(int i=1;i<=n;i++) 
        RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i-1]+k]!=rk[SA[i]+k]);
}
void get_sa(int lim)
{
    p=1;
    for(int i=1;i<=n;i++) v[b[i]]++;
    for(int i=1;i<=lim;i++) v[i]+=v[i-1];
    for(int i=1;i<=n;i++) sa[p][v[b[i]]--]=i;
    for(int i=1;i<=n;i++) 
        rk[p][sa[p][i]]=rk[p][sa[p][i-1]]+(b[sa[p][i]]!=b[sa[p][i-1]]);
    for(int k=1;k<=n;k<<=1) 
    {
        mul(k,sa[p],rk[p],sa[q],rk[q]);
        swap(p,q);
    }
    for(int j,k=0,i=1;i<=n;i++)
    {
        j=sa[p][rk[p][i]-1];
        while(b[i+k]==b[j+k]) k++;
        h[rk[p][i]]=k;if(k) k--;
    }
}
void add(int x,int y){for(;x<=n;x+=lowbit(x)) c[x]+=y;}
int query(int x)
{
    int ret=0;
    for(;x;x-=lowbit(x)) ret+=c[x];
    return ret;
}
bool cmp(int a,int b)
{
    if(sum[a]==sum[b]) return a<b;
    return sum[a]<sum[b];
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    scanf("%s",s+1);
    son[n].push_back(0);
    for(int flag=0,i=1;i<=n;i++) 
    {
        if(s[i]=='(') a[i]=1,b[i]=1;
        else a[i]=-1,b[i]=2;
        sum[i]=sum[i-1]+a[i];
        son[sum[i]+n].push_back(i);
        id[i]=i-1;
    }
    sort(id+1,id+n+1,cmp);se.insert(n+1);
    for(int i=1;i<=n;i++) 
    {
        r[id[i]+1]=*se.upper_bound(id[i]);
        se.insert(id[i]);
    }
    get_sa(2);
    for(int i=0;i<=n*2;i++)
    {
        for(int j=son[i].size()-1;j>=0;j--)
        {
            int x=son[i][j]+1,st=x+h[rk[p][x]];
            if(st<=r[x]) ans=(ans+query(r[x]-1)-query(st-1));
            if(x>1) add(x-1,1);
        }
        for(int j=son[i].size()-1;j>=0;j--) 
        if(son[i][j]) add(son[i][j],-1);
    }
    cout<<ans<<endl;
}

G

题目大意

给出一个n个数的序列,对于一个序列,可以进行两种操作,对一个数乘或除一个质数,现在要把这n个数的每一个子序列的所有元素变成相同的,问总共最少需要多少步。
n<=300000

题解

很显然,每个质因数可以单独考虑,然后对于一个子序列的一种质因数,答案就是所有的数在这个质因数的次数到到这些数的中位数的距离之和。
问题就是如何求这个距离。
我们可以枚举中位数搞,但是写起来挺麻烦的。
再归纳一下,可以得到更优美的做法。
考虑每个数作为比中位数大的数出现了多少次。小又出现了多少遍。
设f[i]表示排名为i的数应该被加减多少次。
显然f[0]=qpow(2,n-1)-1
然后有f[i+1]=f[i]-C(n-1,i)-C(n-1,i+1)

mycode

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300005
#define mod 1000000007
#define inv2 500000004
int n,a[N];
vector<int> val[N];
ll ans,p[N],inv[N],mul[N];
ll qpow(ll x,ll k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;x=x*x%mod;
    }
    return ret;
}
ll C(int n,int m)
{
    return p[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        int tmp=a[i];
        for(int j=2;j*j<=tmp;j++)
        if(tmp%j==0)
        {
            int cnt=0;
            while(tmp%j==0) cnt++,tmp/=j;
            val[j].push_back(cnt);
        }
        if(tmp>1) val[tmp].push_back(1);
    }
    p[0]=inv[0]=1;
    for(int i=1;i<=n;i++) 
    {
        p[i]=p[i-1]*i%mod;
        inv[i]=qpow(p[i],mod-2);
    }
    mul[0]=qpow(2,n-1)-1;
    for(int i=0;i<n-1;i++) mul[i+1]=(mul[i]-C(n-1,i)-C(n-1,i+1))%mod;
    for(int i=1;i<=300000;i++)
    if(val[i].size()>0)
    {
        sort(val[i].begin(),val[i].end());
        for(int j=0;j<val[i].size();j++) ans=(ans+val[i][val[i].size()-1-j]*mul[j])%mod;
    }
    cout<<(ans+mod)%mod<<endl;
}