A - Profitable Interest Rate

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
int a,b;cin>>a>>b;
if(a>=b){
cout<<a<<"\n";
}else{
int k=2*a-b;
if(k>0){
cout<<k<<"\n";
}else{
cout<<0<<"\n";
}
}
}

B - Buying Lemonade

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
int n,k;cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
int sum=0,ans=0,mn=0;
for(int i=0;i<n;i++){
a[i]-=mn;
if(sum+a[i]*(n-i)<k){
sum+=a[i]*(n-i);
mn+=a[i];ans+=a[i]*(n-i);
}else{
ans+=k-sum;
break;
}
ans++;
}
cout<<ans<<"\n";
}

C - Concatenation of Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
int n;cin>>n;
vector<array<int,3>>a(n);
for(int i=0;i<n;i++){
cin>>a[i][0]>>a[i][1];
a[i][2]=a[i][0]+a[i][1];
}
sort(a.begin(),a.end(),[&](auto l,auto r){
if(l[2]!=r[2])return l[2]<r[2];
else return min(l[0],l[1])<min(r[0],r[1]);
});
for(int i=0;i<n;i++){
cout<<a[i][0]<<" "<<a[i][1]<<" ";
}
cout<<"\n";
}

D - Skipping

只有答题才能得分,所以跳题相当于花费a[i]从位置i转移到b[i]

答题就是花费0从i转移到i-1

最终答案就是所有能遍历到的位置上的a[i]-cost[i]

b[i]小于等于i时选择跳过是不明智的,因为此时在到达b[i]的过程中通过答题到b[i]能获得的分数一定更大

i 到 j 有两种方法,第一种是 j=b[i],直接从 i 跳到 j ;第二种是 i<j<b[i] ,从 i 跳到 b[i] 再向左答题到 j,两种方法的花费都是a[i],

所以我们遍历所有位置,每次取能到当前位置且花费最小,转移到当前位置求每个能遍历到的位置的最小花费

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
void solve(){
int n;cin>>n;
vector<pair<int,int>>a(n+1);
for(int i=1;i<=n;i++) cin>>a[i].first;
for(int i=1;i<=n;i++) cin>>a[i].second;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push({a[1].first,a[1].second});
vector<int>dp(n+1,1e18);
dp[1]=0;
for(int i=2;i<=n;i++){
while(pq.size()&&pq.top().second<i){
pq.pop();
}
if(pq.empty()){
break;
}
dp[i]=pq.top().first;
if(a[i].second>i){
pq.push({dp[i]+a[i].first,a[i].second});
}
}
int sum=0,ans=0;
for(int i=1;i<=n;i++){
sum+=a[i].first;
ans=max(ans,sum-dp[i]);
}
cout<<ans<<"\n";
}

A - Sakurako and Kosuke

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve(){
int n;cin>>n;
int m=1,cnt=0;
for(int i=1;;i++){
if(i&1){
cnt-=(2*i-1);
}else{
cnt+=(2*i-1);
}
if(abs(cnt)<=n){
continue;
}else{
m=i;
break;
}
}
cout<<(m&1?"Kosuke":"Sakurako")<<"\n";
}

B - Sakurako and Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
int n;cin>>n;
vector<vector<int>>g(n+1,vector<int>(n+1));
map<int,vector<int>>mp;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>g[i][j];
if(g[i][j]<0){
mp[i-j].push_back(abs(g[i][j]));
}
}
}
int ans=0;
for(auto &[x,y]:mp){
sort(y.begin(),y.end(),greater<int>());
ans+=y[0];
}
cout<<ans<<"\n";
}

C - Sakurako’s Field Trip

C这个题有一点说法,其实想明白什么时候换就可以

从左到n/2的位置每次考虑是否交换当前位置,当i这个位置与i-1的数相同的时候或者n-i+1与其下一个数(就是当前数与其遍历过的上一个数)相同的时候选择交换,可以证明这样操作对答案的增益一定是非负的

