NOIP2013 题解

转圈游戏

　　题解：快速幂

 1 #include <cstdio>
 2 
 3 int n, m, k, x;
 4 
 5 inline long long QuickPow(int a, int k, int MOD){
 6     long long base = a, ret = 1;
 7     while (k){
 8         if (k&1) ret = (ret*base)%MOD;
 9         base = (base*base)%MOD, k >>= 1;
10     }
11     return ret;
12 }
13 
14 int main(){
15     scanf("%d %d %d %d", &n, &m, &k, &x);
16     printf("%lld
", (x%n+(m%n)*QuickPow(10, k, n)%n)%n);
17 }

circle.cpp

火柴排队

　　题解：求逆序对(因为写不来归排就写的树状数组，怕TLE就蛋疼的加了一个读入优化)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXN =  100000+10;
 7 const int MOD = 99999997;
 8 
 9 int n, ans, c[MAXN], d[MAXN];
10 char cc;
11 
12 struct Match{
13     int v, n;
14 
15     friend bool operator < (const Match& A, const Match& B){
16         return A.v<B.v;
17     }
18 }a[MAXN], b[MAXN];
19 
20 inline void add(int p, int v){
21     while (p<=n)
22         d[p] += v, p += (p&(-p));
23 }
24 
25 inline int sum(int p){
26     int ret = 0;
27     while (p>0)
28         ret += d[p], p -= (p&(-p));
29     return ret;
30 }
31 
32 inline int NextInt(){
33     int ret = 0;
34     do cc = getchar();
35     while (cc<48 || cc>57);
36     do ret *= 10, ret += (cc-48), cc = getchar();
37     while (48<=cc && cc<=57);
38     return ret;
39 }
40 
41 int main(){
42     memset(d, 0, sizeof(0));
43     n = NextInt(), ans = 0;
44     for (int i=0; i<n; i++)
45         a[i].v = NextInt(), a[i].n = i+1;
46     sort(a, a+n);
47     for (int i=0; i<n; i++)
48         b[i].v = NextInt(), b[i].n = i+1;
49     sort(b, b+n);
50     
51     for (int i=0; i<n; i++)
52         c[a[i].n] = b[i].n;
53     
54     for (int i=1; i<=n; i++)
55         add(c[i], 1), 
56         ans = (ans+i-sum(c[i]))%MOD;
57     printf("%d
", ans);
58 }

match.cpp

货车运输

　　题解：先建一个最大生成树，再用lca乱搞一下就好了

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 const int MAXL = 20;
  7 const int MAXN = 10000+10;
  8 const int MAXM = 50000+10;
  9 const int INF = 0x3f3f3f3f;
 10 
 11 int n, m, f[MAXN], nimo[MAXN][MAXL], an[MAXN][MAXL], dep[MAXN];
 12 bool vis[MAXN];
 13 char c;
 14 
 15 struct Edge{
 16     int d, to;
 17     Edge *next;
 18 }e[MAXM], *head[MAXN];
 19 
 20 struct Bary{
 21     int u, v, d;
 22 
 23     friend bool operator < (const Bary& A, const Bary& B){
 24         return A.d>B.d;
 25     }
 26 }bd[MAXM];
 27 
 28 inline int NextInt(){
 29     int ret = 0;
 30     do c = getchar();
 31     while (c<48 || c>57);
 32     do ret *= 10, ret += (c-48), c = getchar();
 33     while (48<=c && c<=57);
 34     return ret;
 35 }
 36 
 37 inline int find(int x){
 38     return x==f[x] ? x : f[x]=find(f[x]);
 39 }
 40 
 41 int ne = 0;
 42 inline void AddEdge(int f, int t, int d){
 43     e[ne].to = t, e[ne].d = d;
 44     e[ne].next = head[f];
 45     head[f] = e + ne++;
 46 }
 47 
 48 inline void Add(int u, int v, int d){
 49     f[find(u)] = find(v); 
 50     AddEdge(u, v, d), AddEdge(v, u, d);
 51 }
 52 
 53 inline void BuildTree(int x){
 54     vis[x] = true;
 55     for (Edge *p=head[x]; p; p=p->next)
 56         if (!vis[p->to])
 57             an[p->to][0] = x, nimo[p->to][0] = p->d, dep[p->to] = dep[x]+1, BuildTree(p->to);
 58 }
 59 
 60 inline int swim(int &x, int ht){
 61     int ret = INF;
 62     for (int i=MAXL-1; i>=0; i--)
 63         if (dep[an[x][i]]>=ht) ret = min(ret, nimo[x][i]), x = an[x][i];
 64     return ret;
 65 }
 66 
 67 inline int lca(int x, int y){
 68     int ret = INF;
 69     if (dep[x]^dep[y]) ret = dep[x]>dep[y] ? swim(x, dep[y]) : swim(y, dep[x]);
 70     if (x==y) return ret;
 71     for (int i=MAXL-1; i>=0; i--)
 72         if (an[x][i]^an[y][i])
 73             ret = min(ret, min(nimo[x][i], nimo[y][i])),
 74             x = an[x][i], y = an[y][i];
 75     return min(ret, min(nimo[x][0], nimo[y][0]));
 76 }
 77 
 78 int main(){
 79     memset(vis, false, sizeof(vis));
 80     memset(an, 0, sizeof(an));
 81 
 82     n = NextInt(), m = NextInt();
 83     for (int i=1; i<=n; i++)
 84         f[i] = i;
 85     for (int i=0; i<m; i++)
 86         bd[i].v = NextInt(), bd[i].u = NextInt(), bd[i].d = NextInt();
 87     
 88     sort(bd, bd+m);
 89     for (int i=0; i<m; i++)
 90         if (find(bd[i].u)^find(bd[i].v)) Add(bd[i].u, bd[i].v, bd[i].d);
 91     for (int i=1; i<=n; i++)
 92         if (!vis[i]) dep[i] = 0, BuildTree(i), nimo[i][0] = INF, an[i][0] = i;
 93 
 94     for (int i=1; i<MAXL; i++)
 95         for (int j=1; j<=n; j++)
 96             an[j][i] = an[an[j][i-1]][i-1],
 97             nimo[j][i] = min(nimo[j][i-1], nimo[an[j][i-1]][i-1]);
 98     
 99     int Q, a, b;
100     scanf("%d", &Q);
101     while (Q--)
102         scanf("%d %d", &a, &b),
103         printf("%d
", find(a)==find(b) ? lca(a, b) : -1);
104 }

truck.cpp

积木大赛：

　　题解：模拟，ans = ∑max{0, a[i]-a[i-1]}

 1 #include <cstdio>
 2 
 3 int num, h[100010];
 4 
 5 int max(int a,int b){
 6     return a>b ? a : b;
 7 }
 8 
 9 int main(){
10     scanf("%d",&num);
11     for (int i=0; i<num; i++)
12         scanf("%d", &h[i]);
13     
14     long long ans = 0;
15     for (int i=0; i<num; i++)
16         ans += max(0, h[i]-h[i-1]);
17     printf("%lld",ans);
18 }

block.cpp

花匠：

　　题解：贪心，缩点，把满足的连这的一群点缩为一个

 1 #include <cstdio>
 2 const int MAXN = 1e6+10;
 3 
 4 int n, Pri, cj, a[MAXN];
 5 
 6 int main(){
 7     scanf("%d", &n), Pri = 1, cj = 1221;
 8     for (int i=0; i<n; i++)
 9         scanf("%d", a+i);
10     for (int i=1; i<n; i++){
11         if (a[i]>a[i-1] && cj!=1) cj = 1, Pri ++;
12         if (a[i]<a[i-1] && cj!=0) cj = 0, Pri ++;
13     }
14     printf("%d", Pri);
15 }

flower.cpp