Hexo
0%

Posted on In ,
Symbols count in article: 1.8k Reading time ≈ 2 mins.

字符串操作

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
68
69
70
71
72
73
74
75
76
77
78
79
cin:getline(char *,int n);//输入操作

* strlen(str);//计算字符串长度

* strcpy(str1,str2);//字符串赋值(将str2赋给str1)

* strtok(str,c)//字符串分割函数(对字符串按照字字符串c(可以是单个字符)进行分割,返回分割后的子字符串)
{
    char str[20]="china,chinese";
    char * token;//返回值为指针
    char c[2]=',';
    token=strtok(str,c);
    while(token!=NULL)
    {
        printf("%s\n",token);
        token = strtok(NULL,c);//继续分割
    }
    //output
    china
    chinese
}

* strcat(str1,str2);//字符串拼接函数，将str2字符串拼接到str1字符串后(!!!str1定义长度，必须大于拼接后的字符串长度)

* atoi(str);//将字符串str转为整形(支持正负数识别)
{
  char a[10]="100";
  int val=atoi(a);
  cout<<val<<endl;
   //output
   100
}

* atof(str);//将字符串str转为浮点型(支持正负数识别)

* atoi()和atof()有个缺点就是如果字符串是其他非数字字符，就会返回0，如果是数字0的话，照样返回0，这样就无法识别到底是字符'0'还是其他非数字字符。此时需要另一个函数:
strtol()//字符串转整形
{
    long int strtol(const char*str,char *endptr,int base);//将字符串str根据base转成对应进制数，并将转后结果作为函数结果返回；endptr指针指向原字符串中转化字符串的下一个字符
   char str[20]="0";
   char *endpty;
   int val;
   val = strtol(str,&endpty,8);//这里的base为8，指的是将字符串中的数字作为进制去识别，转化为十进制输出，则有效识别数字为1~7，9为无效字符，则到9时停止
   if(endpty!=str)
   {
	cout<<val<<endl;
    cout<<endpty<<endl;
   }
   else
   {
	cout<<"转化的是字符！"<<endl;
   }
    //output
    543
    9cend$3
}

* strcmp(const char*s1,const char*s2)//字符串比较，若s1==s2则返回0;若s1<s2则返回负数;若s1>s2则返回正数(两个字符串自左向右逐个字符比较(按ASCII值大小相比较)，直到出现不同的字符或遇到'\0'为止)
    
* strstr(const char*s1,const char*s2);//字符串查找，用于查找s2在s1中的位置。返回s1中第一次出现s2的指针；如果s2不是s1的一部分，则返回空指针。
{
    char s1[10]="aabb";
    char s2[10]="ab";
    char *value;
    value=strstr(s1,s2);
    if(value!=NULL)
    {
        cout<<value<<endl;
    }
    else
    {
        cout<<"找不到"<<endl;
    }
    
    //output
    abb
}

*char * strerror(int errnum);//用于获取指向错误消息字符串的指针。返回值为char*类型；
Read more »

Posted on In ,
Symbols count in article: 2.8k Reading time ≈ 3 mins.

字典树

用于统计，排序和保存大量的字符串（但不仅限于字符串,如01字典树）

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
const int N = 1000050;
int trie[N][26];// 每个trie代表一条边，字典树其中1~N为边上方节点的编号，0代表root节点，1~26为连在i节点下方的26个字母。如果trie[i][x]=0,则代表字典树中目前没有这个点，而trie[i][x]的值代表这个点下方连有的点的编号
int cnt[N];
int id;//节点编号

void insert(string s)//建树
{
	int p = 0;
	for (int i = 0; i < s.size(); i++)
	{
		int x = s[i] - 'a';//转化
		if (trie[p][x] == 0) trie[p][x] = ++id;//等于0时不存在
		p = trie[p][x];//向下走
	}
	cnt[p]++;//
}