证明如下

  1. 如果a[i]==a[n-i+1],操作无影响

  2. a[i]!=a[n-i+1],

    设交换之前点i对答案的增益为 ans=(a[i]==a[i-1]+a[i]==a[i+1]+a[n-i+1]==a[n-i]+a[n-i+1]==a[n-i+2])

    交换之后点i对答案的增益为 ans1=(a[n-i+1]==a[i-1]+a[n-i+1]==a[i+1]+a[i]==a[n-i]+a[i]==a[n-i+2])

    最坏情况就是

    a[i]==a[i-1]&&a[i]!=a[i+1]&&a[n-i+1]!=a[n-i]&&a[n-i+1]!=a[n-i+2]

    a[n-i+1]==a[i+1]&&a[i]==a[n-i]&&a[i]==a[n-i+2]

    这样的话,交换之后答案多2,但是这种情况下在下一次交换过程中会被重新满足条件执行交换

综上,一直执行交换,最后求答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
int n;cin>>n;
vector<int>a(n+10,0),cnt(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
for(int i=1;i<=(n+1)/2;i++){
if(a[i]==a[i-1]||a[n-i+1]==a[n-i+2]){
swap(a[i],a[n-i+1]);
}
}
for(int i=1;i<=n-1;i++){
if(a[i]==a[i+1]) ans++;
}
cout<<ans<<"\n";
}

D - Kousuke’s Assignment

没啥说的,遇到0就断开一定是最优的

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
void solve(){
int n;cin>>n;
vector<int>a(n+1),pre(n+1,0);
for(int i=1;i<=n;i++){
cin>>a[i];
pre[i]=pre[i-1]+a[i];
}
int ans=0,lst=0;
map<int,int>mp;
for(int i=1;i<=n;i++){
if(a[i]==0){
lst=i;ans++;
continue;
}
int d=pre[i]-pre[lst];
if(d==0){
if(lst<i){
ans++;
lst=max(i,lst);
}
}else if(mp.count(d)){
if(lst<mp[d]){
ans++;
lst=max(i,lst);
}
}
mp[d]=i;
}
cout<<ans<<'\n';
}

E - Sakurako, Kosuke, and the Permutation

每次交换完之后就保证当前位置不再交换,这样顺序从1到n就是最小交换次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
int n;cin>>n;
vector<int>a(n+1),pos(n+1);
for(int i=1;i<=n;i++){
cin>>a[i];
pos[a[i]]=i;
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==i) continue;
if(pos[i]==a[i]&&a[a[i]]==i) continue;
swap(a[pos[i]],a[a[i]]);
swap(pos[a[pos[i]]],pos[a[a[i]]]);
ans++;
}
cout<<ans<<"\n";
}

F - Kosuke’s Sloth

递推数列具有模周期性,找到第一个循环节中的下标再乘n即可

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
int n,k;cin>>n>>k;
f[1]=f[2]=1;
int pos=0;
for(int i=1;;i++){
if(i>=3) f[i]=(f[i-1]+f[i-2])%k;
if(f[i]%k==0){
pos=i;
break;
}
}
cout<<(pos%mod)*(n%mod)%mod<<"\n";
}



XCPC 基础

对拍板子

介绍Windows环境下与Linux环境下的对拍

对拍去DEV

Windows环境

以DEV为例,首先建四个源代码到一个新建文件夹中,源代码分别命名为wa.cpp,data.cpp,violent.cpp,windows.cpp,除此之外什么也不需要添加

  1. 一份错误的/需要比对的代码,导入wa.cpp
  2. 一份暴力的/用来比对的代码,导入violent.cpp
  3. 一份用来造数据的代码
  4. 一份执行对拍程序的代码

wa.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("in.txt", "r", stdin); //读入数据生成器造出来的数据
freopen("wa.txt", "w", stdout); //输出答案
//下方注释为你的程序
/*
int a, b;
cin >> a >> b;
cout << a;
*/
return 0;
}

violent.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("in.txt", "r", stdin); //读入数据生成器造出来的数据
freopen("violent.txt", "w", stdout); //输出答案
//下方程序为你已经导入的程序
/*
int a, b;
cin >> a >> b;
cout << a + b;
*/
return 0;
}

data.cpp

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main() {
struct _timeb T;
_ftime(&T);
srand(T.millitm); //获得毫秒,减小运行时间
int a = rand(); //此时a是一个随机数字
printf("%d\n", a);
}

windows.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
while (1) { //一直循环,直到找到不一样的数据
system("data.exe");
system("violent.exe");
system("wa.exe");
if (system("fc wa.txt violent.txt")) //当 fc 返回 1 时,说明这时数据不一样
break; //不一样就跳出循环
}
return 0;
}

