比赛-NOIP2015 普及组复赛 (Nov, 2016)

先贴上代码，迟一些会附上文字讲解。

 1 #include <cstdio>
 2 int k, ans;
 3 
 4 int main()
 5 {
 6     freopen("coin.in", "r", stdin);
 7     freopen("coin.out", "w", stdout);
 8     
 9     int day = 0, i = 0;
10     scanf("%d", &k);
11     do {
12         if ((day += ++i) > k) {
13             ans -= (day - k - i) * i;
14             break;
15         }
16         ans += i * i;
17     } while (true);
18     
19     printf("%d
", ans);
20     
21     fclose(stdin);
22     fclose(stdout);
23     
24     return 0;
25 }

coin

 1 #include <cstdio>
 2 
 3 const int MAX_N = 105, MAX_M = 105;
 4 
 5 int n, m;
 6 int nxt[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, 
 7                 {-1, 1}, {-1, -1}, {1, 1}, {1, -1}};
 8 bool G[MAX_N][MAX_M];
 9 
10 void input()
11 {
12     int i, j;
13     char tt;
14     scanf("%d%d", &n, &m);
15     for (i = 1; i <= n; ++i)
16         for (j = 1; j <= m; ++j) {
17             while ((tt = getchar()) == '
' || tt == ' ');
18             G[i][j] = tt == '*';
19         }
20     return ;
21 }
22 
23 void solve()
24 {
25     int i, j, k, ans;
26     for (i = 1; i <= n; ++i) {
27         for (j = 1; j <= m; ++j) {
28             if (G[i][j]) {
29                 putchar('*');
30                 continue;
31             }
32             ans = 0;
33             for (k = 0; k < 8; ++k)
34                 ans += G[i + nxt[k][0]][j + nxt[k][1]];
35             printf("%d", ans);
36         }
37         putchar('
');
38     }
39     return ;
40 }
41 
42 int main()
43 {
44     freopen("mine.in", "r", stdin);
45     freopen("mine.out", "w", stdout);
46     
47     input();
48     solve();
49     
50     fclose(stdin);
51     fclose(stdout);
52     return 0;
53 }

mine

 1 #include <cstdio>
 2 
 3 const int MAX_NM = 100005, MOD = 10007;
 4 
 5 int n, m, ans;
 6 int N[MAX_NM], C[MAX_NM];
 7 int k[2][MAX_NM], sum[2][MAX_NM];
 8 
 9 inline void getnum(int &num)
10 {
11     char tt;
12     bool flag = false;
13     while (((tt = getchar()) < '0' || tt > '9') && tt != '-');
14     if (tt == '-') {
15         flag = true;
16         num = 0;
17     }
18     else {
19         num = tt - '0';
20     }
21     while ((tt = getchar()) >= '0' && tt <= '9')
22         num = num * 10 + tt - '0';
23     if (flag)
24         num = -num;
25     return ;
26 }
27 
28 inline void add_mod(int &a, int b)
29 {
30     a = (a + b % MOD) % MOD;
31     return ;
32 }
33 
34 int main()
35 {
36     freopen("sum.in", "r", stdin);
37     freopen("sum.out", "w", stdout);
38     
39     int i, tmp;
40     getnum(n);
41     getnum(m);
42     for (i = 1; i <= n; ++i) {
43         getnum(N[i]);
44         N[i] %= MOD;
45     }
46     for (i = 1; i <= n; ++i) {
47         getnum(C[i]);
48         add_mod(k[i & 1][C[i]], 1);
49         add_mod(sum[i & 1][C[i]], N[i]);
50     }
51     for (i = 1; i <= n; ++i)
52         add_mod(ans, i % MOD * (N[i] * (k[i & 1][C[i]] - 2) % MOD + sum[i & 1][C[i]]) % MOD);
53     
54     printf("%d
", ans);
55     
56     fclose(stdin);
57     fclose(stdout);
58     
59     return 0;
60 }

sum

  1 #include <cstdio>
  2 #include <algorithm>
  3 using namespace std;
  4 
  5 const int MAX_N = 100005;
  6 
  7 int n, ans, top_l;
  8 int S[MAX_N], A[MAX_N];
  9 int l[MAX_N];//max heap
 10 char s[25];
 11 
 12 struct house {
 13     int num;
 14     int w;
 15 } W[MAX_N];
 16 
 17 
 18 inline void getnum(int &num)
 19 {
 20     char tt;
 21     bool flag = false;
 22     while (((tt = getchar()) < '0' || tt > '9') && tt != '-');
 23     if (tt == '-') {
 24         flag = true;
 25         num = 0;
 26     }
 27     else {
 28         num = tt - '0';
 29     }
 30     while ((tt = getchar()) >= '0' && tt <= '9')
 31         num = num * 10 + tt - '0';
 32     if (flag)
 33         num = -num;
 34     return ;
 35 }
 36 
 37 void putnum(int num)
 38 {
 39     int top = 0;
 40     if (num < 0) {
 41         putchar('-');
 42         num = -num;
 43     }
 44     do
 45         s[++top] = num % 10 + '0';
 46     while (num /= 10);
 47     while (top)
 48         putchar(s[top--]);
 49     putchar('
');
 50     return ;
 51 }
 52 
 53 bool my_cmp(struct house a, struct house b)
 54 {
 55     return a.w > b.w;
 56 }
 57 
 58 void shift_up(int k, int *heap, int top)
 59 {
 60     int dad = k >> 1, tmp = heap[k];
 61     while (dad >= 1) {
 62         if (tmp > heap[dad]) {
 63             heap[k] = heap[dad];
 64             k = dad;
 65             dad >>= 1;
 66         } else {
 67             break;
 68         }
 69     }
 70     heap[k] = tmp;
 71     return ;
 72 }
 73 
 74 void shift_dn(int k, int *heap, int top)
 75 {
 76     int son = k << 1, tmp = heap[k];
 77     while (son <= top) {
 78         if (son < top && heap[son] < heap[son + 1])
 79             ++son;
 80         if (tmp < heap[son]) {
 81             heap[k] = heap[son];
 82             k = son;
 83             son <<= 1;
 84         } else {
 85             break;
 86         }
 87     }
 88     heap[k] = tmp;
 89     return ;
 90 }
 91 
 92 int main()
 93 {
 94     freopen("salesman.in", "r", stdin);
 95     freopen("salesman.out", "w", stdout);
 96     
 97     
 98     int i, x, dis = 0, p = 1;
 99     bool flag = false;
100     
101     getnum(n);
102     for (i = 1; i <= n; ++i)
103         getnum(S[i]);
104     for (i = 1; i <= n; ++i) {
105         getnum(A[i]);
106         W[i].w = A[i] + (S[i] << 1);
107         W[i].num = i;
108     }
109     
110     sort(W + 1, W + n + 1, my_cmp);
111     
112     for (x = 1; x <= n; ++x) {
113         int tmp;
114         if (p > n || (top_l && l[1] > W[p].w - (S[dis] << 1))) {
115             ans += l[1];
116             l[1] = l[top_l];
117             shift_dn(1, l, --top_l);
118         } else {
119             ans += W[p].w - (S[dis] << 1);
120             dis = W[p].num;
121             while (++p <= n && S[W[p].num] < S[dis]) {
122                 l[++top_l] = A[W[p].num];
123                 shift_up(top_l, l, top_l);
124             }
125         }
126         putnum(ans);
127     }
128     
129     fclose(stdin);
130     fclose(stdout);
131     return 0;
132 }

salesman