A. 统计数字（数位DP）
暴力的从1到n每个数字处理一遍是非常慢的，通过规律来计算得解可以大大优化。
例如n = 465的情况：
首先不考虑去掉前导0，那么从00到99，0~9每个数字出现的次数一是一样的，一共有100 *2个数次，平摊到每个数字则是都出现了20次；
同理，100到199，除了1多出现100次以外，0 2 3 4 5 6 7 8 9又出现了20次；
同理200~299，300~399；
400之后，不能再统计到499，统计的规模要缩小，换成400~409，410~419，420~429，…，450~459；
接着考虑460~465。
然后要去掉多余的前导零：
首先000有一个，然后001~009有9个，010~099有90个，再往后没有前导零了。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
int d[10];
int cnt[10];
int getdigit(int n)
{
int ret = 0;
while(n)
{
d[ret] = n % 10;
n /= 10;
ret++;
}
return ret;
}
int ten_pow(int k)
{
int ret = 1;
while(--k) { ret *= 10; }
return ret;
}
void getans(int n)
{
memset(cnt, 0, sizeof(cnt));
int len = getdigit(n);
for(int p = len - 1; p > 0; p--)
{
int k = ten_pow(p);
for(int i = 0; i < 10; i++) cnt[i] += k * d[p] * p;
for(int i = len - 1; i > p; i--) cnt[d[i]] += k * 10 * d[p];
for(int i = 0; i < d[p]; i++) cnt[i] += k * 10;
// for(int i = 0; i < 10; i++) printf("%d ", cnt[i]); cout << endl;
}
int w = n % 10;
for(int i = 0; i <= w; i++) cnt[i]++;
for(int i = len - 1; i > 0; i--) cnt[d[i]] += w + 1;
cnt[0] -= len;
int t = len, s = 9;
while(t--)
{
cnt[0] -= t * s;
s *= 10;
}
for(int i = 0; i < 10; i++) printf("%d\n", cnt[i]);
}
int main()
{
// freopen("13124.in", "r", stdin);
int n;
while(~scanf("%d", &n))
{
getans(n);
}
return 0;
}
B. 青姬の爱恋
素数打表到maxn^(1/2)，对于每个数n，找到较小的素数p，输出n / p。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
const int maxn = 1e5;
const int prin = 5e4;
int prime[prin];
///仅包含奇数，isprime[k]代表2*k+3
bool isprime[maxn >> 1];
int ptop = 0;
void sieve()
{
memset(isprime, true, sizeof(isprime));
prime[0] = 2;
int sq = sqrt(maxn);
for(int i = 3; i < maxn; i += 2)
if(isprime[(i-3) >> 1])
{
if(i <= sq + 3)
{
for(int j = i * i; j < maxn; j += 2 * i)
isprime[(j-3) >> 1] = false;
}
prime[++ptop] = i;
}
}
int main()
{
// freopen("13125.in", "r", stdin);
sieve();
int n;
while(~scanf("%d", &n))
{
int k = 0;
while(n % prime[k] != 0 && k < ptop) { k++; }
printf("%d\n", n / prime[k]);
}
return 0;
}
C. 买水果
整数规划，更简便的计算方法是用到五边形数定理。
#include <stdio.h>
#include <string.h>
int p[110];
void init()
{
p[0] = p[1] = 1;
p[2] = 2;
p[3] = 3;
for(int i = 4; i < 110; i++)
{
p[i] = 0;
int flag = 1;
for(int j = 1; ; j++)
{
int p1 = j * (3 * j - 1) / 2;
int p2 = j * (3 * j + 1) / 2;
if(p1 > i && p2 > i) break;
if(p1 <= i) p[i] = p[i] + flag * p[i - p1];
if(p2 <= i) p[i] = p[i] + flag * p[i - p2];
flag *= (-1);
}
}
}
int main()
{
init();
int t, n;
while(scanf("%d", &n) != EOF)
{
printf("%d\n", p[n]);
}
}
D. 小明和小红
Nim博弈类问题。在N符合条件的情况下，先手有必赢的策略。
假设N模4不为0，先手第一轮拿走N % 4颗糖果，后手每次拿x颗糖果，先手都拿4 – x颗，后手必输；
若N模4为0，先手必输。
E. 离散函数
绿色的线条表示非最优解，蓝色线条表示非法解，红色线条表示最优解。
对于每个点，一定是和它的相邻一个点的连线是最优解，所以只需要找相邻两个点的斜率最大值即可。
F. 熊大的学籍管理系统（hash）
将字符串通过hash函数处理成一个数，如果出现不同的字符串hash后得到同一个hash值，则用链表储存下来，查询的时候，只需搜该hash值对应的所有字符串。
这个题还可以用c++里stl中的map来做，非常方便。
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define HASH 20011
typedef char Str[12];
Str id[HASH], na[HASH];
int n, head[HASH], next[HASH];
inline int BKDR_hash(char *str)
{
int seed = 131;
int hash = 0;
while(*str) hash = hash * seed + (*str++);
return (hash & 0x7fffffff) % HASH;
}
inline int add_hash(int s)
{
int h = BKDR_hash(id[s]);
next[s] = head[h];
head[h] = s;
return 1;
}
inline int srch(char *str)
{
int h = BKDR_hash(str);
int u = head[h];
while(u)
{
if(strcmp(id[u], str) == 0) return u;
u = next[u];
}
return -1;
}
Str idtmp, natmp, quary;
int main()
{
// freopen("13129.in", "r", stdin);
int N, Q, k;
while(scanf("%d", &N) != EOF)
{
memset(id, 0, sizeof(id));
memset(na, 0, sizeof(na));
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
k = 1;
for(int i = 0; i < N; i++)
{
scanf("%s%s", idtmp, natmp);
if(srch(idtmp) != -1) printf("%s has existed!\n", idtmp);
else
{
memcpy(id[k], idtmp, sizeof(id[k]));
memcpy(na[k], natmp, sizeof(na[k]));
add_hash(k);
k++;
}
}
scanf("%d", &Q);
for(int i = 0; i < Q; i++)
{
scanf("%s", quary);
int w = srch(quary);
if(w == -1) printf("Can not find %s!\n", quary);
else printf("%s\n", na[w]);
}
}
return 0;
}
G. 她们会去哪里（几何）
纯计算。
H. The Princess Number（暴力）
数据范围不够大，可以暴力做。数据范围大的时候，先对所有数排序，再进行统计即可。
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 1000100
int cnt[MAXN], a[MAXN], na[MAXN], n;
int ans[MAXN], maxc, maxa, tot;
int l(int ai)
{
return lower_bound(a, a + n, ai) - a;
}
int r(int ai)
{
return upper_bound(a, a + n, ai) - a;
}
int main()
{
int cas = 1;
while(~scanf("%d", &n))
{
for(int i = 0; i < n; i++)
scanf("%d", a + i);
sort(a, a + n);
maxa = a[n - 1];
int now = 0;
na[0] = a[0];
for(int i = 0; i < n; i++)
if(na[now] != a[i])
na[++now] = a[i];
now++;
maxc = 0;
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < now; i++)
{
cnt[na[i]] = r(na[i]) - l(na[i]);
maxc = max(maxc, cnt[na[i]]);
}
tot = 0;
for(int i = 0; i <= maxa; i++)
if(cnt[i] == maxc)
ans[tot++] = i;
printf("Case #%d: %d\n", cas++, tot);
for(int i = 0; i < tot; i++)
{
if(i)
printf(" ");
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}