题意:字符串A中包含的字符串B可以翻译或不翻译,总共有多少方案。
题解:动规,dp[i]表示A的第i位为止有多少方案。
转移方程:
dp[i]=dp[i-1](不翻译)
dp[i]+=dp[i-B.size()](翻译i结尾的子串B)
初始条件:dp[0]=1(代表不翻译的这种情况)
dp[B.size()]=2(若从A起点开始的子串是B,则有翻译和不翻译两种)
//http://acm.hdu.edu.cn/showproblem.php?pid=5763
#include<iostream>
#include<string>
using namespace std;
#define M 1000000007
#define N 100005
int t,dp[N];
string A,B;
int main(){
cin>>t;
for(int c=1;c<=t;c++){
cin>>A>>B;
for(int i=0;i<A.size();i++){
dp[i]=i?dp[i-1]:1;
if(i+1>=B.size()&&A.substr(i-B.size()+1,B.size())==B){
dp[i]=(dp[i]+dp[i-B.size()])%M;
if(i+1==B.size())dp[i]=2;
}
}
cout<<"Case #"<<c<<": "<<dp[A.size()-1]<<endl;
}
return 0;
}
题意:x到y有多少个7的倍数,且满足≠ai mod pi。
题解:利用容斥定理奇加偶减,处理限制条件。
中国剩余定理求出满足ai=X%pi的最小正整数X。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll p[21],a[21];
ll p1[21],a1[21],num;
ll n,x,y;
ll ans;
ll exgcd(ll l,ll r,ll &x,ll &y)
{
if(r==0){x=1;y=0;return l;}
else
{
ll d=exgcd(r,l%r,y,x);
y-=l/r*x;
return d;
}
}
ll qmul(ll a,ll b,ll m){//快速乘法
ll ans=0;
ll k=a;
while(b){
if(b&1)
ans=(ans+k)%m;
k=(k+k)%m;
b>>=1;
}
return ans;
}
ll Remain(ll p[],ll a[],ll m){
ll ans=0;
for(int i=1;i<=num;i++)
{
ll x,y,Mk=m/p[i];
exgcd(Mk,p[i],x,y);
x=(x%p[i]+p[i])%p[i];
ans=(ans+qmul(qmul(Mk,x,m),a[i],m))%m;//ans+=Mk*x*a[i]
}
return (ans+m)%m;
}
ll work()
{
ll m=1;
for(int i=1;i<=num;i++)
m*=(ll)p1[i];
ll sum=Remain(p1,a1,m);
ll k1=(x-sum)/m;
if(k1*m+sum<x)k1++;
if(k1<0)k1=0;
if(y<sum)return 0;
ll k2=(y-sum)/m;
return k2-k1+1;
}
void solve()
{
ans=0;
for(ll i=0;i<=(1<<n)-1;i++)
{
num=0;
memset(p1,0,sizeof(p1));
memset(a1,0,sizeof(a1));
for(int j=0;j<n;j++)
if((i&(1<<j)))
{
p1[++num]=p[j+1];
a1[num]=a[j+1];
}
p1[++num]=7;a1[num]=0;
if(num%2==1)ans+=work();
else ans-=work();
}
return;
}
int main()
{
int t;
cin>>t;
for(int l=1;l<=t;l++)
{
cin>>n>>x>>y;
for(int i=1;i<=n;i++)cin>>p[i]>>a[i];
solve();
cout<<"Case #"<<l<<": "<<ans<<endl;
}
return 0;
}
1012 Bubble Sort
树状数组维护数字i前面有多少个比它小的数,即第几小。最左距离就是rank,最右距离就是max(原位置,终位置),求出距离极差即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int t,n,p[N],sum[N],ans[N];
inline int lowbit(int x){return x&(-x);}
int getsum(int x){
int s=0;
for(;x;x-=lowbit(x))s+=sum[x];
return s;
}
void update(int v,int x){
for(;x<=n;x+=lowbit(x))sum[x]+=v;
}
int main(){
cin>>t;
for(int c=1;c<=t;c++){
memset(sum,0,sizeof sum);
cout<<"Case #"<<c<<":";
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i];
update(1,p[i]);
int r=getsum(p[i]);
ans[p[i]]=max(i-r,p[i]-r);
}
for(int i=1;i<=n;i++)
cout<<" "<<ans[i];
cout<<endl;
}
return 0;
}