int  find(string s)//搜索
{
	int p = 0;
	for (int i = 0; i < s.size(); i++)
	{
		int x = s[i] - 'a';
		if (trie[p][x] == 0)return 0;//不存在
		p = trie[p][x];
	}
	return cnt[p];
}

检索字符串

如果是查询某个单词的话，我们用bool变量 v[i]表示节点i是否是单词结束的标志。 那么最后return的是v[root],所以在插入操作中插入完每个单词是，要对单词最后一个字母的v[i]置为true，其他的都是false

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
/*
  trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母 
  trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号 
*/ 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
//bool isw[maxn];查询整个单词用
void insert(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)//现在插入的字母在之前同一节点处未出现过 
        {
            trie[rt][x]=++tot;//字母插入一个新的位置，否则不做处理 
        }
        rt=trie[rt][x];//为下个字母的插入做准备  
    }
    /*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/
}
bool find(char *s,int rt)
{
    for(int i=0;s[i];i++)
    {
        int x=s[i]-'a';
        if(trie[rt][x]==0)return false;//以rt为头结点的x字母不存在，返回0 
        rt=trie[rt][x];//为查询下个字母做准备 
    }
    return true;
    //查询整个单词时，应该return isw[rt] 
}
char s[22];
int main()
{
    tot=0;
    int rt=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(s,rt);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        if(find(s,rt))printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

查询前缀出现的次数

开一个sum[]，表示位置i被访问过的次数，那么最后return的是sum[root]，插入操作中每访问一个节点，都要让他的sum++，这里前缀的次数是标记在前缀的最后一个字母所在位置的后一个位置上。

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int trie[400001][26],len,root,tot,sum[400001];
bool p;
int n,m; 
char s[11];
void insert()
{
    len=strlen(s);
    root=0;
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) trie[root][id]=++tot;
        sum[trie[root][id]]++;//前缀保存 
        root=trie[root][id];
    }
}
int search()
{
    root=0;
    len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int id=s[i]-'a';
        if(!trie[root][id]) return 0;
        root=trie[root][id];
    }//root经过此循环后变成前缀最后一个字母所在位置
    return sum[root];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert();
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        cin>>s;
        printf("%d\n",search());
    }
}

维护异或极值

Read more »

Posted on In ,
Symbols count in article: 59 Reading time ≈ 1 mins.

分数规划

每种物品有两个权值a和b，选出若干物品使得$\frac{\sum a}{\sum b}$最小/最大

二分法

image-20240523145555458

Read more »

Posted on In ,
Symbols count in article: 8.6k Reading time ≈ 8 mins.

博弈论

公平组合游戏

  • 由两名玩家交替行动
  • 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
  • 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束

尼姆游戏

给定 N堆物品，第 i 堆物品有 $a_i$个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜

结论：定义 Nim 和为$a_1\oplus a_2\oplus a_3…\oplus a_n$,当且仅当 Nim和为 0 时，该状态为先手必败状态 否则该状态为先手必胜状态

巴什博弈

有 1 堆石子，总个数是 n ，两名玩家轮流在石子堆中拿石子，每次至少取 1 个，至多取 m 个。取走最后一个石子的玩家为胜者。判定先手和后手谁胜。

结论： 若 n%(m+1)==0 ，则先手获胜，否则后手获胜

威佐夫博弈

Read more »

Posted on In ,
Symbols count in article: 1.4k Reading time ≈ 1 mins.

普通莫队算法

有一个长度为n的序列${c_i}$,现在给出m个询问，每次给出两个数l，r，从编号在l到r之间的数中随机选出两个不同的数，求两个数相等的概率

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
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];

struct query {
  int l, r, id;

  bool operator<(const query &x) const {  // 重载<运算符
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];

void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}

void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

int main() {
  scanf("%d%d", &n, &m);
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 0; i < m; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {  // 具体实现
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    printf("%lld/%lld\n", ans1[i], ans2[i]);
  }
  return 0;
}
Read more »