作者存档：edward_mj

【题目】

Description

最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保 证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖 出BSi股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W 天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的 股票数不能超过MaxP。
在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱，聪明的 程序员们，你们能帮助他吗？

Input

输入数据第一行包括3个整数，分别是T，MaxP，W。
接下来T行，第i行代表第i-1天的股票走势，每行4个整数，分别表示APi，BPi，ASi，BSi。

Output

输出数据为一行，包括1个数字，表示lxhgww能赚到的最多的钱数。

Sample Input

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

Sample Output

3

Hint

【数据范围】
对于30%的数据，0<=W＜T<=50,1<=MaxP<=50
对于50%的数据，0<=W＜T<=2000,1<=MaxP<=50
对于100%的数据，0<=W＜T<=2000,1<=MaxP<=2000
对于所有的数据，1<=BPi＜=APi<=1000,1<=ASi,BSi<=MaxP 【算法分析】
该题很容易得出方程和状态：
F[i,j]表示第i天，手上有j点股份，所得的最大收入。
然后预处理从第i天开始买的情况。
即F[i,j]=-buyprize[i]*j   其中 j<=buylimit[i]。
然后是转移。
转移分两种，一种是卖，一种是买。
F[i,j]=max{
1、F[i-1,j] 就是第i天不买股份，手上依然j点股份。
2、F[i-w-1,k] – buyprize[i]*(j-k) 其中 1<=j-k<=buylimit[i]   表示今天买j-k那么多股份。
3、F[i-w-1,k] + sellprize[i]*(k-j) 其中 1<=k-j<=selllimit[i]   表示今天卖k-j这么多股份。
}
然后第一种方案直接转移。然后后面两种，显然可以用单调队列优化。
最终时间复杂度O(T*maxp)
【CODE】
#include #include #include const int N=2005;
int T,maxp,W;
int inp[N],outp[N],inlimit[N],outlimit[N];
int F[N][N];
struct queue{int p,f;}q[N];

void input(){
scanf("%d%d%d",&T,&maxp,&W);
for (int i=1;i<=T;i++)
scanf("%d%d%d%d",&inp[i],&outp[i],&inlimit[i],&outlimit[i]);
}

