题解:HDU6641 TDL

本题为 2019 HDU Multi-University Training Contest 6 的 1008 题

题目传送门🚪

Problem Description

For a positive integer $n$, let’s denote function $f(n,m)$ as the $m$-th smallest integer $x$ that $x>n$ and $\mathrm{gcd}(x,n)=1$. For example, $f(5,1)=6$ and $f(5,5)=11$.

You are given the value of $m$ and $(f(n,m)−n)\oplus n$, where $\oplus$ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer $n$ that $(f(n,m)−n)\oplus n=k$, or determine (whether) it is impossible.

Input

The first line of the input contains an integer $T$($1 \leq T \leq 10$), denoting the number of test cases.

In each test case, there are two integers $k,m$($1 \leq k\leq 10^{18}$,$1\leq m\leq100$).

Output

For each test case, print a single line containing an integer, denoting the smallest $n$. If there is no solution, output $-1$ instead.

Sample Input

1
2
3
2
3 5
6 100

Sample Output

1
2
5
-1

顺便吐槽下出题人的英语水平,“or determine it is impossible” 是什么鬼?

题意 & 题解

一道(对众多大佬来说比较水的)数论题,被拿来当签到题QAQ。

题目中,$(f(n,m) - n)\oplus n=k$,我们设 $d = f(n,m) - n$,则有 $d \oplus n = k$,两面同时异或上 $n\oplus k$,则有 $d \oplus n \oplus n \oplus k = k\oplus n \oplus k$ $\Rightarrow$ $n = d \oplus k$。$f(n,m)$ 表示大于 $n$ 的第 $m$ 大的与 $n$ 互质的数。由于 $m \leq 100$,一个奇数周围与它互质的数一般要多于与它不互质的数(举个例子,假设一个奇数 $9$,它周围有 $10$、$11$、$12$、$13$、$14$、$15$、$16$、$17$、$18$、$19$、$20$,其中与它互质的有$11$、$13$、$14$、$16$、$17$、$19$、$20$,要多于不与它互质的个数),所以我去枚举 $d$ 的值要优于枚举 $n$ 的值,况且一个数与它相邻的数一定是互质的,所以我们从 $1$ 开始枚举 $d$ 就可以了。枚举 $d$ 带入 $n = d \oplus p$ 得到的 $n$ 带回 $d=f(n,m)-n$ 中进行验证,如果成立,则代表这个结果是可行的。$f(n,m) = n + d$,$f(n,m)$ 满足与 $n$ 互质,即 $\mathrm{gcd}(f(n,m), n) = 1$,根据更相减损术,$\mathrm{gcd}(f(n,m) - n,n)$ $=$ $\mathrm{gcd}(f(n,m),n)$,所以枚举 $d$ 后通过判断 $d$ 与 $n$ 是否互质可以排除很多不满足的情况。而 $d$ 的枚举我们只需要枚举到第 $115$ 个质数,理由如下:

根据算术基本定理(唯一分解定理),任何一个大于 $1$ 的合数自然数 $N$,都可以分解成有限个质数的乘积,即:
$$
N = P_1^{a_{1}}P_2^{a_{2}}P_3^{a_{3}} \cdots P_n^{a_{n}}=\prod_{i=1}^nP_i^{a_i}
$$
根据约数个数定理,一个数的因数个数 $K$ 为:
$$
K = (a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1)=\prod_{i=1}^n(a_i+1)
$$
最终结果 $n$ 不会超过long long的范围,而前 $16$ 个质数之积已经超过了long long的范围,也就是说,最小的一个可分解为 $15$ 个以上质数的数已经不符合要求了,所以最终结果 $n$ 最多有 $15$ 质数因数。而根据更相减损术,如果对于一个质数 $x$ 与一个自然数 $n$ 互质,则 $x$ 也与 $x+n$ 互质。如果我们根据算术基本定理对 $n$ 分解后它有 $15$ 个素数因数,那么第 $115$ 个素数(即 $631$)一定会是 $d$ 可以取到的极限了。所以 $d$ 只需要从 $1$ 枚举到 $631$,超出此范围就一定没有满足的结果了。

AC代码

来自同队的 zyg 大佬,感谢大佬!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std ;
typedef long long ll ;

ll gcd (ll x , ll y){
if (y==0) return x ;
else return gcd(y,x%y) ;
}
const ll maxn = 1e18+5 ;
int main(){
int t ;
scanf("%d",&t) ;
while(t--){
ll k ;
int m ;
ll ans = maxn ;
scanf("%lld %d",&k , &m) ;
for (ll i = 1; i <= 631 ; i++) { // 631是第115个质数
ll n = i^k ;
if (gcd(i,n)!=1) continue ;
int temp = 0 ;
for (ll j = 1 ; j< i ; j++) {
if (gcd(j,n)==1) temp++ ;
}
if (temp==m-1&&ans>n){
ans = n ;
}
}
if (ans == maxn) cout << -1 << endl ;
else cout << ans << endl ;
}
return 0 ;
}

