2024 河南萌新联赛 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        unsigned long long n;
        cin>>n;
        long long ans=floor(sqrt(n));
        cout<<ans<<endl;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <bits/stdc++.h>
using namespace std;
int main(){
    int f[1000005],mod=1e9+7;
    f[0]=f[1]=1;
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=3;j++){
            if(i-j<0)break;
            f[i]=(f[i]+f[i-j])%mod;
        }
    }
    cout<<f[n]<<endl;
}

 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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
#define ls (now << 1)
#define rs (now << 1 | 1)
#define int long long

int n, m;
int a[N];

struct Node {
    int len, sum, tag;
} tr[N << 2];

Node operator + (const Node &l, const Node &r) {
    Node a;
    a.sum = l.sum + r.sum;
    a.tag = 0;
    a.len = l.len + r.len;
    return a;
}

void update(int now) {
    tr[now] = tr[ls] + tr[rs];
}

void settag(int now, int k) {
    tr[now].tag += k;
    tr[now].sum += tr[now].len * k;
}

void pushdown(int now) {
    if (tr[now].tag) {
        settag(ls, tr[now].tag);
        settag(rs, tr[now].tag);
        tr[now].tag = 0;
    }
}

void build(int now, int l, int r) {
    if (l == r) {
        tr[now] = {1, a[l], 0};
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(now);
}

void modify(int now, int l, int r, int s, int t, int val) {
    if (l <= s && r >= t) {
        settag(now, val);
        return;
    }
    pushdown(now);
    int mid = (s + t) >> 1;
    if (l <= mid) modify(ls, l, r, s, mid, val);
    if (r > mid) modify(rs, l, r, mid + 1, t, val);
    update(now);
}

int query(int now, int l, int r, int s, int t) {
    if (l <= s && r >= t) return tr[now].sum;
    pushdown(now);
    int mid = (s + t) >> 1;
    int ans = 0;
    if (l <= mid) ans += query(ls, l, r, s, mid);
    if (r > mid) ans += query(rs, l, r, mid + 1, t);
    return ans;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    cin>>m;
    while (m--) {
        int op, x, y, z;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> z;
            modify(1, x, y, 1, n, z);
        } else {
            cin>>x;
            cout << query(1, x, x, 1, n) << endl;
        }
    }
    return 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
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
typedef long long ll;
const int N = 1e7 + 7, mod = 1e9 + 7;

bool isp[N];
vector<int> pri;

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < pri.size(); i++) {
        for (int j = pri.size() - 1; j > i; j--) {
            int tmp = pri[i] + pri[j];
            if(tmp>=n)continue;
            if (isp[n - tmp]) {
                cout << pri[i] << " " << n - tmp << " " << pri[j] << "\n";
                return;
            }
        }
    }
    cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    memset(isp, 1, sizeof(isp));
    isp[0] = isp[1] = 0;
    for (int i = 2; i * i <= N; i++) {
        if (isp[i]) {
            for (int j = i * i; j <= N; j += i) isp[j] = 0;
        }
    }
    for (int i = 2; i <= N; i++) if (isp[i]) pri.push_back(i);
    int t;
    cin >> t;
    while (t--) solve();
    return 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
typedef long long ll;
const int N=1e6+7, mod=1e9+7;

