提高组模拟试题 1

A.赌徒 (gambler)

需要一定思考的送分题

• 数据规模超大，应为结论题。
• 注意特判，然后推导结论。
• 附代码：

#include<bits/stdc++.h>
using namespace std;
long long test,n,m,k;
int t;
int main() {
    freopen("gambler.in","r",stdin);
    freopen("gambler.out","w",stdout);
    scanf("%lld%d",&test,&t);
    while(t--) {
        scanf("%lld%lld%lld",&n,&m,&k);
        if(k==0) {
            if(m==0)
                cout<<"Ivor"<<endl;
            else
                cout<<"Harper"<<endl;
        } else {
            if(m==0 || m%k==0)
                cout<<"Ivor"<<endl;
            else {
                if(n+m<=k)
                    cout<<"Harper"<<endl;
                else {
                    if(m%2==1 && k%2==0)
                        cout<<"Harper"<<endl;
                    else {
                        cout<<"Ivor"<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

B.残片 (garbage)

要让字典序最小，应满足以下二点：

1. 不存在一个字符串是该字符串的前缀。

2. else 找出该字符串与其他字符串首次不一样的字符，得到不等关系，若关系矛盾，则无法最小。字典树快速解决:枚举每个字符串;匹配不同的字符时，遍历字典树;暴力建图，判环。

前缀存在问题也可字典树解决

C.护手 (gauntlet)

正解为求贡献，树状数组实现，链式前向星计算。

但不太适合我这种只骗分的蒟蒻。

题目允许离线，区间查询，区间答案能够快速转移到相邻区间答案。

因此选择基于分块思想的莫队。83分。

• 正在学习中————

D.无量 (gazillion)

动态规划，二分找答案，注意空间和时间问题。

总结

• A题没考虑完整，52分。改后AC；
• B题完全不会，字典树上手难；但考试中花式打表，骗了10分；
• C题暴力枚举，结果0分，正在莫队整改；
• D题暴力广搜，0分。DP不想整。