E 666

求6的子串的个数，误导了一发男神，让他求成子序列了。

ans=∑i=1k(Pi+1)∗Pi/2,Pi为某一段连续的6的个数。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define LL long long using namespace std; char str[222222]; int main(){ int T; int n; scanf("%d", &T); while(T--){ int n; scanf("%d%s", &n, str); long long ans = 0; LL num = 0; for(int i=0;i<n;i++){ if (str[i] == '6'){ num++; } else{ ans += num*(num+1)/2; num = 0; } } if(num>0)ans += num*(num+1)/2; printf("%lld\n", ans); } return 0; }

H Blocks

斐波那契数列，f[1]=1,f[2]=2,求f[n]%(1e9+7)。 n很大，于是要用到矩阵加速。

求[1110]n,ans=base[0][0]+base[1][0]

#include<cstdio> #include<cstring> #include<iostream> using namespace std; typedef long long ll; const ll P = 1000000007; const int N=13; ll n,m; struct matrix{ ll a[N][N]; int row,col; matrix():row(N),col(N){memset(a,0,sizeof(a));} matrix(int x,int y):row(x),col(y){memset(a,0,sizeof(a));} ll* operator [] (int x){return a[x];} matrix operator * (matrix x){ matrix tmp ; for (int i=0;i<=n+1;i++) for (int j=0;j<=n+1;j++){ tmp[i][j]=0; for (int k=0;k<=n+1;k++) tmp[i][j]=(tmp[i][j]+a[i][k]*x[k][j])%P; } return tmp; } void operator *= (matrix x){*this = *this * x;} matrix operator ^ (ll x){ matrix ret; for (int i=0;i<=n+1;i++)ret[i][i]=1; matrix tmp = *this; for (;x;x>>=1,tmp*=tmp){if(x&1)ret *=tmp;} return ret; } }; int main(){ ll a,b,num; n=2; while(cin>>num,(num)){ a=b=1; matrix base; base[0][0]=a;base[0][1]=1;base[1][0]=b;base[1][1]=0; base = base ^ (num); cout<<(base[0][1]+base[1][1])%P<<endl; } return 0; }

I Pairs Again

给你一个序列，找两数之差为K的对数的个数。 map水过。 数字有可能重复，注意统计个数。

#include <cstdio> #include <cstring> #include <map> #include <iostream> #define LL long long using namespace std; LL a[111111]; int main(){ int n,k; while(~scanf("%d%d",&n,&k)){ long long ans = 0; map<long long, int>mp; for(int i=1;i<=n;i++){ scanf("%lld", &a[i]); mp[a[i]]++; } for(int i=1;i<=n;i++)ans+=mp[a[i]+k]; cout<<ans<<endl; } return 0; }

J Odd number

计算奇数的个数。

#include <cstdio> using namespace std; int main(){ int n; while(~scanf("%d", &n)){ int ans=0; int a; while(n--){ scanf("%d",&a); if(a%2==1)ans++; } printf("%d\n",ans); } return 0; }

D Pairs

统计和小于K的数对的对数。 跟青岛热身赛C题差不多。 乘法原理ans[i+j-1] = a[i]*b[j] 用数组下标代替数字的值。 求个前缀和。