题解:HDU6629 String Mathching

本题为 2019 HDU Multi-University Training Contest 5 的 1007 题

题目传送门:🚪

Problem Description

String matching is a common type of problem in computer science. One string matching problem is as following:

Given a string $S[0\cdots len−1]$, please calculate the length of the longest common prefix of $S[i\cdots len−1]$ and $S[0 \cdots len−1]$ for each $i>0$.

I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:

img

We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.

input

The first line contains an integer $T$, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.

  • $1 \leq T \leq 30$

  • string length $\leq 106$ for every string

Output

For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.

Sample Input

1
2
3
4
 3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

Sample Output

1
2
3
17
7
32

题意 & 算法

题目就是问题目中这个算法中比较的次数。题目中提及的算法就是暴力对串中每一个位置进行前缀匹配。我们可以推知,如果子串长度为 $x$ ,我们就需要进行 $x+1$ 次匹配(因为还有一次匹配失败的情况)。而如果我匹配的子串最后一位到达了原串的最后一位的话,我们只需要进行 $x$ 次匹配(因为匹配失败的情况不会出现了)。所以这个问题就转换成了前缀匹配。扩展KMP算法就是为这种问题产生的。

KMP算法讲解传送门:🚪

这个题挺坑的,各种卡时间啊。卡memset()(其实也没必要用memset()),卡cin……T 了一晚上我才过去……

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int nexts[1000006];
char T[1000006];
long long ans = 0;
void getNext(){
int m = strlen(T);
// m:T的长度
int a = 0, p = 0;
for (int i = 1; i < m; i++) {
if (i >= p || i + nexts[i - a] >= p) {
if (i >= p) p = i;
while (p < m && T[p] == T[p - i])
p++;
nexts[i] = p - i;
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
a = i;
}
else{
nexts[i] = nexts[i - a];
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
}
}
}
int main(){
int n;
scanf("%d", &n);
while(n--){
scanf("%s", T);
ans = 0;
getNext();
printf("%lld\n", ans);
}
return 0;
}

题解:洛谷P1955:[NOI2015]程序自动分析

算法:并查基、离散化、文件读入与写出。

题目描述

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 $x_1,x_2,x_3\dots$代表程序中出现的变量,给定 $n$ 个形如$x_i=x_j$或$x_i \neq x_j$的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式

从文件prog.in中读入数据。

输入文件的第 $1$ 行包含 $1$ 个正整数 $t$,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第 $1$ 行包含 $1$ 个正整数 $n$ ,表示该问题中需要被满足的约束条件个数。接下来 $n$ 行,每行包括 $3$ 个整数 $i,j,e$,描述 $1$ 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 $e=1$,则该约束条件为 $xi=xj$;若 $e=0$,则该约束条件为 $xi\neq xj$;

输出格式

输出到文件 prog.out 中。

输出文件包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串“ YES” 或者“NO”(不包含引号,字母全部大写),“YES” 表示输入中的第 $k$ 个问题判定为可以被满足,“NO” 表示不可被满足。

输入输出样例

输入 #1

1
2
3
4
5
6
7
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出 #1

1
2
NO
YES

输入 #2

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出 #2

1
2
YES
NO

说明/提示

【样例解释1】

在第一个问题中,约束条件为:$x1=x2,x1\neq x2$。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:$x1=x2,x1=x2$。这两个约束条件是等价的,可以被同时满足。

【样例说明2】

在第一个问题中,约束条件有三个:$x1=x2,x2=x3,x3=x1$。只需赋值使得$x1=x1=x1$,即可同时满足所有的约束条件。

在第二个问题中,约束条件有四个:$x1=x2,x2=x3,x3=x4,x4\neq x1$。由前三个约束条件可以推出$x1=x2=x3=x4$,然而最后一个约束条件却要求$x1\neq x4$,因此不可被满足。

【数据范围】

img

【时限2s,内存512M】

题目传送门:🚪

文件读入与写出

虽说题干写着从文件读入,写出到文件,但其实这个题完全不需要……直接标准读入读出就可以……可怜我太实诚……酿造了如下惨状:

1564486633365

既然提到了就说说这个……

