这次的题目难得的水，但是由于许多哲学的原因，第二题题意表述很迷。
然后是真的猜题意了搞了。
不过这样都可以涨Rating我也是服了。
Upt:链接莫名又消失了
A. 「NOIP2017模拟赛11.03」Egypt丶小黑车
题意一看就是很精简的数学题，
首先我们用经典的方法，假设我们用\(f_x\)表示\([1,x]\)的答案，那么最后输出的就是\(f_r-f_{l-1}\)了
然后考虑求解\(f_x\)。我们知道对于一个\([1,x]\)的区间里，含有约数\(d\)的数有\(\lfloor \frac{x}{d}\rfloor\)个。
所以我们考虑枚举所有以数码\(k\)开头的数\(d\)，然后累加\(\lfloor \frac{x}{d}\rfloor\)即可。
然后我们发现这样会很慢，所以我们对于一整段数一起枚举。
什么意思，比如在枚举数码\(k=1\)时，我们每次分别求解\([1,1],[10,19],[100,199]......\)
然后我们要做的就是快速对于一段区间进行统计了。
我们先考虑最暴力的想法：每次从\([l,r]\)之间依次枚举，但这样的话当\(r-l\ge 10^5\)时就会超时
但是我们发现，当\(r-l\ge10^5\)时，设其中的一个数为\(s\)，那么\(n/s\le 10^4\)。
所以我们枚举商\(m\)，然后通过商来得出\([l,r]\)中对应的数有哪些即可。
CODE
#include<cstdio>
using namespace std;
typedef long long LL;
const LL pow[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000},div=100000;
LL a[15],b[15],l,r;
inline LL min(LL a,LL b)
{
return a<b?a:b;
}
inline LL max(LL a,LL b)
{
return a>b?a:b;
}
inline LL work(LL l,LL r,LL n)
{
if (r<l) return 0; register LL i; LL ans=0;
if (r-l<=div)
{
for (i=l;i<=r;++i)
ans+=n/i; return ans;
}
for (i=n/r;i<=n/l;++i)
{
LL low=max(n/(i+1),l),high=min(n/i,r);
if (n/low!=n/high) ans+=(high-low)*i; else ans+=(high-low+1)*i;
}
return ans;
}
inline void solve(LL n,LL *num)
{
if (!n) return; register LL i,j;
for (i=1;i<=9;++i)
for (j=0;j<=10&&pow[j]<=n;++j)
num[i]+=work(i*pow[j],min(n,(i+1)*pow[j]-1),n);
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
scanf("%lld%lld",&l,&r);
solve(l-1,a), solve(r,b);
for (register LL i=1;i<=9;++i)
printf("%lld\n",b[i]-a[i]);
return 0;
}
B. 「NOIP2017模拟赛11.03」Egypt丶李小车
首先讲一下题目缺少了一个很重要的条件，就是只有当敌方英雄在位置\(n\)上时才能结束踢人
然后我们考虑一下，如果我们事先知道一个点能不能到达终点，这样就可以直接统计答案了。
为什么？因为如果对面现在在位置\(i\)上，我们分情况讨论：
- \(i=n\)直接结束踢人即可。因为再踢下去肯定是没有当前优的。
- \(i+a_i\)可以到达终点，这样我们直接让字符串加上\(a\)即可。因为这样可以让字典序最小，用\(b\)的话再短也没有用。
- \(i+b_i\)可以到达且\(i+a_i\)无法到达。同上，字符串加上\(b\)即可。因为总比无解要强。
- 两个都无法到达，那么必定无解。
然后我们在上面的基础上判断一下是否有点被重复访问即可。
对于一个点能否走到终点，只需要把边反向建之后从终点BFS即可。
CODE
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int N=1e5;
struct edge
{
int to,next;
}e[N<<1];
int head[N],n,a[N],b[N],q[N],cnt,tot;
bool vis[N],use[N];
char ans[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc(); int flag=1;
while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=tc(); }
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc(); x*=flag;
}
inline bool check(int x)
{
return x>=1&&x<=n;
}
inline void add(int x,int y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline void BFS(int x)
{
int H=0,T=1; q[1]=x; vis[x]=1;
while (H<T)
{
int now=q[++H];
for (register int i=head[now];i!=-1;i=e[i].next)
if (!vis[e[i].to]) vis[e[i].to]=1,q[++T]=e[i].to;
}
}
inline void print(void)
{
for (register int i=1;i<=tot;++i)
putchar(ans[i]);
}
inline void DFS(int now)
{
if (!(now^n)) { print(); exit(0); }
if (use[now]) { puts("Infinity!"); exit(0); } use[now]=1;
if (check(now+a[now])&&vis[now+a[now]]) ans[++tot]='a',DFS(now+a[now]); else ans[++tot]='b',DFS(now+b[now]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
memset(head,-1,sizeof(head));
memset(e,-1,sizeof(e));
for (i=1;i<=n;++i)
{
read(a[i]);
if (check(i+a[i])) add(i+a[i],i);
}
for (i=1;i<=n;++i)
{
read(b[i]);
if (check(i+b[i])) add(i+b[i],i);
}
BFS(n); if (!vis[1]) { puts("No solution!"); return 0; }
DFS(1); return 0;
}
C. 「NOIP2017模拟赛11.03」Egypt丶法拉利
这道题其实是水题，但是我真的因为ZZ然后没发现反例。
首先有一个很naive的想法。统计之前问号的个数，然后在冲突时看一下是否有问号，有就用问号来抵消冲突。
但是这个方法有一个致命的弱点，就是对于问号的时间把控有问题。比如有一组反例（感谢CJJ dalao无偿提供）
3
?
I 1
I 1
对于上面的想法会给出\(-1\)。但答案很明显是\(3\)。
那么是哪里出问题了，很简单，就是问号操作在I操作之间才出现，这样就无法抵消效果。
想到这里就很简单了，我们把所以问号的操作的时间存到set里。每次矛盾时把在它后前的最早出现的问号使用掉，因为你前面的不用用后面的可能会让后面的没法用。一个小贪心。
然后我们就直接上STL大法即可解决其实线段树也是可以的
CODE
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int N=1e5+5;
int a[N],last[N],x,m;
char opt;
set <int> s;
set <int>::iterator it;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(m);
for (i=1;i<=m;++i)
{
opt=tc(); while (opt!='I'&&opt!='O'&&opt!='?') opt=tc();
if (opt^'?')
{
read(x); a[x]+=opt^'I'?-1:1;
if (a[x]<0||a[x]>1) { if ((it=s.lower_bound(last[x]))!=s.end()) s.erase(it),a[x]+=opt^'I'?1:-1; else return printf("%d",i),0; }
last[x]=i;
} else s.insert(i);
}
return printf("-1"),0;
}