首页 > 代码库 > 2016弱校联萌十一专场10.5
2016弱校联萌十一专场10.5
A.
因为字符串不可以交叉，其实容易解
把不同字符的可用区域看成一个区间，用类似于链表的方法连接起来
查询的就是查询到的链表数量/4（当然右区间必须属于y）
区间查询用倍增或线段树都可以
//倍增#include <cstdio>#include <cstring>char s[100005];int m, n, pe, pa, ps, py, dep;int pre[100005], ed[100005];int fa[100005][20];int main() { scanf("%s", s); scanf("%d", &m); n = strlen(s); for (int i = 0; i < n; ++i) { if (s[i] == ‘e‘) { pre[i + 1] = py; pe = i + 1; } if (s[i] == ‘a‘) { pre[i + 1] = pe; pa = i + 1; } if (s[i] == ‘s‘) { pre[i + 1] = pa; ps = i + 1; } if (s[i] == ‘y‘) { pre[i + 1] = ps; py = i + 1; } ed[i + 1] = py; } for (int i = 1; i <= n; ++i) fa[i][0] = pre[i]; for (dep = 1; 1 << dep < n; ++dep); for (int i = 1; i < dep; ++i) for (int j = 1; j <= n; ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1]; for (; m--;) { int l, r; scanf("%d%d", &l, &r); int x = ed[r]; int res = 1; for (int i = dep - 1; i >= 0; --i) { if (fa[x][i] >= l) { x = fa[x][i]; res += 1 << i; } } printf("%d\n", res / 4); } return 0;}
F.
求f(f(n))%20160519，其中f(0)=0 f(1)=1 f(i)=f(i-1)+f(i-2)
fib数列其实有循环节的，当运行到f(k-1)%k==k-1 f(k)==1 那循环节就是k
顺带补下这种数列的循环节知识：
当模数是质数模5余1或4，则这种数是5的二次剩余，则循环节是p-1的因子
当模数是质数模5余2或3，则这种数是5的二次非剩余，则循环节是2p+2的因子
当模数是合数，p=p1^a1*p2^a2*.....
可以想到积性函数，循环节是lcm(p1^(a1-1)*(p1的对应循环节数)*p2^(a2-1)*(p2的对应循环节数)*...)
lcm(...)是里面所有数的最小公倍数
然后快速幂一波AC
I.
题意：求出[l,r]所有单调不递增||单调不递减数
数位dp，没得说的，注意常数太大，o(10logn)会超时
所以就愉快地记忆化搜索，把指定位置是包括0~9位的全部填上
或者直接开场直接处理9、99、999...这些数的对应计数
这样就可以o(logn)胡搞了
果然不应该搞这么久的。。。比赛哪有那么多时间给你搞
以上是标准做法，已AC，我的非主流做法在下：
我是想用前缀和把搜索过程的复杂度压缩一下的，结果WA
大神求教
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>#include<stack>#include<math.h>#include<vector>#include<map>#include<set>#include<stdlib.h>#include<cmath>#include<string>#include<algorithm>#include<iostream>#include<assert.h>using namespace std;typedef long long ll;int max(int a,int b){return a>b?a:b;}int min(int a,int b){return a<b?a:b;}ll fac[21];ll tal[20][10][2],pre[20][10][2];//0:down,1:allll f(int n){return n<0?0:fac[n];}void gettal(){ fac[0]=1; memset(tal,0,sizeof(tal)); memset(pre,0,sizeof(pre)); int i,j; for(i=1;i<21;i++)fac[i]=fac[i-1]*i; for(i=0;i<10;i++)tal[0][i][1]=1,tal[0][i][0]=0,pre[0][i][1]=pre[0][i][0]=i+1; for(i=1;i<20;i++) { for(j=0;j<10;j++) { tal[i][j][0]=j==0?0:f(i+j-1)/f(j-1)/f(i); tal[i][j][0]+=tal[i-1][j][0]; tal[i][j][1]=tal[i][j][0]+tal[i-1][j][1]-tal[i-1][j][0]; tal[i][j][1]+=j==9?0:f(8-j+i)/f(8-j)/f(i); pre[i][j][0]=j?pre[i][j-1][0]+tal[i][j][0]:tal[i][j][0]; pre[i][j][1]=j?pre[i][j-1][1]+tal[i][j][1]:tal[i][j][1]; } }}ll solve(ll n){ if(!n)return 1; int i,j,path,ph; ll tmp,ans=0; for(i=0,tmp=1;n>=tmp;i++,tmp*=10);i--;tmp/=10; int stat=1; path=n/tmp; ans+=pre[i][path-1][1]-pre[i][0][1]; tmp/=10; for(i--;i>0;i--) { ans+=pre[i][9][1]-pre[i][0][1]; ph=(n%(tmp*10))/tmp; if(stat==1)//keep { if(path>ph){stat=0;if(ph)ans+=pre[i][ph-1][0]+ph;} else if(path==ph){if(ph)ans+=pre[i][ph-1][0]+ph;} else { stat=2; ans+=pre[i][ph-1][0]+ph; ans+=tal[i][ph][1], ans+=pre[i][ph-1][1]-pre[i][path][1]; ans-=pre[i][ph-1][0]-pre[i][path][0]; } path=ph; } else if(stat==2)//increase { if(path>ph) { stat=3; break; } ans+=pre[i][ph-1][1]-pre[i][path-1][1]-pre[i][ph-1][0]+pre[i][path-1][0]; path=ph; } else if(stat==0 && path)//decrease { if(ph)ans+=pre[i][min(path,ph)-1][0]+min(path,ph); path=min(path,ph); } tmp/=10; } ans+=pre[0][9][1]; ph=(n%(tmp*10))/tmp; if(stat==0)ans+=min(path,ph)+1; else if(stat==1)ans+=ph+1; else if(stat==2)ans+=max(0,ph-path+1); return ans;}int main(){ int t; ll l,r; gettal(); scanf("%d",&t); while(t--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } return 0;}
J.
题意。。。实在难以描述，看https://acm.bnu.edu.cn/v3/statments/taiwan2016.pdf吧
这题一看像是多项式乘法，但是下面的不是加而是取其最大，所以什么fft，nft都可以歇歇了
其实也不难想到解法，把最大数填上对应位置，之后从大到小填，碰到已填元素就跳过
直到整个表都填满为止
为什么这样看似o(n^2)的解法不会超时。。。我也不知道。。。
写时SB了，数组开成10^5结果老RE
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>#include<stack>#include<math.h>#include<vector>#include<map>#include<set>#include<stdlib.h>#include<cmath>#include<string>#include<algorithm>#include<iostream>#include<assert.h>using namespace std;typedef long long ll;int max(int a,int b){return a>b?a:b;}int min(int a,int b){return a<b?a:b;}int a[2][200060];int occupy[200060];int main(){ int n,j,i,t; memset(occupy,-1,sizeof(occupy)); scanf("%d",&n); for(j=0;j<2;j++) { for(i=0;i<n;i++) { scanf("%d",&t); a[j][t]=i; } } int cnt=n; for(i=n*2-2;cnt;i--) { for(j=max(0,i-n+1);j<n && cnt;j++) { if(i<j)continue; if(i-j>=n)break; t=a[0][j]+a[1][i-j]; if(occupy[t%n]==-1)occupy[t%n]=i,cnt--; } } for(i=0;i<n;i++)printf("%d%c",occupy[i],i==n-1?‘\n‘:‘ ‘); return 0;}
2016弱校联萌十一专场10.5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。