牛客OI测试赛3
A.数字权重
#include#include #include #include #include #include #include using namespace std; typedef long long ll; const int maxn=36; vector g[maxn]; ll dp[maxn][maxn]; const ll mod=1e9+7; ll powmod(ll a,ll n){ if(n==0) return 1; if(n==1) return a%mod; ll ans=powmod(a,n/2); ans=ans*ans%mod; if(n&1) return ans*a%mod; return ans; } int main(){ ll n,k; cin>>n>>k; if(k>=10||k<=-10){ cout<<0< =0) cout<<(9-k)*powmod((ll)10,n-2)%mod; else cout<<(10+k)*powmod((ll)10,n-2)%mod; }
首先,考虑到结果的每一位之间互相不影响,因而可以对每一位分别计算,对于区间[L,R]中的每一位,如果0的个数大于1的个数,则该位取1,否则该位取0
#include#include #include #include #include #include #include using namespace std; typedef unsigned long long ll; const int maxn=200005; int p[31]; int a[33][maxn]; int main(){ p[0]=1; for(int i=1;i<=30;i++) p[i]=p[i-1]*2; int n; scanf("%d",&n); for(int i=1;i<=n;i++){ int z; scanf("%d",&z); for(int j=0;j<=30;j++){ if((z>>j)&1) a[j][i]=1; } } for(int j=0;j<=30;j++) for(int i=1;i<=n;i++) a[j][i]+=a[j][i-1]; int q; scanf("%d",&q); for(int i=1;i<=q;i++){ int l,r; scanf("%d%d",&l,&r); int z=0; for(int i=0;i<=30;i++){ if(a[i][r]-a[i][l-1]<(r-l+2)/2) z+=p[i]; } printf("%d\n",z); } }
简单博弈论:对于每一个位置,分三种情况:先手能拿,后手能拿,二者都可以拿。分别计算这三种情况的个数分别为s1,s2,sum 必胜策略肯定是二者都取sum中的硬币,易知其必胜情况
#include#include #include #include #include #include #include using namespace std; typedef unsigned long long ll; const int maxn=2000005; char s[maxn],t[maxn]; int main(){ int n; scanf("%d",&n); scanf("%s",s); scanf("%s",t); int s1=0,s2=0,sum=0; for(int i=0;i<2*n;i++){ if(s[i]=='U'&&t[i]=='U') sum++; else if(s[i]=='U') s1++; else if(t[i]=='U') s2++; } if(s1>s2||(s1==s2&&sum%2==1)) cout<<"clccle trl!"< D.粉樱花之恋
斐波拉契求和,答案即为$sum[k+1]$,矩阵快速幂即可
$fib[i+2]=2fib[i]+fib[i-1]=fib[i]+2fib[i-1]+fib[i-2]=fib[i]+fib[i-1]+2fib[i-2]+fib[i-3]=...=fib[i]+...+2f[2]+f[1]=sum[i]+1$
故$sum[i]=f[i+2]-1$ sum[i]=f[i+2]-1
#include#include #include #include #include #include #include using namespace std; typedef unsigned long long ll; const ll mod=998244353; struct Matrix{ ll m[2][2]; }; Matrix mul(Matrix a,Matrix b){ Matrix m; for(int i=0;i<2;i++) for(int j=0;j<2;j++){ ll sum=0; for(int k=0;k<2;k++) sum=(sum+a.m[i][k]*b.m[k][j]%mod)%mod; m.m[i][j]=sum; } return m; } Matrix matrix_quick_powmod(Matrix a,ll n){ Matrix m,p; m.m[0][0]=m.m[0][1]=m.m[1][0]=1ll; m.m[1][1]=0; if(n==0){ m.m[0][0]=m.m[1][1]=1ll; m.m[0][1]=m.m[1][0]=0; return m; } if(n==1) return m; else p=matrix_quick_powmod(m,n/2); p=mul(p,p); if(n&1) p=mul(p,m); return p; } Matrix a,b; int main(){ ll n; cin>>n; for(int i=0;i<2;i++) for(int j=0;j<2;j++) if(i+j!=2) a.m[i][j]=b.m[i][j]=1ll; a=matrix_quick_powmod(a,n+2); cout<<(a.m[0][0]-1+mod)%mod< E.符合条件的整数
#include#include #include #include #include #include #include using namespace std; typedef long long ll; const int maxn=36; vector g[maxn]; ll dp[maxn][maxn]; const ll mod=1e9+7; int main(){ int a,b; ll m=1,n=1; cin>>a>>b; for(int i=1;i<=a;i++) m*=2; for(int i=1;i<=b;i++) n*=2; ll i,ans=0; for(i=n-1;i>=m;i--){ if(i%7==m%7){ if(i%7==1) ans++; break; } if(i%7==1) ans++; } cout<
写了个KMP其实暴力即可,因为匹配串不特殊,如果未出现,则不能随意调换,否则换了之后可能匹配了,先将第一个字符和第二个字符,判断是否匹配,如果匹配就换第一个和第三个字符,如果只出现一次,则调换匹配串第一个字符和第二个字符,如果出现两次,则调换第一次出现的第一个字符和第二次出现的第二个字符
#include#include #include #include #include #include #include using namespace std; typedef unsigned long long ll; const int maxn=1000005; vector ans; void cal_next(char *str,int *next,int len){ next[0]=-1; int k=-1; for(int q=1;q<=len-1;q++){ while(k>-1&&str[k+1]!=str[q]){ k=next[k]; } if(str[k+1]==str[q]) k++; next[q]=k; } } bool KMP(char *str,int slen,char *ptr,int plen){ int *next=new int[plen]; cal_next(ptr,next,plen); int k=-1; bool f=0; for(int i=0;i -1&&ptr[k+1]!=str[i]) k=next[k]; if(ptr[k+1]==str[i]) k++; if(k==plen-1){ f=1; ans.push_back(i-plen+1); k=i-plen+2; } } return f; } char s[maxn],t[maxn]={"suqingnianloveskirito"}; int main(){ scanf("%s",s); int slen=strlen(s); int tlen=strlen(t); //cout<