网站开发小组,wordpress扒站教程,房产投资还有前景吗,wordpress全屏显示百度地图前言
依旧是白嫖账号#xff0c;只打了一些题/kk 正题 1002 Buying Snacks
题目大意 nnn个物品#xff0c;每个可以买一次也可以不买#xff0c;如果买需要选择1/21/21/2块钱的#xff0c;然后也可以相邻两个一起买并且减少一块的花销#xff0c;求恰好用掉mmm块钱的方案…前言
依旧是白嫖账号只打了一些题/kk 正题 1002 Buying Snacks
题目大意
nnn个物品每个可以买一次也可以不买如果买需要选择1/21/21/2块钱的然后也可以相邻两个一起买并且减少一块的花销求恰好用掉mmm块钱的方案。
1≤n≤109,1≤m≤20000,1≤T≤51\leq n\leq 10^9,1\leq m\leq 20000,1\leq T\leq 51≤n≤109,1≤m≤20000,1≤T≤5
解题思路
设fi,jf_{i,j}fi,j表示iii个物品花jjj块钱的方案那么有 fi,jfi−1,jfi−1,j−1fi−1,j−2fi−2,j−12×fi−2,j−2fi−2,j−3f_{i,j}f_{i-1,j}f_{i-1,j-1}f_{i-1,j-2}f_{i-2,j-1}2\times f_{i-2,j-2}f_{i-2,j-3}fi,jfi−1,jfi−1,j−1fi−1,j−2fi−2,j−12×fi−2,j−2fi−2,j−3 然后化成生成函数就是 Fi(x)(1xx2)Fi−1(x)(x2x2x3)Fi−2(x)F_i(x)(1xx^2)F_{i-1}(x)(x2x^2x^3)F_{i-2}(x)Fi(x)(1xx2)Fi−1(x)(x2x2x3)Fi−2(x) 和之前一道倍增FFTFFTFFT很像然后考虑分割位置填两个就是F1(x)1xx2F_{1}(x)1xx^2F1(x)1xx2然后 Fab(x)Fa(x)Fb(x)(x2x2x3)Fa−1(x)Fb−1(x)F_{ab}(x)F_{a}(x)F_b(x)(x2x^2x^3)F_{a-1}(x)F_{b-1}(x)Fab(x)Fa(x)Fb(x)(x2x2x3)Fa−1(x)Fb−1(x) 上倍增FFTFFTFFT就好了。
code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N116,P998244353;
ll T,n,k,m,r[N],f[3][N],t[3][N],g[2][N];
void fm(ll x){xx31P;}
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
void NTT(ll *f,ll op){for(ll i0;in;i)if(ir[i])swap(f[i],f[r[i]]);for(ll p2;pn;p1){ll tmppower(3,(P-1)/p),lenp1;if(op-1)tmppower(tmp,P-2);for(ll k0;kn;kp){ll buf1;for(ll ik,tt;i(k|len);i){tt1ll*buf*f[i|len]%P;fm(f[i|len]f[i]-tt);fm(f[i]f[i]tt-P);buf1ll*buf*tmp%P;}}}if(op-1){ll invnpower(n,P-2);for(ll i0;in;i)f[i]1ll*f[i]*invn%P;}return;
}
void print(ll x)
{if(x9)print(x/10);putchar(x%100);return;}
signed main()
{scanf(%lld,T);while(T--){memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(t,0,sizeof(t)); scanf(%lld%lld,m,k);k;n1;while(n(k*2))n1;for(ll i0;in;i)r[i](r[i1]1)|((i1)?(n1):0);f[0][0]f[0][1]f[0][2]f[1][0]g[0][0]1;for(ll d1;dm;d1){if(md){for(ll j0;j3;j){for(ll i0;in;i)t[j][i](ik)?f[j][i]:0;NTT(t[j],1);}NTT(g[0],1);NTT(g[1],1);for(ll i0;in;i){ll b0g[0][i],b1g[1][i];g[0][i]1ll*b0*t[0][i]%P;g[1][i]1ll*b0*t[1][i]%P;t[0][i]1ll*t[1][i]*b1%P;t[1][i]1ll*t[2][i]*b1%P;}NTT(g[0],-1);NTT(g[1],-1);NTT(t[0],-1);NTT(t[1],-1);for(ll i0;ik;i){(g[0][i1]t[0][i])%P;(g[0][i2]2ll*t[0][i])%P;(g[0][i3]t[0][i])%P;(g[1][i1]t[1][i])%P;(g[1][i2]2ll*t[1][i])%P;(g[1][i3]t[1][i])%P;}for(ll ik;in;i)g[0][i]g[1][i]0;}if(d*2m)break;for(ll j0;j3;j){for(ll i0;in;i)t[j][i](ik)?f[j][i]:0;NTT(t[j],1);}for(ll i0;in;i){f[0][i]1ll*t[0][i]*t[0][i]%P;f[1][i]1ll*t[1][i]*t[0][i]%P;f[2][i]1ll*t[1][i]*t[1][i]%P;t[0][i]1ll*t[1][i]*t[1][i]%P;t[1][i]1ll*t[1][i]*t[2][i]%P;t[2][i]1ll*t[2][i]*t[2][i]%P;}for(ll j0;j3;j)NTT(f[j],-1),NTT(t[j],-1);for(ll i0;ik-1;i){(f[0][i1]t[0][i])%P;(f[0][i2]2ll*t[0][i])%P;(f[0][i3]t[0][i])%P;(f[1][i1]t[1][i])%P;(f[1][i2]2ll*t[1][i])%P,(f[1][i3]t[1][i])%P;(f[2][i1]t[2][i])%P;(f[2][i2]2ll*t[2][i])%P;(f[2][i3]t[2][i])%P;}for(ll ik;in;i)f[0][i]f[1][i]f[2][i]0;}for(ll i1;ik;i)print(g[0][i]),putchar( );putchar(\n);}return 0;
}1004 Counting Stars
题目大意
nnn个数字要求支持操作
将一个区间所有数字的最低位减去将一个区间非零数字的最高位提高一位
每次操作玩输出操作区间的和
1≤T≤5,1≤n,q≤105,1≤ai≤1091\leq T\leq 5,1\leq n,q\leq 10^5,1\leq a_i\leq 10^91≤T≤5,1≤n,q≤105,1≤ai≤109
解题思路
每个数字操作一最多执行logai\log a_ilogai次所以这个操作暴力做就好了
然后第二个操作我们把每个数字的最高位分离出来就变成了区间乘二。
代码是lemondinosaur\text{lemondinosaur}lemondinosaur爷写的 1006 GCD Game
题目大意
nnn个数字每次操作的人可以选择一个数字xxx然后找一个1≤kx1\leq kx1≤kx将xxx变为gcd(x,k)gcd(x,k)gcd(x,k)。
不能操作者输求是否先手必胜 1≤T≤100,∑n≤106,1≤ai≤1071\leq T\leq 100,\sum n\leq 10^6,1\leq a_i\leq 10^71≤T≤100,∑n≤106,1≤ai≤107
解题思路
其实就是去掉任意个质因子所以用线性筛筛出每个数字的最小质因子然后递推出每个数字的质因子数就好了。 时间复杂度O(ai∑n)O(a_i\sum n)O(ai∑n)
code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e710;
int T,n,cnt,pri[N/10],v[N],c[N];
void Prime(){v[1]1;for(int i2;iN;i){if(!v[i])pri[cnt]i,v[i]i;for(int j1;jcnti*pri[j]N;j){v[i*pri[j]]pri[j];if(i%pri[j]0)break;}}return;
}
int main()
{Prime();for(int i2;iN;i)c[i]c[i/v[i]]1;scanf(%d,T);while(T--){scanf(%d,n);int ans0;for(int i1,x;in;i)scanf(%d,x),ansans^c[x];if(ans)puts(Alice);else puts(Bob);}return 0;
}1009 Singing Superstar
题目大意
给一个字符串SSSnnn次询问字符串aia_iai在SSS中出现的最大不重次数。
1≤T≤5,1≤n≤105,1≤∣ai∣≤30,∑∣S∣,∑∣ai∣≤4×1051\leq T\leq 5,1\leq n\leq 10^5,1\leq |a_i|\leq 30,\sum |S|,\sum|a_i|\leq 4\times 10^51≤T≤5,1≤n≤105,1≤∣ai∣≤30,∑∣S∣,∑∣ai∣≤4×105
解题思路
根据贪心的思想是能够匹配尽量匹配 把所有SSS长度不超过303030的子串建一棵TrieTrieTrie然后记下每个子串的最后出现位置然后统计ansansans就好了。
code
#includecstdio
#includecstring
#includealgorithm
#define ull unsigned long long
using namespace std;
const int N1e510;
int n,T,l,cnt,ans[N*30],t[N*30][26],last[N*30];
char s[N],st[N];
int main()
{scanf(%d,T);while(T--){scanf(%s,s1);lstrlen(s1);cnt1;last[1]ans[1]0;memset(t[1],0,sizeof(t[1]));for(int i1;il;i){int x1;for(int j1;j30;j){if(i-j11)break;int cs[i-j1]-a;if(!t[x][c]){cnt;memset(t[cnt],0,sizeof(t[cnt]));t[x][c]cnt;last[cnt]ans[cnt]0;}xt[x][c];if(i-last[x]j)last[x]i,ans[x];}}scanf(%d,n);while(n--){scanf(%s,st1);int tlstrlen(st1),x1;for(int itl;i1;i--)xt[x][st[i]-a];printf(%d\n,ans[x]);}}return 0;
}
