[20181103][模拟赛]

T1

思路

因为0的个数超过了一半，所以只要将拍完序后，最中间的数到想得到的中位数之间的每个数都变成S即可。

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    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;
}
ll ans;
ll a[N];
int main() {
    freopen("median.in","r",stdin);
    freopen("median.out","w",stdout);
    int n = read();
    ll s = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    sort(a + 1,a + n + 1);
    for(int i = n/2 + 1;i <= n;++i) {
        if(a[i] >= s) break;
        ans += s - a[i]; 
    }
    cout<<ans;
    return 0;
}

T2

60分思路

对于前60分，可以直接\(n^2\)dp。用f[i][j]表示前i天，其中j天写了作业的方案数。这样没写作业的天数就是i-j,根据要求\((i-j)-j<k　=>　j >i-k\)只要控制一下转移的边界就行了。

100分思路

对于一百分，\[C(_{2n}^n) - C(_{2n}^{n+k})\]

然后分解质因数求组合数。

60分代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 1000000 + 100;
int mod;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    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 n, K;
namespace BF1 {
    ll f[2010][2010];
    void Main() {
        f[0][0] = 1;
        for(int i = 1;i <= n * 2;++i) {
            if(i < K) f[i][0] = 1;
            for(int j = max(((i - K)/2 + 1),1);j <= min(i,n);++j) {
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
                f[i][j] >= mod ? f[i][j] -= mod : 0;
            }
        }
        cout<<f[n * 2][n];
        return; 
    }

}
int ff[N];
int main() {
    freopen("term.in","r",stdin);
    freopen("term.out","w",stdout);
    n = read(), K = read();
    mod = read();
    if(n <= 1000) {
        BF1::Main();
        return 0;
    }
    return 0;
}

T3

思路

将所有的点点权全都放到边上去。然后建个反图，找出S可以到达的边集与T可以到达的边集的交集。然后将答案拆位从高到低贪心。用bitset优化一下。就可以在两秒里跑过了

代码

//2.424s
//2.211s
//2.121s
//2.013s
//1.917s
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<queue>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 200000 + 100,M = 500000 + 100;
bitset<M>s,t,tmp;
char buf[100000],*_p1 = buf,*_p2 = buf;
#define nc() (_p1==_p2&&(_p2=(_p1=buf)+fread(buf,1,100000,stdin),_p1==_p2) ? EOF :*_p1++)
inline int read() {
    int x=0,f=1;
    char ch=nc();
    for(; !isdigit(ch); ch=nc())if(ch=='-')f=-1;
    for (; isdigit(ch); ch=nc())x=x*10+ch-'0';
    return x*f;
}
struct node {
    int v,nxt;
}e[3][M];
int a[N];
int head[3][N],ejs[3];
int vis[N];
int n,m,S,T;
queue<int>q,q2;
inline void bfsS() {
    while(!q.empty()) q.pop();
    q.push(S);
    memset(vis,0,sizeof(vis));
    vis[S] = 1;
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = head[1][u];i;i = e[1][i].nxt) {
            int v = e[1][i].v;
            s[i] = 1;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(v);
        }
    }
}
inline void bfsT() {
    while(!q.empty()) q.pop();
    q.push(T);
    memset(vis,0,sizeof(vis));
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = head[2][u];i;i = e[2][i].nxt) {
            int v = e[2][i].v;
            t[i] = 1;
            if(vis[v]) continue;
            vis[v] = 1;
            q.push(v);
        }
    }
}
int W[M];
int vis2[N],vis1[N];
inline void bfs1() {
    while(!q.empty()) {
        int u = q.front();q.pop();
        for(int i = head[1][u];i;i = e[1][i].nxt) {
            int v = e[1][i].v;
            tmp[i] = 1;
            if(vis1[v] == 1) continue;
            vis1[v] = 1;
            q.push(v);
        }
    }
}
inline void bfs2() {
    while(!q2.empty()) {
        int u = q2.front();q2.pop();
        for(int i = head[2][u];i;i = e[2][i].nxt) {
            int  v = e[2][i].v;
            tmp[i] = 1;
            if(vis2[v] == 1) continue;
            vis2[v] = 1;
            q2.push(v);
        }
    }
}
int main() {
    freopen("rabbit.in","r",stdin);
//  freopen("rabbit.out","w",stdout);
    n = read(),m = read(),S = read(),T = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read(),w = read();
        e[1][i].v = v;e[1][i].nxt = head[1][u];head[1][u] = i;
        e[2][i].v = u;e[2][i].nxt = head[2][v];head[2][v] = i;
        W[i] = a[u] & a[v] & w;
    }
    if(S == T) {
        printf("%d",a[S]);
        return 0;
    }
    bfsS();
    bfsT();
    tmp = s & t;
    if(!tmp.count()) {
        puts("-1");return 0;
    }
    for(int i = 1;i <= m;++i) {
        if(tmp[i] && W[i] == 0) {
            puts("0");
            return 0;
        }
    }
    int ans = 0;
    for(int i = 30;i >= 0;--i) {
        memset(vis1,0,sizeof(vis1));
        memset(vis2,0,sizeof(vis2));
        int bz = 0;
        for(int j = 1;j <= m;++j) {
            if(tmp[j] == 0) continue;
            if(!(W[j] & (1<<i))) {
                bz = 1;
                if(!vis1[e[1][j].v]) {
                    q.push(e[1][j].v);
                    vis1[e[1][j].v] = 1;
                }
                if(!vis2[e[2][j].v]) {
                    q2.push(e[2][j].v);
                    vis2[e[2][j].v] = 1;
                }
            }
        }
        if(bz == 0) {
            ans |= (1<<i);
            continue;
        }
        for(int j = 1;j <= m;++j)if((W[j] & (1 << i))) tmp[j] = 0;
        bfs1();
        bfs2();
        tmp = tmp & s  & t;
    }
    cout<<ans;
    return 0;
}