本场比赛5道简单题，除了A题榜歪了以外，其他4题通过率均符合预期。

A - NB群友

题目链接

问题可以转化成求“积$\leq R$的数的个数” $-$ “积$\leq (L-1)$的数的个数”，于是我们可以dfs枚举$2 \sim 9$每个数字出现的次数，然后再组合数统计一下答案，剪剪枝就能过。

#include<bits/stdc++.h>

using namespace std;

#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,a,b) for(int i=a; i<=b; ++i)
#define PER(i,a,b) for(int i=a; i>=b; --i)
#define MP make_pair
#define PB push_back
#define fi first
#define se second
typedef long long LL;
typedef double DB;

const int maxT = 50;
const int P = 1e9+7;
const LL MaxInt = (1LL<<32) - 1;

LL Fac[100], InvFac[100];
LL C[100][100];
int cnt[20];

LL lim;
LL dfs(LL now, int pt) {
    if(pt<=1) {
        int s = 0;
        LL ret = 1;
        REP(i,2,9) {
            s += cnt[i];
            ret = ret * C[s][cnt[i]] % P;
        }
        if(s==0) return 0LL;
        return ret;
    }
    LL ret = 0;
    cnt[pt] = 0;
    while(now <= lim) {
        ret = (ret + dfs(now, pt-1)) % P;
        now *= pt, ++cnt[pt];
    }
    return ret;
}

int main() {
    C[0][0] = 1;
    for(int i = 1; i <= 50; ++i) {
        C[i][0] = C[i][i] = 1;
        for(int k = 1; k < i; ++k) C[i][k] = (C[i-1][k] + C[i-1][k-1]) % P;
    }
    int _; scanf("%d", &_);
    while(_--) {
        LL a,b;
        scanf("%lld%lld", &a, &b);
        lim = b;
        LL sb = dfs(1,9);
        lim = a-1;
        LL sa = dfs(1,9);
        LL ans = (sb - sa + P) % P;
        printf("%lld\n", ans);
    }
    return 0;
}

C - 六学家的困惑

题目链接

此题出题人对此题的定位是签到题，但组题人表示好像不怎么签到。。。

正解是贪心，然而现场很多人的贪心策略是直接比较两根管子四个端点处的数字大小，然后取最大的那个数，于是就WA了。考虑下面这个例子：

595
575

最优的取球顺序应该是先取第一根管子的$5$，再取第一根管子的$9$。但如果使用上面的贪心策略，就有可能先取第二根管子的$5$，再取第二根管子的$7$，这样就错了。

正确做法应该是：在每次取球时，对于每根管子，分别从左往右读和从右往左读，这样就可以得到一共$4$个字符串。比较这$4$个字符串的字典序大小，取字典序最大的那个字符串的第一个字符对应的球即可。

单组数据复杂度$O(n^2)$。

// 邵老师牛逼!
#include<bits/stdc++.h>

using namespace std;

const int maxT = 14;
const int maxn = 40;

int cmp(char *s1, int p1, int d1, int n1, char *s2, int p2, int d2, int n2) {
    int n = min(n1,n2);
    for(int i = 1; i <= n; ++i) {
        if(s1[p1] < s2[p2]) return -1;
        if(s1[p1] > s2[p2]) return 1;
        p1+=d1, p2+=d2;
    }
    if(n1 < n2) return -1;
    if(n1 > n2) return 1;
    return 0;
}

int main() {
    int __; scanf("%d", &__);
    assert(1<=__ && __<=maxT);
    char s1[maxn+5], s2[maxn+5];
    char ans[maxn*2+5];
    for(int _ = 1; _ <= __; ++_) {
        scanf("%s%s", s1, s2);
        int l1 = 0, r1 = strlen(s1)-1;
        int l2 = 0, r2 = strlen(s2)-1;
        int n = r1+r2+2;
        for(int i = 0; i < n; ++i) {
            int di1 = 0, di2 = 0;
            if(cmp(s1, l1, 1, r1-l1+1, s1, r1, -1, r1-l1+1) >= 0) di1 = 1;
            else di1 = -1;

            if(cmp(s2, l2, 1, r2-l2+1, s2, r2, -1, r2-l2+1) >= 0) di2 = 1;
            else di2 = -1;

            int pt = 0, di = 0;
            if(cmp(s1, (di1==1)?l1:r1, di1, r1-l1+1, s2, (di2==1)?l2:r2, di2, r2-l2+1) >= 0)
                pt = 1, di = di1;
            else pt = 2, di = di2;
            char c = 0;
            if(pt==1) {
                if(di==1) ans[i] = s1[l1++];
                else ans[i] = s1[r1--];
            }
            else if(pt==2) {
                if(di==1) ans[i] = s2[l2++];
                else ans[i] = s2[r2--];
            }
        }
        ans[n] = '\0';
        printf("Case #%d: %s\n", _, ans);
    }
    return 0;
}

E - 数独挑战

题目链接

舞蹈链模板题。 这题出在校赛就是给大家爆搜的，听说过舞蹈链的选手可能会被唬住，没听过的选手直接大力剪枝莽一莽就过了。至于有些人的爆搜TLE了？那只能说明你们的剪枝不够优秀。。。

以下只给出爆搜代码：

#include<cstdio>
using namespace std;

int v[100][2],map[10][10];

bool judge(int x,int y,int k)
{
    for(int i=0;i<9;i++)
        if(map[i][y]==k||map[x][i]==k)
            return false;
    int dx=x-x%3,dy=y-y%3;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(map[dx+i][dy+j]==k)
                return false;
    return true;
}

int dfs(int n)
{
    if(n<0) return 1;
    for(int i=1;i<=9;i++)
    {
        int x=v[n][0],y=v[n][1];
        if(judge(x,y,i))
        {
            map[x][y]=i;
            if(dfs(n-1)) return 1;
            map[x][y]=0;
        }
    }
    return 0;
}

int main()
{
    int num=0;
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            scanf("%d",&map[i][j]);
            if(map[i][j]==0)
            {
                v[num][0]=i;
                v[num++][1]=j;
            }
        }
    dfs(num-1);
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
            printf("%d ",map[i][j]);
        printf("%d\n",map[i][8]);
    }
    for(int j=0;j<8;j++)
        printf("%d ",map[8][j]);
    printf("%d",map[8][8]);
    return 0;
}

I - 炒股

题目连接

（据说某C姓出题人被这题卡了）

全场通过率第二高的题，贪心策略没什么好讲，看代码理解理解就懂了。唯一需要注意的是这题答案会爆int范围，因此需要用long long保存答案。

以下提供Python 3代码 （于是完全不用考虑爆int的问题了）：

n = int( input() )

pa = int( input() )
ans = 0
for i in range(1,n):
    a = int( input() )
    if(a>pa): ans += a-pa
    pa = a

print(ans)

L - 石头剪刀布

题目链接

由于觉得C题不够签到，为防止有队伍爆零而临时加的签到题 （然而仍然没防住）。

在这题上出现的错误包括但不限于：

  • 拼错单词
  • system("pause");
  • #include "stdafx.h"

Emmm……我只能说，出题人尽力了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string str;
    cin >> n;
    while (n-- > 0) {
        cin >> str;
        if (str == "Scissors") cout << "Rock\n";
        if (str == "Rock") cout << "Paper\n";
        if (str == "Paper") cout << "Scissors\n";
    }
    return 0;
}