分类存档：默认分类

【题目】

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();
}
}

【算法分析】
= =，看了解题报告才弄出来。
一开始写了个暴力的最大权闭合图骗分，结果直接崩溃。。。0分。。。Orz，也许是敲错了吧
一开始还以为容斥原理+最小割。。。
该题是动态规划。
首先我们画画图，发现它是楼梯形的。当然，如果两个宝藏y坐标相同，而x坐标差1的话，是可以成一横线的。
然后我们就可以按格子划分状态得到方程：
f[i,j]=max(f[i-1,j-1]+Sum+j,f[i-1][j]+Sum+j,f[i-1][j+1])
然后仅有在宝藏的斜线与y坐标相同的水平线上的状态才是有用的。
于是我们就只搞这些状态就可以了。
处理斜线的话，向上斜的就会x-y为定值，向下斜的就会x+y为定值，然后分别按x-y,x+y，y，排下序，最终就可以利用归并排序的思想，在本x的有效状态数的复杂度内，弄出有效的状态。
然后转移即可。
【CODE】
#include #include using namespace std;
const int N=1005;
const int maxx=10005;
const int E=1000000;
const int INF=100000000;
int n,tot[2],m,ans,X;
int list[2][E],f[2][E];
struct PT{int x,y,p,w;}a[N],b[N],c[N];

int cmp(const void *a,const void *b){
return ((PT*)a)->w-((PT*)b)->w;
}

void input(){
std::ios::sync_with_stdio(false);
tot[0]=0; tot[1]=0;
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y >> a[i].p;
a[i].y=abs(a[i].y);
}
int ll=1,rr=1;
for (int i=1;i<=n;i++){
ll=min(ll,a[i].x-a[i].y);
rr=max(rr,a[i].x+a[i].y);
}
ll-=5; rr=rr+5-ll;
for (int i=1;i<=n;i++){
a[i].x-=ll;
b[i]=a[i];
c[i]=a[i];
}
X=rr;
for (int i=1;i<=n;i++){
a[i].w=a[i].y;
b[i].w=b[i].x+b[i].y;
c[i].w=c[i].y-c[i].x;
}
qsort(a+1,n,sizeof(PT),cmp);
qsort(b+1,n,sizeof(PT),cmp);
qsort(c+1,n,sizeof(PT),cmp);
}

void build(int x,int &tot,int *list,int *f){
tot=1;
list[1]=0;
f[1]=0; f[2]=f[3]=f[4]=-INF;
int t1=1,t2=1,t3=1,now,pos;
while (t1<=n || t2<=n || t3<=n){
now=INF; pos=0;
if (t1<=n && a[t1].w if (t2<=n && b[t2].w-x if (t3<=n && c[t3].w+x switch (pos){
case 0:for (;;);
case 1:
if (a[t1].w !=list[tot]) list[++tot]=a[t1].w;
t1++;
break;
case 2:
if (b[t2].w-x!=list[tot] && b[t2].w-x>=0) list[++tot]=b[t2].w-x;
t2++;
break;
case 3:
if (c[t3].w+x!=list[tot] && c[t3].w+x>=0) list[++tot]=c[t3].w+x;
t3++;
break;
}
}
}

void dp(int x,int &pt,int &nt,int *pl,int *nl,int *pf,int *f){
int i,j=1,k=1,Sum=0,jj;
for (i=1;i<=nt;i++){
while (k<=n && a[k].y<=nl[i]){
if (a[k].x==x) Sum+=a[k].p;
k++;
}
while (j<=pt && pl[j]+1 f[i]=-INF;
for (jj=j;jj<=j+3 && jj<=pt;jj++)
if (abs(pl[jj]-nl[i])<=1)
f[i]=max(f[i],pf[jj]+Sum-nl[i]);
}
f[1]=max(0,f[1]);
ans=max(ans,f[1]);
}

void work(){
ans=0; f[0][0]=f[0][2]=-INF;
tot[0]=1; list[0][1]=0; f[0][1]=0;
for (int i=1;i<=X;i++){
build(i,tot[i%2],list[i%2],f[i%2]);
dp(i,tot[1-i%2],tot[i%2],list[1-i%2],list[i%2],f[1-i%2],f[i%2]);
}
}

int main(){
freopen("treasures.in","r",stdin);
freopen("treasures.out","w",stdout);
input();
work();
cout << ans << endl;
return 0;
}