A 

B 

思路:如果存在大于0的交面积的话, 那么肯定能找到一条水平的直线 和 一条垂直的直线,

使得水平直线的左右两边点的个数相等且为n, 垂直直线的左右两边点的个数相等且为n

也就是说不能有点在这两条线上, 否则交面积为0

然后左上角的点和右下角的点配对, 左下角的点和右上角的点配对

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 2e5 + 5, M = 1e5 + 5;const int MOD = 1e9 + 7;pii a[N];int fac[M];bool cmp(pii a, pii b) {    return a.se < b.se;}void init() {    fac[0] = 1;    for (int i = 1; i < M; i++) fac[i] = (1LL * fac[i-1] * i) % MOD;}int main() {    int T, n;    init();    scanf("%d", &T);    while(T--) {        scanf("%d", &n);        for (int i = 1; i <= 2*n; i++) scanf("%d %d", &a[i].fi, &a[i].se);        bool f = false;        sort(a+1, a+1+2*n);        double x = 0, y = 0;        if(a[n].fi != a[n+1].fi) x = (a[n].fi + a[n+1].fi) / 2.0;        else f = true;        sort(a+1, a+1+2*n, cmp);        if(a[n].se != a[n+1].se) y = (a[n].se + a[n+1].se) / 2.0;        else f = true;        int cnt = 0;        for (int i = 1; i <= 2*n; i++) if(a[i].fi > x && a[i].se > y) cnt++;        if(f) printf("0\n");        else printf("%lld\n", (1LL * fac[cnt] * fac[n-cnt]) % MOD);    }    return 0;}
          
         
        
       
      

 

C 

思路:打表找规律, 发现ai的系数为C(n+1, i) - 1

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e6 + 10;const int MOD = 1e9 + 7;int a[N];LL fac[N], inv[N];LL q_pow(LL n, LL k) {    LL ans = 1;    while(k) {        if(k&1) ans = (ans * n) % MOD;        n = (n * n) % MOD;        k >>= 1;     }    return ans;}void init() {    fac[0] = 1;    for (int i = 1; i < N; i++) fac[i] = fac[i-1] * i % MOD;    inv[N-1] = q_pow(fac[N-1], MOD-2);    for (int i = N-2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD; }LL C(int n, int m) {    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;}int main() {    int T;    init();    scanf("%d", &T);    while(T--) {        int n;        scanf("%d", &n);        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);        LL ans = 0;        for (int i = 1; i <= n; i++) {            (ans = ans + (C(n+1, i) - 1) * a[i] % MOD) %= MOD;        }         printf("%lld\n", (ans + MOD) % MOD);    }    return 0;}
          
         
        
       
      

 

D 

思路:将a数组放到集合里, 方便查找删除

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 100;int a[N], b[N];multiset
           
             s;vector
            
              vc;int main() { int T, n, k; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &k); s.clear(); vc.clear(); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), s.insert(a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); for (int i = 1; i <= n; i++) { multiset
             
              :: iterator it = s.lower_bound(b[i]); if(it == s.end() || *it != b[i]) { vc.pb(b[i]); } else s.erase(it); } if((int)vc.size() == 0) puts("YES"); else if((int)vc.size() == 1) { if(*s.begin() - k <= vc[0] && vc[0] <= *s.begin() + k) puts("YES"); else puts("NO"); } else puts("NO"); } return 0;}
             
            
           
          
         
        
       
      

 

E 

F 

G 

思路:对于每个点, 它连向父亲的边只有当它的子树中不能自销的多余部分才会用到

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e4 + 5;vector
           
             g[N];int send[N], rev[N];LL ans = 0;pii dfs(int u, int o, int w) { pii tmp = {send[u], rev[u]}; for (pii p : g[u]) { if(p.fi != o) { pii pp = dfs(p.fi, u, p.se); tmp.fi += pp.fi; tmp.se += pp.se; } } ans += 1LL * abs(tmp.fi - tmp.se) * w; return tmp;}int main() { int T, n, u, v, w, q; scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) g[i].clear(), send[i] = rev[i] = 0; for (int i = 1; i < n; i++) { scanf("%d %d %d", &u, &v, &w); g[u].pb({v, w}); g[v].pb({u, w}); } scanf("%d", &q); while(q--) { scanf("%d %d", &u, &v); send[u]++; rev[v]++; } ans = 0; dfs(1, 1, 0); printf("%lld\n", ans); } return 0;}
           
          
         
        
       
      

 

H 

