感觉16年好难啊QAQ，两天的T2T3是不是都放反了啊……
场上预计得分：100+80+100+100+65+100=545（省一分数线280）
ps：loj没有部分分，部分分见洛咕
题解：
D1T1 玩具谜题
水题送温暖~当然主要关注点都在mengbier和mogician上2333
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
int n,m,nw=,x,op,a[];
char s[][];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d%s",&a[i],s[i]);
}
for(int i=;i<=m;i++){
scanf("%d%d",&op,&x);
if(op^a[nw])nw=(nw+x)%n;
else nw=(nw+n-x)%n;
}
printf("%s",s[nw]);
return ;
}
D1T2 天天爱跑步
绝对是这六题里最难的一题……这题目难度与顺序无关啊……想了半小时只会80，yy了一个线段树合并调不出来，树上差分并不会，最后百度了一发才搞懂……
首先考虑S->T这一条路径，肯定是从S出发先向上走到lca，再向下走到T，那么分开讨论这两种情况；
1.S->lca，此时路径上能对答案产生贡献的点i要满足$dep[i]+w[i]=dep[s]$；
2.lca->T，此时路径上能对答案产生贡献的点i要满足$dep[i]-w[i]=dep[t]-L$（其中L表示S到T的总长度）
这里貌似可以树链剖分+线段树直接维护？但是我出于对出题人基本的信任并没有写……
正解是用桶维护深度，维护一个向上的桶u和一个向下的桶d，对整棵树dfs；
对于一条s到t的路径，扫到s时就在s的$u[dep[s]]$中加一个，lca退栈时就把影响减掉，扫到lca时就在$d[dep[t]]$中加一个，t退栈时就减掉（这就是树上差分的思想）；
那么每次的答案$ans[i]$就等于子树中$u[dep[i]+w[i]]+d[dep[i]-w[i]]$的数量；
注意这里可能会有负数，所以要整体加上$MAXN$；
最后如果s到t是一条链那么答案会算重，要把答案减一；
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
#define MX 300001
using namespace std;
typedef long long ll;
struct edge{
int v,next;
}a[];
int n,m,u,v,l,tot=,fa[][],ans[],bb[],bs[],bg[],dep[],ss[],t[],z[],num[],head[];
vector<int>s[],t1[],t2[];
void add(int u,int v){
a[++tot].v=v;
a[tot].next=head[u];
head[u]=tot;
}
void dfs(int u,int ff,int dpt){
fa[u][]=ff;
dep[u]=dpt;
for(int i=;i<=;i++)fa[u][i]=fa[fa[u][i-]][i-];
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(v!=ff){
dfs(v,u,dpt+);
}
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int l=dep[u]-dep[v];
for(int i=;i>=;i--){
if((<<i)&l){
u=fa[u][i];
}
}
if(u==v)return u;
for(int i=;i>=;i--){
if(fa[u][i]!=fa[v][i]){
u=fa[u][i],v=fa[v][i];
}
}
return fa[u][];
}
void dfs1(int u,int ff){
int nw=bs[dep[u]+num[u]];
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(v!=ff){
dfs1(v,u);
}
}
bs[dep[u]]+=bg[u];
ans[u]+=bs[dep[u]+num[u]]-nw;
for(int i=,ii=s[u].size();i<ii;i++){
bs[s[u][i]]--;
}
}
void dfs2(int u,int ff){
int nw=bb[dep[u]-num[u]+MX];
for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){
int v=a[tmp].v;
if(v!=ff){
dfs2(v,u);
}
}
for(int i=,ii=t1[u].size();i<ii;i++){
bb[t1[u][i]+MX]++;
}
ans[u]+=bb[dep[u]-num[u]+MX]-nw;
for(int i=,ii=t2[u].size();i<ii;i++){
bb[t2[u][i]+MX]--;
}
}
int main(){
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++){
scanf("%d",&num[i]);
}
dfs(,,);
for(int i=;i<=m;i++){
scanf("%d%d",&ss[i],&t[i]);
z[i]=lca(ss[i],t[i]);
l=dep[ss[i]]+dep[t[i]]-*dep[z[i]];
bg[ss[i]]++;
s[z[i]].push_back(dep[ss[i]]);
t1[t[i]].push_back(dep[t[i]]-l);
t2[z[i]].push_back(dep[t[i]]-l);
}
dfs1(,);
dfs2(,);
for(int i=;i<=m;i++){
if(dep[z[i]]+num[z[i]]==dep[ss[i]])ans[z[i]]--;
}
for(int i=;i<=n;i++){
printf("%d ",ans[i]);
}
return ;
}
D1T3 换教室
题面看起来很复杂，实际上并不难……
显然这是个期望dp，且路程期望具有可加性，那么设$f[i][j][0 / 1]$表示当前在第i个时间段，已经申请了j次，这次是否申请；
推出式子就好了……
设$dis[i][j]$表示i到j的最短路：
$f[i][j][0]=min\{f[i-1][j][0]+dis[c[i-1]][c[i]],f[i-1][j][1]+dis[c[i-1]][c[i]]\times(1-k[i-1])$
$+dis[d[i-1]][c[i]]\times k[i-1]\}$
$f[i][j][1]=min\{f[i-1][j-1][0]+dis[c[i-1]][c[i]]\times(1-k[i])+dis[c[i-1]][d[i]]\times k[i],$
$f[i-1][j-1][1]+dis[c[i-1]][c[i]]\times(1-k[i-1])\times(1-k[i])+dis[d[i-1]][c[i]]\times k[i-1]\times(1-k[i])$
$+dis[c[i-1]][d[i]]\times(1-k[i-1])\times k[i]+dis[d[i-1]][d[i]]\times k[i-1]\times k[i]\}$
由于v很小，所以可以直接用floyd求出所有点对之间的最短路，于是就做完了……
时间复杂度$O(nm+V^3)$
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,v,e,u,vv,w,c[],d[],sp[][];
double k[],f[][][],tt,ans;
int main(){
memset(sp,0x3f,sizeof(sp));
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=;i<=n;i++){
scanf("%d",&c[i]);
}
for(int i=;i<=n;i++){
scanf("%d",&d[i]);
}
for(int i=;i<=n;i++){
scanf("%lf",&k[i]);
}
for(int i=;i<=v;i++){
sp[i][i]=;
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
f[i][j][]=1e16;
f[i][j][]=1e16;
}
}
f[][][]=f[][][]=;
for(int i=;i<=e;i++){
scanf("%d%d%d",&u,&vv,&w);
if(u==vv){
continue;
}
sp[u][vv]=min(sp[u][vv],w);
sp[vv][u]=sp[u][vv];
}
for(int kk=;kk<=v;kk++){
for(int i=;i<=v;i++){
for(int j=;j<=v;j++){
sp[i][j]=min(sp[i][kk]+sp[kk][j],sp[i][j]);
}
}
}
for(int i=;i<=n;i++){
f[i][][]=f[i-][][]+sp[c[i-]][c[i]];
for(int j=;j<=min(m,i);j++){
f[i][j][]=min(f[i-][j][]+sp[c[i-]][c[i]],f[i-][j][]+sp[c[i-]][c[i]]*(1.0-k[i-])+sp[d[i-]][c[i]]*k[i-]);
f[i][j][]=f[i-][j-][]+sp[c[i-]][c[i]]*(1.0-k[i])+sp[c[i-]][d[i]]*k[i];
tt=f[i-][j-][]+sp[c[i-]][c[i]]*(1.0-k[i-])*(1.0-k[i])+sp[d[i-]][c[i]]*k[i-]*(1.0-k[i])+sp[c[i-]][d[i]]*(1.0-k[i-])*k[i]+sp[d[i-]][d[i]]*k[i-]*k[i];
f[i][j][]=min(f[i][j][],tt);
}
}
ans=f[n][][];
for(int i=;i<=m;i++){
ans=min(ans,min(f[n][i][],f[n][i][]));
}
printf("%.2lf",ans);
return ;
}
D2T1 组合数问题
并不是很水？要预处理前缀和；
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
using namespace std;
typedef long long ll;
int n,m,t,k,s[][],C[][];
int main(){
scanf("%d%d",&t,&k);
C[][]=;
for(int i=;i<=;i++){
C[i][]=;
for(int j=;j<=i;j++){
C[i][j]=(C[i-][j]+C[i-][j-])%k;
}
}
for(int i=;i<=;i++){
for(int j=;j<=;j++){
s[i][j]=s[i-][j]+s[i][j-]-s[i-][j-]+(!C[i][j]&&i>=j);
}
}
while(t--){
scanf("%d%d",&n,&m);
printf("%d\n",s[n][m]);
}
return ;
}
D2T2 蚯蚓
谁能给我解释一下这个鬼畜的部分分……
这题的难点在于阅读理解……题目写的很复杂，要仔细理解题意；
场上看到$M=7\times 10^6$直接虚掉……写了个优先队列65分滚粗了QAQ
注意到每次操作完整体增加q不好处理，因此可以考虑把q累加起来，每次计算完答案再加上总和，把分出来的两个数减去q即可，这样子做每次把分出来的数丢进优先队列就能拿到65分；
正解是非常巧妙的单调队列；
注意到这样子做所有没被拆分过的蚯蚓的长度是单调不增的，考虑被拆出来的两条新蚯蚓，由于拆分的两段比例都相等，所以较长那段和较短那段的长度也是单调不增的；
这样子可以只在开始排序一遍，开三个单调队列来分别维护$x$，$\lfloor px\rfloor$和$x-\lfloor px\rfloor$，每次选队头最大的进行操作即可；
想起来复杂，代码很短……
时间复杂度$O(nlogn+m)$
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 1000000000000000
#define eps 1e-9
using namespace std;
typedef long long ll;
int n,m,q,t,l1=,l2=,l3=,r1,r2=,r3=,id,num[],q1[],q2[],q3[];
ll t1,t2,u,v,ans,sum=;
bool cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d%d%d%lld%lld%d",&n,&m,&q,&u,&v,&t);
r1=n;
for(int i=;i<=n;i++){
scanf("%d",&q1[i]);
}
sort(q1+,q1+n+,cmp);
for(int i=;i<=m;i++){
id=;
ans=-inf;
if(l1<=r1&&q1[l1]>ans){
ans=q1[l1];
id=;
}
if(l2<=r2&&q2[l2]>ans){
ans=q2[l2];
id=;
}
if(l3<=r3&&q3[l3]>ans){
ans=q3[l3];
id=;
}
ans+=sum;
if(i%t==)printf("%lld ",ans);
sum+=q;
t1=ans*u/v;
t2=ans-t1;
q2[++r2]=t1-sum;
q3[++r3]=t2-sum;
if(id==)l1++;
else if(id==)l2++;
else l3++;
}
puts("");
for(int i=;i<=n+m;i++){
id=;
ans=-inf;
if(l1<=r1&&q1[l1]>ans){
ans=q1[l1];
id=;
}
if(l2<=r2&&q2[l2]>ans){
ans=q2[l2];
id=;
}
if(l3<=r3&&q3[l3]>ans){
ans=q3[l3];
id=;
}
if(i%t==)printf("%lld ",ans+sum);
if(id==)l1++;
else if(id==)l2++;
else l3++;
}
return ;
}
D2T3 愤怒的小鸟
暴力状压DP可过……（可能在考数学？）
预处理$g[i][j]$表示打第$i$和第$j$只猪的抛物线能打到哪些猪，然后状压表示当前打死了哪些猪；
显然$f[s|g[i][j]]=min\{f[s|g[i][j]],f[s]+1\}$
时间复杂度$O(n^22^n)$
ps:公式如下：
$y_1=ax_{1}^{2}+bx_1$
$y_2=ax_{2}^{2}+bx_2$
则$a=\frac{y_1x_2-x_1y_2}{x_1x_2(x_1-x_2)}$，$b=\frac{x_{1}^{2}y_2-x_{2}^{2}y_1}{x_1x_2(x_1-x_2)}$
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 0x7f7f7f7f
#define eps 1e-9
using namespace std;
typedef long long ll;
struct pt{
double x,y;
}p[];
int t,n,m,f[],nxt[][];
void pre(){
memset(nxt,,sizeof(nxt));
for(int i=;i<n;i++){
for(int j=i+;j<=n;j++){
double x=p[i].x,y=p[i].y,xx=p[j].x,yy=p[j].y;
if(fabs(x-xx)<eps)continue;
double a=(y*xx-x*yy)/(x*xx*(x-xx)),b=(x*x*yy-xx*xx*y)/(x*xx*(x-xx));
if(a>-eps)continue;
for(int k=;k<=n;k++){
double _x=p[k].x,_y=p[k].y;
if(fabs(a*_x*_x+b*_x-_y)<eps)nxt[i][j]|=(<<k-);
}
}
}
}
void work(){
memset(f,0x7f,sizeof(f));
f[]=;
for(int s=;s<(<<n);s++){
if(f[s]!=inf){
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
f[s|nxt[i][j]]=min(f[s|nxt[i][j]],f[s]+);
}
f[s|(<<i-)]=min(f[s|(<<i-)],f[s]+);
}
}
}
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
pre();
work();
printf("%d\n",f[(<<n)-]);
}
return ;
}
总结：
我太菜了.jpg