比赛地址：http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=9380#overview
今天终于找回了一些感觉了。虽然很遗憾由于多打了相同的一句，导致G没有过，不过与队友的配合终于感觉了。。
开场有些慢，由于我想错了K题，然后就去拍了，打错了一个下标，40分钟后才交了一发错误的K。。。影响了队伍整体的推进速度。
H过后。。在确定K想错后。。开始拍了C（自己在短时间写代码的能力太错了），用了十多分钟才过掉
接着E题，想到了用积分公式爆答案，不过感觉花时间太久了，间隔了35分钟。。。
tc在想D的建树过程，无法证明正确性。最后讨论想到了地推。。这里也出慢了。。打表之类的根据情况选择最有可能的因素打呀。。
A - Association of Strings
不会做
B - Binary Substring
给三个数A,B,C，找最小的X（A<=X<=B）使C的二进制串被包含与X的二进制串
队友写的。。貌似比较暴力。。我想想再更新这里
C - Common Palindrome
给两个串A,B，找一个最长的回文串同时是A，B的子序列
因为串的长度只有60，时限10s，
因此可以用dp[a1][b1][a2][b2]：表示A[a1,b1]与B[a2,b2]能够得到最长回文
那么枚举[a1，b1]配[a2，b2]的最长回文首尾是哪两个相同字母
则dp[a1][b1][a2][b2]={2+dp[][][][]}(里面的变换应该不用我说吧)
还可能就是只包含一个字母、、、注意下各种限制条件。。这题就很好写了。
D - Draw and Score
N个点构成一个二叉树，每次连接一个点进去，一共进行N-1次，每次统计左右儿子数相同的节点数Ci，最终求Ci和的最大值
递推+打表找规律。
F[n]：n个点能够达到的最长值
F[n]=max{F[i]+F[n-i-1]+min（i,n-i-1）}( 0<=i<=n-i-1 )
E - Elliptic Athletics Track
给a，b（a,b<=20），求椭圆的周长
祖冲之求圆周长的方法。对 x，x+dx，求出对应的y，从而得到dy，将sqrt(dx^2+dy^2)作为在那一小段区间内，椭圆的的弧长
F - Fun with Binary Tree
一颗二叉树，一个命令字符串包含“L”，“R”，分别表示走到当前点的左右儿子，你可以不执行一个命令，但不能连续两次拒绝。问是否存在完成所有命令的方案。
最暴力的方法：对每个指令，记录当前可以到达哪些点，一直执行到最后一个指令，看是否有满足的点，这种方法要T，有一个很好的剪枝：对一个节点，如果往下可以连续同样的操作（全为L或者R）走L步，刚好当前的指令从这个点也可以连续做相同的操作L步，那么我们不必一步一步的往下走，通过分析，可以直接得到某些点能够到达某些指令。。（减少了大概L/2的样子）。。大致思路就这样我还没写。。
G - Good Measures of Dispersion
N个数，每次可以对区间执行3个操作：置为一个数，加一个数，求这个区间的方差，和最值的差值
很裸一道线段树的题。
方差的公式=（N*平方和 - 和的平方）/(N*N) （N表示数目）
某一区间增加a，平方和=（Xi+a）^2 = Xi^2 +2*Xi*a+a*a
=原来的平方和+2*a*和+N*a^2
注意下懒操作之类的就行了。附上我的代码，代码长度很短^_^
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int const N=100005;
long long oo=(1LL<<62)-1LL;
int num[N],Node;
struct node
{
int a,b,l,r;
long long sum,ssum,Min,Max,add,setN;
bool flag;
void read(int a,int b){ this->a=a; this->b=b;flag=false;add=0;}
void Add(long long c)
{
Min+=c;Max+=c;
ssum+=sum*c*2LL+c*c*(b-a+1);
sum+=c*(b-a+1);
if(flag)setN+=c;
else add+=c;
}
void Set(long long c)
{
flag=true;
sum=ssum=setN=Min=Max=add=0;
Add(c);
}
}tr[N*2],tmp;
void update(int k,int l,int r)
{
tmp=tr[k];
tmp.Max=max(tr[l].Max,tr[r].Max);
tmp.Min=min(tr[l].Min,tr[r].Min);
tmp.sum=tr[l].sum+tr[r].sum;
tmp.ssum=tr[l].ssum+tr[r].ssum;
tr[k]=tmp;
}
void makeTree(int a,int b)
{
int k=++Node;
tr[k].read(a,b);
if(a==b){ tr[k].Set(num[a]); return; }
tr[k].l=Node+1; makeTree(a,(a+b)/2);
tr[k].r=Node+1; makeTree((a+b)/2+1,b);
update(k,tr[k].l,tr[k].r);
}
void insert(int a,int b,long long c,int cmd,int k)
{
if(tr[k].b<=b&&tr[k].a>=a)
{
switch(cmd)
{
case 0:tr[k].Set(c);break;
case 1:tr[k].Add(c);break;
case 2:update(0,0,k);break;
}
}
else
{
if(tr[k].flag)
{
tr[tr[k].l].Set(tr[k].setN);
tr[tr[k].r].Set(tr[k].setN);
tr[k].flag=false;
}
if(tr[k].add)
{
tr[tr[k].l].Add(tr[k].add);
tr[tr[k].r].Add(tr[k].add);
tr[k].add=0;
}
int m=(tr[k].a+tr[k].b)>>1;
if(a<=m)insert(a,b,c,cmd,tr[k].l);
if(b> m)insert(a,b,c,cmd,tr[k].r);
update(k,tr[k].l,tr[k].r);
}
}
long long gcd(long long a,long long b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int main()
{
int T,n,m;
long long t,x,y,d;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
printf("Case %d:\n",cas);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&num[i]);
Node=0;makeTree(1,n);
int cmd,a,b,c;
for(int i=1;i<=m;i++)
{
scanf("%d",&cmd);
if(cmd==0||cmd==1)
{
scanf("%d%d%d",&a,&b,&c);
insert(a,b,c,cmd,1);
}
else
{
scanf("%d%d",&a,&b);
tr[0].Min=oo;tr[0].Max=-oo;
tr[0].sum=0;tr[0].ssum=0;
insert(a,b,0,cmd,1);
t=b-a+1;
x=tr[0].ssum*t-tr[0].sum*tr[0].sum;
y=t*t;
d=gcd(x,y);
printf("%lld/%lld ",x/d,y/d);
printf("%lld\n",tr[0].Max-tr[0].Min);
}
}
}
return 0;
}
H - Hardest Problem Ever (Easy)
签到题
I - Interesting Route
没读
J - Just Some Permutations
没读
K - K-Neutral Rectangles
N*M的矩阵，求一个最大面积的矩阵，使得所选矩阵内任意相邻两点的数字差的绝对值不超过K。
求矩阵的问题，一般都要枚举行，表示最大面积的矩阵的最下面那条边在这行上。
这题也一样。。枚举每行，然后在这上面求一个最大矩阵
如果最优矩阵只含一列的话，可以维护H[j]，表示从第i行往上走，该列最远能走的距离。然后考虑多列的情况，用S[j]表示第j列与第j+1列相连，能往上走的最远距离，很明显S[j]<=H[j]
| 4 | |||
| 1 | 3 | 4 | |
| 1 | 2 | 3 | 4 |
| 1 | 2 | 3 | 4 |
如图：H[1]=3,H[2]=2,H[3]=3,H[4]=4
你会发现这个问题就转化成通过S[j]求最大的矩阵： 比如我们取第1,2列，得到S=min(S[1],S[2])=2,那么高度就为2，长是多少呢？
是2么？ 显然不对，因为S[j]表示与第j+1列能够匹配的最大高度，显然第3列有两个元素与第2列能够相邻（s[2]=2）
因此这样得到一个2*3的矩阵，大家是否已经想到做法了？与广告印刷这题就几乎一模一样了，求得L[j],R[j]表示向左，向右最远走到的列的编号。唯一不同的是最后算面积是：s[j]*(R[j]-L[j]+1+1 )
附广告印刷的单调队列的处理方式（今天自己才想到的一个写法）
H[N],L[N],R[N]// 每列的高度，向左，向右能到达的位置
Q[N],tp;// 维护的单调上升的队列，Q[i]记录的位置编号
ps:以前写这种我都是从左扫一次，从右扫了一次，其实一次扫描就行了
void Ins(int k)
{
L[k]=R[k]=k;// 初始第k列左右能够到达的位置
while(tp!=0&&H[Q[tp]]>=H[k])// 队列最后那列的高度不小于当前高度
{
L[k]=L[Q[tp]]; //更新第k列左边能到的位置
R[Q[tp-1]]=R[Q[tp]]; // 更新队列倒数第二那列右边能够达到的位置
tp--;
}
++tp;Q[tp]=k;
}
for(int k=1;k<=m;k++)Ins(k);
Ins(0);// 对最后形成的单调队列处理，让所有的出队列