最近集训做了不少题，在这里整理一下其中有趣的题目。
有趣的题目是指：弱弱的icebound想一想可以做得出来的题，并且不是很难写，不毒瘤，也不太水的题。
按倒序吧：
第二次比赛：
Gym – 101606L Lounge Lizards
有一些蜥蜴，第i只蜥蜴站在(xi,yi)点，他们有各自的高度hi。点(Tx,Ty)处有一个电视机，蜥蜴们想要看电视，但是高度高的蜥蜴会挡住高度低的蜥蜴。
求最多有多少只蜥蜴能看到电视。
首先考虑弱化问题：如果蜥蜴们不站在平面上，而是站在数轴上，答案是什么呢？
就是最长上升子序列。。。
如果蜥蜴在平面上，如果被挡，只有可能是电视机、蜥蜴A、蜥蜴B三点共线的时候，蜥蜴A才有可能挡住蜥蜴B。所以我们只需要考虑N点共线的情况即可。
我们把电视机设为原点，转化为极坐标系(d,θ)，那么所有θ相同的点均会共线。
然后统计共线的点(map或排序，map好像会被卡)，做最长上升子序列即可.
代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const double eps=1e-7; const int N=1100005; double get_jiao(int x,int y) { return atan2(1.0*y,1.0*x); } struct pos { int p; int x,y,h; double jiao; }s[N]; double dis(double x,double y) {return x*x+y*y;} bool cmp(pos a,pos b) { if(abs(a.jiao-b.jiao)<eps)return dis(1.0*a.x,1.0*a.y)<dis(1.0*b.x,1.0*b.y);="" return="" a.jiao<b.jiao;="" }="" int="" stack[n],top,n;="" dp(int="" s[],int="" n)="" {="" top="0;" for(int="" i="1;i<=n;i++)" if(top="=0||s[i]">stack[top])stack[++top]=s[i]; else *lower_bound(stack+1,stack+top+1,s[i])=s[i]; } return top; } int a[N]; int work(int l,int r) { int cnt=0; if(l>r)swap(l,r); //cout<<"work "<<l<<" "<<r<<endl;="" for(int="" i="l;i<=r;i++)a[++cnt]=s[i].h;" return="" dp(a,cnt);="" }="" int="" main()="" {="" tx,ty;="" cin="">>tx>>ty; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].h); s[i].x-=tx,s[i].y-=ty; s[i].jiao=get_jiao(s[i].x,s[i].y); } sort(s+1,s+n+1,cmp); int p=1; long long ans=0; for(int i=2;i<=n;i++) { if(abs(s[i].jiao-s[p].jiao)<eps) {="" continue;="" }="" else="" ans+="work(p,i-1);" p="i;" cout<<ans<<endl;="" return="" 0;="" <="" pre=""> <a href="http://codeforces.com/problemset/problem/977/D" rel="noopener noreferrer" target="_blank">cf 977d Divide by three, multiply by two</a> 有一种游戏 可以把一个数除3或者乘二，在玩这个游戏的时候，操作n次，每次操作都会产生一个数，把这些数按操作顺序排好，就成了操作队列。 给出n个数，要求你把他们排序为一个合法的操作队列。 比如 9 3 6 12 就是合法的队列。 这个题其实可以爆搜过的。。。在这里说一个排序做法。 对于一个数a[i]，他只有含有3的因子时才可以除3，而乘2没有限制。 所以，先把3的因子多的数放前面，如果两个数3的因子相同，先放小的，这样可以乘2。 sort一下就过了。。。 <pre lang="cpp">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int N=105; struct pos { unsigned long long a; int three; }s[N]; int get_three(unsigned long long t) { int ret=0; while(t%3==0) { t/=3; ret++; } return ret; } bool cmp(pos a,pos b) { if(a.three==b.three)return a.a<b.a; return="" a.three="">b.three; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)cin>>s[i].a; for(int i=1;i<=n;i++)s[i].three=get_three(s[i].a); sort(s+1,s+n+1,cmp); for(int i=1;i<=n;i++)cout<<s[i].a<<" ";="" return="" 0;="" }="" <="" pre=""> <strong>第三次比赛：</strong> <a href="http://codeforces.com/problemset/problem/791/D" rel="noopener noreferrer" target="_blank">CF 791D：Bear and Tree Jumps</a> 给出一颗树，现在每次最多可以走k步，最少可以走1步，定义f(s,t)为从s到t走的最少步数。 求∑f(s,t) 其中s,t为树上的所有点。 考虑弱化问题，如果k=1，也就是求树上最短路的总和，这是一个经典的树形dp，不多说了，把这个树上最短路总和的答案设为sum。 乍一看，每次最多走k步这个最短路的答案在sum/k附近。但是，对于一条路径path(s,t)，前半部分每次跳k步，最后有可能会剩下一部分，还要再跳一下，设最后这部分的需要跳的步数为q。 那么看上去，答案是(sum)/k+q。把q放进去，还原为路径长度，补全答案，变成(sum+dis)/k 所以一遍树形dp先把sum求了，再求dis就行。那dis怎么算？ 我们考虑两点间距离公式 d=deep[v]+deep[u]-2*deep[lca(u,v)] 很容易得到每次需要向答案中增补的dis=d%k。 我们发现k只有5，引导着我们把k放进树形dp里。 设状态f[v][j]为以v为根的子树中，deep%k=j的节点的方案数。至此我们把深度放进mod k剩余系下考虑: 那么v子树贡献的答案为[k-(x+y-2*deep[v])]*(∑f[z][x])*f[u][y] 其中z,u为v的儿子，x,y为深度(均小于k大于0，mod k剩余系)。 这个转移方程实际是枚举深度，把v子树中任意两点以深度表示，从而减少了状态量。 细节需要注意一下，∑f[z][x]用【一边转移一边算答案】得到，也是常见的技巧。 代码： <pre lang="cpp">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; //树形dp CF见过好像 const int N=200005,M=N*3; int head[N],list[M],nxt[M],tot; void add(int a,int b) { tot++; list[tot]=b; nxt[tot]=head[a]; head[a]=tot; } long long f[N][6],ans,sz[N]; int vis[N],n; long long k; void dfs(int v,int deep,int fa) { f[v][deep%k]=1;//根到v方案数 sz[v]=1; // vis[v]=1; for(int i=head[v];i;i=nxt[i]) { int u=list[i]; if(u!=fa) { dfs(u,deep+1,v); for(int x=0;x<k;x++) for(int="" y="0;y<k;y++)" {="" long="" d="((x+y-deep*2)%k+k)%k;" cha="((k-d)%k+k)%k;" ans+="cha*f[v][x]*f[u][y];" }="" sz[v]+="sz[u];" x="0;x<k;x++)f[v][x]+=f[u][x];" int="" main()="" scanf("%d%lld",&n,&k);="" i="1;i<=n-1;i++)" a,b;scanf("%d%d",&a,&b);="" add(a,b);="" add(b,a);="" dfs(1,0,0);="" cout<<ans="" k<<endl;="" <="" pre=""> <a href="http://codeforces.com/problemset/problem/2/B" rel="noopener noreferrer" target="_blank">CodeForces - 2B The least round way</a> 给出一个n*n方阵，从左上角出发，每次可以向右或向下走，直到走到右下角为止。 要求找到一条路径，使得经过路径上的数字乘积末尾的0最少。 又是一个末尾0的问题，之前算阶乘末尾0的时候就搞过了。。 一个整数数字末尾的0的数量=min(因子2的指数，因子5的指数），这是个常见结论。 所以，我们只要让路径上2的因子指数最少或者5的因子指数最少就行。 首先预处理s[i][j][0]=(i,j)位置的数字的2的因子指数，s[i][j][1]=(i,j)位置的数字5的因子指数。 设f[i][j][0]为到点(i,j)的2的因子指数，f[i][j][1]为到点(i,j)的5的因子指数。 那么f[i][j][k]=min(f[i-1][j][k],f[i][j-1][k])+s[i][j][k] 很科学 最后统计答案记录路径就行了........WA? 这题有一个坑，如果路径上有0，那么答案一定为1(末尾有1个0) 坑爆，我们预处理0，把0看成一个10的倍数(10,100,1000其实有1,5都行)，这样求出来的是【尽量不经过0】的路径。 如果这个【尽量不经过0】的路径答案为0或1，那肯定有一条更优秀或者同样好的路径了，不需要走0了。 如果答案比1大，那么肯定经过0，特判处理。 代码： <pre lang="cpp">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=1005; int get(int a,int b) { int ret=0; while((a%b==0)&&a!=0) { a/=b; ret++; } return ret; } int path[N][N][2],f[N][N][2],s[N][N][2],a[N][N]; char ans_q[N*N]; int cnt,n,xo,yo,fo; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); int now=a[i][j]; if(now==0) { now=10; fo=1; xo=i,yo=j; } s[i][j][0]=get(now,2); s[i][j][1]=get(now,5); } memset(f,0x3f,sizeof f); for(int k=0;k<=1;k++)f[1][1][k]=s[1][1][k]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<=1;k++) { if(i==1&&j==1)continue; if((i-1>0)&&f[i][j][k]>f[i-1][j][k]+s[i][j][k]) { f[i][j][k]=f[i-1][j][k]+s[i][j][k]; path[i][j][k]='D'; } if((j-1>0)&&f[i][j][k]>f[i][j-1][k]+s[i][j][k]) { f[i][j][k]=f[i][j-1][k]+s[i][j][k]; path[i][j][k]='R'; } } int ans_k=0,ans=min(f[n][n][0],f[n][n][1]); if(f[n][n][0]>=f[n][n][1])ans_k=1; if(ans>1&&fo==1)//这种情况显然走0比较划算 { ans=1; for(int i=1;i<xo;i++) ans_q[++cnt]="D" ;="" for(int="" i="1;i<yo;i++)" }="" else="" {="" int="" x="n,y=n;" while(1)="" if(x="=1&&y==1)break;" char="" now="path[x][y][ans_k];" if(now="='D')x--;//向下" y--;="" 向右="" reverse(ans_q+1,ans_q+cnt+1);="" printf("%d\n",ans);="" printf("%c",ans_q[i]);="" return="" 0;="" <="" pre=""> <a href="http://codeforces.com/problemset/problem/57/C" rel="noopener noreferrer" target="_blank">CodeForces - 57C Array</a> 给出长度n，求长度为n，且每个数字都是[1,n]范围内的数列的个数，并满足以下条件之一： 从第二个元素开始，每个元素不超过前一个元素 从第二个元素开始，每个元素不小于前一个元素 <del datetime="2018-08-11T11:54:28+00:00">解法1：像icebound一样随便打个表就看出来答案是C(2n,n)-n了，然后组合数模板扔上去即可。</del> 解法2： 网搜得到题解： 由于对称性，我们只要求非降序的个数就可以了（n个数全部相等的情况既属于非升也属于非降） 我们在满足条件的n个数之前加一个虚节点1，在第n个数之后加一个虚节点n，那么考虑这n+2个数组成的非降序列： 假设序列里的第i个数为a[i]，我们设xi=a[i+1]-a[i]+1，1<=i<=n+1，则满足每个数>=1,且sum(x[1],x[2]...x[n+1])=2*n； 那么相当于求将2*n分成n个部分，且每个部分的值大于等于1，则易得非降序列总数为：C(n,2*n-1)（2*n-1 选 n） 所以最后的答案是2*C(n,2*n-1)-n； 这个其实是差分序列的应用，orz。 <pre lang="cpp">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const long long p=1000000007; long long power(long long a,long long b,long long p) { long long ret=1; while(b) { if(b%2)ret=(ret*a)%p; b/=2; a=(a*a)%p; } return ret; } long long jie(long long t,long long p) { long long ret=1; for(long long i=1;i<=t;i++) ret=(ret*i)%p; return ret; } long long C(long long n,long long m,long long p) { long long fz=jie(n,p); long long fm=(jie(m,p)*jie(n-m,p))%p; return (fz*power(fm,p-2,p))%p; } int main() { long long n; scanf("%lld",&n); cout<<((C(n*2,n,p)-n)%p+p)%p<<endl; return="" 0;="" }="" <="" pre=""> <a href="https://www.hackerrank.com/contests/w30/challenges/substring-queries" rel="noopener noreferrer" target="_blank">HackerRank - substring-queries </a> 给你n个字符串，多次询问最长公共子串。 不会做，好像是后缀数组。 过几天补。。 <a href="https://www.hackerrank.com/contests/w26/challenges/hard-homework" rel="noopener noreferrer" target="_blank">HackerRank - hard-homework </a> 给一个数字n，求sin(x)+sin(y)+sin(z)最大值，且x+y+z=n 不会做，好像是神题。 过几天补。。 <a href="http://codeforces.com/problemset/problem/145/C" rel="noopener noreferrer" target="_blank">CodeForces - 145C Lucky Subsequence</a> 定义lucky number: 每个数位只能是4或7的数字。 给出一个序列，求合法的,长度为k的子序列数量： 合法子序列是指：子序列中不存在两个相同的lucky number。 这是个经典问题吧。。。（然而差点没做出来） 首先，我们发现，lucky number个数很少（数组开到3000过了） 我们预处理每个序列里含有多少个不同的lucky number f[i][j]表示前i个lucky number选了j个的方案数 f[i][j]=f[i-1][j]+f[i-1][j-1]*s[j] s[j]为第j个lucky number的出现次数 （这好像是斯特林数？) 然后我们统计答案： ans=∑(f[n][i]*c(m,k-i)) 其中m为非lucky number的数量 就是先选i个lucky number，再从m个里面选k-i个填满这个序列 代码： <pre lang="cpp">#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<map> using namespace std; const int N=3505,M=200005; const long long p=1000000007; /* lucky number的数量应该很少 f[i][j]表示前i个lucky number 选了j个的方案数 不能重 f[i][j]=f[i-1][j]+f[i-1][j-1]*s[j] ans=Σf[all][i]*C(剩下的,k-i) 傻逼了 组合数可能很大 */ int n,k; long long f[N][N],s[N],jie[M]; long long power(long long a,long long b,long long p) { long long ret=1; while(b) { if(b%2)ret=(ret*a)%p; b/=2; a=(a*a)%p; } return ret; } void init_jie(long long p) { jie[0]=1; for(long long i=1;i<=110005;i++)jie[i]=(jie[i-1]*i)%p; } long long C(long long n,long long m,long long p) { if(m>n)return 0; if(m==0||m==n)return 1; long long fz=jie[n]%p; long long fm=(jie[m]*jie[n-m])%p; return (fz*power(fm,p-2,p))%p; } bool is_lucky(int t) { while(t) { if(t%10!=7&&t%10!=4)return 0; t/=10; } return 1; } map<int,int>vis; int a[M],cnt; int main() { scanf("%d%d",&n,&k); int m=0; init_jie(p); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(is_lucky(a[i])) { if(vis[a[i]]==0) vis[a[i]]=++cnt; s[vis[a[i]]]++; } else m++; } for(int i=0;i<=cnt;i++)f[i][0]=1; for(int i=1;i<=cnt;i++) { for(int j=1;j<=i;j++) f[i][j]=(f[i-1][j]+(f[i-1][j-1]*s[i]%p)%p)%p; } long long ans=0; for(int i=0;i<=cnt&&i<=k;i++) { ans=(ans+(f[cnt][i]*C(m,k-i,p))%p)%p; } cout<<ans%p<<endl; return="" 0;="" }="" <="" pre=""> 未完待续。。。。 </ans%p<<endl;></int,int></map></cmath></algorithm></cstdio></cstring></iostream>