NOIP2013提高组解题报告

1 #include
2 #include
3 #include
4 using namespace std;
5 int n,m,k,x,ans&＃61;1;
6 long long power(long long x,long long y)
7 {
8 if(y&＃61;&＃61;0)return 1;
9 if(y&＃61;&＃61;1)return x%n;
10 long long m&＃61;y/2,ans;
11 bool r&＃61;y%2;
12 ans&＃61;power(x,y/2);
13 if(r)return ((ans*ans)%n*x)%n;
14 else return (ans*ans)%n;
15 }
16 int main()
17 {
18 freopen("circle.in","r",stdin);
19 freopen("circle.out","w",stdout);
20 cin>>n>>m>>k>>x;
21 ans&＃61;(power(10%n,k)*m&＃43;x%n)%n;
22 cout<<ans;
23 fclose(stdin);fclose(stdout);
24 return 0;
25 }

1 #include
2 #include
3 #include
4 using namespace std;
5 const int mod&＃61;99999997;
6 struct node{
7 int num,id;
8 }a[100001],b[100001];
9 int n,ans;
10 int num[100001],tmp[100001];
11 inline int qread()
12 {
13 int x&＃61;0,j&＃61;1;
14 char ch&＃61;getchar();
15 while(ch<&＃39;0&＃39; || ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)j&＃61;-1;ch&＃61;getchar();}
16 while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}
17 return x*j;
18 }
19 inline void merge_array(int l,int r)
20 {
21 int m&＃61;(l&＃43;r)>>1,i&＃61;l,cnt&＃61;0;
22 int m2&＃61;m&＃43;1;
23 while(i<&＃61;m && m2<&＃61;r)
24 {
25 if(num[i]<&＃61;num[m2])
26 tmp[cnt&＃43;&＃43;]&＃61;num[i&＃43;&＃43;];
27 else
28 {
29 ans&＃43;&＃61;m-i&＃43;1;
30 ans%&＃61;mod;
31 tmp[cnt&＃43;&＃43;]&＃61;num[m2&＃43;&＃43;];
32 }
33 }
34 while(i<&＃61;m)
35 tmp[cnt&＃43;&＃43;]&＃61;num[i&＃43;&＃43;];
36 while(m2<&＃61;r)
37 tmp[cnt&＃43;&＃43;]&＃61;num[m2&＃43;&＃43;];
38 for(int i&＃61;0;i)
39 num[l&＃43;i]&＃61;tmp[i];
40 }
41 void merge_sort(int l,int r)
42 {
43 if(l<r)
44 {
45 int m&＃61;(l&＃43;r)>>1;
46 merge_sort(l,m);
47 merge_sort(m&＃43;1,r);
48 merge_array(l,r);
49 }
50 }
51 bool cmp(const node &a,const node &b)
52 {
53 return a.num<b.num;
54 }
55 int main()
56 {
57 // freopen("match.in","r",stdin);
58 // freopen("match.out","w",stdout);
59 scanf("%d",&n);
60 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
61 {
62 a[i].num&＃61;qread();
63 a[i].id&＃61;i;
64 }
65 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
66 {
67 b[i].num&＃61;qread();
68 b[i].id&＃61;i;
69 }
70 sort(a&＃43;1,a&＃43;n&＃43;1,cmp);
71 sort(b&＃43;1,b&＃43;n&＃43;1,cmp);
72 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
73 num[a[i].id]&＃61;b[i].id;
74 merge_sort(1,n);
75 printf("%d\n",ans);
76 // fclose(stdin);fclose(stdout);
77 return 0;
78 }

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 const int N&＃61;1e4&＃43;7;
7 struct Road{
8 int u,v,w;
9 }road[N*5];
10 struct node{
11 int v,w,nxt;
12 }e[N*2];
13 int n,m,Q,Enum;
14 int fat[N],head[N],f[N][22],dis[N][22],deep[N];
15 bool vis[N];
16 int qread()
17 {
18 int x&＃61;0,j&＃61;1;
19 char ch&＃61;getchar();
20 while(ch<&＃39;0&＃39; || ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)j&＃61;-1;ch&＃61;getchar();}
21 while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}
22 return x*j;
23 }
24 void Insert(int u,int v,int w)
25 {
26 e[&＃43;&＃43;Enum].v&＃61;v;
27 e[Enum].w&＃61;w;
28 e[Enum].nxt&＃61;head[u];
29 head[u]&＃61;Enum;
30 }
31 int find(int x)
32 {
33 if(fat[x]!&＃61;x)fat[x]&＃61;find(fat[x]);
34 return fat[x];
35 }
36 bool cmp(const Road &a,const Road &b)
37 {
38 return a.w>b.w;
39 }
40 void build(int x)
41 {
42 vis[x]&＃61;1;
43 for(int i&＃61;head[x];i;i&＃61;e[i].nxt)
44 {
45 int v&＃61;e[i].v;
46 if(vis[v])continue;
47 f[v][0]&＃61;x;
48 dis[v][0]&＃61;e[i].w;
49 deep[v]&＃61;deep[x]&＃43;1;
50 build(v);
51 }
52 }
53 void find_father()
54 {
55 for(int j&＃61;1;j<&＃61;21;j&＃43;&＃43;)
56 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
57 {
58 f[i][j]&＃61;f[f[i][j-1]][j-1];
59 dis[i][j]&＃61;min(dis[f[i][j-1]][j-1],dis[i][j-1]);
60 }
61 }
62 int Lca(int a,int b)
63 {
64 if(deep[a]<deep[b])swap(a,b);
65 int tmp&＃61;deep[a]-deep[b];
66 for(int i&＃61;0;i<&＃61;21;i&＃43;&＃43;)
67 if(tmp&(1<<i))
68 a&＃61;f[a][i];
69 if(a&＃61;&＃61;b)return a;
70 for(int i&＃61;21;i>&＃61;0;i--)
71 if(f[a][i]!&＃61;f[b][i])
72 {
73 a&＃61;f[a][i];
74 b&＃61;f[b][i];
75 }
76 return f[a][0];
77 }
78 int query(int a,int b)//查询树上两点间的距离
79 {
80 int ans&＃61;0x3f3f3f3f;
81 int tmp&＃61;deep[a]-deep[b];
82 for(int i&＃61;0;i<&＃61;21;i&＃43;&＃43;)
83 if(tmp&(1<<i))
84 {
85 ans&＃61;min(ans,dis[a][i]);
86 a&＃61;f[a][i];
87 }
88 return ans;
89 }
90 int main()
91 {
92 // freopen("truck.in","r",stdin);
93 // freopen("truct.out","w",stdout);
94 scanf("%d%d",&n,&m);
95 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)
96 {
97 road[i].u&＃61;qread();
98 road[i].v&＃61;qread();
99 road[i].w&＃61;qread();
100 }
101 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
102 fat[i]&＃61;i;
103 sort(road&＃43;1,road&＃43;m&＃43;1,cmp);
104 for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;)//最大生成树
105 {
106 int r1&＃61;find(road[i].u);
107 int r2&＃61;find(road[i].v);
108 if(r1!&＃61;r2)
109 {
110 fat[r2]&＃61;r1;
111 Insert(road[i].u,road[i].v,road[i].w);
112 Insert(road[i].v,road[i].u,road[i].w);
113 }
114 }
115 memset(dis,0x3f,sizeof(dis));
116 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
117 if(!vis[i])
118 build(i);
119 find_father();
120 scanf("%d",&Q);
121 int u,v;
122 while(Q--)
123 {
124 u&＃61;qread();v&＃61;qread();
125 if(find(u)!&＃61;find(v))
126 printf("-1\n");
127 else
128 {
129 int lca&＃61;Lca(u,v);
130 printf("%d\n",min(query(u,lca),query(v,lca)));
131 }
132 }
133 // fclose(stdin);fclose(stdout);
134 return 0;
135 }

