EXAM-2018-7-27

未完成

[ ] F

A

要用ll，然后注意正方形的情况，细心一点

E

有点动态规划的感觉，状态的转移，不难，要注意不要漏掉状态

K

正解是DFS 然后用贪心数据弱的话能过，先排圆心

M

树状数组，可以维护前面有多少数比这个数小，然后通过相减也可以得出后面有多少数比它小，后面要用到容斥的思想

12xx（xx比1 2大）可以通过组合数算出，即前面比它小的选一个，后面比它大的选两个，然后相乘。
1234 可以再次通过树状数组，每个节点的val是前lsamller[]的和，刚好可以得到有多少123 然后乘后面比它大的数的个数就可以

最后12xx-1234就是最后结果

注意取模运算

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn = int(2e5) + 7, mod = 16777216;

ll s[maxn],l[maxn],r[maxn],big[maxn],puls[maxn];

struct fen{

    ll tree[maxn];

    int n;

    void init(int len_){

        n=len_;

        memset(tree,0,sizeof(tree));

    }

    inline int lowbit(int t){

        return t&(-t);

    }

    void add(int x,int y){

        for(int i=x;i<=n;i+=lowbit(i)){

            tree[i]+=y;

        }

    }

    int getsum(int x){

        int ans=0;

        for(int i=x;i>0;i-=lowbit(i)){

            ans+=tree[i];

        }

        return ans;

    }

}fens;

int read()

{

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int main()

{

    int n;

    n=read();

    fens.init(n);

    ll ret=0;

    for(int i=1;i<=n;i++){

        s[i]=read();

        l[i]=fens.getsum(s[i]);

        r[i]=s[i]-1-l[i];

        big[i]=n-i-r[i];

        fens.add(s[i],1);

        ret=(ret+(l[i]*(1ll*big[i]*(big[i]-1)/2%mod)%mod))%mod;

    }

    fens.init(n);

    ll ans=0;

    for(int i=1;i<=n;i++){

            puls[i]=fens.getsum(s[i]);

        ans=(ans+puls[i]*big[i]%mod)%mod;

        fens.add(s[i],l[i]);

    }

    printf("%lld\n",(ret-ans+mod)%mod);

    return 0;

}

C

可以转化为图论做，很难看懂

题解的意思是拆开一个点，分成横坐标和纵坐标，然后连边，用BFS，v的点权由u的点权和uv的边权推出，如果矛盾则不符合题意。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

    if(c == '-') f = -1;

    c = getchar();

    }

    while(c >= '0' && c <= '9') {

    res = res * 10 + c - '0';

    c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

    out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next,val;

}E[4005];

int head[2005],sumE,num[2005];

bool vis[2005];

int T,N,M,K;

void add(int u,int v,int c) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    E[sumE].val = c;

    head[u] = sumE;

}

void addtwo(int u,int v,int c) {

    add(u,v,c);add(v,u,c);

}

queue<int> q;

bool BFS(int x) {

    while(!q.empty()) q.pop();

    q.push(x);

    vis[x] = 1;

    num[x] = 0;

    while(!q.empty()) {

    int u = q.front();q.pop();

    for(int i = head[u] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(!vis[v]) {

        num[v] = E[i].val - num[u];

        vis[v] = 1;

        q.push(v);

        }

        else if(num[u] + num[v] != E[i].val) return false;

    }

    }

    return true;

}

void Init() {

    read(N);read(M);read(K);

    memset(head,0,sizeof(head));sumE = 0;

    memset(vis,0,sizeof(vis));

    int x,y,c;

    for(int i = 1 ; i <= K ; ++i) {

    read(x);read(y);read(c);

    addtwo(x,y + N,c);

    }

}

void Solve() {

    read(T);

    while(T--) {

    Init();

    bool ans = 1;

    for(int i = 1 ; i <= N + M ; ++i) {

        if(!ans) break;

        if(!vis[i]) ans &= BFS(i);

    }

    if(ans) puts("Yes");

    else puts("No");

    }

}

int main() {

    Solve();

    return 0;

}

地址EXAM-2018-7-27

巴特西

EXAM-2018-7-27

EXAM-2018-7-27

未完成

A

E

K

M

C

最新文章

热门文章