题目列表：hdu5214~5223
5214：
当时第一反应是由递推公式推出通项公式，事实证明这就是作！大！死！
因为通项公式是这样的：L[n]=a^(n-1)*(b+L[1])-b
于是就需要快速幂。然而用了快速幂还是慢。。。【实际上是被卡在了7000ms多一点点。。。】
其实直接放到数组里一项一项递推就行。。速度并不慢还省事
另外本题还有一个point：被mod的那个数字很奇怪，所以直接用unsigned int存就行。不仅省空间还不用mod了（溢出相当于自动mod）
当时没想起来这个于是用了long long，于是数组存不下，于是T^T
#include <iostream>
#include <cstdio>
#include <cstring>
#define LL unsigned int
//#define MOD 4294967296
using namespace std;
LL N,L1,R1,a,b,c,d,T;
LL ll[],rr[];
LL li,ri; int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d%d%d%d",&N,&L1,&R1,&a,&b,&c,&d);
ll[]=L1; rr[]=R1;
if(L1>R1) swap(L1,R1);
LL minl=L1,minr=R1,maxl=L1,maxr=R1;
for(LL i=;i<=N;i++)
{
ll[i]=ll[i-]*a+b;
rr[i]=rr[i-]*c+d;
li=ll[i],ri=rr[i];
if(li>ri) swap(li,ri);
if (ri<minr)
{
minl=li;
minr=ri;
}
if (li>maxl)
{
maxl=li;
maxr=ri;
}
}
bool ok=false;
//cout<<minl<<","<<minr<<" "<<maxl<<","<<maxr<<endl;
for(LL i=;i<=N;i++)
{
li=ll[i]; ri=rr[i];
if(li>ri) swap(li,ri);
//cout<<li<<","<<ri<<endl;
if((li>minr)&&(ri<maxl))
{
ok=true;
break;
}
}
if (ok) printf("YES\n"); else printf("NO\n");
}
return ;
}
5222：
并查集+拓扑排序
对于双向边联通的那些点，可以看作一个点。（因为它们任意两点之间都可以到达）
最后把这个union作为一个点，和剩下的单向边放一起构图。然后拓扑排序判断有没有环。
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include<vector>
#include<cstring>
using namespace std;
#define MAXN 10000000
int f[MAXN]; //father
int d[MAXN]; //->i
int nxt[MAXN];
int head[MAXN];
int ev[MAXN];
int cnt;
int N,M1,M2,T,x,y; int find(int x)
{
if (f[x]!=x)
f[x]=find(f[x]);
return f[x];
} void iunion(int x,int y)
{
int fx,fy;
fx=find(x);
fy=find(y);
if (fx!=fy)
f[fx]=fy;
} void addedge(int x,int y) //x->y
{
d[y]++; //d[i]:点i的入度
ev[cnt]=y; //ev[i]:第i条边的destination
nxt[cnt]=head[x]; //nxt[i]:第i条边的下一条边
head[x]=cnt; //head[i]:由i节点出发的第一条边的序号
cnt++;
} void topsort()
{
int res=;
vector<int>vec;
for(int i=; i<=N; i++)
if(i==find(i))
{
++res;
if(d[i]==)
vec.push_back(i);
}
for(int i=; i<vec.size(); i++)
{
int u=vec[i];
for(int j=head[u]; ~j; j=nxt[j])
{
int v=ev[j];
d[v]--;
if(!d[v])
vec.push_back(v);
}
}
int last=vec.size();
if(last!=res)
printf("YES\n");
else printf("NO\n");
} int main()
{
cin>>T;
while(T--)
{
scanf("%d%d%d",&N,&M1,&M2);
for(int i=; i<=N; i++) f[i]=i;
bool ok=false;
for(int i=; i<=M1; i++)
{
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
if(fx==fy) ok=true;
else f[fx]=fy;
}
cnt=;
memset(d,,sizeof(d));
memset(head,-,sizeof(head));
for(int i=; i<=M2; i++)
{
scanf("%d%d",&x,&y);
int tx=find(x),ty=find(y);
addedge(tx,ty);
}
if(ok)
{
printf("YES\n");
}
else
topsort(); } return ;
}
5223：
这题当时交给队友了。。。。
题意：给出若干L,R,A，表示gcd(p[L],p[L+1],...,p[R])=A。要求解出原数组p[]
sol：首先来看几个有代表性的情况：
1 9 7 1 9 6 1 9 8 1 9 3 1 9 4 1 9 8 1 5 3
2 5 3 2 5 4 2 5 4 2 5 7 2 5 6 2 5 4 2 7 7
stupid stupid stupid stupid stupid ok ok
对所有的L,R,A，令p[i]=lcm(p[i],A)（L<=i<=R）。最后再验证一遍
其实最后验证的时候求区间的gcd可以用优化的方法（类似RMQ的那个）。本题数据小懒得用了= =
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define LL long long LL p[]; //array
int L[],R[]; //Li,Ri
LL A[]; //Ansi
int T,N,Q; LL gcd(LL a,LL b) //辗转相除法，返回gcd(a,b)
{
if (b==) return a;
return gcd(b,a%b);
} LL lcm(LL a,LL b)
{
LL t=gcd(a,b);
t=a*b/t;
return t;
} LL ggcd(int l,int r)
{
LL aa=p[l];
for(int i=l+;i<=r;i++)
aa=gcd(aa,p[i]);
return aa;
} LL llcm(int l,int r)
{
LL aa=p[l];
for(int i=l+;i<=r;i++)
aa=lcm(aa,p[i]);
return aa;
} int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&N,&Q);
for(int i=;i<=;i++)p[i]=;
for(int i=;i<=Q;i++)
{
scanf("%d%d%I64d",&L[i],&R[i],&A[i]);
//LL t=llcm(L[i],R[i]);
//t=lcm(t,A[i]);
for(int j=L[i];j<=R[i];j++)
p[j]=lcm(p[j],A[i]);
//p[j]=t;
}
bool ok=true;
for (int i=;i<=Q;i++)
{
LL t=ggcd(L[i],R[i]);
// printf("%d,%d = %I64d\n",L[i],R[i],t);
if (t!=A[i]) ok=false;
}
// for(int i=1;i<=N;i++)
// printf("%d ",p[i]);
// printf("\n");
if(ok)
{
for(int i=;i<N;i++)
printf("%I64d ",p[i]);
printf("%I64d\n",p[N]);
}
else
printf("Stupid BrotherK!\n");
}
return ;
}