inline int min(int x,int y){return xinline int max(int x,int y){return x>y?x:y;}

void dp(){
int i,j,k,h,t;
int *pf,*f;
memset(F,200,sizeof(F));
for (i=1;i<=T;i++){
F[i][0]=0;
for (j=1;j<=min(inlimit[i],maxp);j++) F[i][j]=-inp[i]*j;
}
for (i=2;i<=T;i++){
pf=F[i-W-1];
f=F[i];
for (j=0;j<=maxp;j++) F[i][j]=max(F[i][j],F[i-1][j]);
if (i pf=F[i-W-1];
f=F[i];
h=t=0; q[0].p=0; q[0].f=pf[0];
for (j=1;j<=maxp;j++){
while (h<=t && j-q[h].p>inlimit[i]) h++;
if (h<=t) f[j]=max(f[j],q[h].f+(q[h].p-j)*inp[i]);
while (h<=t && q[t].f+(q[t].p-j)*inp[i] t++;
q[t].p=j;
q[t].f=pf[j];
}
h=t=0; q[0].p=maxp; q[0].f=pf[maxp];
for (j=maxp-1;j>=0;j–){
while (h<=t && q[h].p-j>outlimit[i]) h++;
if (h<=t) f[j]=max(f[j],q[h].f+(q[h].p-j)*outp[i]);
while (h<=t && q[t].f+(q[t].p-j)*outp[i] t++;
q[t].p=j;
q[t].f=pf[j];
}
}
}

void output(){
int ans=0;
for (int i=0;i<=maxp;i++)
ans=max(ans,F[T][i]);
printf("%dn",ans);
}

int main(){
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
input();
dp();
output();
}

【题目】

Description

　　在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如 68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88）， 于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号 码”，比如12，16，666都是“近似幸运号码”。
现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

Input

输入数据是一行，包括2个数字a和b

Output

输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数

Sample Input

【样例输入1】
1 10
【样例输入2】
1234 4321

Sample Output

【样例输出1】
2
【样例输出2】
809

Hint

对于30%的数据，保证1<=a<=b<=1000000
对于100%的数据，保证1<=a<=b<=10000000000 【算法分析】
该题使用容斥原理，把符合的数先都DFS出来，然后把互为约数的，大的那个删掉。
最后需要注意各种不要超范围。
因为题目给的范围异常猥琐，b*b都会爆long long，所以需要各种先除后乘。
【其他】
由于之前因为程序中注释处溢出一直TLE，然后围观与标程有什么不同，以至于已经和标程没啥区别了
= =。。。Orz。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int N=20000;
lld a,b,tot=0,ans,X;
lld list[N];

void makelist(int dep,lld x){
if (x>b) return;
list[tot++]=x;
makelist(dep+1,x*10+6);
makelist(dep+1,x*10+8);
}

lld gcd(lld x,lld y){
lld z;
while (y){
z=x%y;
x=y;
y=z;
}
return x;
}

void dfs(int st,int times,lld num){
int i; lld g;
for (i=st;i>=1;i–){
g=gcd(list[i],num);
if (num/g<=X/list[i]){ // 改成if (num/g*list[i]<=X)的话 ，会因溢出而TLE在那里！
if (times&1) ans-=X/(num/g*list[i]);
else ans+=X/(num/g*list[i]);
dfs(i-1,times+1,num/g*list[i]);
}
}
}

lld cal(lld x){
if (x<=5) return 0;
ans=0; X=x;
dfs(tot-1,0,1);
return ans;
}

int main(){
freopen("luckynumber.in","r",stdin);
freopen("luckynumber.out","w",stdout);
cin >> a >> b;
makelist(0,0);
sort(list,list+tot);
for (int i=2;i bool flag=false;
for (int j=1;j if (list[i]%list[j]==0){
flag=true;
break;
}
if (flag){
for (int j=i;j+1 list[j]=list[j+1];
tot–;
i–;
}
}
cout << cal(b)-cal(a-1) << endl;
}

一、n的约数个数是O(sqrt(n))级别的。

二、n! 质因数分解的模板：
void Div(int *list,int n){
int i,j,tmp;
for (i=0;i for (i=0;i tmp=n;
while (tmp/pl[i]){
list[i]+=tmp/pl[i];
tmp/=pl[i];
}
}
}

三、勾股数定理
对于a^2+b^2=c^2
1、a=m^2-n^2
2、b=2*m*n
3、c=m^2+n^2
4、gcd(n,m)=1。
5、gcd(a,b,c)=1。
同时满足这五条式的是一组勾股数，而且对于所有满足这五条式的(m,n)乘一个k(k>=1)，即(km,kn)。就可以表示所有的勾股数，并且勾 股数和三元对(m,n,k)一一对应。
换句话说，每个勾股数都只能表示为一个三元对(m,n,k)。
并且k=1时，必须满足c%4==1才能分出来。(Fermat’s two-square theorem. A prime number with p=4n+1 can be written as the sum of two square numbers)

四、p为质数，那么(a/b) mod p=(a* b^(p-2)) mod p

五、若gcd(b,p)=1 那么 a = b*x (mod p)  只有一个0<=xφ(n)=n*（1-1/p1)(1-1/p2)….(1-1/pk),其中p1、p2…pk为n的所 有素因子。
比如：φ(12)=12*(1-1/2)(1-1/3)=4。

七、 A^x = A^(x % Phi(C) + Phi(C)) (mod C) 其中phi是欧拉函数

证明参见师父的博客http://hi.baidu.com/aekdycoin/blog/item/b6f1762565bb403fc8955908.html

 

八、在数论上的一条欧拉公式A^Phi(C)=1 (mod C)  前提是：(A,C)=1

 

九、

Fib数列的循环。

1) pi = 5, 暴力

2) 循环可能满足

  a) 是P – 1的因子

  b) 是2P + 2 的因子……

  c) 就是P……

————————————————持续更新——————————————————————————

【题目大意】
给定一棵树，然后给出两种操作：
1、改变某条边的权值
2、询问点x到点y的路径上，长度最长的边的长度是多少？
【算法分析】
我是按照漆子超大神的论文做的。
他如是说道：
对于一棵树，定义Size(u)为以u为根的子树的结点数。
然后对于u与所有儿子v相连的边而言，Size(v)最大的，那条边就叫重边，其它边都是轻边。
Then，有一个重要结论：
每个点到根的路径上都不超过O(lg N)条轻边和O(lg N)条重路径。
（重路径是由重边连续连成的）
然后我们对于每个询问(x,y)的路径，就可以分成(x,lca(x,y))的路径和(y,lca(x,y))的路径。
于是问题变成怎么求x到它一个祖先结点的边权的最大值。
我们就可以轻边直接算，重路径利用线段树求解。
最终就可以在O(Q lg ^2 n)的复杂度得到解。(Q问询问个数)
至于具体实现的话，我是把连续的重边先DFS，然后再DFS其它轻边。
弄一个队列装起来，这样DFS完以后就可以保证连续的重边(重路径)在队列里是连续的。
然后就把连续的重路径涂上同一个颜色。在记录一下这种颜色在队里里起始点是哪。
方便后面利用。
至于求lca我是利用的经典的转化为RMQ求解。
当然，少不了N个指向数组指来指去。。。。，指到头都晕了。

【用到的东西】
LCA——>RMQ
线段树
【其它】
我那叫一个激动啊。。200+行，5KB的程序一次过样例，一次AC！
3552963 2010-04-24 18:16:42 cwj Query on a tree accepted 4.25 6.0M

C++

4.0.0-8

时间有点丑，大概是因为我每次都memset的关系吧。。。
不过能A就成。。。
【CODE】
#include #include #include #define max(x,y) (x)>(y)?(x):(y)
#define min(x,y) (x)<(y)?(x):(y)
const int E=20005;
const int N=10005;
const int INF=1000000000;
struct edge{int x,y,w,next,op,heavy,inlist;}g[E];
struct Node{int l,r,data;}tr[E*5];
int n,Tc,e,heavytot,ctot,rmqtot,ans,nowdep;
int ls[N],Size[N],dep[N],fa[N];
int heavyedge[N],color[E],colorst[E];
int R[E],rmq[16][E],lg[E];

inline void swap(int &x,int &y){x=x^y; y=x^y; x=x^y;}

void addedge(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w;
g[e].next=ls[x]; ls[x]=e;
}

void init(){
e=0;
heavytot=0;
ctot=0;
rmqtot=0;
memset(ls,0,sizeof(ls));
memset(heavyedge,0,sizeof(heavyedge));
memset(Size,0,sizeof(Size));
memset(g,0,sizeof(g));
memset(fa,0,sizeof(fa));
memset(color,0,sizeof(color));
memset(colorst,0,sizeof(colorst));
memset(R,0,sizeof(R));
memset(rmq,0,sizeof(rmq));

char op[100];
int x,y,w,i;

scanf("%d",&n);
for (i=1;i scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
g[e].op=i+n-1;
}
for (i=1;i addedge(g[i].y,g[i].x,g[i].w);
g[e].op=i;
}
}

void Get_Size(int p,int &times){
rmq[0][++rmqtot]=dep[p];
R[p]=rmqtot;
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op){
dep[g[t].y]=dep[p]+1;
fa[g[t].y]=t;
Get_Size(g[t].y,times);
rmq[0][++rmqtot]=dep[p];
}
Size[p]=times-Size[p];
}

