LibreOJ真是吼啊！
数码
推个式子，把枚举因数转为枚举倍数。然后就发现它是根号分段的。然后每一段算一下就好了。
#include <cstdio>
#include <cstring> #define R register
typedef long long ll;
struct Data {
ll num[];
inline void clear()
{
memset(num, , << );
}
inline Data operator + (const Data &that) const
{
R Data ret; memcpy(ret.num, num, << );
for (R int i = ; i <= ; ++i) ret.num[i] += that.num[i];
return ret;
}
inline void operator += (const Data &that)
{
for (R int i = ; i <= ; ++i) num[i] += that.num[i];
}
inline Data operator - (const Data &that) const
{
R Data ret; memcpy(ret.num, num, << );
for (R int i = ; i <= ; ++i) ret.num[i] -= that.num[i];
return ret;
}
inline void operator *= (const int &that)
{
for (R int i = ; i <= ; ++i) num[i] *= that;
}
} ;
inline Data calc2(R int N)
{
R ll tmp; R Data ret; ret.clear();
for (tmp = ; tmp - <= N; tmp *= )
for (R int i = ; i <= ; ++i)
ret.num[i] += tmp / ;
tmp /= ;
for (R int i = ; i < (N / tmp); ++i) ret.num[i] += tmp;
ret.num[N / tmp] += N % tmp + ;
// printf("calc2(%d) = \n", N);
// for (R int i = 1; i <= 9; ++i) printf("%lld\n", ret.num[i]);
return ret;
}
inline Data calc(R int N)
{
R Data ret; ret.clear();
for (R int i = , j; i <= N; i = j + )
{
j = N / (N / i);
R Data tmp = calc2(j) - calc2(i - );
tmp *= N / i;
ret += tmp;
}
return ret;
}
int main()
{
R int l, r; scanf("%d%d", &l, &r);
R Data ans = calc(r) - calc(l - );
for (R int i = ; i <= ; ++i)
printf("%lld\n", ans.num[i]);
return ;
}
数码
跳格子
预处理出每个点能不能到终点。然后直接暴搜就好了。
#include <cstdio>
#include <cstdlib> #define R register
#define maxn 100010
struct Edge {
Edge *next;
int to;
} *last[maxn], e[maxn << ], *ecnt = e;
inline void link(R int a, R int b)
{
*++ecnt = (Edge) {last[a], b}; last[a] = ecnt;
}
int q[maxn], n, a[maxn], b[maxn];
bool arv[maxn], ins[maxn];
char st[maxn];
void dfs(R int x, R int step)
{
if (!arv[x]) return ;
if (x == n)
{
for (R int i = ; i < step; ++i) printf("%c", st[i]); puts("");
exit();
}
if (ins[x])
{
puts("Infinity!");
exit();
}
ins[x] = ;
if (x + a[x] > && x + a[x] <= n)
{
st[step] = 'a';
dfs(x + a[x], step + );
}
if (x + b[x] > && x + b[x] <= n)
{
st[step] = 'b';
dfs(x + b[x], step + );
}
}
int main()
{
scanf("%d", &n);
for (R int i = ; i <= n; ++i) scanf("%d", a + i), i + a[i] > && i + a[i] <= n ? link(i + a[i], i), : ;
for (R int i = ; i <= n; ++i) scanf("%d", b + i), i + b[i] > && i + b[i] <= n ? link(i + b[i], i), : ;
R int head = , tail = ; arv[q[] = n] = ;
while (head < tail)
{
R int now = q[++head];
for (R Edge *iter = last[now]; iter; iter = iter -> next)
if (!arv[iter -> to]) arv[q[++tail] = iter -> to] = ;
}
if (!arv[]) {puts("No solution!"); return ;}
dfs(, );
return ;
}
跳格子
优惠券
一开始傻逼了，以为只要前缀就好了，后来才发现是区间。。。对于每个不满足的条件的左/右括号扔进一个数据结构里，然后每次遇到问号的时候，去消右端点最近的一个括号。然后这个数据结构用堆就够啦~
#include <cstdio>
#include <vector>
#include <queue> #define R register
#define maxn 500010
int last[maxn], lastt[maxn];
struct Opt {int type, x;} p[maxn];
std::vector<int> v[maxn];
std::priority_queue<int, std::vector<int>, std::greater<int> > q;
int main()
{
R int n, num = ; scanf("%d", &n);
for (R int i = ; i <= n; ++i)
{
char opt[]; scanf("%s", opt);
if (opt[] == 'I')
{
R int x; scanf("%d", &x);
p[i] = (Opt) {, x};
}
if (opt[] == 'O')
{
R int x; scanf("%d", &x);
p[i] = (Opt) {, x};
}
if (opt[] == '?') p[i] = (Opt) {, };
}
for (R int i = ; i <= n; ++i)
{
if (p[i].type == ) continue;
if (lastt[p[i].x] == p[i].type)
{
v[last[p[i].x]].push_back(i);
}
last[p[i].x] = i;
lastt[p[i].x] = p[i].type;
}
for (R int i = ; i < v[].size(); ++i) q.push(v[][i]);
for (R int i = ; i <= n; ++i)
{
for (R int j = ; j < v[i].size(); ++j) q.push(v[i][j]);
if (p[i].type == && !q.empty())
{
R int top = q.top(); q.pop();
if (top < i) return !printf("%d\n", top);
}
}
if (q.empty()) puts("-1");
else printf("%d\n", q.top());
return ;
}
优惠劵