六校联考day1——2018.8.29

比赛总结

备注：放假了，未参加，后来做了一下。

T1

在衢州时的ACM，做过。

T2

求多少个[l,r]，满足$\frac{sum[r] - sum[l-1]}{r - l + 1} <= k$
转化$sum[r] - sum[l - 1] <= k \times (r - l + 1)$
$sum[r] - sum[l - 1] <= k \times ((r) - (l - 1))$
$sum[r] - sum[l - 1] <= k \times r - k \times (l - 1)$
$sum[r] - k \times r <= sum[l-1] - k \times (l - 1)$
$sum[r] - k \times r <= sum[l-1] - k \times (l - 1)$
即对于每个r，求多少个l满足上式。
就是在[1,r-1]里多少个T[i] >= T[r]，对于1~r这样的区间没法统计，所以特判一下。
离散化后树状数组维护。

开longlong。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 50010;
LL s[N], T[N], Num[N];
int pos[N];
struct BIT{
    int n;int sum[N];
    void update(int p,int x) { 
        for (; p<=n; p+=(p&(-p))) sum[p] += x;
    }
    int query(int p) {
        int ans = 0;
        for (; p; p-=(p&(-p))) ans += sum[p];
        return ans;
    }
    void Clear() {
        memset(sum, 0, sizeof(sum));
    }
    int Ask(int l,int r) {
        return query(r) - query(l - 1);
    }
}bit;
int find(int L,int R,LL x) {
    int ans = 0;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (Num[mid] >= x) ans = mid, R = mid - 1;
        else L = mid + 1;
    }
    return ans;
}
void solve(int n,int k) {
    for (int i=1; i<=n; ++i) T[i] = s[i] - 1ll * k * i, Num[i] = T[i];
    sort(Num + 1, Num + n + 1);
    int cnt = 1;
    for (int i=2; i<=n; ++i) if (Num[i] != Num[cnt]) Num[++cnt] = Num[i];
    for (int i=1; i<=n; ++i) pos[i] = find(1, cnt, T[i]);
    bit.n = cnt;
    bit.Clear();
    LL Ans = 0;
    for (int i=1; i<=n; ++i) {
        Ans += (Num[pos[i]] <= 0);
        Ans += bit.Ask(pos[i], cnt);
        bit.update(pos[i], 1);
    }
    cout << Ans << "\n";
}
int main() {
    freopen("h.in","r",stdin);
    freopen("h.out","w",stdout);
    int n = read();
    for (int i=1; i<=n; ++i) 
        s[i] = s[i - 1] + read();
    int m = read();
    while (m --) {
        int k = read();
        solve(n, k);
    }
    return 0;
}

T3

很重要一点，原图中两个点之间只有一条边。
所以对于u->v->w，如果这两条属于一个人，那么只有u->w属于个人的时候是正确的。如果对于一个人的点全正确，那么就是合法的，否则是不合法的。
枚举三个点，这样是$n^3$。
正难则反，那么知道了一个人如果没有不正确的情况，也就是合法的，否则不合法的。
正确的情况知道了，就是u->w一定属于同一个人，那么不正确的情况：
1、u->w属于另一个人
2、w->u这条边存在，不管属于谁，都说明了u->w这条边不存在。
2就是原图中有环，1就是将一个人的边取反后图中有环。
如果原图与将一个人取反后的图都没有环，那么说明答案为YE5，否则答案为N0。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 3010;
int deg[N], q[N];
bool vis[N];
char s[N][N];
vector<int> e[N];
int n;
void add_edge(int u,int v) {
    deg[v] ++;
    e[u].push_back(v);
}
void init() {
    memset(deg, 0, sizeof(deg));
    for (int i=1; i<=n; ++i) {
        e[i].clear();
        deg[i] = 0;
        q[i] = 0;
        vis[i] = false;
    }
}
void build(int flag) {
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            if (s[i][j] == 'H') add_edge(i, j);
            if (s[i][j] == 'W') flag ? add_edge(i, j) : add_edge(j, i);
        }
    }
}
bool topo() {
    int L = 1, R = 0;
    for (int i=1; i<=n; ++i) 
        if (!deg[i]) q[++R] = i;
    while (L <= R) {
        int u = q[L++];
        vis[u] = true;
        for (int sz=e[u].size(),i=0; i<sz; ++i) {
             int v = e[u][i];
             if (vis[v]) return false; // 判环 
             deg[v] --;
             if (!deg[v]) q[++R] = v;
        }
    }
    for (int i=1; i<=n; ++i) // 可能有一个封闭的环，没有入度为0的点。 
        if (!vis[i]) return false;
    return true;
}
int main() {
    freopen("p.in","r",stdin);
    freopen("p.out","w",stdout);
    int T = read();
    while (T--) {
        n = read();
        for (int i=1; i<=n; ++i) scanf("%s",s[i]+1);
        init(); build(1);
        if (!topo()) { puts("N0"); continue; }
        init(); build(0);
        if (!topo()) { puts("N0"); continue; }
        puts("YE5");
    }
    return 0;
}