bestcoder杯回顾

题目列表：hdu5214~5223

5214：

当时第一反应是由递推公式推出通项公式，事实证明这就是作！大！死！

因为通项公式是这样的：L[n]=a^(n-1)*(b+L[1])-b

于是就需要快速幂。然而用了快速幂还是慢。。。【实际上是被卡在了7000ms多一点点。。。】

其实直接放到数组里一项一项递推就行。。速度并不慢还省事

另外本题还有一个point：被mod的那个数字很奇怪，所以直接用unsigned int存就行。不仅省空间还不用mod了（溢出相当于自动mod）

当时没想起来这个于是用了long long，于是数组存不下，于是T^T

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define LL  unsigned int
 5 //#define MOD 4294967296
 6 using namespace std;
 7 LL N,L1,R1,a,b,c,d,T;
 8 LL ll[10000010],rr[10000010];
 9 LL li,ri;
10 
11 int main()
12 {
13     scanf("%d",&T);
14     while(T--)
15     {
16         scanf("%d%d%d%d%d%d%d",&N,&L1,&R1,&a,&b,&c,&d);
17         ll[1]=L1;   rr[1]=R1;
18         if(L1>R1)   swap(L1,R1);
19         LL minl=L1,minr=R1,maxl=L1,maxr=R1;
20         for(LL i=2;i<=N;i++)
21         {
22             ll[i]=ll[i-1]*a+b;
23             rr[i]=rr[i-1]*c+d;
24             li=ll[i],ri=rr[i];
25             if(li>ri)   swap(li,ri);
26             if (ri<minr)
27             {
28                 minl=li;
29                 minr=ri;
30             }
31             if (li>maxl)
32             {
33                 maxl=li;
34                 maxr=ri;
35             }
36         }
37         bool ok=false;
38         //cout<<minl<<","<<minr<<"  "<<maxl<<","<<maxr<<endl;
39         for(LL i=1;i<=N;i++)
40         {
41             li=ll[i];   ri=rr[i];
42             if(li>ri)   swap(li,ri);
43             //cout<<li<<","<<ri<<endl;
44             if((li>minr)&&(ri<maxl))
45             {
46                 ok=true;
47                 break;
48             }
49         }
50         if (ok) printf("YES
");    else printf("NO
");
51     }
52     return 0;
53 }

View Code

5222：

并查集+拓扑排序

对于双向边联通的那些点，可以看作一个点。（因为它们任意两点之间都可以到达）

最后把这个union作为一个点，和剩下的单向边放一起构图。然后拓扑排序判断有没有环。

  1  #pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include<vector>
  5 #include<cstring>
  6 using namespace std;
  7 #define MAXN 10000000
  8 int f[MAXN];        //father
  9 int d[MAXN];        //->i
 10 int nxt[MAXN];
 11 int head[MAXN];
 12 int ev[MAXN];
 13 int cnt;
 14 int N,M1,M2,T,x,y;
 15 
 16 int find(int x)
 17 {
 18     if (f[x]!=x)
 19         f[x]=find(f[x]);
 20     return f[x];
 21 }
 22 
 23 void iunion(int x,int y)
 24 {
 25     int fx,fy;
 26     fx=find(x);
 27     fy=find(y);
 28     if (fx!=fy)
 29         f[fx]=fy;
 30 }
 31 
 32 void addedge(int x,int y)       //x->y
 33 {
 34     d[y]++;             //d[i]:点i的入度
 35     ev[cnt]=y;          //ev[i]:第i条边的destination
 36     nxt[cnt]=head[x];   //nxt[i]:第i条边的下一条边
 37     head[x]=cnt;        //head[i]:由i节点出发的第一条边的序号
 38     cnt++;
 39 }
 40 
 41 void topsort()
 42 {
 43     int res=0;
 44     vector<int>vec;
 45     for(int i=1; i<=N; i++)
 46         if(i==find(i))
 47         {
 48             ++res;
 49             if(d[i]==0)
 50                 vec.push_back(i);
 51         }
 52     for(int i=0; i<vec.size(); i++)
 53     {
 54         int u=vec[i];
 55         for(int j=head[u]; ~j; j=nxt[j])
 56         {
 57             int v=ev[j];
 58             d[v]--;
 59             if(!d[v])
 60                 vec.push_back(v);
 61         }
 62     }
 63     int last=vec.size();
 64     if(last!=res)
 65         printf("YES
");
 66     else printf("NO
");
 67 }
 68 
 69 int main()
 70 {
 71     cin>>T;
 72     while(T--)
 73     {
 74         scanf("%d%d%d",&N,&M1,&M2);
 75         for(int i=1; i<=N; i++)   f[i]=i;
 76         bool ok=false;
 77         for(int i=1; i<=M1; i++)
 78         {
 79             scanf("%d%d",&x,&y);
 80             int fx=find(x),fy=find(y);
 81             if(fx==fy)  ok=true;
 82             else f[fx]=fy;
 83         }
 84         cnt=0;
 85         memset(d,0,sizeof(d));
 86         memset(head,-1,sizeof(head));
 87         for(int i=1; i<=M2; i++)
 88         {
 89             scanf("%d%d",&x,&y);
 90             int tx=find(x),ty=find(y);
 91             addedge(tx,ty);
 92         }
 93         if(ok)
 94         {
 95             printf("YES
");
 96         }
 97         else
 98             topsort();
 99 
100     }
101 
102     return 0;
103 }

View Code

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的那个）。本题数据小懒得用了= =

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 #define LL long long
 6 
 7 LL  p[1010];             //array
 8 int L[1010],R[1010];     //Li,Ri
 9 LL  A[1010];             //Ansi
10 int T,N,Q;
11 
12 LL gcd(LL a,LL b)                  //辗转相除法，返回gcd(a,b)
13 {
14     if (b==0) return a;
15     return gcd(b,a%b);
16 }
17 
18 LL lcm(LL a,LL b)
19 {
20     LL t=gcd(a,b);
21     t=a*b/t;
22     return t;
23 }
24 
25 LL ggcd(int l,int r)
26 {
27     LL aa=p[l];
28     for(int i=l+1;i<=r;i++)
29         aa=gcd(aa,p[i]);
30     return aa;
31 }
32 
33 LL llcm(int l,int r)
34 {
35     LL aa=p[l];
36     for(int i=l+1;i<=r;i++)
37         aa=lcm(aa,p[i]);
38     return aa;
39 }
40 
41 int main()
42 {
43     scanf("%d",&T);
44     while(T--)
45     {
46         scanf("%d%d",&N,&Q);
47         for(int i=0;i<=1000;i++)p[i]=1;
48         for(int i=1;i<=Q;i++)
49         {
50             scanf("%d%d%I64d",&L[i],&R[i],&A[i]);
51             //LL t=llcm(L[i],R[i]);
52             //t=lcm(t,A[i]);
53             for(int j=L[i];j<=R[i];j++)
54                 p[j]=lcm(p[j],A[i]);
55                 //p[j]=t;
56         }
57         bool ok=true;
58         for (int i=1;i<=Q;i++)
59         {
60             LL t=ggcd(L[i],R[i]);
61         //    printf("%d,%d = %I64d
",L[i],R[i],t);
62             if (t!=A[i])    ok=false;
63         }
64         //            for(int i=1;i<=N;i++)
65         //                printf("%d ",p[i]);
66         //            printf("
");
67         if(ok)
68         {
69             for(int i=1;i<N;i++)
70                 printf("%I64d ",p[i]);
71             printf("%I64d
",p[N]);
72         }
73         else
74             printf("Stupid BrotherK!
");
75     }
76     return 0;
77 }

View Code