A.倒水
有一个大水缸，里面水的温度为T单位，体积为C升。另有n杯水（假设每个杯子的容量是无限的），每杯水的温度为t[i]单位，体积为c[i]升。
现在要把大水缸的水倒入n杯水中，使得n杯水的温度相同，请问这可能吗？并求出可行的最高温度，保留4位小数。
注意：一杯温度为$t_1$单位、体积为$c_1$升的水与另一杯温度为$t_2$单位、体积为$c_2$升的水混合后，温度变为$(t_1 \times c_1+t_2 \times c_2)/(c_1+c_2)$，体积变为$c_1+c_2$。
二分
二分最终温度。
注意确定好$l$和$r$ 的范围，可能出现的除零操作。
复杂度$O(nlog_2T)$ 。
代码如下：
#include <cstdio>
#define N 100005
using namespace std;
typedef long long ll;
int n,T,C,t[N],c[N];
double Max(double a,double b){
return a>b?a:b;
}
double Min(double a,double b){
return a<b?a:b;
}
double Abs(double x){
return x>0?x:-x;
}
int check(double x){
double tot=0,temp;
for(register int i=0;i<n;++i){
if(Abs(*(t+i)-x)<1e-8)continue;
if(Abs(T-x)<1e-8)return 0;
if(x<T&&x<*(t+i))return 0;
if(x>T&&x>*(t+i))return 0;
temp=*(c+i)*(x-*(t+i))/(T-x);
tot+=temp;
}
return tot<=C;
}
int main(void){
scanf("%d%d%d",&n,&T,&C);
scanf("%d%d",t,c);
double l=Min(T,*(t+0)),r=Max(T,*(t+0));
for(register int i=1;i<n;++i){
scanf("%d%d",t+i,c+i);
r=Min(r,Max(T,*(t+i)));
l=Max(l,Min(T,*(t+i)));
}
double mid=(l+r)/2;
while(r-l>1e-5){
if(check(mid))l=mid;
else r=mid;
mid=(l+r)/2;
}
if(check(r)||check(l))printf("Possible\n%.4lf\n",r);
else printf("Impossible\n");
}B.二分图染色(弱化版)
待更
C.合并回文子串
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如”abc”和”xyz”可以被组合成”axbycz”或”abxcyz”等。定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如”aba”和”xyyx”）。输出这个最大价值。
DP
定义状态
因为合并的字符串是连续的，故可以定义状态$dp[i][j][k][h]$ 表示字符串A从第$i$ 位开始连续$j$ 个字符与字符串B从第$k$ 位开始连续$h$ 个字符能否合并成一个回文串C。
转移方程
$dp[i][j][k][h] ;|= dp[i+1][j-2][k][h] ，a[i]=a[i+j-1]$ 且$j \geqslant 2$ ；
$dp[i][j][k][h] ;|= dp[i][j][k+1][h-2] ，b[k]=b[k+h-1]$ 且$ h\geqslant 2$ ；
$dp[i][j][k][h] ;|= dp[i][j-1][k+1][h-1] ，a[i+j-1]=b[k]$ 且$j \geqslant 1,h \geqslant 1$ ；
$dp[i][j][k][h] ;|= dp[i+1][j-1][k][h-1] ，a[i]=b[k+h-1]$ 且$j \geqslant 1,h \geqslant 1$ ；
边界情况
- 当$j+h \leqslant 1$ 即合并串C的长度小于等于$1$ 时，该串必为回文串。
- 考虑到边界$+1$ 后会超过数组范围，故$i \leqslant strlen(a),k \leqslant strlen(b)$ 。
复杂度$O(Tn^4)$ 。
代码如下：
#include <cstdio>
#include <cstring>
using namespace std;
int T,dp[55][55][55][55],lan,lbn,ans;
char a[55],b[55];
int Max(int a,int b){
return a>b?a:b;
}
int main(void){
scanf("%d",&T);
while(T--){
scanf("%s%s",a,b);
lan=strlen(a);
lbn=strlen(b);
ans=0;
memset(dp,0,sizeof(dp));
for(int j=0;j<=lan;++j){
for(int h=0;h<=lbn;++h){
for(int i=0;i+j<=lan;++i){
for(int k=0;k+h<=lbn;++k){
if((j+h<=1)
||(i<lan&&j>=2&&a[i]==a[i+j-1]&&dp[i+1][j-2][k][h])
||(k<lbn&&h>=2&&b[k]==b[k+h-1]&&dp[i][j][k+1][h-2])
||(i<lan&&k<lbn&&j>=1&&h>=1&&a[i]==b[k+h-1]&&dp[i+1][j-1][k][h-1])
||(i<lan&&k<lbn&&j>=1&&h>=1&&a[i+j-1]==b[k]&&dp[i][j-1][k+1][h-1])){
dp[i][j][k][h]=1;
ans=Max(ans,j+h);
}
}
}
}
}
printf("%d\n",ans);
}
}D.身体训练
n个人排成一列跑步，前后两人之间相隔 u 米，每个人正常速度均为 v 米/秒。
最后一个人需要以当时自己的最高速度往前跑，直到超过排头的人 u 米，然后降回到原始速度 v米/秒。每个人最初的最高速度为c[i] 米/秒，每轮衰减d[i]米/秒，也就是说，如果i是第j个跑的，那么他的速度就是c[i]-(j-1)*d[i] 米/秒。n个人初始以随机的顺序排列，每种顺序的概率完全相等，跑完一轮（每个人都追到排头一次，序列恢复原样）的期望需要的时间是多少？
模拟
按题意直接暴力模拟$ans = \frac{1}{n}\sum_{i=1}^n\sum_{j=1}^n\frac{nu}{c[i]-(j-1)d[i]-v}$ 。
代码如下：
#include <cstdio>
using namespace std;
int n;
double ans,v,u,c[1005],d[1005];
int main(void){
scanf("%d%lf%lf",&n,&v,&u);
for(register int i=1;i<=n;++i)scanf("%lf",c+i);
for(register int i=1;i<=n;++i)scanf("%lf",d+i);
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)
ans+=u*n/(c[i]-(j-1)*d[i]-v);
printf("%.3lf\n",ans/n);
}E.数列互质
给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , … , a[n] }，以及 m 组询问 ( l[i] , r[i], k[i])。求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。
莫队
考虑到查询可以离线，采用莫队算法。
用数组$cnt[x]$ 维护当前区间$[l,r]$ 中，数$x$ 的出现次数。
用$num[x]$ 维护当前区间$[l,r]$ 中，出现次数为$x$ 次的有$num[x]$ 个。设$num[x]$ 的长度为$len$ ，考虑极端情况$\frac{(1+len)len}{2}=n$ ，故$len < \sqrt{n}$ ，可选择map。
查询时，只需遍历整个$num[x]$ ，求得$ans=\sum_{gcd(x,k)=1}num[x]$ ，查询复杂度为$O(\sqrt{n} log_2^2n)$ 。
总复杂度为$O(n^{\frac{3}{2}}log_2^2n)$ 。
代码如下：
#include <cstdio>
#include <map>
#include <algorithm>
#define N 50005
#define D 250
using namespace std;
int n,m,a[N],cnt[N],ans[N];
map<int,int>num;
map<int,int>::iterator it;
struct node{
int l,r,k,id;
friend bool operator<(node a,node b){
if(a.l/D==b.l/D)return a.r<b.r;
return a.l/D<b.l/D;
}
}q[N];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
void add(int x){
int temp=cnt[a[x]];
if(num.count(temp)){
num[temp]--;
if(num[temp]==0)
num.erase(temp);
}
temp=++cnt[a[x]];
num[temp]++;
}
void dec(int x){
int temp=cnt[a[x]];
num[temp]--;
if(num[temp]==0)
num.erase(temp);
temp=--cnt[a[x]];
if(temp)num[temp]++;
}
int query(int x){
int temp=0;
for(it=num.begin();it!=num.end();++it)
if(gcd(it->first,x)==1)temp+=it->second;
return temp;
}
int main(void){
scanf("%d%d",&n,&m);
for(register int i=0;i<n;++i)scanf("%d",a+i);
for(register int i=0;i<m;++i){
scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
q[i].l--;
q[i].r--;
q[i].id=i;
}
sort(q,q+m);
int l=0,r=-1;
while(r<q[0].r){++r;add(r);}
while(l<q[0].l){dec(l);++l;}
ans[q[0].id]=query(q[0].k);
for(int i=1;i<m;++i){
while(r<q[i].r){++r;add(r);}
while(r>q[i].r){dec(r);--r;}
while(l<q[i].l){dec(l);++l;}
while(l>q[i].l){--l;add(l);}
ans[q[i].id]=query(q[i].k);
}
for(register int i=0;i<m;++i)
printf("%d\n",ans[i]);
}F.最长树链
待更