EOJ Monthly 2019.2 存代码

比赛链接

官方题解

D

签到题能不能别这么卡啊

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

LL l, r, k, m;

LL fpow(LL a, LL b, LL up) {
	if(b * log(a) > log(up)) return -1;
	LL ret = 1;
	for(int i = 1; i <= b; i++) {
		ret = ret * a;
		if(ret > up) return -1;
	}
	return ret;
}

LL solve(LL l, LL r, LL k, LL m) {
	// [l, r] x * k ^ m
	LL base = fpow(k, m, r);
	if (base == -1) return 0;
	LL R = r / base;
	LL L = (l - 1) / base;
	return R - L;
}

int main () {
	int T; for (scanf("%d", &T); T--; ) {
		scanf("%lld%lld%lld%lld", &l, &r, &k, &m);
		LL res = solve(l, r, k, m) - solve(l, r, k, m + 1);
		printf("%lld
", res);
	}
	return 0;
}

F

这题反而是第一题撸出来的

#include <bits/stdc++.h>
#define sqr(x) x*x
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;

LL n, m, x[N];

int main(){
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++){
        scanf("%lld", &x[i]);
    }
    sort(x + 1, x + n+1);

    LL sum = 0, sum2 = 0;
    for (int i = 1; i <= m; i++){
        sum += x[i];
        sum2 += sqr(x[i]);
    }
    
    LL ans = m * sum2 - sqr(sum);
    for (int i = m+1; i <= n; i++){
        sum += x[i] - x[i-m];
        sum2 += sqr(x[i]) - sqr(x[i-m]);
        ans = min(ans, m*sum2 - sqr(sum));
    }
    printf("%lld
", ans);
    return 0;
}

E

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;

int a[N]; // weight of node

struct graph{
    vector <int> G[N];     // graph
    int n;                 // number of vetex 
    int w[N];              // weight of vetex
    int ind[N];            // in_degree
    vector <int> top_seq;  // result of topsort

    inline void init(const int &n){
        this->n = n;
        memset(ind, 0, sizeof ind);
        for (int i = 0; i <= n; i++) G[i].clear();
    }

    inline void addEdge(const int &u, const int &v){
        G[u].push_back(v);
        ind[v]++;
    }

    inline void topsort(){
        queue <int> Q;
        for (int i = 1; i <= n; i++){
            if (!ind[i]) Q.push(i);
        }
        
        top_seq.clear();
        for (int u; !Q.empty();){
            u = Q.front(); Q.pop();
            top_seq.push_back(u);
            for (auto v: G[u]){
                ind[v]--;
                if (!ind[v]) Q.push(v);
            }
        }
    }
    
    int dist[N];  // longest path
    inline int longest_path(const int &s, const int &t){
        for (int i = 0; i <= n; i++) dist[i] = -INF;
        dist[s] = w[s];
        for (auto u: top_seq){
            if (dist[u] == -INF) continue;
            for (auto v: G[u]){
                dist[v] = max(dist[v], dist[u] + w[v]);
                //printf("	dist[%d] = %d
", v, dist[v]);
            }
        }
        return dist[t];
    }

    bool check(const int &mid){
        //printf("mid = %d
", mid);
        for (int i = 1; i <= n; i++){
            w[i] = (a[i] >= mid) ? 1 : -1;
        }
		int ans = longest_path(1, n);
        return  ans >= 0;
    }
} g;

int main(){
    //freopen("in.txt", "r", stdin);

    int n, m, L = INF, R = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
		L = min(L, a[i]);
        R = max(R, a[i]);
    }
    g.init(n);
    for (int u, v; m--;){
        scanf("%d%d", &u, &v);
        g.addEdge(u, v);
    }
    g.topsort();

	if (g.longest_path(1, n) == -INF) L = -1;
	else{
		for (int mid; L < R;){
			mid = (L + R) >> 1;
			if (g.check(mid)) L = mid + 1;
			else R = mid;
		}
		if (!g.check(L)) L--;
	}

    printf("%d
", L);
    return 0;
}

从代码量上来说，这是一个自杀写法