一点思维题记录emm

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

const int N = 1000010, M = 10000010;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
} 

int mp[N],ans,n,m;

int main(){
    freopen("1.txt", "r", stdin);
    n = read(), m = read();
    while(m --){
        int x = read(), y = read();
        if(x > y)    swap(x, y);
        if(!mp[x])    mp[x] = y;
        else    mp[x] = min(mp[x], y); 
    }
    int idx = 1, last = 0;
    while(idx <= n && !mp[idx])    idx ++;
    last = mp[idx];
    for(int i = idx + 1; i <= n; ++ i){
        if(!last && mp[i])    last = mp[i];
        if(i == last)    ans ++, last = mp[i];
        if(!mp[i])    continue ;
        if(mp[i] > last)    continue ;
        else    last = mp[i];
    }
    cout << ans;
    return 0;
}

小P和小Q

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

const int N = 100010;

int n,t;
ll x, y;

ll ksm(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)    res = res * a;
        a *= a;
        b >>= 1;
    }
    return res;
}

int main(){
    cin >> t;
    while(t --){
        cin >> x >> y;
        ll tmp = (int)pow(x * y, 1.0 / 3);
        if(ksm(tmp, 3) == x * y || ksm(tmp + 1, 3) == x * y)    puts("Yes");
        else    puts("No");
    }
    return 0;
}

漂亮的树

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

const int N = 100010;

int mp[N * 2], a[N], n, maxx;

int main(){
    cin >> n;
    for(int i = 1; i <= n / 2; ++ i){
        scanf("%d", &a[i]);
        mp[a[i] - i + N] ++;
        maxx = max(maxx, mp[a[i] - i + N]);
    }
    for(int i = n / 2 + 1; i <= n; ++ i){
        scanf("%d", &a[i]);
        mp[a[i] - (n - i + 1) + N] ++;
        maxx = max(maxx, mp[a[i] - (n - i + 1) + N]);
    }
    cout << n - maxx;
    return 0;
}

选值

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

const int N = 100010;

int n,d,a[N];
ll ans;

ll C(ll x){
    return x * (x - 1) / 2;
}

int main(){
    cin >> n >> d;
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a[i]);
    } 
    for(int i = 1; i <= n; ++ i){
        int tmp = a[i] + d;
        int pos = upper_bound(a + 1, a + 1 + n, tmp) - (a + 1);
        //printf("i = %d tmp = %d pos = %d\n", i, tmp, pos);
        int num = (a[pos] > tmp ? pos - i + 1 : pos - i);
        ans += C(num);
        //printf("num = %d C = %d\n", num, C(num));
    }
    cout << ans;
    return 0;
}

水题

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

int n;

int main(){
    while(cin >> n){
        int tmp = n / 2;
        printf("%d\n", tmp * (n - tmp));
    }
    return 0;
}

阶乘

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

ll n, ans, last;

int main(){
    cin >> n;
    for(int i = 5; i <= n; ++ i){
        int t = i;
        while(t % 5 == 0){
            t /= 5;
            last ++;
        }
        ans += last;
    }
    cout << ans;
    return 0;
}