注意,以上所有程序均需要编译并运行

前缀和(Prefix Sum)

通过构建前缀和数组,从而能做到O(1)时间复杂度的区间查询(rangeQuery)

一维前缀和

构建前缀和数组

1
2
vector<int>pre(n+1,0);
for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];

rangeQuery

1
pre[r]-pre[l-1]//求(l,r)区间和

二维前缀和

构建前缀和数组

1
2
3
4
5
6
7
vector<vector<int>>pre(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
//pre[i][j]表示(1,1)为左上角,(i,j)为右下角的矩阵的和
}
}

rangeQuery

1
2
pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
//求左上角为(x1,y1),右下角为(x2,y2)的矩阵和

差分(Difference)

通过构建差分数组,从而能做到O(1)时间复杂度的区间修改(rangeModify)

一维差分

  1. 单点修改,单点询问

构建差分数组

1
2
vector<int>dif(n+5);
for(int i=1;i<=n;i++) dif[i]=a[i]-a[i-1];

rangeModify

1
dif[l]+=k;dif[r+1]-=k;//(l,r)区间每个数都加k

Query

1
for(int i=1;i<=n;i++) b[i]+=b[i-1];//此时b[i]就是修改完后的第i个数的值
  1. 单点修改,区间询问

    具体就是构建两个差分数组,每次单点修改的左端加1,右端也加1,全部操作执行完求前缀和,区间询问[l,r]的时候相减即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    vector<int>L(n+10),R(n+10);
    for(int i=0;i<k;i++){
    int u,v;cin>>u>>v;
    L[u]++;R[v]++;
    }
    for(int i=1;i<=n;i++) {
    L[i]+=L[i-1];
    R[i]+=R[i-1];
    }
    for(int i=1;i<=k;i++){
    int l,r;cin>>l>>r;
    cout<<R[r]-L[l-1]<<"\n";
    }

二维差分

与一维差分不同的是,二维差分数组的构建与修改均可以通过差分函数来完成

1
2
3
4
5
6
7
vector<vector<int>>dif(n+5,vector<int>(m+5));
auto modify=[&](int x1,int y1,int x2,int y2,int x){
dif[x1][y1]+=x;
dif[x1][y2+1]-=x;
dif[x2+1][y1]-=x;
dif[x2+1][y2+1]+=x;
};

构建差分数组

1
2
3
4
5
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
modify(i,j,i,j,a[i][j]);
}
}

rangeModify

1
modify(x1,y1,x2,y2,x);//对左上角为(x1,y1),右下角为(x2,y2)的矩阵每个数都加上x

Query

前缀和求

1
2
3
4
5
6
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dif[i][j]+=dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];
//pre[i][j]表示(1,1)为左上角,(i,j)为右下角的矩阵的和
}
}

间隔差分

[l,r]中间隔k个数字修改,其中r=l + k * n, 相当于[l,l+k,l+2 * k,… l + n * k]这么多数修改

构建差分数组

1
pre[l]++;pre[r]--;//注意此时一定是最右侧的点进行减,不是最右边减一

求和

1
2
3
4
5
for(int i=1;i<=sum;i++)//sum为整个数组大范围,写成这样,即使多次修改区间也能在一次遍历的时间里算完

for(int i=k;i<=sum;i++){
​ pre[i]+=pre[i-k];
}

高精度

