Ryan_<

1、统计[m,n]这个区间有多少个0

分位数分析：

n的第i位为0=n左边的数（高位）*10^(i-1)

n的第i位不为0 =（n左边的数-1）*10^(i-1)+（i位右边的数+1）

ans=f(n)-f(m-1);

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;

ll n, m;

ll cal(ll x) {
	if (x < 0)
		return 0;
	ll ans = 1, cnt = 1, tmp = 0;
	while (x >= 10) {
		ll cur = x % 10;
		x /= 10;
		if (cur) 
			ans += x * cnt;
		else ans += (x-1) * cnt + tmp + 1;
		tmp += cur * cnt;
		cnt *= 10;
	}
	return ans;
}

int main() {
	while (scanf("%lld%lld", &n, &m) != EOF && n != -1 && m != -1) {
		printf("%lld\n", cal(m) - cal(n-1));	
	}	
	return 0;
}

2、超级平均数

3、圆中单色三角形计数【经典问题：补集思想+简单组合计数】

关键：如果从一个点出发两条不同颜色的边，那么这三个点一定构成一个非单色三角形。

ans=C(n,3)-½∑( red[i]*(n-1-red[i]) )

没有思路时可尝试从特殊到一般,注意去重（*½）

#include <cstdio>

const int maxn = 1000 + 10;
int a[maxn][maxn];

int main()
{    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n;
        scanf("%d", &n);
        for(int i = 1; i < n; i++)
            for(int j = i + 1; j <= n; j++)
            {
                int x;
                scanf("%d", &x);
                a[i][j] = a[j][i] = x;
            }
        long long ans1 = 0;
        for(int i = 1; i <= n; i++)
        {
            int t = 0;
            for(int j = 1; j <= n; j++) if(i != j) t += a[i][j];
            ans1 += (long long)t * (n - 1 - t);
        }
        long long ans2 = n * (n-1) / 2 * (n-2) / 3;
        printf("%lld\n", ans2 - ans1 / 2);
    }

    return 0;
}

4、格点中不重合斜线计数

typedef long long ll;
#define MD 1000000007
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;

ll ans[310][310];
ll dp[310][310];

int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void init()
{

    for (int i = 1; i <= 305; i++)
        for (int j = 1; j <= 305; j++)
        {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + (gcd(i, j) == 1);
            ans[i][j] = ans[i-1][j] + ans[i][j-1] - ans[i-1][j-1] + dp[i][j] - dp[i/2][j/2];
        }
}
int main()
{
    init();
    int n, m;
    while (scanf("%d%d", &n, &m) && n)
    {
        printf("%lld\n", ans[n-1][m-1] * 2LL);
    }
    return 0;
}

4、格点三角形计数

5、格点四边形计数