[HDOJ2855 Fibonacci Check-up]【找规律~】【矩阵乘法】

【题目大意】
求 % m
【算法分析】
首先我们发现答案是指关于n的一个函数。
那么我们把小数据暴力一下，得到下表：
0 0 0
1 1 1
2 3 2
3 8 5
4 21 13
5 55 34
6 144 89
7 377 233
8 987 610
9 2584 1597
10 6765 4181
11 17711 10946
12 46368 28657
13 121393 75025
14 317811 196418
15 832040 514229
16 2178309 1346269
17 5702887 3524578
18 14930352 9227465
19 39088169 24157817
20 102334155 63245986
21 267914296 165580141
22 701408733 433494437
23 1836311903 1134903170
24 4807526976 2971215073
25 12586269025 7778742049
26 32951280099 20365011074
27 86267571272 53316291173
28 225851433717 139583862445
29 591286729879 365435296162
30 1548008755920 956722026041
其中第一个是序号，第二个是答案，第三个是ans[i]-ans[i-1]。
设第三个是p[i]，那么容易发现p[i]=3*p[i-1]-p[i-2]。
然后列出矩阵求解即可。
【其它】
居然WA了好多遍。。。真不可饶恕啊= =。
WA的原因是：n=0时没有答案输出来。。。。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
lld n,mod;
lld a[1][3];
lld c[3][3],p[3][3],res[3][3];

void Pow(lld cf){
if (cf==1){
memcpy(p,c,sizeof(c));
return;
}
lld i,j,k;
Pow(cf/2);
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*p[k][j])%mod;
memcpy(p,res,sizeof(res));
if (cf%2){
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*c[k][j])%mod;
memcpy(p,res,sizeof(res));
}
}

