Wannafly挑战赛5
A.珂朵莉与宇宙
题意
给你一个长为n的序列a，有n*(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数（1 <= n <= 100000，0 <= ai <= 10）
分析
前缀和+标记
石乐志啊最近，这么辣鸡的题都卡了一下，直接前缀和count一下，这个数据范围一看就像emmmm
经典的sum[0]=1，这个是为了全选（1到当前位置全选）的时候，还有的是先统计在更新（有时间在撕烤一下）
时间复杂度小于O（n*1000）
#include<bits/stdc++.h> const int mod = 1e9+7; const int maxn = 1e5+5; const double EPS = 1e-6; using namespace std; int fac[maxn]; int n; int a[maxn]; int sum[maxn*10+10]; int main() { scanf("%d", &n); int allsum=0; ll ok=0; sum[0]++; for(int i=1;i<=n;i++) { scanf("%d", &a[i]); allsum+=a[i]; for(int j=0;j<=1000;j++) { if(allsum<j*j) break; ok=ok+1ll*sum[allsum-j*j]; } sum[allsum]++; } printf("%lld\n", ok); return 0; }View Code
B.可编程拖拉机比赛
签到
C.标准差
题意
n个点m条边的有向图，边上有边权we，你需要找到一条1到n的路径使得经过的边的标准差最小（n<=30，m<=100，w<=100） x1,x2,...,xk的标准差计算方法如下： 设。 则标准差。 note：这条路径不一定要是简单路径 分析 这道题很可做啊，首先看出数据范围很小，暴力搜索即可 环的问题：不难想出，一个环如果对答案有正贡献，则走无数次这个环，最终答案也就可以看做这个环的标准差。 如何找环：BF算法可以找，但dfs直接可以找，根据dfs序对dfs上的点编号，一个点如果找到两次，肯定有环，dfs的时候再根据dfs序把边权赋给节点即可 ！！需要注意的是一个点可能在多个环上，每次遍历完当前节点的所有点，这个点要重新蛇者为未标记，重新标号。 时间复杂度O() ?? // 不太会算啊QAQ，感觉很低的样子#include <bits/stdc++.h> using namespace std; const int maxn = 200; int num[maxn], vis[maxn]; int cnt, head[maxn*2]; double answer=0x3f3f3f3f*1.0; int n,m,u,v,w; struct node { int nnext,to,w; }edge[maxn]; void addedge(int u, int v, int w) { ++cnt; edge[cnt].to=v; edge[cnt].nnext=head[u]; edge[cnt].w=w; head[u]=cnt; } double getfc(int l, int r) { double sum=0; double allsum=0,ans1=0; for(int i=l; i<=r;i++) { allsum+=num[i]; } allsum=allsum/(1.0*(r-l+1)); for(int i=l;i<=r;i++) { ans1+=(num[i]-allsum)*(num[i]-allsum); } ans1=ans1/(1.0*(r-l+1)); return ans1; } void dfs(int point, int id) { vis[point]=id; for(int i=head[point]; i!=0; i=edge[i].nnext) { int v=edge[i].to; num[id]=edge[i].w; if(vis[v]) answer=min(answer, getfc(vis[v], id)); else if(v==n) answer=min(answer,getfc(1,id)); else dfs(v,id+1); } vis[point]=0; } int main() { scanf("%d%d", &n, &m); for(int i=1;i<=m;i++) { scanf("%d%d%d", &u, &v, &w); addedge(u,v,w); } dfs(1,1); answer=sqrt(answer); printf("%.6f\n", answer); return 0; }View Code
D.子序列
题意给定一个小写字母字符串T，问有多少长度为m的小写字母字符串S满足，T是S的一个子序列(不需要连续)
分析
组合数学
枚举最后一个字符的位置，分别考虑左右两边的情况，统计下即可
时间复杂度O(m*sqrt（幂）)
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5+10; const ll mod = 1e9+7; long long sum, zuo, you; ll fac[maxn]; ll t,m; char s[maxn]; ll qpow(ll a, ll b) { ll ans=1; while(b) { if(b&1) { ans*=a; ans%=mod; } a*=a, a%=mod; b>>=1; } return ans; } ll C(ll a,ll b) { return fac[a]*qpow(fac[b]%mod*fac[a-b]%mod, mod-2)%mod; } int main() { fac[0]=1; fac[1]=1; for(int i=2;i<=100000;i++) fac[i]=fac[i-1]*i, fac[i]%=mod; scanf("%s%lld", s, &m); ll zuo=1, you=1, sum=0; ll length=strlen(s); for(int i=length+1;i<=m;i++) { you*=26;you%=mod; } for(int i=length;i<=m;i++) { sum=C(i-1,length-1)*zuo%mod*you%mod+sum%mod; sum%=mod; zuo*=25, zuo%=mod; you*=qpow(26,mod-2); you%=mod; // cout<<sum<<endl; } printf("%lld\n", sum); return 0; }View Code 优质内容筛选与推荐>>
1、[AndroidDev-01]Android开发环境搭建
2、[转载Terrence Dorsey]Windows Phone 7开发工具和资源
3、C++ constexpr变量和constexpr函数
4、Socket通信客户端设计（Java）
5、SafetyNet Attestation API