听说这是JSOI2015Day2
膜了贵省的题目，感到不明觉厉。
Orz NiroBC 230
Orz Gold_7 220
Orz Chrysanthemum 220
我等蒟蒻第三题炸飞，120收场。
T1
第一眼看到题目慌掉了。让我打个暴力压压惊。
好像答案就是2nk。。。。
T2
第一眼看到题目慌掉了。让我打个暴力压压惊。
诶这个K究竟有什么用，不明觉厉啊。那就20分好了。
正解是：
二分答案（什么居然是分数规划）
那么如果存在更优解，显然有：[tex]\frac{M(i,j)-m(i,j)}{j-i+K}>b[/tex]
首先暴力处理出len=l的情况。
显然对于len∈(l,r]，如果它能产生最优解，那么可以得到：
M(i,j)=a[i],m(i,j)=a[j]或M(i,j)=a[j],m(i,j)=a[i]。
那么将分母乘过去，就有：a[i]+b*i-(a[j]+b*j)>b*K或a[i]-b*i-(a[j]-b*j)>b*K。
令c[i]=a[i]+b*i或a[i]-b*i，那么等式成立的条件是：
存在i,j，满足：l<j-i+1<=r,c[i]-c[j]>b*K。
那么就可以单调队列辣！！！
T3
第一眼看到题目慌掉了，突然发现这道题好像做过类似的。
恩好像跟前面那个Count on a tree差不多，写个可持久化trie树吧。
恩我第一次写。
恩我过样例了。
恩我炸了。
原来是lca的时候大于小于号打错了。
（听说这道题还有一个不明觉厉的hash做法）
Codes
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int maxn=1000000007;
ll n,k;
ll quickmi(ll x,ll y,ll mod){
ll ans=1;
while (y){
if ((y&1)==1)ans=ans*x%mod;
x=x*x%mod;
y=y>>1;
}
return ans;
}
int main(){
freopen("subset.in","r",stdin);
freopen("subset.out","w",stdout);
scanf("%lld%lld",&n,&k);
printf("%lld\n",quickmi(2,n*k,maxn));
}
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
const int M=100010;
double a[M],c[M];
int cas,n,K,l,r,i;
struct node{int head;int tail;int w[M];}h1,h2;
int check(double b){
for (int i=1;i<=n;i++)c[i]=a[i]+b*i;
h1.head=1,h1.tail=1,h1.w[1]=n;
for (int i=n-l+1;i>=1;i--){
while (h1.head<h1.tail&&h1.w[h1.head]>i+r-1)h1.head++;
if (c[i]-c[h1.w[h1.head]]>=b*K)return 1;
while (h1.head<=h1.tail&&c[h1.w[h1.tail]]>=c[i+l-2])h1.tail--;
h1.w[++h1.tail]=i+l-2;
}
for (int i=1;i<=n;i++)c[i]=-a[i]+b*i;
h1.head=1,h1.tail=1,h1.w[1]=n;
for (int i=n-l+1;i>=1;i--){
while (h1.head<h1.tail&&h1.w[h1.head]>i+r-1)h1.head++;
if (c[i]-c[h1.w[h1.head]]>=b*K)return 1;
while (h1.head<=h1.tail&&c[h1.w[h1.tail]]>=c[i+l-2])h1.tail--;
h1.w[++h1.tail]=i+l-2;
}
return 0;
}
int main(){
scanf("%lld",&cas);
while (cas--){
scanf("%d%d%d%d",&n,&K,&l,&r);
for (i=1;i<=n;i++)scanf("%lf",&a[i]);
double L=0,R=1000;
h1.head=1,h1.tail=1,h2.head=1,h2.tail=1;
h1.w[1]=1,h2.w[1]=1;
for (i=2;i<=n;i++){
while (h1.head<h1.tail&&h1.w[h1.head]<i-l+1)h1.head++;
while (h2.head<h2.tail&&h2.w[h2.head]<i-l+1)h2.head++;
while (h1.head<=h1.tail&&a[h1.w[h1.tail]]<a[i])h1.tail--;
while (h2.head<=h2.tail&&a[h2.w[h2.tail]]>a[i])h2.tail--;
h1.w[++h1.tail]=i;
h2.w[++h2.tail]=i;
if (i>=l)L=max(L,(a[h1.w[h1.head]]-a[h2.w[h2.head]])/(l-1+K));
}
l++;
if (l<=r){
while (R-L>0.000001){
double mid=(L+R)/2;
if (check(mid))L=mid;else R=mid;
}
}
printf("%.4lf\n",L);
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
int n,i,x,y,m,edgenum,cnt;
char a[M];
int head[M],vet[M],next[M],root[M],dep[M];
int fa[M][17];
char ch[M][20];
char st[20];
struct node{int w;int son[26];}tree[M*10];
void addedge(int x,int y){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
}
void addtrie(int &p,int x,int dep){
tree[++cnt]=tree[p],p=cnt,tree[p].w++;
if (dep==strlen(ch[x]))return;
addtrie(tree[p].son[ch[x][dep]-'a'],x,dep+1);
}
int query(int x,int dep){
if (x==0&&dep)return 0;
if (dep==strlen(st))return tree[x].w;
return query(tree[x].son[st[dep]-'a'],dep+1);
}
int lca(int x,int y){
if (dep[x]<dep[y])swap(x,y);
int t=dep[x]-dep[y];
for (int i=0;i<=16;i++)
if (t&(1<<i))x=fa[x][i];
for (int i=16;i>=0;i--)
if (fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
if (x==y)return x;
return fa[x][0];
}
void dfs(int u,int cnt){
int e,v;
if (u!=1)root[u]=root[fa[u][0]],addtrie(root[u],cnt,0);
for (int i=1;i<=16;i++)
if ((1<<i)<=dep[u])fa[u][i]=fa[fa[u][i-1]][i-1];
else break;
for (e=head[u];e;e=next[e]){
v=vet[e];
if (v!=fa[u][0])fa[v][0]=u,dep[v]=dep[u]+1,dfs(v,e+1>>1);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<n;i++){
scanf("%d%d",&x,&y);
scanf("%s",ch[i]);
addedge(x,y);
addedge(y,x);
}
dfs(1,-1);
scanf("%d",&m);
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
scanf("%s",st);
printf("%d\n",query(root[x],0)+query(root[y],0)-2*query(root[lca(x,y)],0));
}
}
评论 (0)