void solve(){
a[0][0]=1; a[0][1]=1; a[0][2]=2;
c[0][0]=1; c[0][1]=0; c[0][2]=0;
c[1][0]=0; c[1][1]=0; c[1][2]=-1;
c[2][0]=1; c[2][1]=1; c[2][2]=3;
Pow(n-1);
lld i,j,k;
memset(res,0,sizeof(res));
for (i=0;i<1;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=((res[i][j]+a[i][k]*p[k][j])%mod+mod)%mod;
cout << (res[0][0]+mod)%mod << "n";
}

int main(){
lld Tc;
cin >> Tc;
for (lld i=0;i cin >> n >> mod;
if (n==0) cout << "0n";
if (n==1) cout << 1%mod << "n";
if (n>=2) solve();
}
}

[POJ3375 Network Connection & 衡阳八中1980]去除冗余状态优化的动态规划

【题目链接】
http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1980 （中文）
http://acm.pku.edu.cn/JudgeOnline/problem?id=3375
【算法分析】
初看题目。。以为费用流。然后看规模，果断dp。
去除无用状态以后就能AC。
当然，一开始果断排序。
然后，容易用F[i][j]表示选完A[i]和B那边选过B[j]时最小值是多少。
实际上容易发现，令Best[i]为abs(A[i]-B[j])得到最小值时的位置。
那么他最多向前让n-i位（因为他后面还有n-i个数要配），或者说向后让i-1位。
所以，对于每个A[i]，只要储存[Best[i]-(n-1),Best[i]+(i-1)]这个区间上的F值就可以了。
于是能在规定时限内很快通过。
【时间复杂度】O(n lg n + m lg m + n^2)
【空间复杂度】O(n^2 + m) 滚动可以变成O(n + m)
【其它】WA了几次，因为算Best的时候，没有考虑到B数组相等，一直卡在那里的情况= =。。。
【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
const int M=1000005;
const int N=2005;
const int INF=0x7FFFFFFF;
int n,m;
int a[N],b[M],St[N];
int F[N][N];

void Read(int &x){
char ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
int sign=1;
if (ch==’-‘){
sign=-1;
ch=getchar();
while (ch==’ ‘ || ch==’n’) ch=getchar();
}
x=0;
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
x*=sign;
}

void input(){
Read(m); Read(n);
for (int i=1;i<=m;i++) Read(b[i]);
for (int i=1;i<=n;i++) Read(a[i]);
}

int cmp(const void *A,const void *B){return (*((int*)A))-(*((int*)B));}
void init(){
qsort(a+1,n,sizeof(int),cmp);
qsort(b+1,m,sizeof(int),cmp);
int i,j=1;
for (i=1;i<=n;i++){
while (j St[i]=max(1,j-(n-i));
}
}

void dp(){
int i,j,k,ans=INF;
if (n==1){
for (i=1;i<=m;i++) ans=min(ans,abs(a[1]-b[i]));
printf("%dn",ans);
return;
}
F[1][0]=abs(a[1]-b[St[1]]);
for (i=1;St[1]+i<=m && i<=n;i++)
F[1][i]=min(F[1][i-1],abs(a[1]-b[St[1]+i]));
for (i=2;i<=n;i++){
k=St[i-1];
for (j=St[i];j<=m && j<=St[i]+n;j++){
while (k int &t=F[i][j-St[i]];
t=INF;
if (j!=St[i]) t=F[i][j-St[i]-1];
t=min(t,F[i-1][k-St[i-1]]+abs(a[i]-b[j]));
if (i==n) ans=min(ans,t);
}
}
printf("%dn",ans);
}

int main(){
input();
init();
dp();
}

[POJ2942 Knights of the Round Table]【点的双连通分量】

【题目大意】
给一个无向图，对于每个点，求他是否在一个奇环中。如果不是ans++。输出ans。
【算法分析】
先求点的双连通分量，然后对于每个双连通分量，如果他里面有奇环，那么整个双连通分量上的点都在某奇环上。（这个可以用可以用奇偶性证明，实际上就是把整个图搞成两个有重叠部分的环）
然后判断一个双连通分量里有无奇环就可以交替染色。如果出现一条边的两端颜色相等，那么有奇环。
否则无奇环（利用反证法证明）
【其它】
原来我一直用的那个自创的沙茶并查集类Tarjan思想的算的是边的双连通分量，而不是点的双连通分量。于是果断WA到沙茶。。。哎，算法问题。。。
然后终于下定决心学习正版的Tarjan。学习结束重写1Y。
【CODE】
#include #include #include #define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define clr(T) memset(T,0,sizeof(T))
const int N=1005;
struct edge{int x,y,next;}g[N*N];
int n,m,times,tot,e,Qt,cnt,check;
int a[N][N],ls[N],vis[N];
int DFN[N],done[N],Stack[N*N],low[N],Q[N*N],color[N*N],odd[N];

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

void init(){
int i,j,x,y;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
a[i][j]=i!=j;
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=0;
}
times=tot=cnt=0;
e=1;
clr(ls);
clr(vis);
clr(DFN);
clr(done);
clr(low);
clr(odd);
for (i=1;i for (j=i+1;j<=n;j++)
if (a[i][j]){
addedge(i,j);
addedge(j,i);
}
}

void draw(int x){
vis[x]=cnt;
for (int t=ls[x];t;t=g[t].next)
if (color[t]==cnt && vis[g[t].y]!=cnt){
odd[g[t].y]=1-odd[x];
draw(g[t].y);
}else
if (color[t]==cnt && vis[g[t].y]==cnt && odd[g[t].y]==odd[x])
check=1;
}

void solve(int x){
cnt++;
for (int i=1;i<=Qt;i++){
color[Q[i]]=cnt;
color[Q[i]^1]=cnt;
}
check=0;
odd[x]=1;
draw(x);
if (check)
for (int i=1;i<=Qt;i++)
done[g[Q[i]].x]=done[g[Q[i]].y]=1;
}

void dfs(int x,int fa){
DFN[x]=low[x]=++times;
for (int t=ls[x];t;t=g[t].next){
int y=g[t].y;
if (y==fa) continue;
if (!DFN[y]){
Stack[++tot]=t;
dfs(y,x);
low[x]=min(low[x],low[y]);
if (DFN[x]<=low[y]){
Qt=0;
while (Stack[tot]!=t)
Q[++Qt]=Stack[tot–];
Q[++Qt]=Stack[tot–];
solve(x);
}
}else if (DFN[y] Stack[++tot]=t;
low[x]=min(low[x],DFN[y]);
}
}
}

void Tarjan(){
for (int i=1;i<=n;i++)
if (!DFN[i])
dfs(i,0);
}

int main(){
for (;;){
scanf("%d%d",&n,&m);
if (!n) break;
init();
Tarjan();
int ans=0;
for (int i=1;i<=n;i++)
if (!done[i]) ans++;
printf("%dn",ans);
}
return 0;
}

[Croatian Olympiad in Informatics 【kolo】]【找规律】【正模拟】【逆模拟】

【题目链接】
http://www.hsin.hr/coci/
提交地址：http://evaluator.hsin.hr/
【题目大意】
1..n的n个数站成一个圈。
一共进行k轮
对于第i轮
选取位于最顶端的数。
他和自己逆时针方向相邻的那个数交换，一直交换pl[i]次。 其中pl[i]为第i个质数。
输入n,k,A。
A表示一开始的第A个数。
问进行了k轮以后，A的两个邻居是谁？
【算法分析】
假如n<=10^5，那么还可以用平衡树模拟搞一下。
但是n超大，所以不能如此。
质数自然是用筛法筛出来了。
然后我们可以先搞出A最后到了哪里。然后算出他的邻居，最后再逆回来，看一开始在哪里，就可以知道编号了。
然后具体的，容易发现，假如经过n*(n-1)次交换，那么相当于没动。
所以每次处理可以讲交换次数先%(n*(n-1))。  这里小心会爆int。
然后我们可以发现每转n次，那么将相当于忽略了顶端的那个数以后，都向顺时针转了一格。
于是首先是模拟转了p/n次以后的。
最后模拟剩下的转圈。这个不容易想。

然后逆回去将相当于反过来做了。。。
【其它】第一次交，95分。原因是我%(n*n)而不是%(n*(n-1))。。。居然这都有这么高分。。。泪流满面。
【Record】
est # Score Time Memory Result 1 5 0.52s 10392 kB Correct! 2 5 0.52s 10392 kB Correct! 3 5 0.52s 10392 kB Correct! 4 5 0.52s 10392 kB Correct! 5 5 0.52s 10392 kB Correct! 6 5 0.52s 10392 kB Correct! 7 5 0.53s 10392 kB Correct! 8 5 0.54s 10392 kB Correct! 9 5 0.54s 10392 kB Correct! 10 5 0.54s 10392 kB Correct! 11 5 0.53s 10392 kB Correct! 12 5 0.53s 10392 kB Correct! 13 5 0.54s 10392 kB Correct! 14 5 0.54s 10392 kB Correct! 15 5 0.54s 10392 kB Correct! 16 5 0.60s 10392 kB Correct! 17 5 0.66s 10392 kB Correct! 18 5 0.68s 10392 kB Correct! 19 5 0.67s 10392 kB Correct! 20 5 0.66s 10392 kB Correct! 【CODE】
#include #include #include #include using namespace std;
const int Size=7368789;
typedef long long lld;
int n,k,A,pt;
int pl[500005];
bool v[Size];

int Get(int x){return (x%n+n)%n;}

void Next(int &x,int p){
p=(int)(p%((lld)(n)*(n-1)));
if (x==0){
x=Get(p);
return;
}
x-=p/n;
if (x<=0) x--;
x=Get(x);
if (p%n>=x) x=Get(x-1);
}

void Pre(int &x,int p){
p=(int)(p%((lld)(n)*(n-1)));
if (p%n==x){
x=0;
return;
}
if (x x+=p/n;
if (x>=n) x=Get(x+1);
}

void Sai(){
memset(v,true,sizeof(v));
int i,j;
for (i=2;i for (j=i+i;j pt=0;
for (i=2;pt if (v[i]) pl[pt++]=i;
}

int main(){
int i,ans1,ans2;
// freopen("kolo.in.7","r",stdin);
// freopen("kolo.out","w",stdout);
cin >> n >> k >> A;
A–;
Sai();
for (i=0;i ans1=Get(A+1);
ans2=Get(A-1);
for (i=k-1;i>=0;i–){
Pre(ans1,pl[i]);
Pre(ans2,pl[i]);
}
cout << ans1+1 << " " << ans2+1 << endl;
}

[COCI Croatian Olympiad in Informatics 【hrastovi】]【二分】【各种排序】

【题目链接】http://www.hsin.hr/coci/
【题目大意】
给定N个点和Q个矩形。
对于每个矩形，求有多少个点落在其边界上。
【算法分析】
把一个矩形分成4条线段。然后分别处理。
可以先处理x=k的线段。
就是，把点按x为第一关键字，y为第二关键字排序。
然后对于每个x=k的线段，然后二分出对应范围，弄个Sum数组搞一下。就可以了。
对于y=k的线段，类似地处理。
就可以很快地搞定。
【其它】1Y。
【CODE】
#include #include #include struct Point{int x,y;}p[300005];
struct Ques{int x1,y1,x2,y2;}Q[100005];
struct Line{int key,l,r,pos;}L[200005];
int n,Qt,Lt;
int Sum[300005],ans[100005];

void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
scanf("%d",&Qt);
for (int i=1;i<=Qt;i++)
scanf("%d%d%d%d",&Q[i].x1,&Q[i].y1,&Q[i].x2,&Q[i].y2);
}

int cmpx_p(const void *A,const void *B){
if ( ((Point*)A)->x != ((Point*)B)->x ) return ((Point*)A)->x-((Point*)B)->x;
return ((Point*)A)->y-((Point*)B)->y;
}

int cmp_L(const void *A,const void *B){
return ((Line*)A)->key-((Line*)B)->key;
}

int Findx_l(int st,int ed,int y){
int l=st,r=ed,mid;
while (l mid=(l+r)/2;
if (y<=p[mid].y) r=mid;
else l=mid+1;
}
if (y<=p[l].y) return l;
return 0x7FFFFFFF;
}

int Findx_r(int st,int ed,int y){
int l=st,r=ed,mid;
while (l mid=(l+r+1)/2;
if (p[mid].y<=y) l=mid;
else r=mid-1;
}
if (p[l].y<=y) return l;
return -0x7FFFFFFF;
}

void solvex(){
int i,j,stp,edp,stL,edL,l,r;
Lt=0;
for (i=1;i<=Qt;i++){
L[++Lt].l=Q[i].y1; L[Lt].r=Q[i].y2; L[Lt].pos=i; L[Lt].key=Q[i].x1;
L[++Lt].l=Q[i].y1; L[Lt].r=Q[i].y2; L[Lt].pos=i; L[Lt].key=Q[i].x2;
}
qsort(p+1,n,sizeof(Point),cmpx_p);
qsort(L+1,Lt,sizeof(Line),cmp_L);
edL=1;
for (i=1;i<=n;i=edp+1){
stp=i;
for (edp=i;edp for (stL=edL;stL<=Lt && L[stL].key for (edL=stL;edL if (stL>Lt || L[stL].key!=p[i].x) continue;
for (j=stp;j<=edp;j++) Sum[j]=j-stp+1;
for (j=stL;j<=edL;j++){
l=Findx_l(stp,edp,L[j].l);
r=Findx_r(stp,edp,L[j].r);
if (l>r) continue;
ans[L[j].pos]+=Sum[r]-Sum[l]+1;
}
}
}

int cmpy_p(const void *A,const void *B){
if ( ((Point*)A)->y != ((Point*)B)->y ) return ((Point*)A)->y-((Point*)B)->y;
return ((Point*)A)->x-((Point*)B)->x;
}

int Findy_l(int st,int ed,int x){
int l=st,r=ed,mid;
while (l mid=(l+r)/2;
if (x<=p[mid].x) r=mid;
else l=mid+1;
}
if (x<=p[l].x) return l;
return 0x7FFFFFFF;
}

int Findy_r(int st,int ed,int x){
int l=st,r=ed,mid;
while (l mid=(l+r+1)/2;
if (p[mid].x<=x) l=mid;
else r=mid-1;
}
if (p[l].x<=x) return l;
return -0x7FFFFFFF;
}

void solvey(){
int i,j,stp,edp,stL,edL,l,r;
Lt=0;
for (i=1;i<=Qt;i++){
L[++Lt].l=Q[i].x1+1; L[Lt].r=Q[i].x2-1; L[Lt].pos=i; L[Lt].key=Q[i].y1;
if (L[Lt].l>L[Lt].r) Lt–;
L[++Lt].l=Q[i].x1+1; L[Lt].r=Q[i].x2-1; L[Lt].pos=i; L[Lt].key=Q[i].y2;
if (L[Lt].l>L[Lt].r) Lt–;
}
qsort(p+1,n,sizeof(Point),cmpy_p);
qsort(L+1,Lt,sizeof(Line),cmp_L);
edL=1;
for (i=1;i<=n;i=edp+1){
stp=i;
for (edp=i;edp for (stL=edL;stL<=Lt && L[stL].key for (edL=stL;edL if (stL>Lt || L[stL].key!=p[i].y) continue;
for (j=stp;j<=edp;j++) Sum[j]=j-stp+1;
for (j=stL;j<=edL;j++){
l=Findy_l(stp,edp,L[j].l);
r=Findy_r(stp,edp,L[j].r);
if (l>r) continue;
ans[L[j].pos]+=Sum[r]-Sum[l]+1;
}
}
}

int main(){
// freopen("HRASTOVI.in","r",stdin);
// freopen("HRASTOVI.out","w",stdout);
init();
solvex();
solvey();
for (int i=1;i<=Qt;i++) printf("%dn",ans[i]);
return 0;
}