void Get_heavyedge(int p){
int zz=0,mm=0;
for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && Size[g[t].y]>mm){
mm=Size[g[t].y];
zz=t;
}
if (!zz) return;
heavyedge[++heavytot]=zz;
g[zz].heavy=1;
g[zz].inlist=heavytot;
g[g[zz].op].heavy=1;
g[g[zz].op].inlist=heavytot;
Get_heavyedge(g[zz].y);

for (int t=ls[p];t;t=g[t].next)
if (t!=g[fa[p]].op && t!=zz)
Get_heavyedge(g[t].y);
}

void draw_color(){
ctot=1; color[heavyedge[1]]=1; colorst[1]=1;
for (int i=2;i<=heavytot;i++){
int &t=heavyedge[i],&pt=heavyedge[i-1];
if (g[pt].y!=g[t].x){
ctot++;
colorst[ctot]=i;
}
color[t]=ctot;
color[g[t].op]=ctot;
}
}

void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r;
if (l==r){
tr[p].data=g[heavyedge[l]].w;
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

void buildrmq(){
int i,k;
lg[1]=0;
for (i=2;i<=rmqtot;i++){
lg[i]=lg[i-1];
if (1< }
for (k=1;(1< for (i=1;i+(1< rmq[k][i]=min(rmq[k-1][i],rmq[k-1][i+(1<}

void pre_work(){
int tmp=0;
dep[1]=1;
fa[1]=0;
Get_Size(1,tmp);
Get_heavyedge(1);
draw_color();
build(1,1,heavytot);
buildrmq();
}

void Change(int p,int pos){
if (tr[p].l==tr[p].r){
tr[p].data=g[heavyedge[pos]].w;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (pos<=mid) Change(p*2,pos);
else Change(p*2+1,pos);
tr[p].data=max(tr[p*2].data,tr[p*2+1].data);
}

int getmin(int x,int y){
if (x>y) swap(x,y);
int step=lg[y-x+1];
return min(rmq[step][x],rmq[step][y-(1<}

int getmax(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r) return tr[p].data;
int tmp1=-INF,tmp2=-INF,mid=(tr[p].l+tr[p].r)/2;
if (l<=mid) tmp1=getmax(p*2,l,r);
if (r>=mid+1) tmp2=getmax(p*2+1,l,r);
return max(tmp1,tmp2);
}

void Try(int x){
if (dep[x]==nowdep) return;
if (g[fa[x]].heavy){
int &p=g[heavyedge[colorst[color[fa[x]]]]].x,tmp;
if (dep[p]>=nowdep){
Try(p);
tmp=getmax(1,colorst[color[fa[x]]],g[fa[x]].inlist);
ans=max(ans,tmp);
}
else{
tmp=getmax(1,g[fa[x]].inlist-(dep[x]-nowdep-1),g[fa[x]].inlist);
ans=max(ans,tmp);
}
}
else{
Try(g[fa[x]].x);
ans=max(ans,g[fa[x]].w);
}
}

void solve(){
char op[100];
int x,y;
for (;;){
scanf("%s",op+1);
if (op[1]==’D’) return;
if (op[1]==’C’){
scanf("%d%d",&x,&y);
g[x].w=y;
g[g[x].op].w=y;
if (g[x].heavy) Change(1,g[x].inlist);
}
else{
ans=0;
scanf("%d%d",&x,&y);
nowdep=getmin(R[x],R[y]);
Try(x);
Try(y);
printf("%dn",ans);
}
}
}

int main(){
scanf("%d",&Tc);
for (int i=0;i init();
pre_work();
solve();
}
}