小白月赛24

J 建设道路

• 注意取模，可能为负数时，+=mod再%=mod
• 代入推导

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 7;
const ll mod = 1e9 + 7;
inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}
ll a[N];
ll sum[N];
int main() {
    ll n = read();
    ll ans = 0;
    for (int i = 1; i <= n; ++i) a[i] = read(), a[i] %= mod, sum[n] = a[n];
    for (int i = n - 1; i > 1; --i) sum[i] = (sum[i + 1] + a[i]) % mod;
    for (int i = 1; i <= n; ++i)
        ans += (((n - 1) * a[i]) % mod * a[i]) % mod,
        ans -= ((2 * sum[i + 1]) % mod * a[i]) % mod, ans += mod,
        ans %= mod;
    printf("%lld\n", ans);
    return 0;
}

解放思想，解放生产力的python

n = int(input())
a = list(map(int, input().split()))
sum = [a[0]]
for i in range(1, n): sum.append(a[i]+sum[i-1])
ans = 0
for i in range(n): ans += (n-1)*a[i]*a[i]
for i in range(n-1): ans -= (2*(sum[n-1]-sum[i])*a[i])
mod = 10**9+7
print(ans % (mod))

存值对提升效率也是显著的

n=int(input())
l=list(map(int,input().split()))
ans=0
s=sum(l)
for i in l:ans=(ans+i*i*(n-1)-i*(s-i))%1000000007
print(ans)

进一步展开可以得到就是差值部分。

n=int(input())
l=list(map(int,input().split()))
s=sum(l)
print(sum(i*i*(n-1)-i*(s-i)for i in l)%1000000007)

B 组队

双指针。

比赛的时候的思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const ll mod = 1e9 + 7;
inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}
ll a[N], d[N];
int main() {
    int T = read();
    while (T--) {
        ll n = read(), k = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        sort(a + 1, a + n + 1);
        for (int i = 2; i <= n; ++i) d[i] = a[i] - a[i - 1];
        ll res = 0, len = 2;
        for (; len < n; ++len) {
            res += d[len];
            if (res > k) break;
        }  //此时i在下一个人身上
        res -= d[len];
        ll cnt = --len;
        for (ll j = len + 1; j <= n; ++j) {
            res += d[j];
            while (res > k) res -= d[j + 1 - len--];
            cnt = max(cnt, ++len);
        }
        printf("%lld\n", cnt);
    }
    return 0;
}

其实可以写得干净一点

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 7;
inline ll read() {
    ll s = 0, f = 1;
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}
ll a[N];
int main() {
    int T = read();
    while (T--) {
        ll n = read(), k = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        sort(a + 1, a + n + 1);
        // 1 3 5 7 8
        ll ans = 0;
        for (ll i = 2, j = 1; i <= n; ++i) {
            while (a[i] - a[j] > k) ++j;
            ans = max(ans, i - j + 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

另外遇事不决二分总是不会错的。

py

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    i = 1
    j = 0
    while i < n:
        while a[i]-a[j] > k:
            j+=1
        ans = max(i-j+1,ans)
        i+=1
    print(ans)

A 最短路

https://ac.nowcoder.com/discuss/411752?type=101&order=0&pos=16&page=1

其实不太理解为什么过的人这么少。

题目也没说清楚。强调一条直线然后还包括圆弧的。

#include<bits/stdc++.h>
using namespace std;
double dis(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
    double x1,y1,x2,y2,x3,y3,r,ans=0;
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>r;
    double d1=dis(x1,y1,x2,y2),d2=dis(x1,y1,x3,y3),d3=dis(x2,y2,x3,y3);
    double e1=acos(r/d2),e2=acos(r/d3);
    double e3=acos((d2*d2+d3*d3-d1*d1)/(2*d2*d3));
    if(e1+e2>e3){ printf("%.6f\n",d1);return 0; }
    ans=sqrt(d2*d2-r*r)+sqrt(d3*d3-r*r)+(e3-e1-e2)*r;
    printf("%.6f\n",ans);
    return 0;
}