C的方法

  • fopen()函数

    使用方式:fp = fopen("input.in", "r")

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,是文件的类型和操作要求,有如下几种(组合):
      • r:只读(read),要求文件必须已经存在;
      • w:只写(Write),若文件不存在则自动创建,如果已存在则删除原文件后新建;
      • a:追加(Append),保留文件中已有内容,从文件尾开始写;
      • t:文本文件(Text),可忽略;
      • b:二进制文件(Binary);
      • +:读写。
    • 返回值为文件指针,为FILE类型的指针变量。

    在具体使用此方法写入时,使用fscanf(fp, "%d", &n)来读取:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同scanf()的使用方式;
    • 第三及以后的参数为传入变量的指针。

    使用fprintf(fp, "%d\n", n)来写入文件:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同printf()的使用方式;
    • 第三及以后的参数为输出变量。

    结束使用该函数使用:fclose(fp)

  • freopen()函数

    使用方式:freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,同fopen()函数;
    • 第三个参数为文件指针,通常使用标准流文件(stdin/stdout/stderr)。

    使用freopen()函数,并使用了标准流文件后,就可以直接使用scanf()printf()来读入和写出。

    结束使用fclose(stdin);fclose(stdout)

C++的方法

1
2
3
4
5
6
ifstream inputFL("input.in");
ofstream outputFL("putput.out");
inputFL >> n;
outputFL << n << endl;
inputFL.close();
outputFL.close();

正式题解

基本题意就是给你几个约束条件看他们能不能共存成立。而相等关系的约束条件我们可以很容易地想到将其转换为一个图,出现相等关系就说明它们在一个个图上 $\Rightarrow$ 两个值的最终祖先节点相同。而出现不等关系就说明它们没在一个图上,所以这个问题就可以转换成一个并查集问题。在这里贴上并查基常用的板子:

  • 得到最终祖先:

    1
    2
    3
    4
    5
    int get(int x){
    if(x == fa[x]){
    return x;
    }else return fa[x] = get(fa[x]);
    }
  • 合并两棵树:

    1
    2
    3
    4
    5
    6
    7
    void merge(int a, int b){
    int faOa = get(a);
    int faOb = get(b);
    if(faOa != faOb){
    fa[b] = a;
    }
    }

而注意到题目数据量很大,$i$、$j$ 的范围到了 $10^9$,无法开那么大的数组,所以我们使用到了离散化。我的离散化的博文的传送门:🚪

基本思想就是看输入的两个值是否相同,如果相同就保留到一棵树上。如果不相同的话检查两个点的根结点是否相同,如果相同则说明这两个值已经相同,出现矛盾,则输出“NO”。为了实现这个思想,我们首先要对输入进行排序,将相等关系放在前面预先判断。

AC代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define inputFL cin
#define outputFL cout
using namespace std;
struct Node{
int x;
int y;
bool e;
}Nodes[100005];
bool cmp(Node a, Node b){
return a.e > b.e;
}
int dict[1000005];
int fa[1000005];
int cnt, uqcnt;
int n;
int get(int x){
if (x == fa[x]) {
return x;
}else return fa[x] = get(fa[x]);
}
// void merge(int x, int y){
// fa[get(x)] = get(y);
// }
int main(){
// ifstream inputFL("prog.in"); // C++方式, C使用freopen()
// ofstream outputFL("prog.out");
int T;
inputFL >> T;
while(T--){
inputFL >> n;
memset(dict, 0, sizeof(dict));
memset(fa, 0, sizeof(fa));
uqcnt = cnt = 0;
for (int i = 0; i < n; i++) {
inputFL >> Nodes[i].x >> Nodes[i].y >> Nodes[i].e;
dict[cnt++] = Nodes[i].x;
dict[cnt++] = Nodes[i].y;
}
sort(dict, dict + cnt);
uqcnt = unique(dict, dict + cnt) - dict;
for (int i = 0; i < n; i++) {
Nodes[i].x = lower_bound(dict, dict + uqcnt, Nodes[i].x) - dict;
Nodes[i].y = lower_bound(dict, dict + uqcnt, Nodes[i].y) - dict;
}
for (int i = 0; i < uqcnt; i++) {
fa[i] = i;
}
bool check = 1;
sort(Nodes, Nodes + n, cmp);
for (int i = 0; i < n; i++) {
int a = get(Nodes[i].x);
int b = get(Nodes[i].y);
if (Nodes[i].e) {
fa[a] = b;
}else{
if (a == b) {
check = 0;
outputFL << "NO" << endl;
break;
}
}
}
if (check)
outputFL << "YES" << endl;
}
}

特别提醒:一定要分清离散化中各个变量的具体含义与用处,否则就会出现以下的状况而无从下手:

1564489428381

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×