1 #include
2 #include
3 using namespace std;
4 int n,h[100500],ans;
5 int main()
6 {
7 cin>>n;
8 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
9 cin>>h[i];
10 ans&＃61;h[1];
11 for(int i&＃61;1;i)
12 if(h[i]1])
13 ans&＃43;&＃61;h[i&＃43;1]-h[i];
14 cout<<ans;
15 return 0;
16 }

1 #include
2 #include
3 using namespace std;
4 int n,m,ans,now,last,tmp;
5 int h[100001];
6 inline int qread()
7 {
8 int x&＃61;0,j&＃61;1;
9 char ch&＃61;getchar();
10 while(ch<&＃39;0&＃39; || ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)j&＃61;-1;ch&＃61;getchar();}
11 while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}
12 return x*j;
13 }
14 int main()
15 {
16 scanf("%d",&n);
17 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
18 h[i]&＃61;qread();
19 last&＃61;h[1];
20 for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
21 {
22 now&＃61;h[i];
23 if(now!&＃61;last)
24 if(!tmp || (tmp>0 && now0 && now>last))
25 //除了第二个以外仅当上升(下降)序列变为下降(上升)序列才会多一株
26 {
27 ans&＃43;&＃43;;
28 tmp&＃61;now-last;
29 }
30 last&＃61;now;
31 }
32 printf("%d\n",ans&＃43;1);
33 return 0;
34 }