cout超时，哈哈哈哈哈。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> #define LL long long using namespace std; const double PI = acos(-1.0); struct complex { double r,i; complex(double _r = 0,double _i = 0) { r = _r; i = _i; } complex operator +(const complex &b) { return complex(r+b.r,i+b.i); } complex operator -(const complex &b) { return complex(r-b.r,i-b.i); } complex operator *(const complex &b) { return complex(r*b.r-i*b.i,r*b.i+i*b.r); } }; void change(complex y[],int len) { int i,j,k; for(i = 1, j = len/2;i < len-1;i++) { if(i < j)swap(y[i],y[j]); k = len/2; while( j >= k) { j -= k; k /= 2; } if(j < k)j += k; } } void fft(complex y[],int len,int on) { change(y,len); for(int h = 2;h <= len;h <<= 1) { complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h)); for(int j = 0;j < len;j += h) { complex w(1,0); for(int k = j;k < j+h/2;k++) { complex u = y[k]; complex t = w*y[k+h/2]; y[k] = u+t; y[k+h/2] = u-t; w = w*wn; } } } if(on == -1) for(int i = 0;i < len;i++) y[i].r /= len; } const int MAXN = 100001; complex x1[MAXN<<2]; int a[MAXN]; LL ans[MAXN<<2],sum[MAXN<<2]; int main(){ int T,n,m; scanf("%d",&T); while(T--){ scanf("%d%d",&n, &m); memset(ans,0,sizeof(ans)); for(int i=0;i<n;i++){ scanf("%d",&a[i]); ans[a[i]]++; } sort(a,a+n); int len1=a[n-1]+1; int len=1; while(len<2*len1) len<<=1; for(int i=0;i<len;i++){ if(ans[i]) x1[i] = complex(ans[i],0); else if(ans[i]==0) x1[i] = complex(0,0); } fft(x1,len,1); for(int i=0;i<len;i++) x1[i] = x1[i]*x1[i]; fft(x1,len,-1); for(int i=0;i<len;i++) ans[i] = (LL)(x1[i].r+0.5); len = a[n-1] << 1; for(int i = 0;i < n;i++) ans[a[i]+a[i]]--;//去重 for(int i = 1;i <= len;i++) ans[i]/=2;//去正反 for(int i = 1;i <= len;i++) ans[i]+=ans[i-1];//前缀和 while(m--){ int k; scanf("%d", &k); printf("%lld\n",ans[k-1]); } } return 0; }

PS:真的全世界都会FFT？

K Candy

M个人每个人都有N个选择，M^N%P 二分快速幂。。。

#include <iostream> using namespace std; long long a,b; const long long p = 1000000007; long long bigpow(long long x, long long y) { long long ret = 1; long long tmp = x; while (y > 0) { if (y & 1) ret = (ret%p)*(tmp%p)%p; y >>= 1; tmp = (tmp%p) * (tmp%p) % p; } return ret; } int main(){ int T; cin>>T; while(scanf("%lld%lld",&a,&b),T--) printf("%lld\n",bigpow(b,a)); return 0; }

L Lucky Number

找出字符串匹配，6，8，86，68个数符合要求的数字。 贪心。 首先考虑几种不可能的情况。 a1 < a3||a2 < a3||a1 < a4||a2 < a4 8、6个数不匹配。 abs(a4-a3)>1 然后贪心，先放6之后68>=86，考虑细节处。 先放8相反。

直接贴标程吧。

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; char ch[3000006]; int main(){ int a1,a2,a3,a4; while(~scanf("%d%d%d%d",&a1,&a2,&a3,&a4)){ if(abs(a3-a4)>1||a1<a3||a2<a3||a1<a4||a2<a4){ puts("-1"); continue; } if(a3-a4==1){//668686868686888888 for(int i=0;i<a1-a3;i++) printf("6"); for(int i=0;i<a3;i++) printf("68"); for(int i=0;i<a2-a3;i++) printf("8"); puts(""); continue; } if(a4-a3==1){ if(a4==1){//888666 for(int i=0;i<a2;i++) printf("8"); for(int i=0;i<a1;i++) printf("6"); puts("");; } else {//86666668686868888886 printf("8"); for(int i=0;i<a1-a4+1;i++) printf("6"); for(int i=0;i<a4-2;i++) printf("86"); for(int i=0;i<a2-a4+1;i++) printf("8"); printf("6"); puts(""); } continue; } a3++; a4++; if(a1>=a3&&a2>=a3-1){ for(int i=0;i<a1-a3;i++) printf("6"); for(int i=0;i<a3-1;i++) printf("68"); for(int i=0;i<a2-a3+1;i++) printf("8"); printf("6"); puts(""); } else if(a1==a3-1&&a2>=a3){ for(int i=0;i<a3-1;i++) printf("86"); for(int i=0;i<a2-a4+1;i++) printf("8"); puts(""); } else { puts("-1"); continue; } } }