UOJ Logo NaCl的博客

博客

题解

2018-08-17 16:44:55 By NaCl

写在前面

为开拓心灵的处女地
走入禁区,也许——
就在那里牺牲
留下歪歪斜斜的脚印
给后来者
签署通行证

——《献给我的同代人》舒婷

进制转换(change)

可以使用 printf 的格式化输出,当然这些语言特性实际上相当鸡肋。

由于非常简单就不说了。

AZe 数

$\varphi(n) = n - 1$ 意味着小于 $n$ 的数均与 $n$ 互质。只有 $n$ 为质数满足这一点。

因此 AZe 数就是质数,故使用线性筛。

双月同天(moon)

前面的 $ 字符很容易处理,如果您使用 char 数组传统字串,可以初始化为 char b[10001] = "$"; 然后 scanf("%s%s", a, b + 1);。如果使用 std::string,可以先读入再 b = "$" + b

char匹配可以用 strstr 函数,std::string 匹配可以用 find 方法。

由于存在 $a=3;$aa=5; 这种情况,找到后判断下一位是否为字母,如果不是字母即可。

姆 Q 的难题

我们暂时允许类别为空。

如果全部类别中没有只有一本书的,则每个类别去除一本,成为 $f(m - n, n)$。

如果「存在」一个类别有一本书,相当于在 $f(m, n - 1)$ 上有一本书掉了出来。

在允许为空的情况下,答案即为两部分之和。边界条件如果 n 为 0 有 0 种,n 为 1 或 $m\le1$ 也是 1 种(每个类别去除一本这个操作之前的那种情况)。

现在不允许类别为空,故答案变为 $f(m - n, n)$。

普通题++(simple++)

本题出题人说不卡 std::sort()

采用标准库 <utility> 中的 std::pair 简单处理即可。请参考评论区。

评论

insilent
前排兹次
lris
T5出题人…… 用pair不太好写,最好还是按我上次那个struct写。 最大的坑点是fcmp检查,不忽略末尾空格,但这是本题库里默认的评测方式qwq 链表做法: #include<iostream> #include<cstdio> #define max(a, b) a>b? a:b const int N=10005; struct Node { int rank; Node *nxt; Node(int rank=0, Node *nxt=NULL): rank(rank), nxt(nxt) {} void Print() { printf("%d ", rank); if(nxt) nxt->Print(); } void Print_end() { if(nxt) { printf("%d ", rank); nxt->Print_end(); } else printf("%d", rank); } }*head[N]; void Addnode(int value, int pos) { head[value]=new Node(pos, head[value]); } int main() { int n=read(), t, zd=0; for(int i=1; i<=n; i++) t=read(), zd=max(zd, t), Addnode(t, i); for(int i=0; i<zd; i++) if(head[i]) head[i]->Print(); head[zd]->Print_end(); return 0; }
Capella
支持——话说 AZe 数还行
z2512690268
T1标程送上。 #include<cstdio> #include<iostream> using namespace std; char MAP[6] = {'A', 'B', 'C', 'D', 'E', 'F'}; long long in; void change(long long aim, long long sys){ if(aim){ change(aim/sys, sys); int t = aim%sys; if(t>=10) cout << MAP[t-10]; else cout << t; } } int main(void){ cin >> in; change(in, 2); cout << endl; change(in, 8); cout << endl; change(in, 16); }
insilent
T4 一道经典的递归题 大佬说的很清楚 以下标程 #include<cstdio> int work(int book,int kind) { if(book==0||kind==1) return 1; if(book<0||kind<0) return 0; return work(book-kind,kind)+work(book,kind-1); } int main() { int m,n; scanf("%d%d",&m,&n); printf("%d\n",work(m-n,n)); return 0; }
AZe
T2 这道题的题面似乎很难理解,但是实质真的很简单…… 理解一下互质,NaCl已经写得很清楚了,不清楚的可以私信我 然后,欧拉函数真的非常重要,建议你们有余力的看看? 上std ~~~cpp #include<iostream> using namespace std; const int inf=10000005; int prime[inf]; bool is_prime[inf+1]; int shai(int n){ int p=0; for(int i=0;i<=n;i++) is_prime[i]=true; is_prime[0]=false; is_prime[1]=false; for(int i=2; i<=n; i++){ if(is_prime[i]){ prime[p++]=i; for(int j=2; j*i<=n; j++) is_prime[j*i]=false; } } return p; } int main(){ int m; cin>>m; int num=shai(m); cout<<num<<" "<<prime[num-1]-2; return 0; } ~~~cpp
NaCl
T3 数据小,暴力可过,如果数据大可以用 KMP 算法。 下面是标程,仅供测试数据。标程是 KMP 算法的非主流版,如果要学那个算法建议百度。
NaCl
#include <cstdio> #include <cstring> #include <cctype> const int MAXN = 10002; char a[MAXN], b[MAXN] = "$"; int f[MAXN] = {-1}, ans = 0, fir = -1; int main() { scanf("%s%s", a, b + 1); int la = strlen(a), lb = strlen(b); for(int i = 0, j = 1;; i++, j++) if(j >= lb) { f[j] = i; break; } else if(b[i] == b[j]) f[j] = f[i]; else { f[j] = i; do i = f[i]; while(i >= 0 && b[i] != b[j]); } for(int i = 0, j = 0; i < la; ) if(a[i] == b[j]) { i++, j++; if(j == lb) { j = f[j]; if(!isalpha(a[i])) { ans++; if(!~fir) fir = i - lb; }}} else { j = f[j]; if(j < 0) i++, j++; } printf("%d %d", fir, ans); return 0; }

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。