NOIP 2013 提高组 Day1

题目：http://wenku.baidu.com/link?url=WgP-2UcEJy53ShbZC3gQVHZTXrHbgg14COe3HE9ybEfI82sr8nMvc-FobNBS9WwQxCEiCtb3TdETK-ZD3i3F1lMOqq3-J1cfkTrfhrbXLJe

1.转圈游戏

[快速幂]

　　注意：二分时记得保存值，不可重复运算；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 int n,m,k,x;
 8 int ans;
 9 int PM(int a, int b, int c)
10 {
11     int ans=1;
12     a=a%c;
13     while(b>0)
14     {
15         if(b%2==1)
16         ans=(ans*a)%c;
17         b= b/2;
18         a=(a*a)%c;
19     }
20     return ans;
21 }
22 int main()
23 {
24     freopen("circle.in","r",stdin);
25     freopen("circle.out","w",stdout);
26     cin>>n>>m>>k>>x;
27     ans=PM(10,k,n);
28     cout<<(x+ans*m)%n;
29     return 0;
30 }

2.火柴排队

[归并排序][逆序对]

　　提示：还可以用树状数组和线段树；

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 int  ans;
 8 struct poin{
 9     int num;
10     int s;
11 }q[100005];
12 poin w[100005];
13 int com(const poin &a,const poin &b)
14 {
15     if(a.s<b.s)return 1;
16     return 0;
17 }
18 int n;
19 int a[100005],r[100005];
20 void mergesort(int s,int t)
21 {
22     if(s==t)return ;
23     int m=(s+t)>>1;
24     mergesort(s,m);
25     mergesort(m+1,t);
26     int i=s;
27     int j=m+1;
28     int k=s;
29     while(i<=m&&j<=t)
30     {
31         if(a[i]<=a[j])
32         {
33             r[k++]=a[i++];
34         }
35         else
36         {
37             ans=(ans+m-i+1)%99999997;
38             r[k++]=a[j++]; 
39         }
40     }
41     while(i<=m)
42         r[k++]=a[i++];
43     while(j<=t)
44         r[k++]=a[j++];
45     for(int i=s;i<=t;i++)
46         a[i]=r[i];
47 }
48 int main()
49 {
50     freopen("match.in","r",stdin);
51     freopen("match.out","w",stdout);
52     cin>>n;
53     for(int i=1;i<=n;i++)
54     {
55         scanf("%d",&q[i].s);
56         q[i].num=i;
57     }
58     for(int j=1;j<=n;j++)
59     {
60         scanf("%d",&w[j].s);
61         w[j].num=j;
62     }
63     sort(q+1,q+1+n,com);
64     sort(w+1,w+1+n,com);
65     for(int i=1;i<=n;i++)
66     a[w[i].num]=q[i].num;
67     mergesort(1,n);
68     cout<<ans;
69     return 0;
70 }

3.货车运输

[不会][60分][并查集]

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 int father[10001];
 6 int n,q,tot,m;
 7 struct xx{
 8     int x,y,w;
 9 }bian[50005];
10 int find(int x)//
11 {
12     if(father[x]!=x) father[x]=find(father[x]);
13     return father[x];
14 }
15 void unionn(int a,int b)//
16 {
17     int fa=find(a);
18     int fb=find(b);
19     if(fa!=fb) father[fa]=fb;
20 }
21 bool cmp(const xx a,const xx b)
22 {     
23     return b.w<a.w;
24 }
25 int main()
26 {
27     freopen("truck.in","r",stdin);
28     freopen("truck.out","w",stdout);
29     cin>>n>>m;    
30     for(int i=1;i<=m;i++)
31     {
32         int x,y,z;
33         scanf("%d %d %d",&x,&y,&z);
34         bian[i].x=x,bian[i].y=y,bian[i].w=z;
35     }
36     sort(bian+1,bian+m+1,cmp);
37     cin>>q;
38     for(int i=1;i<=q;i++)
39     {int x,y,minn=1e6,k=1;
40         for(int i=1;i<=n;i++)father[i]=i;
41         scanf("%d %d",&x,&y);
42         for(int i=1;i<=m;i++)
43         {
44             if(find(x)==find(y)){
45                 printf("%d
",minn);
46                 break;
47             }
48             else if(find(bian[i].x)!=find(bian[i].y))
49             {
50                 unionn(bian[i].x,bian[i].y);
51                 if(bian[i].w<minn)
52                 minn=bian[i].w;
53             }
54         }
55         if(find(x)!=find(y)) printf("-1
");
56     }
57     return 0;
58 }