版本一 太全,不实用

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
const int MAXN = 5005;//位数
struct bign{
int len, s[MAXN];
bign (){
//初始化
memset(s, 0, sizeof(s));
len = 1;
}
bign (int num) { *this = num; }
bign (const char *num) { *this = num; } //让this指针指向当前字符串
bign operator = (const int num){
char s[MAXN];
sprintf(s, "%d", num); //sprintf函数将整型映到字符串中
*this = s;
return *this; //再将字符串转到下面字符串转化的函数中
}
bign operator = (const char *num){
for(int i = 0; num[i] == '0'; num++) ; //去前导0
len = strlen(num);
for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; //反着存
return *this;
}
bign operator + (const bign &b) const{
//对应位相加,最为简单
bign c;
c.len = 0;
for(int i = 0, g = 0; g || i < max(len, b.len); i++){
int x = g;
if(i < len) x += s[i];
if(i < b.len) x += b.s[i];
c.s[c.len++] = x % 10; //关于加法进位
g = x / 10;
}
return c;
}
bign operator += (const bign &b){
//如上文所说,此类运算符皆如此重载
*this = *this + b;
return *this;
}
void clean(){
//由于接下来的运算不能确定结果的长度,先大而估之然后再查
while(len > 1 && !s[len-1]) len--; //首位部分‘0’故删除该部分长度
}
bign operator * (const bign &b){
//乘法重载在于列竖式,再将竖式中的数转为抽象,即可看出运算法则。
bign c;
c.len = len + b.len;
for(int i = 0; i < len; i++){
for(int j = 0; j < b.len; j++){
c.s[i+j] += s[i] * b.s[j];//不妨列个竖式看一看
}
}
for(int i = 0; i < c.len; i++){
//关于进位,与加法意同
c.s[i+1] += c.s[i]/10;
c.s[i] %= 10;
}
c.clean(); //我们估的位数是a+b的长度和,但可能比它小(1*1 = 1)
return c;
}
bign operator *= (const bign &b){
*this = *this * b;
return *this;
}
bign operator - (const bign &b){
//对应位相减,加法的进位改为借1
//不考虑负数
bign c;
c.len = 0;
for(int i = 0, g = 0; i < len; i++){
int x = s[i] - g;
if(i < b.len) x -= b.s[i]; //可能长度不等
if(x >= 0) g = 0; //是否向上移位借1
else{
g = 1;
x += 10;
}
c.s[c.len++] = x;
}
c.clean();
return c;
}
bign operator -= (const bign &b){
*this = *this - b;
return *this;
}
bign operator / (const bign &b) {
//运用除是减的本质,不停地减,直到小于被减数
bign c, f = 0; //可能会在使用减法时出现高精度运算
for(int i = len-1; i >= 0; i--){
//正常顺序,从最高位开始
f = f*10; //上面位的剩余到下一位*10
f.s[0] = s[i]; //加上当前位
while(f >= b){
f -= b;
c.s[i]++;
}
}
c.len = len; //估最长位
c.clean();
return c;
}
bign operator /= (const bign &b){
*this = *this / b;
return *this;
}
bign operator % (const bign &b){
//取模就是除完剩下的
bign r = *this / b;
r = *this - r*b;
r.clean();
return r;
}
bign operator %= (const bign &b){
*this = *this % b;
return *this;
}
bool operator < (const bign &b){
//字符串比较原理
if(len != b.len) return len < b.len;
for(int i = len-1; i != -1; i--){
if(s[i] != b.s[i]) return s[i] < b.s[i];
}
return false;
}
bool operator > (const bign &b){
//同理
if(len != b.len) return len > b.len;
for(int i = len-1; i != -1; i--){
if(s[i] != b.s[i]) return s[i] > b.s[i];
}
return false;
}
bool operator == (const bign &b){
return !(*this > b) && !(*this < b);
}
bool operator != (const bign &b){
return !(*this == b);
}
bool operator <= (const bign &b){
return *this < b || *this == b;
}
bool operator >= (const bign &b){
return *this > b || *this == b;
}
string str() const{
//将结果转化为字符串(用于输出)
string res = "";
for(int i = 0; i < len; i++) res = char(s[i]+'0')+res;
return res;
}
};
istream& operator >> (istream &in, bign &x){
//重载输入流
string s;
in >> s;
x = s.c_str(); //string转化为char[]
return in;
}
ostream& operator << (ostream &out, const bign &x){
//重载输出流
out << x.str();
return out;
}

声明方式

1
2
3
bign a;//除了声明外其他如整型般使用
a="333333333333333333333333333";
cout<<a*a<<endl;

版本二

STL

int128库函数自定义

int128范围是$-2^{127}-2^{127-1}$

unsigned int128范围是$0-2^{128}$,约39位数

给int128 赋初值不能直接用一个很大的数字,比如1E100,这样赋出来是LONG_LONG_MAX

可以使用字符串,然后一直累乘

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
using i128 = __int128;