思路:背包dp变形

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e3 + 5;pii a[N];int dp[N]; int main() {    int T, n, L;    scanf("%d", &T);    while(T--) {        scanf("%d %d", &n, &L);        for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].fi, &a[i].se);        for (int i = 0; i <= L; i++) dp[i] = 0;        for (int i = 1; i <= n; i++) {            for (int j = L; j >= a[i].se; j--) {                if(j-a[i].se + 1 >= a[i].fi) dp[j] = max(dp[j], dp[j-a[i].se] + 1);            }        }        printf("%d\n", dp[L]);    }    return 0;}
          
         
        
       
      

 

I 

思路:二分答案, check时对于每辆bus, 如果它上一天是空闲的, 才能填补今天的空缺, 然后今天原本的车就是昨天需要的车, 不够的拿昨天剩余的补

代码:

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);//headconst int N = 1e5 + 5;vector
           
             a[N];int T, m, n, r, t, tmp[N];bool check(int x) { int pre = 0; for (int i = 1; i <= n; i++) { if(i == 1) { int tot = 0; for (int j = 1; j <= m; j++) { tmp[j] = (a[j][i] + r - 1) / r; tot += tmp[j]; } if(tot > x) return false; pre = x - tot; } else { int tot = 0; for (int j = 1; j <= m; j++) { if(tmp[j] >= (a[j][i] + r - 1) / r) tmp[j] = (a[j][i] + r - 1) / r; else { if(pre >= (a[j][i] + r - 1) / r - tmp[j]) pre -= (a[j][i] + r - 1) / r - tmp[j]; else return false; tmp[j] = (a[j][i] + r - 1) / r; } tot += (a[j][i] + r - 1) / r; } if(tot > x) return false; pre = x - tot; } } return true;}int main() { scanf("%d", &T); while(T--) { scanf("%d %d %d", &m, &n, &r); for (int i = 1; i <= m; i++) { a[i].clear(); a[i].pb(0); for (int j = 1; j <= n; j++) { scanf("%d", &t); a[i].pb(t); } } int l = 1, r = 5e5, mid = l+r >> 1; while(l < r) { if(check(mid)) r = mid; else l = mid+1; mid = l+r >> 1; } printf("%d\n", mid); } return 0;}
           
          
         
        
       
      

 

J 

思路:2-sat

建边:

对于一条mark的边,

如果其中一点在点覆盖中, 那么另外一点肯定不在点覆盖中

如果其中一点不在点覆盖中, 那么另外一点肯定在点覆盖中

对于一条unmark的边,

如果其中一点在点覆盖中, 那么另外一点不确定

如果其中一点不在点覆盖中, 那么另外一点肯定在点覆盖中

代码:

#include
      
       using namespace std;const int N=500000;int ins[N],dfn[N],low[N],cnt,sta[N];int top,v,u;int Next[N],head[N],to[N];int tot;int scc[N];int scccnt;void make_list(int u,int v){    Next[++tot]=head[u],head[u]=tot,to[tot]=v;}void tarjan(int x){    ins[x]=dfn[x]=low[x]=++cnt,sta[top++]=x;    for(int p=head[x],v=to[p];p;p=Next[p],v=to[p])        if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);        else if(ins[v])low[x]=min(low[x],dfn[v]);    if(low[x]==dfn[x]){        scc[x]=++scccnt,ins[x]=0;        while((u=sta[--top])!=x)ins[u]=0,scc[u]=scccnt;    }}int main(){    int T;    int n,m;    int u,v,w;    scanf("%d",&T);    for(int t=1;t<=T;t++){        scanf("%d%d",&n,&m);        memset(head,0,sizeof(int)*(n*2+5));        memset(dfn,0,sizeof(int)*(n*2+5));        top=0;        tot=0;        memset(scc,0,sizeof(int)*(n*2+5));        memset(low,0,sizeof(int)*(n*2+5));        scccnt=0;        memset(ins,0,sizeof(int)*(n*2+5));        cnt=0;        memset(sta,0,sizeof(int)*(n*2+5));        for(int i=1;i<=m;i++){            scanf("%d%d%d",&u,&v,&w);            if(w){                make_list(u,v+n);                make_list(v,u+n);                make_list(u+n,v);                make_list(v+n,u);            }            else{                make_list(u+n,v);                make_list(v+n,u);            }        }        for(int i=1;i<=2*n;i++){            if(!dfn[i])tarjan(i);        }        bool ok=1;        for(int i=1;i<=n;i++){            ok&=(scc[i]!=scc[i+n]);        }        if(ok)puts("YES");        else puts("NO");    }    return 0; }