1 #include <cstdio> 2 #include <cstring> 3  4 #define R register 5 typedef long long ll; 6 struct Data { 7     ll num[10]; 8     inline void clear() 9     {10         memset(num, 0, 10 << 3);11     }12     inline Data operator + (const Data &that) const13     {14         R Data ret; memcpy(ret.num, num, 10 << 3);15         for (R int i = 1; i <= 9; ++i) ret.num[i] += that.num[i];16         return ret;17     }18     inline void operator += (const Data &that)19     {20         for (R int i = 1; i <= 9; ++i) num[i] += that.num[i];21     }22     inline Data operator - (const Data &that) const23     {24         R Data ret; memcpy(ret.num, num, 10 << 3);25         for (R int i = 1; i <= 9; ++i) ret.num[i] -= that.num[i];26         return ret;27     }28     inline void operator *= (const int &that)29     {30         for (R int i = 1; i <= 9; ++i) num[i] *= that;31     }32 } ;33 inline Data calc2(R int N)34 {35     R ll tmp; R Data ret; ret.clear();36     for (tmp = 10; tmp - 1 <= N; tmp *= 10)37         for (R int i = 1; i <= 9; ++i)38             ret.num[i] += tmp / 10;39     tmp /= 10;40     for (R int i = 1; i < (N / tmp); ++i) ret.num[i] += tmp;41     ret.num[N / tmp] += N % tmp + 1;42 //    printf("calc2(%d) = \n", N);43 //    for (R int i = 1; i <= 9; ++i) printf("%lld\n", ret.num[i]);44     return ret;45 }46 inline Data calc(R int N)47 {48     R Data ret; ret.clear();49     for (R int i = 1, j; i <= N; i = j + 1)50     {51         j = N / (N / i);52         R Data tmp = calc2(j) - calc2(i - 1);53         tmp *= N / i;54         ret += tmp;55     }56     return ret;57 }58 int main()59 {60     R int l, r; scanf("%d%d", &l, &r);61     R Data ans = calc(r) - calc(l - 1);62     for (R int i = 1; i <= 9; ++i)63         printf("%lld\n", ans.num[i]);64     return 0;65 }

 1 #include <cstdio> 2 #include <cstdlib> 3  4 #define R register 5 #define maxn 100010 6 struct Edge { 7     Edge *next; 8     int to; 9 } *last[maxn], e[maxn << 1], *ecnt = e;10 inline void link(R int a, R int b)11 {12     *++ecnt = (Edge) {last[a], b}; last[a] = ecnt;13 }14 int q[maxn], n, a[maxn], b[maxn];15 bool arv[maxn], ins[maxn];16 char st[maxn];17 void dfs(R int x, R int step)18 {19     if (!arv[x]) return ;20     if (x == n)21     {22         for (R int i = 1; i < step; ++i) printf("%c", st[i]); puts("");23         exit(0);24     }25     if (ins[x])26     {27         puts("Infinity!");28         exit(0);29     }30     ins[x] = 1;31     if (x + a[x] > 0 && x + a[x] <= n)32     {33         st[step] = ‘a‘;34         dfs(x + a[x], step + 1);35     }36     if (x + b[x] > 0 && x + b[x] <= n)37     {38         st[step] = ‘b‘;39         dfs(x + b[x], step + 1);40     }41 }42 int main()43 {44     scanf("%d", &n);45     for (R int i = 1; i <= n; ++i) scanf("%d", a + i), i + a[i] > 0 && i + a[i] <= n ? link(i + a[i], i), 1 : 0;46     for (R int i = 1; i <= n; ++i) scanf("%d", b + i), i + b[i] > 0 && i + b[i] <= n ? link(i + b[i], i), 1 : 0;47     R int head = 0, tail = 1; arv[q[1] = n] = 1;48     while (head < tail)49     {50         R int now = q[++head];51         for (R Edge *iter = last[now]; iter; iter = iter -> next)52             if (!arv[iter -> to]) arv[q[++tail] = iter -> to] = 1;53     }54     if (!arv[1]) {puts("No solution!"); return 0;}55     dfs(1, 1);56     return 0;57 }

 1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4  5 #define R register 6 #define maxn 500010 7 int last[maxn], lastt[maxn]; 8 struct Opt {int type, x;} p[maxn]; 9 std::vector<int> v[maxn];10 std::priority_queue<int, std::vector<int>, std::greater<int> > q;11 int main()12 {13     R int n, num = 0; scanf("%d", &n);14     for (R int i = 1; i <= n; ++i)15     {16         char opt[3]; scanf("%s", opt);17         if (opt[0] == ‘I‘)18         {19             R int x; scanf("%d", &x);20             p[i] = (Opt) {1, x};21         }22         if (opt[0] == ‘O‘)23         {24             R int x; scanf("%d", &x);25             p[i] = (Opt) {0, x};26         }27         if (opt[0] == ‘?‘) p[i] = (Opt) {2, 0};28     }29     for (R int i = 1; i <= n; ++i)30     {31         if (p[i].type == 2) continue;32         if (lastt[p[i].x] == p[i].type)33         {34             v[last[p[i].x]].push_back(i);35         }36         last[p[i].x] = i;37         lastt[p[i].x] = p[i].type;38     }39     for (R int i = 0; i < v[0].size(); ++i) q.push(v[0][i]);40     for (R int i = 1; i <= n; ++i)41     {42         for (R int j = 0; j < v[i].size(); ++j) q.push(v[i][j]);43         if (p[i].type == 2 && !q.empty())44         {45             R int top = q.top(); q.pop();46             if (top < i) return !printf("%d\n", top);47         }48     }49     if (q.empty()) puts("-1");50     else printf("%d\n", q.top());51     return 0;52 }