ostream &operator<<(ostream &os, i128 n) {
if (n == 0) {
return os << 0;
}
string s;
while (n > 0) {
s += char('0' + n % 10);
n /= 10;
}
reverse(s.begin(), s.end());
return os << s;
}

i128 toi128(const string &s) {
i128 n = 0;
for (auto c : s) {
n = n * 10 + (c - '0');
}
return n;
}

i128 sqrti128(i128 n) {
i128 lo = 0, hi = 1E16;
while (lo < hi) {
i128 x = (lo + hi + 1) / 2;
if (x * x <= n) {
lo = x;
} else {
hi = x - 1;
}
}
return lo;
}

i128 gcd(i128 a, i128 b) {
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}

常用库函数重载

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
using i64 = long long;
using i128 = __int128;

/**
上取整下取整
**/
i64 ceilDiv(i64 n, i64 m) {
if (n >= 0) {
return (n + m - 1) / m;
} else {
return n / m;
}
}

i64 floorDiv(i64 n, i64 m) {
if (n >= 0) {
return n / m;
} else {
return (n - m + 1) / m;
}
}

/**
最大值赋值
**/
template<class T>
void chmax(T &a, T b) {
if (a < b) {
a = b;
}
}

/**
最大公约数
**/
i128 gcd(i128 a, i128 b) {
return b ? gcd(b, a % b) : a;
}

/**
精确开平方
**/
i64 sqrt(i64 n) {
i64 s = std::sqrt(n);
while (s * s > n) {
s--;
}
while ((s + 1) * (s + 1) <= n) {
s++;
}
return s;
}

/**
精确开平方
**/
i64 get(i64 n) {
i64 u = std::sqrt(2.0L * n);
while (u * (u + 1) / 2 < n) {
u++;
}
while (u * (u - 1) / 2 + 1 > n) {
u--;
}
return u;
}

/**
求 Log
**/
int logi(int a, int b) {
int t = 0;
i64 v = 1;
while (v < b) {
v *= a;
t++;
}
return t;
}

int llog(int a, int b) {
if (a <= b) {
int l = logi(a, b);
return (l == 0 ? 0 : std::__lg(2 * l - 1));
}
int l = logi(b, a + 1) - 1;
assert(l > 0);
return -std::__lg(l);
}

sqrt

对long long使用sqrt,类型转换为long double

1
x=(long double)sqrt(x);//x为long long类型

pdbs

头文件及命名空间,注意编译器开g++

1
2
3
#include <bits/extc++.h> //类似万能头,包含大多扩展库
using namespace __gnu_cxx;
using namespace __gnu_pbds;

平衡二叉树常见成员函数

1
2
3
4
5
6
7
8
empty() / size()
insert(x) // 插入元素x
erase(x) // 删除元素/迭代器x
order_of_key(x) // 返回元素x的排名
find_by_order(x) // 返回排名为x的元素迭代器
lower_bound(x) / upper_bound(x) // 返回迭代器
join(Tree) // 将Tree树的全部元素并入当前的树
split(x, Tree) // 将大于x的元素放入Tree树

代码

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
#include <bits/extc++.h>
using namespace __gnu_pbds;
bool Solve() {
using PII = pair<int, int>;
tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> ver;
map<int, int> dic;
int n; cin >> n;
while (n--) {
int op, x;
cin >> op >> x;
if (op == 1) { // 插入一个元素x,允许重复
ver.insert({x, ++dic[x]});
} else if (op == 2) { // 删除元素x,若有重复,则任意删除一个
ver.erase({x, dic[x]--});
} else if (op == 3) { // 查询元素x的排名(排名定义为比当前数小的数的个数+1)
cout << ver.order_of_key({x, 1}) + 1 << endl;
} else if (op == 4) { // 查询排名为x的元素
x--;
cout << ver.find_by_order(x)->first << endl;
} else if (op == 5) { // 查询元素x的前驱
int idx = ver.order_of_key({x, 1}) - 1; // 无论x存不存在,idx都代表x的位置,需要-1
cout << ver.find_by_order(idx)->first << endl;
} else if (op == 6) { // 查询元素x的后继
int idx = ver.order_of_key( {x, dic[x]}); // 如果x不存在,那么idx就是x的后继
if (ver.find({x, 1}) != ver.end()) idx++; // 如果x存在,那么idx是x的位置,需要+1
cout << ver.find_by_order(idx)->first << endl;
}
}
return 0;
}