1 /*
2 对于一个指定块和一个空白块&＃xff0c;有四种不同有效状态: 空白块在指定块的上下左右
3 对于每一个有效状态有4种后继状态&＃xff1a;另外三个方向的状态、交换空白块和有效块
4 将有用状态与后继状态连边构图&＃xff0c;边权为由有用状态到后继状态所需的最小步数
5 算出空白块移到指定块四周的步数
6 将算出的结果作为初始值&＃xff0c;再在图中跑最短路
7 */
8 #include
9 #include
10 #include
11 #include
12 using namespace std;
13 const int dx[4]&＃61;{-1,0,1,0},dy[4]&＃61;{0,1,0,-1};
14 struct Point{
15 int x,y;
16 }nxt,cnt;
17 struct node{
18 int v,w,nxt;
19 }e[3601*5];
20 int n,m,Q,Enum;
21 int pre_dis[31][31],dis[3601],head[3601];
22 //pre_dis表示空白块与指定块的一个有效状态&＃xff0c;到另外三个有效状态的最小距离
23 bool a[31][31],vis[3601];
24 queueq;
25 queue<int>k;
26 void Insert(int u,int v,int w)
27 {
28 e[&＃43;&＃43;Enum].v&＃61;v;
29 e[Enum].w&＃61;w;
30 e[Enum].nxt&＃61;head[u];
31 head[u]&＃61;Enum;
32 }
33 int turn(int i,int j)
34 {
35 return (i-1)*m&＃43;j-1<<2;
36 }
37 void bfs(int ex,int ey,int px,int py,int d)
38 //空白块移动到其他块的最小距离
39 {
40 memset(pre_dis,-1,sizeof(pre_dis));
41 pre_dis[px][py]&＃61;1;//指定块
42 pre_dis[ex][ey]&＃61;0;//空白块
43 cnt.x&＃61;ex;cnt.y&＃61;ey;
44 q.push(cnt);
45 while(!q.empty())
46 {
47 cnt&＃61;q.front();
48 q.pop();
49 for(int i&＃61;0;i<&＃61;3;i&＃43;&＃43;)
50 {
51 nxt.x&＃61;cnt.x&＃43;dx[i];nxt.y&＃61;cnt.y&＃43;dy[i];
52 if(a[nxt.x][nxt.y] && pre_dis[nxt.x][nxt.y]&＃61;&＃61;-1)
53 {
54 pre_dis[nxt.x][nxt.y]&＃61;pre_dis[cnt.x][cnt.y]&＃43;1;
55 q.push(nxt);
56 }
57 }
58 }
59 if(d&＃61;&＃61;4)return;
60 int tmp&＃61;turn(px,py);
61 for(int i&＃61;0;i<&＃61;3;i&＃43;&＃43;)
62 if(pre_dis[px&＃43;dx[i]][py&＃43;dy[i]]>0)//当前有效状态与后继状态连边
63 Insert(tmp&＃43;d,tmp&＃43;i,pre_dis[px&＃43;dx[i]][py&＃43;dy[i]]);
64 Insert(tmp&＃43;d,turn(ex,ey)&＃43;(d&＃43;2)%4,1);//空白块与指定块交换
65 }
66 void SPFA(int sx,int sy)
67 {
68 memset(dis,-1,sizeof(dis));
69 for(int i&＃61;0;i<&＃61;3;i&＃43;&＃43;)
70 if(pre_dis[sx&＃43;dx[i]][sy&＃43;dy[i]]!&＃61;-1)
71 {
72 int tmp&＃61;turn(sx,sy)&＃43;i;
73 dis[tmp]&＃61;pre_dis[sx&＃43;dx[i]][sy&＃43;dy[i]];
74 k.push(tmp);
75 }
76 while(!k.empty())
77 {
78 int u&＃61;k.front();
79 k.pop();
80 vis[u]&＃61;0;
81 for(int i&＃61;head[u];i;i&＃61;e[i].nxt)
82 {
83 int v&＃61;e[i].v;
84 if(dis[v]&＃61;&＃61;-1 || dis[v]>dis[u]&＃43;e[i].w)
85 {
86 dis[v]&＃61;dis[u]&＃43;e[i].w;
87 if(!vis[v])
88 {
89 vis[v]&＃61;1;
90 k.push(v);
91 }
92 }
93 }
94 }
95 }
96 int main()
97 {
98 scanf("%d%d%d",&n,&m,&Q);
99 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
100 for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)
101 scanf("%d",&a[i][j]);
102 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
103 for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;)
104 if(a[i][j])
105 {
106 if(a[i-1][j])bfs(i-1,j,i,j,0);
107 if(a[i][j&＃43;1])bfs(i,j&＃43;1,i,j,1);
108 if(a[i&＃43;1][j])bfs(i&＃43;1,j,i,j,2);
109 if(a[i][j-1])bfs(i,j-1,i,j,3);
110 }
111 int ex,ey,sx,sy,tx,ty,ans;
112 while(Q--)
113 {
114 ans&＃61;0x3f3f3f3f;
115 scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
116 if(sx&＃61;&＃61;tx && sy&＃61;&＃61;ty)
117 {
118 printf("0\n");
119 continue;
120 }
121 bfs(ex,ey,sx,sy,4);
122 SPFA(sx,sy);
123 int tmp&＃61;turn(tx,ty);
124 for(int i&＃61;0;i<&＃61;3;i&＃43;&＃43;)
125 if(dis[tmp&＃43;i]!&＃61;-1)
126 ans&＃61;min(ans,dis[tmp&＃43;i]);
127 if(ans&＃61;&＃61;0x3f3f3f3f)
128 ans&＃61;-1;
129 printf("%d\n",ans);
130 }
131 return 0;
132 }