Rainy2k
0%

其他

Posted on Edited on

暂未分类的题目

暴力/练习

https://codeforces.com/contest/1293/problem/D

注意:t≤1016t \leq 10^{16},要将inf设置成101710^{17}

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1000;
const ll limit = 1e17;
ll x[maxn], y[maxn];

int main() {
    ll  ax, bx, ay, by;
    ll xs, ys, t;
    cin >> x[0] >> y[0] >> ax >> ay >> bx >> by >> xs >> ys >> t;
    int cnt = 0;
    while(x[cnt]<(limit-bx+1)/ax&&y[cnt]<(limit-by+1)/ay) {
        cnt++;
        x[cnt] = x[cnt - 1] * ax + bx;
        y[cnt] = y[cnt - 1] * ay + by;
    }
    ll ans = 0;
    for (int i = 0; i <= cnt;i++) {
        for (int j = 0; j <= cnt;j++) {
            ll a = abs(xs - x[i]) + abs(ys - y[i]);
            ll b = abs(x[i] - x[j]) + abs(y[i] - y[j]);
            if(a<=t-b) {
                ll m = abs(i - j) + 1;
                ans = max(ans, m);
            }
        }
    }
    cout << ans << endl;
}

中缀表达式 Bracket Sequence

https://nanti.jisuanke.com/t/43466

就是算一下

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
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int maxn = 3e5+10;
vector<long long> v[maxn];
int num(string s) {
    int len = s.size();
    int ret = 0;
    for (int i = 0; i < len;i++) {
        ret = ret * 10 + s[i] - '0';
    }
    return ret;
}
int main() {
    int n;
    scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n;i++) {
        string s;
        cin >> s;
        if(s[0]=='(') {
            cnt++;
        } 
        else if(s[0]==')') {
            if(cnt%2==0) {
                long long x = 0;
                while(v[cnt].size()) {
                    x += v[cnt].back();
                    x %= mod;
                    v[cnt].pop_back();
                }
                cnt--;
                v[cnt].push_back(x);
            }
            else {
                long long x = 1;
                while(v[cnt].size()) {
                    x *= v[cnt].back();
                    x %= mod;
                    v[cnt].pop_back();
                }
                cnt--;
                v[cnt].push_back(x);
            }
        }
        else{
            int x = num(s);
            v[cnt].push_back(x);
        }
    }

    long long ans = 0;
    while(v[0].size()) {
        ans = ans + v[0].back();
        ans %= mod;
        v[0].pop_back();
    }
    printf("%lld\n", ans);
}

[CF1175B] catch overflow

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<bits/stdc++.h>
using namespace std;
const long long limit = ((long long)1 << 32) - 1;

int main() {
    int n;
    scanf("%d", &n);
    long long ans = 0,t = 1;
    int f = 0, cnt = 0;
    vector<long long> v;
    for (int i = 1; i <= n;i++) {
        string s;
        cin >> s;
        if(s[0]=='a') {
            ans += t;
            if(ans>limit) {
                f = 1;
            }
        }
        if(s[0]=='f'){
            int x;
            scanf("%d", &x);
            if(t>limit){
                cnt++;
                continue;
            }
            t *= x;
            v.push_back(x);
        }
        if(s[0]=='e') {
            if(cnt==0){
                t /= v.back();
                v.pop_back();
            }
            else
                cnt--;
        }
    }
    if(f)
        printf( "OVERFLOW!!!\n" );
else
    cout << ans << endl;
}

NowCoder 非递归实现组合型枚举

模拟汇编的操作

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
vector<int> v;
int n, m;
int st[maxn], address, top;
/*
void cal(int x){//参数x表示当前选择的数字
    if(v.size()>m||v.size()+(n-x+1)<m)
        return;
    if(x==n+1){
        for (int i = 0; i < v.size();i++){
            printf("%d ", v[i]);
        }
        printf("\n");
        return;
    }
    //选x
    v.push_back(x);
    cal(x + 1);
    //不选x
    v.pop_back();
    cal(x + 1);
    return;
}*/

void cal(int x,int ret_addr){//新指令(数字)进栈
    int old_top = top;
    st[++top] = x;
    st[++top] = ret_addr;
    st[++top] = old_top;
}
int ret(){
    int ret_addr = st[top - 1];
    top = st[top];//让最后一条语句出栈
    return ret_addr;
}
int main(){
    cin >> n >> m;
    cal(1, 0);//数字1进栈
    while(top){
        int x = st[top - 2]; //获取的是数字x
        switch(address){
            case 0:
                if(v.size()>m||v.size()+(n-x+1)<m){
                    address = ret(); //也就是return;
                    continue;
                }
                if(x==n+1){
                    for (int i = 0; i < v.size();i++){
                        printf("%d ", v[i]);
                    }
                    printf("\n");
                    address = ret();
                    continue;
                }
                v.push_back(x);
                cal(x + 1, 1);
                address = 0;
                continue;
            case 1:
                v.pop_back();
                cal(x + 1, 2);//返回后从cas2继续执行
                address = 0;
                continue;
            case 2:
                address = ret();
        }
    }
}

其他

语法

断言

1
2
3
4
5
6
int a = 0;
assert(a==0);
程序正常运行
    
assert(a==1);
会报出错误,也就是说我所断言的a==1是错误的

最大子段和

1
2
3
4
5
6
7
int best=0,sum=0;
for(int i=0;i<n;i++)
{
    sum=max(array[i],sum+array[k]);
    best=max(sun,best);
}
cout<<best<<endl;

双指针问题

[CF1304D]Shortest and Longest LIS

https://codeforces.com/contest/1304/problem/D

构造最长LIS时,要从最小的数开始填

构造最长LIS时,要从最大的数开始填

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;

const int maxn = 2e5 + 100;
int ans[maxn];
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;string s;
        cin >> n >> s;
        int num = n, last = 0;
        for (int i = 0; i < n;i++) {
            if(i==n-1||s[i]=='>') {
                for (int j = i; j >= last;j--) {
                    ans[j] = num--;
                }
                last = i + 1;
            }
        }
        for (int i = 0; i < n;i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        num = 1, last = 0;
        for(int i=0;i<n;i++) {
            if(i==n-1||s[i]=='<') {
                for (int j = i; j >= last;j--) {
                    ans[j] = num++;
                }
                last = i + 1;
            }
        }
        for (int i = 0; i < n;i++) {
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
}

[CF1199C] mp3

这题神烦

https://codeforces.com/contest/1199/problem/C

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<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 4e5 + 100;
vector<int> v;
map<int, int> mp;
int pre[maxn];
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    k *= 8;
    int m = 0;
    for (int i = 1; i <= n;i++) {
        int x;
        scanf("%d", &x);
        if(!mp[x]) {
            v.push_back(x);
        }
        mp[x]++;
    }
    sort(v.begin(), v.end());
    m = unique(v.begin(), v.end())-v.begin();
    int tot = k / n;
    if(tot>20)
        tot = 20;
    tot = 1 << tot;
    for (int i = 0; i < m;i++){
        if(i==0)
            pre[i] = mp[v[i]];
        else
            pre[i] = pre[i - 1] + mp[v[i]];
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i < m;i++) {
        int j = i + tot - 1;
        int x = 0;
        if(i!=0)
            x = pre[i - 1];
        if(j>=m) {
            ans = min(ans, x);
            break;
        }
        int y = pre[j];
        ans = min(ans, pre[m - 1] - y + x);
    }
    ans = max(ans, 0);
    cout<<ans<<endl;
}