防卡unordered_map

1
2
3
unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);

卡时

1
2
3
4
5
auto start=clock();//程序开头
auto time=clock();//中断点
clock在windows环境下单位为毫秒(*1000得秒)
在Linux环境下为微秒(*1000000得秒)
if(time-start>=900) break;//程序已经执行0.9s,中断退出

1

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
1.find(str,pos)//找到的返回下标,找不到返回string::npos
2.count//(起始位,终止位,目标物)
3.getline(cin,s)//整行读入,并将结果存储在字符串s里面
4.s.erase(pos,n)//把字符串s从pos开始的n个字符删除
5.mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//以实时时间作为种子产生一个64位数的随机数,调用的时候写rng(),可能为正也可能为负
6.__builtin_popcount( )//返回括号内数字二进制表达中1的个数
7.//二维map(以int为例)
map<int,map<int,int>>mp;
8.for (auto t : {"DFS", "dfs"}//t[0]有两个,是D和d。都等效为t[0]
9.substr(起始位置,长度)//用来截取string类型的字符串
10 s.replace(p0,n0,n,ch)//删除p0开始的n0个字符,然后在p0处插入n个字符ch
11.//在平面内,从(0,0)到点(x,y)的路径数f[x][y]=f[x-1][y]+f[x][y-1]
12.//ceil函数向上取整(对浮点)
13.// 0x7fffffff表示int类型的最大值(7个f)
14.//在数字前面补零 printf(“%050d”,n)-----格式化输出50位的n,不够的在前面补零。
15.//double型不能用位运算
16.// 用cout输出的时候Setprecision(p)表示保留有效数字p位
//再加fixed前面修饰可以改为保留小数点后p位
17.//setw用来设置字段宽度
18.//加0边ascll,减0变int,减‘a’求第几个位置,%26防止爆位
19.//类似对1e9+7取模要从一开始计算的时候就取,不能只对答案取模
20.//gcd(a,b)和lcm(a,b)在a,b最小的情况下就是a=gcd(a,b)与b=lcm(a,b);
21.//用k加 (1e9+7)再模1e9+7防止因k小于0造成的错误
22.//异或实际上就是二进制的不进位加法,异或同一个数两次相当于没有异或这个数
23.//iota配合sort实现单数组的多数组对应下标绑定排序
24..iota(起始位,末位,初始值)//用来批量递增赋值数组,增量为1
25.//用STL包括位运算可能爆int的时候记得写成0LL,1LL
26.//二分查找.lower_bound和upper找不到会返回数组最后一个元素下标+1
27.//清空标记形不要用vector,用C-array老实的memset
28.//iota配合sort执行结构化排序 举例
//iota(p.begin(),p.end(),0);
//sort(p.begin(),p.end(),[&](int i,int j){
// return a[i]<a[j];
//});
//该代码执行后是p中元素按照a的元素大小进行排序,a[p[0]]就是a中第0小的元素值
//p[0]就是这个第一小的元素在原数组中的坐标
29 //转移的时候,记得初始化所有的最左端点的前一个数(-1/0)
//所有的右端点初始化为右端点的后一个数(n/n+1)
30 //vector二分插入,保证数组有序
//a.insert(upper_bound(a.begin(),a.end(),x),x);
//insert是在迭代器前一个位置插入元素

进制转换

10进制转其他进制(n是数字,k是进制)

大于10的数字用字符表示

1
2
3
4
5
6
7
8
9
10
11
void solve(){
int n;cin>>n;
int k;cin>>k;
string ans;
while(n){
ans.push_back(n%k<10 ? n%k+'0' : n%k-10+'A');
n/=k;
}
reverse(ans.begin(),ans.end());
cout<<ans<<'\n';
}

其他进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<char,int>it;
int r,ans;
void init(){
int s=10;
for (char i='A';i<='Z';i++) {
it[i]=s++;
}
}
int main(){
string n;cin>>r>>n;
init();
for(int i=0;i<n.size();i++){
ans*=r;
if(isalpha(n[i])) ans+=it[n[i]];
else ans+=n[i]-'0';
}
cout<<ans<<endl;

字符串进制转化

1
2
stoi(s) //s需要是字符串,只能将string类型字符串转化为10进制,且不超过int范围
auto s=to_string(x)//将x转化为字符串形式

二分

左端点减1,右端点加1

基姆拉尔森计算公式

计算自1970年的某年某月某日是星期几

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

int daysInMonth(int y, int m) {
return d[m - 1] + (isLeap(y) && m == 2);
}

int getDay(int y, int m, int d) {
int ans = 0;
for (int i = 1970; i < y; i++) {
ans += 365 + isLeap(i);
}
for (int i = 1; i < m; i++) {
ans += daysInMonth(y, i);
}
ans += d;
return (ans + 2) % 7 + 1;
}

三分模板

整数三分

每次都将区间变为[l,mid1],(mid1,mid2],(mid2,r]三个区间
根据条件判断将l,r指针移动至哪个区间,复杂度为log以3为底(区间大小)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
int l=2,r=999;
while (l<r){
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
int s=query(mid1,mid2);
if (s == mid1 * mid2){
l = mid2 + 1;
}else if (s == mid1 * mid2 + mid1){
l = mid1 + 1;
r = mid2;
}else{
r = mid1;
}
}
cout << "! " << l << endl;
}

实数三分

1
2
3
4
5
6
7
8
9
10
11
12
13
const double eps = 1e-9;//根据条件判断
while(r - l < eps) {
double lmid = l + (r - l) / 3;
double rmid = r - (r - l) / 3;
lans = cal(lmid),rans = cal(rmid);
// 求凹函数的极小值
if(lans <= rans) r = rmid;
else l = lmid;
// 求凸函数的极大值
if(lans >= rans) l = lmid;
else r = rmid;
}
cout << l << endl;

Trick

比赛相关

  1. 认真读题至少2遍,必要时和队友确认题意
  2. 想思路前务必带入样例验证思路,否则请重复步骤1
  3. 初始化不要多次声明vector(特别是二分这种多次用到初始化的),用遍历的方式去赋初始值

切入点/典中典

  1. 子序列选择问题,暴力做法是枚举所有可能的子序列,当然这一定做不到,复杂度是$2^n$级别的

​ sol1 一般这类问题都可以通过dp解决,找到能够”拼接”起来的转移方程

​ sol2 通过组合数解决,注意应该直接计算保留的子序列方案数 not 删除的种类数

  1. q个询问此类问题一般都是复杂度O(1)[提前预处理],O(logn)[预处理后在线询问]

  2. 区间[l,r]询问,转换成前缀和处理,即pre[r]-pre[l-1]

  3. red求能组成多少个不同的red,只需要求每个’e’前面多少个r和后面多少个d,两者相乘即可

数论

  1. 将数x分开,每块最多t,分开的操作为拆成两个和为x的正整数,求次数
1
ans += (a[i] - 1) / t;
  1. 中位数就想二分
  2. 二进制乘以2,相当于整个数左移一位,末位补0,乘$2^{k}$就是左移k位
  3. 6x+8y+10z,取数不限可以遍历>=6的所有偶数
  4. 对于一个数组中的gcd,从左到右gcd如果递减,每次起码缩小一半(原因就是gcd一旦变化,一定会变成原有gcd的因数),所以gcd的变化是log级别的
  5. 递推数列具有模周期性,对于斐波那契数列,这个周期不会超过 60× 模数。
  6. 皮亚诺定理:模数为k的循环节长度不会超过6k
  7. 当题面给定数字范围可能超过long long的时候,首先应该想到按位贪心等算法,而不是高精度或i128

操作问题

  1. 数组中异或最终变成某个确定数的问题,可以使用前/后缀异或和的方法dp转移
  2. 循环移位 - 加长数组至2倍,然后直接找循环节出现的起始和结束位置
  3. $操作a_{i}-=1;a_{i+1}+=1$,无操作限制求极差,将使得序列变成不递减序列,二分求极大极小做差
  4. 操作$a_i+=x$,次数不限,最终要求到某个数/求mex…,可以用dp,dp[a[i]+x]+=(dp[$a[i]$]-1),或者对x取模,用map存储,

图论

  1. 有其他增项的最短路
  2. 有无某种特性可以点数*2为无,点数 *2+1为有

DEBUG

  1. 当程序连输入的数据都输出不来,就是程序中某段卡死了