int n;
ll l,r;
ll a[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>l>>r;
//     sort(a+1,a+1+n);

    ll mn=0,mnn=0,mx=0,mxx=0;
    for(int i=1;i<=n;i++){
        if(a[i]<l)mn+=(l-a[i]),mnn+=(r-a[i]);
        else if(a[i]>r)mx+=(a[i]-r),mxx+=(a[i]-l);
        else mnn+=(r-a[i]),mxx+=(a[i]-l);
    }
    ll ans=0;
    if(mx==mn)ans=mx;
    else if(mx>mn){
        if(mx>mnn){
            cout<<"-1\n";
            return;
        }
        ans=mx;
    }
    else{
        if(mn>mxx){
            cout<<"-1\n";
            return;
        }
        ans=mn;
    }

    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 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
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;
const int N = 1e5; 
#define int long long
const int INF = LLONG_MAX;

struct Node {
    int y, v;
    Node(int _y, int _v) { y = _y; v = _v; }
};

int n, m, s, t, dist[N];
vector<Node> edge[N];
set<pair<int, int>> q;

void dijkstra(int s, int t) {
    q.clear();
    fill(dist, dist + N, INF);
    dist[s] = 0;
    q.insert({0, s});
    while (!q.empty()) {
        int x = q.begin()->second;
        q.erase(q.begin());
        if (x == t) break;
        for (auto i : edge[x]) {
            int new_dist = max(dist[x], i.v);
            if (new_dist < dist[i.y]) {
                q.erase({dist[i.y], i.y});
                dist[i.y] = new_dist;
                q.insert({dist[i.y], i.y});
            }
        }
    }
    cout << dist[t] << endl;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, a;
        cin >> u >> v >> a;
        edge[u].push_back({v, a});
        edge[v].push_back({u, a});
    }
    cin >> s >> t;
    dijkstra(s, t);
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
    int n;
    cin >> n;
    int sum = 0;
    vector<int> a(n + 1,0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    int ans = LLONG_MAX, pre = 0;
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        pre += a[i];
        ans = min(ans, a[i] * i - pre + sum - pre - a[i] * (n - i));
    }
    cout << ans + 1 << endl;
    return 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
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;
typedef long long ll;
const int N = 2e6+7;
#define int long long

int n, m;
int a[N];
int st[N][21];
int l2[N];  

void build() {
    for (int i = 1; i <= n; i++) {
        st[i][0] = a[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

int query(int l, int r) {
    int j = l2[r - l + 1];
    return max(st[l][j], st[r - (1 << j) + 1][j]);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    l2[1] = 0;
    for (int i = 2; i <= n; i++) {
        l2[i] = l2[i / 2] + 1;
    }

    build();

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << "\n";
    }
    return 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
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

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const int N = 1e6 + 7, mod = 1e9 + 7;
#define int long long

struct Node {
    int y, v;
    Node(int _y, int _v) : y(_y), v(_v) {}
};

int n, m;
vector<Node> edge[N], edges[N];
vector<int> dist(N);

void dijkstra(int s, vector<Node>edge[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    fill(dist.begin(), dist.end(), INT_MAX);
    dist[s] = 0;
    q.push({0, s});
    
    while (!q.empty()) {
        int d = q.top().first;
        int x = q.top().second;
        q.pop();
        
        if (d > dist[x]) continue;
        
        for (auto& i : edge[x]) {
            if (dist[x] + i.v < dist[i.y]) {
                dist[i.y] = dist[x] + i.v;
                q.push({dist[i.y], i.y});
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edges[v].push_back({u, w});
    }
    ll ans = 0;
    dijkstra(1, edge);
    for (int i = 2; i <= n; i++) {
        ans += dist[i];
    }
    dijkstra(1, edges);
    for (int i = 2; i <= n; i++) {
        ans += dist[i];
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <bits/stdc++.h>
using namespace std;

int sg[30][20][40],day[20]={0,31,28,31,30,31,30,31,31,30,31,30,31};

void solve(){
    int y,m,d;
    cin>>y>>m>>d;
    cout<<(sg[y%100][m][d]?"YES\n":"NO\n");
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=8;i<=12;i++)
        for(int j=1;j<=31;j++)sg[24][i][j]=1;
    sg[24][8][1]=0;
    for(int i=24;i>=0;i--){
        for(int j=12;j>=1;j--){
            if(i==24&&j>=8)continue;
            int d=day[j];
            if(i%4==0&&j==2)d++;
            for(int k=d;k>0;k--){
                int x=i,y=j,z=k+1;
                if(z>d)z=1,y++;
                if(y>12)y=1,x++;
                if(sg[x][y][z]==0){
                    sg[i][j][k]=1;
                    continue;
                }
                x=i,y=j+1,z=k;
                bool flag=0;
                if(y>12)y=1,x++,flag=1;
                else if(y!=2){
                    if(z<=day[y])flag=1;
                }
                else{
                    int tmp=28;
                    if(i%4==0)tmp=29;
                    if(z<=tmp)flag=1;
                }
                if(flag&&sg[x][y][z]==0)sg[i][j][k]=1;
            }
        }
    }
    int t;
    cin>>t;
    while(t--)solve();
    return 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls now<<1
#define rs now<<1|1
const int N = 2e5+7, mod = 1e9+7;

int n, m;
int f[N];

struct Node {
    int x, y, z;
};

vector<Node> a;

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

bool check(int mid) {
    iota(f, f + n + n + 1, 0);
    for (auto x : a) {
        if (x.z > mid) {
            int fx = find(x.x), fy = find(x.y);
            if (fx == fy) return false;
            f[find(x.x + n)] = find(x.y);
            f[find(x.y + n)] = find(x.x);
        }
    }
    return true;
}

void solve() {
    cin >> n >> m;
    a.resize(m + 1);
    for (int i = 1; i <= m; i++) cin >> a[i].x >> a[i].y >> a[i].z;
    int l = 0, r = 1e6, ans = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1,ans=mid;
        else l = mid + 1;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}