C. C. Blog

Security Research, Algorithm and Data Structure

发表于 更新于 分类于 ，
本文字数： 137 阅读时长 ≈ 1 分钟

一、队伍训练情况

　　浙大校赛网络同步赛，5题。

二、个人训练情况

　　Codeforces Round #551 (Div. 2)

　 2050编程竞赛

　　4+3+5还是只能做一些非dp的思维题。

三、遇到的问题&可行的解决方案

　　掌握的知识太少。

　　无解，能力有限，近几周需要加强学习，竞赛仅作基础训练。

发表于 更新于 分类于 ，
本文字数： 116 阅读时长 ≈ 1 分钟

一、队伍训练情况

　　计划下周开始到实验室训练

二、个人训练情况

　　计蒜客ACM训练联盟周赛第二场

　　CodeforcesCodeforces Global Round 2

　　51Nod

　　止步于简单题

三、遇到的问题&可行的解决方案

　　目标是什么？正在解决。

发表于 更新于 分类于 ，
本文字数： 297 阅读时长 ≈ 1 分钟

一、队伍训练情况

　　no response

二、个人训练情况

　　刷了PTA和51Nod的一些题。

三、近况总结

　　开学比赛状况不是很理想，之后自己刷了一些题。后面蓝桥杯省一，天梯赛151，尚可，需要准备蓝桥杯国赛和江苏省省赛。

四、遇到的问题&可行的解决方案

　　第一，开学以来刷题疯狂减少，第一二周刷了几十道题，但这几周几乎没怎么刷题。解决方案为重新规划日常安排。

　　第二，开学后的几场比赛可能对心态有影响。要意识到这些比赛能够打出成绩是由于大部分题是简单的模拟，而自己对于很多算法还没有掌握，这些比赛并不能说明自己的水平。

五、对未来的规划

　　在日常规划方面，抽出时间来学习算法和做题，一到两周后准备队伍的磨合和训练。

发表于 更新于 分类于 ，
本文字数： 432 阅读时长 ≈ 1 分钟

1、long long=int*int，会数据溢出，直接定义long long或者long long*=long long。（51Nod 1082）

2、不要再忘记题目条件了！输出No Solution！！！！（51Nod 1090）

3、二分答案可以在修改边界的过程中留一个ans=mid，要向上取整可以（n+mod-1）%mod，注意不要除以0。（POJ3104）

4、别人的程序初始化要看清楚。。。（POJ2976）

5、变量的重名问题！！！

6、重新检查题意！

7、不要偷懒，例如输入两个-1结束，就去判两个-1。

8、有时需要考虑给的数据是否满足前一个小于后一个，题目中不说可能不满足。

9、贪心和二分的正确性，有点玄学。

10、多组输入注意不要提前break掉，开平方不要开复数。（POJ1328）

11、注意修改变量的顺序！！！比如去掉最大公约数要先提取到一个变量，不能两次调用函数！！！

12、循环i套i。

update: 太傻了，不更新了，反正也不太会回来看，刷点题睡个好觉状态就有了。

发表于 更新于 分类于 ，
本文字数： 467 阅读时长 ≈ 1 分钟

俗称马拉车算法->_->

处理最长回文字串复杂度O(n)

这里菜鸡不会证，简单说一下思路。

由于回文串有奇有偶，所以将串之间和两边加上'#'，为了防止后面某个地方超边界，新串0位置加上$。这样每个回文子串为#a#b#a#形式，必定奇数个，且原子串长度为新字串半径减一，求这个半径p[i]。（即p[i]是以i为中心的最长回文字串的半径）

i从1到n，过程中维护一个id点(id<i，i拉着id走，马拉车)，它是某个回文子串的中心，这个字串右边界是当前最大的。（p[i]是半径，故i+p[i]为边界）

那么当右边界比i还大时，就可以根据对称性，找到i关于id的对称点j=2*id-i，来优化找字串的过程。怎么优化呢？在id管辖范围内，p[i]和p[j]情况是相同的。由于超出id右边界的的地方不符合对称性，因此p[i]=p[j]当且仅当p[j]小于等于j-(id-p[id])（即j串的左边界不超出id串的左边界），否则只能直接到id右边界，p[i]=mx-i，之后的手动算。

如果id右边界太小，不能做优化，也得手动算。

以下代码：

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define ll long long
using namespace std;
char s[100020],sn[200020];
int p[200020];
int init(){
    int len=strlen(s);
    sn[0]='$';sn[1]='#';
    int j=2;
    for(int i=0;i<len;i++){
        sn[j++]=s[i];
        sn[j++]='#';
    }
    sn[j]='\0';
    return j;
}
int Manacher(){
    int len=init();
    int mx_len=-1,id,mx=0;
    for(int i=1;i<len;i++){
    if(i<mx){
        p[i]=min(p[2*id-i],mx-i);
    }
    else{
        p[i]=1;
    }
    while(sn[i-p[i]]==sn[i+p[i]]) p[i]++;
        if(p[i]+i>mx){
            id=i;
            mx=p[i]+i;
        }
        mx_len=max(mx_len,p[i]-1);
    }
    return mx_len;
}
int main(){
    cin>>s;
    cout<<Manacher();
    return 0;
}

发表于 更新于 分类于 ，
本文字数： 575 阅读时长 ≈ 1 分钟

