「CF521X」Codeforces Round #295 (Div. 1)

2015年3月14日1,4410

A. DNA Alignment

发现每俩个字母都会算一次

所以只要求出现最多的字母的个数x

快速幂求pow(x,n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'>>ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int ans,mx,n,num[30];
char ch[100005];
ll qpow(ll a,ll b)
{
    ll ans=1;a%=mod;
    for(ll i=b;i;i>>=1,a=a*a%mod)
        if(i>1)ans=ans*a%mod;
    return ans;
}
int main()
{
    n=read();
    scanf("%s",ch+1);
    for(int i=1;i<=n;i++)
    {
        num[ch[i]-'A'+1]++;
        mx=max(mx,num[ch[i]-'A'+1]);
    }
    for(int i=1;i<=26;i++)
        if(num[i]==mx)ans++;
    printf("%I64d\n",qpow(ans,n));
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'>>ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int ans,mx,n,num[30];

char ch[100005];

ll qpow(ll a,ll b)

{

ll ans=1;a%=mod;

for(ll i=b;i;i>>=1,a=a*a%mod)

if(i>1)ans=ans*a%mod;

return ans;

}

int main()

{

n=read();

scanf("%s",ch+1);

for(int i=1;i<=n;i++)

{

num[ch[i]-'A'+1]++;

mx=max(mx,num[ch[i]-'A'+1]);

}

for(int i=1;i<=26;i++)

if(num[i]==mx)ans++;

printf("%I64d\n",qpow(ans,n));

return 0;

}

B. Cubes

贪心，依次选择合法的编号最大/最小的，用set，map维护一下

一个格子能删当且仅当它上方的格子可以找到其它的支撑

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000009
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll ans;
int n;
int ax[100005],ay[100005];
bool mark[100005];
map<pair<int,int>,int> mp;
set<int> st;
bool sta(int x,int y)
{
    if(y==0)return 1;
    for(int i=x-1;i<=x+1;i++)
        if(mp[make_pair(i,y-1)])return 1;
    return 0;
}
bool jud(int id)
{
    int x=ax[id],y=ay[id];
    mp[make_pair(x,y)]=0;
    for(int i=x-1;i<=x+1;i++)
        if(mp[make_pair(i,y+1)])
        {
            if(!sta(i,y+1))
            {
                mp[make_pair(x,y)]=id;
                return 0;
            }
        }
    mp[make_pair(x,y)]=id;
    return 1;
}
void add(int t)
{
    int x=ax[t],y=ay[t];
    mp[make_pair(x,y)]=0;
    st.erase(st.find(t));
    for(int i=x-1;i<=x+1;i++)
    {
        int tmp=mp[make_pair(i,y-1)];
        if(tmp)
        {
            if(jud(tmp))
                st.insert(tmp);
        }
    }
}
void solve()
{
    while(1)
    {
        int t=*--st.end();
        while(!jud(t))
        {
            st.erase(st.find(t));
            if(st.empty())return;
            t=*--st.end();
        }
        add(t);
        ans=(ans*n+t-1)%mod;if(st.empty())return;
        t=*st.begin();
        while(!jud(t))
        {
            st.erase(st.find(t));
            if(st.empty())return;
            t=*st.begin();
        }
        add(t);
        ans=(ans*n+t-1)%mod;if(st.empty())return;
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        ax[i]=read(),ay[i]=read();
        mp[make_pair(ax[i],ay[i])]=i;
    }
    for(int i=1;i<=n;i++)
        if(jud(i))
            st.insert(i);
    solve();
    printf("%I64d\n",ans);
    return 0;
}

100

101

102

103

104

105

106

107

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000009

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

ll ans;

int n;

int ax[100005],ay[100005];

bool mark[100005];

map<pair<int,int>,int> mp;

set<int> st;

bool sta(int x,int y)

{

if(y==0)return 1;

for(int i=x-1;i<=x+1;i++)

if(mp[make_pair(i,y-1)])return 1;

return 0;

}

bool jud(int id)

{

int x=ax[id],y=ay[id];

mp[make_pair(x,y)]=0;

for(int i=x-1;i<=x+1;i++)

if(mp[make_pair(i,y+1)])

{

if(!sta(i,y+1))

{

mp[make_pair(x,y)]=id;

return 0;

}

mp[make_pair(x,y)]=id;

return 1;

}

void add(int t)

{

int x=ax[t],y=ay[t];

mp[make_pair(x,y)]=0;

st.erase(st.find(t));

for(int i=x-1;i<=x+1;i++)

{

int tmp=mp[make_pair(i,y-1)];

if(tmp)

{

if(jud(tmp))

st.insert(tmp);

}

void solve()

{

while(1)

{

int t=*--st.end();

while(!jud(t))

{

st.erase(st.find(t));

if(st.empty())return;

t=*--st.end();

}

add(t);

ans=(ans*n+t-1)%mod;if(st.empty())return;

t=*st.begin();

while(!jud(t))

{

st.erase(st.find(t));

if(st.empty())return;

t=*st.begin();

}

add(t);

ans=(ans*n+t-1)%mod;if(st.empty())return;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

{

ax[i]=read(),ay[i]=read();

mp[make_pair(ax[i],ay[i])]=i;

}

for(int i=1;i<=n;i++)

if(jud(i))

st.insert(i);

solve();

printf("%I64d\n",ans);

return 0;

}

C. Pluses everywhere

每一位根据下一个加号位置算贡献，用排列组合算方案

或者是后面没有加号延伸到末尾

预处理阶乘O1算排列

对排列再记录前缀和

每一位就能O1计算贡献

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
#define eps 1e-6
#define inf 1000000000
#define mod 1000000007
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
    ll x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll ans;
int n,m;
char ch[100005];
ll fac[100005],sum[100005];
ll qpow(ll a,ll b)
{
    ll ans=1;a%=mod;
    for(ll i=b;i;i>>=1,a=a*a%mod)
        if(i&1)ans=ans*a%mod;
    return ans;
}
ll C(ll n,ll m)
{
    if(m>n||m<0)return 0;
    ll s1=fac[n],s2=fac[n-m]*fac[m]%mod;
    return s1*qpow(s2,mod-2)%mod;
}
int main()
{
    fac[0]=1;
    for(int i=1;i<=100000;i++)
        fac[i]=fac[i-1]*i%mod;
    n=read();m=read();
    ll k=1;
    for(int i=1;i<=n;i++)
    {
        sum[i]=(sum[i-1]+k*C(n-i-1,m-1)%mod)%mod;
        k=k*10%mod;
    }
    scanf("%s",ch+1);
    k=1;
    for(int i=n;i;i--)
    {
        int t=ch[i]-'0';
        ans=(ans+t*k%mod*C(i-1,m)%mod)%mod;
        ans=(ans+t*sum[n-i]%mod)%mod;
        k=k*10%mod;
    }
    printf("%I64d\n",ans);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#include<cmath>

#define eps 1e-6

#define inf 1000000000

#define mod 1000000007

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

ll ans;

int n,m;

char ch[100005];

ll fac[100005],sum[100005];

ll qpow(ll a,ll b)

{

ll ans=1;a%=mod;

for(ll i=b;i;i>>=1,a=a*a%mod)

if(i&1)ans=ans*a%mod;

return ans;

}

ll C(ll n,ll m)

{

if(m>n||m<0)return 0;

ll s1=fac[n],s2=fac[n-m]*fac[m]%mod;

return s1*qpow(s2,mod-2)%mod;

}

int main()

{

fac[0]=1;

for(int i=1;i<=100000;i++)

fac[i]=fac[i-1]*i%mod;

n=read();m=read();

ll k=1;

for(int i=1;i<=n;i++)

{

sum[i]=(sum[i-1]+k*C(n-i-1,m-1)%mod)%mod;

k=k*10%mod;

}

scanf("%s",ch+1);

k=1;

for(int i=n;i;i--)

{

int t=ch[i]-'0';

ans=(ans+t*k%mod*C(i-1,m)%mod)%mod;

ans=(ans+t*sum[n-i]%mod)%mod;

k=k*10%mod;

}

printf("%I64d\n",ans);

return 0;

}

« 「BZOJ2796」[POI2012] Fibonacci Representation 「CF528A」Glass Carving »

hzwer.com _ Home | http://hzwer.com

「CF521X」Codeforces Round #295 (Div. 1)

分类目录

热门文章

Myfriends

近期评论