平时十九测

题解：今天题没什么思维，都是板子

第一题：打表找规律，满足a-b=a^b，枚举这个差，复杂度调和级数

#include<bits/stdc++.h>
using namespace std;

const int M = 1e7 + 5;
int cnt[M];
void pre(int N){
    for(int ch = 1; ch <= N; ch++)
        for(int a = ch+ch; a <= N; a += ch)
            if((a^(a-ch))==ch) cnt[a]++;
    for(int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
}
inline int gcd(int a, int b){return b ? gcd(b, a%b) : a;}
int main(){
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    int n,fk=0;;    
    scanf("%d", &n);
    pre(n);
    printf("%d
", cnt[n]);
    
}

View Code

第二题：点分模版

#include<bits/stdc++.h>
using namespace std;
#define RG register
const int M = 1e5 + 5, INF = 2e9;
int n, S, E;
#define ex(i, u) for(register int i = h[u]; i; i = G[i].nxt)
int tot, h[M], siz[M], g[M], root, sum, Ans = INF, dis[M], cnt;
bool vis[M];
struct node{
    int id, dis;
    bool operator < (const node &rhs)const {
        return dis == rhs.dis ? id < rhs.id : dis < rhs.dis;
    }
}tong[M];

struct edge{int v, nxt, w;}G[M<<1];
void add(int u, int v, int w){G[++tot].w = w, G[tot].v = v, G[tot].nxt = h[u], h[u] = tot;}


inline void getroot(int u, int f){
    siz[u] = 1; g[u] = 0;
    ex(i, u){
        int v = G[i].v;
        if(v == f || vis[v])continue;
        getroot(v, u);
        siz[u] += siz[v];
        g[u] = max(g[u], siz[v]);
    }
    g[u] = max(g[u], sum - siz[u]);
    if(g[u] < g[root]) root = u;
}
inline void getdeep(int u, int f, int zx){
    ex(i, u){
        int v = G[i].v;
        if(vis[v] || v == f)continue;
        dis[v] = dis[u] + G[i].w;
        int nx = zx == -1 ? v : zx;
        tong[++cnt] = (node) { nx, dis[v] };
        getdeep(v, u, nx);
    }
}

inline void cal(int u){
    cnt = 0;
    tong[++cnt] = (node) {u, 0};
    dis[u] = 0;
    getdeep(u, 0, -1);
    sort(tong+1, tong+1+cnt);
    for(RG int i = 1; i <= cnt; i++){
        int pos = lower_bound(tong + 1, tong + 1 + cnt, (node) {-1, S - tong[i].dis}) - tong;
        if(pos < i)break;
        for(RG int k = pos; k <= cnt; k++){
            int c = tong[k].dis + tong[i].dis;
            if(c > Ans || c > E)break;
            if(tong[k].id == tong[i].id || c < S) continue;
            Ans = min(Ans, c); break;
        } 
    }
    
    
}



void dfs(int u){
    cal(u);
    vis[u] = 1;
    ex(i, u){
        int v = G[i].v;
        if(vis[v])continue;
        sum = siz[v];
        getroot(v, root=0);
        dfs(root);
    }
}
int read(){
    int x = 0; int f = 1; char c = getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
    return x*=f;
}


int main(){
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);
    n = read(); S = read(); E = read();
    for(int i = 1; i < n; i++){
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
    }    
    sum = n;
    g[0] = INF;
    getroot(1, root = 0);
    dfs(root);
    Ans == INF ? puts("-1") : printf("%d
", Ans);
}

View Code

第三题：费用流，修车+动态建边；

#include <bits/stdc++.h>

using namespace std;
const int maxn = 8e5, maxm = 3e6 + 5;
const int inf = 1000000008;
int S, T, f[45][105], p[45];
int m, n, N;
struct Netflow{
    int h[maxn], tot, dis[maxn], pre[maxn], pree[maxn], inq[maxn];

    struct edge{int v, f, w, nxt;}G[maxm];

    void init(){
        tot = 1;
    }
    void add(int u, int v, int f, int w){
        G[++tot].v = v; G[tot].f = f; G[tot].w = w;
        G[tot].nxt = h[u]; h[u] = tot;

        G[++tot].v = u; G[tot].f = 0; G[tot].w = -w;
        G[tot].nxt = h[v]; h[v] = tot;
    }

    bool spfa(){
        queue <int> Q;
        memset(dis, 127, sizeof(dis));
        memset(inq, 0, sizeof(inq));
        Q.push(S);
        inq[S] = 1; dis[S] = 0;

        while(!Q.empty()){
            int u = Q.front(); Q.pop(); inq[u] = 0;

            for(int i = h[u]; i; i = G[i].nxt){
                int v = G[i].v;
                if(G[i].f && dis[v] > dis[u] + G[i].w){
                    dis[v] = dis[u] + G[i].w;
                    pre[v] = u; pree[v] = i;
                    if(!inq[v])Q.push(v), inq[v] = 1;
                }
            }
        }

        return dis[T] < inf;
    }

    int augment(){
        int ans = 0;
        while(spfa()){
            int u = T, delta = inf;
            while(u != S){
                delta = min(delta, G[pree[u]].f);
                u = pre[u];
            }
            u = T;
            while(u != S){
                G[pree[u]].f -= delta;
                G[pree[u]^1].f += delta;
                u = pre[u];
            }
            //printf("%d %d
",delta, dis[T]);
            int J = (pre[T]-1)/N, K = (pre[T]-1)%N+1;
            if(G[pree[T]].f == 0){
                for(int i = 1; i <= n; i++)
                add(i, pre[T]+1, 1, f[i][J]*(K+1));
                add(pre[T]+1, T, 1, 0);
            } 
            ans += delta * dis[T];
        }
        return ans;
    }
    
    int solve(){
        int Ans = 0;
        while(spfa()){
            Ans += augment();    
        }
        return Ans;
    }
}Tr;




int main()
{
    freopen("bird.in","r",stdin);
    freopen("bird.out","w",stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%d", &p[i]), N += p[i];
    Tr.init();
    S = 0, T = N + m*N + 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &f[i][j]);
    for(int i = 1; i <= n; i++) Tr.add(S, i, p[i], 0);
    
    for(int j = 1; j <= m; j++){
        for(int i = 1; i <= n; i++)
            Tr.add(i, N*j+1, 1, f[i][j]);
        Tr.add(N*j+1, T, 1, 0);
    }
    printf("%d
", Tr.solve() );
    
    return 0;
}

View Code