一、归并排序

递归思路，将一个序列二分，使前半段有序，使后半段有序，然后使用双指针扫一遍使整段有序。

对于n个元素，每个元素都在排序1个元素，2个元素，4个元素，8个元素......的时候出现，因此复杂度是O(nlogn)。

二、求逆序数

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。

如2 4 3 1中，2 1，4 3，4 1，3 1是逆序，逆序数是4。给出一个整数序列，求该序列的逆序数。

输入

第1行：N，N为序列的长度（n <= 50000)
第2 - N + 1行：序列中的元素（0 <= A[i] <= 10^9）

输出

输出逆序数
阅读全文 »

发表于 更新于 分类于 ，
本文字数： 1k 阅读时长 ≈ 2 分钟

给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。

比如两个串为：

abcicba

abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

输入

第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出

输出最长的子序列，如果有多个，随意输出1个。
阅读全文 »

发表于 更新于 分类于 ，
本文字数： 527 阅读时长 ≈ 1 分钟

终于下定决心不碰运气写二分了。。。

思路比较乱，建议直接点进参考①

来说一下我记忆的方法

注意left<=right

首先标准查找是随机的找到一个，分三类，找不到返回-1

然后如果要找第一个和最后一个，因为是准确查找，所以要有判别和找不到返回-1

里面的大于还是大于等于，要具体分析。（分析相等的时候向左找还是向右找，返回谁）

举个例子

寻找最后一个相等的，没有的话找比key小的最后一个（searchLastEqualOrSmaller）

这两个元素的位置都是偏右（比如说{1,2,3,4,4,4,5,6}，分成1,2,3|4,4,4|5,6，3和最后一个4都在所在区间的右边），因此要向右找，让相等的情况跟着缩小左边界，因此是大于

解释一下为什么返回right，根据while结束条件，最后right<right，如果没有相等的，arr[right]<key<arr[left]，否则，key==arr[right]<arr[left]（所以返回left就是比key大的第一个）

大于等于同理

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
80
81
82
83
84
85
86
87
88
89
90
91
 1 //递增 
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 int search(int *arr,int n,int key){
 8     int left=0,right=n-1;
 9     while(left<=right){
10         int mid=(left+right)>>1;
11         if(arr[mid]==key) return mid;
12         else if(arr[mid]>key) right=mid-1;
13         else left=mid+1;
14     }
15     return -1;
16 }
17 int searchFirstEqual(int *arr,int n,int key){
18     int left=0,right=n-1;
19     while(left<=right){
20         int mid=(left+right)>>1;
21         if(arr[mid]>=key) right=mid-1;
22         else left=mid+1;
23     }
24     if(left<n&&arr[left]==key){
25         return left;
26     }
27     return -1;
28 }
29 int searchLastEqual(int *arr,int n,int key){
30     int left=0,right=n-1;
31     while(left<=right){
32         int mid=(left+right)>>1;
33         if(arr[mid]>key) right=mid-1;
34         else left=mid+1;
35     }
36     if(right>=0&&arr[right]==key){
37         return right;
38     }
39     return -1;
40 }
41 int searchLastEqualOrSmaller(int *arr,int n,int key){
42     int left=0,right=n-1;
43     while(left<=right){
44         int mid=(left+right)>>1;
45         if(arr[mid]>key) right=mid-1;
46         else left=mid+1;
47     }
48     return right;
49 }
50 int searchLastSmaller(int *arr,int n,int key){
51     int left=0,right=n-1;
52     while(left<=right){
53         int mid=(left+right)>>1;
54         if(arr[mid]>=key) right=mid-1;
55         else left=mid+1;
56     }
57     return right;
58 }
59 int searchFirstEqualOrLarger(int *arr,int n,int key){
60     int left=0,right=n-1;
61     while(left<=right){
62         int mid=(left+right)>>1;
63         if(arr[mid]>=key) right=mid-1;
64         else left=mid+1;
65     }
66     return left;
67 }
68 int searchFirstLarger(int *arr,int n,int key){
69     int left=0,right=n-1;
70     while(left<=right){
71         int mid=(left+right)>>1;
72         if(arr[mid]>key) right=mid-1;
73         else left=mid+1;
74     }
75     return left;
76 }
77 
78 int main(){
79     int arr[17] = {1, 
80                    2, 2, 5, 5, 5, 
81                    5, 5, 5, 5, 5, 
82                    5, 5, 6, 6, 7};
83     printf("First Equal           : %2d \n", searchFirstEqual(arr, 16, 5));
84     printf("Last Equal            : %2d \n", searchLastEqual(arr, 16, 5));
85     printf("First Equal or Larger : %2d \n", searchFirstEqualOrLarger(arr, 16, 5));
86     printf("First Larger          : %2d \n", searchFirstLarger(arr, 16, 5));
87     printf("Last Equal or Smaller : %2d \n", searchLastEqualOrSmaller(arr, 16, 5));
88     printf("Last Smaller          : %2d \n", searchLastSmaller(arr, 16, 5));
89     return 0;
90     return 0;
91 }

View Code

参考：①你真的会写二分查找吗 - luoxn28 - 博客园

②你真的会写二分检索吗？-liubird- ChinaUnix博客（测试段代码来源）