CCPC-Wannafly Summer Camp 2019 全记录

迈不过友情╰ 2021-10-30 05:12 197阅读 0赞

// 7.19-7.29 东北大学秦皇岛校区十天训练营，题目都挂在了Vjudge上。训练期间比较忙，没空更博总结，回来继续补题消化。

## [Day1][] ##

这天授课主题是简单图论，节奏挺好，wls两小时理完图论里的基本知识点。

下午的赛题就偏入门了（简单图论无疑），只涉及到最短路问题和简单的搜索以及一些奇怪的技巧。（差分约束呢？最小生成树呢？强连通分量呢？）

A - [Jzzhu and Cities][] （补）

把火车线路加上跑**Dijkstra**就好了，标记火车线路，相等时也要push。在最短路上的火车线路不能被取消，剩下的全部能取消。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn = 200010;
    struct Edge {
        int to;
        bool istrain;
        ll w;
        Edge(int v, bool is, ll ww):to(v), istrain(is), w(ww){}
        bool operator<(const Edge& a)const {
            if(w==a.w) return istrain;  // 非火车节点先更新
            return w > a.w;
        }
    };
    vector<Edge> G[maxn];
    
    bool vis[maxn];
    int d[maxn];
    
    int Dijkstra() {
        memset(d, 0x3f, sizeof(d));
        memset(vis, 0, sizeof(vis));
        d[1] = 0;
        int res = 0;
    
        priority_queue<Edge> q;
        q.push(Edge(1, 0, 0));
        while(!q.empty()) {
            Edge tmp = q.top(); q.pop();
            int u = tmp.to;
            if(vis[u]) continue;
    
            vis[u] = 1;
        //    d[u] = tmp.w;
            if(tmp.istrain) ++res;
    
            for(int i=0;i<G[u].size();i++) {
                int v = G[u][i].to;
                if(!vis[v] && d[v]>=d[u]+G[u][i].w) {
                    d[v] = d[u] + G[u][i].w;
                    q.push(Edge(v, G[u][i].istrain, d[v]));
                }
            }
    
        }
        return res;
    
    }
    
    int main() {
        int n, m, k;
        cin>>n>>m>>k;
        int u, v, w;
        for(int i=0;i<m;i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(Edge(v, 0, w));
            G[v].push_back(Edge(u, 0, w));
        }
        for(int i=0;i<k;i++) {
            scanf("%d %d", &v, &w);
            G[1].push_back(Edge(v, 1, w));
            // G[v].push_back(Edge(1, 1, w));
        }
    
        printf("%d\n", k-Dijkstra());
    
        return 0;
    }

B - [Phillip and Trains][]

**BFS** 注意打标记！！！（虽然只是3\*100的地图也要爆内存！）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    int n, k, sx;
    char mp[3][110];
    bool vis[3][110];
    struct node {
        int x, y;
        node(int _x, int _y):x(_x), y(_y) {}
    };
    
    bool check(int x, int y) {
        if(x<0 || x>2)
            return false;
        if(y>=n)
            return true;
        if(mp[x][y]=='.')
            return true;
    
        return false;
    }
    
    bool bfs() {
        queue<node> q;
        q.push(node(sx, 0));
    
        while(q.size()) {
            node now = q.front(); q.pop();
            if(now.y>=n) {
                return true;
            }
    
        //    printf("(%d,%d) -> ", now.x, now.y);
            
            int nx = now.x, ny = now.y+1;
            if(!check(nx, ny))  continue; // 向右走一步
    
            for(int i=-1;i<=1;i++) {      // 尝试三个方向移动
                nx = now.x + i;
                if(check(nx, ny) && check(nx, ny+1) && check(nx, ny+2) && !vis[nx][ny+2]) {
                    q.push(node(nx, ny+2));
                    vis[nx][ny+2] = 1;
                }
            }
        }
        return false;
    }
    
    
    int main() {
        int t; cin>>t;
        while(t--) {
            scanf("%d %d", &n, &k);
            getchar();
            memset(vis, 0, sizeof(vis));
            for(int i=0;i<3;i++) {
                scanf("%s", mp[i]);
                
                if(mp[i][0]=='s')
                    sx = i;
                
            }
            printf("%s\n", bfs()?"YES":"NO");
        }
        
        return 0;
    }

C - [A Mist of Florescence][] （补）

构造题，技巧就是设计井字形的连通块，把其他颜色块涂到井字的格子上。

![1446954-20190731102702017-1626254094.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    int a, b, c, d;
    char ans[50][50];
    void solve() {
        for(int i=1;i<=12;i++) {
            for(int j=1;j<50;j++) {
                if(i%2==1 && j%2==1 && a) ans[i][j] = 'A', --a;
                else ans[i][j] = 'D';
            }
        }
    
        for(int i=13;i<=24;i++) {
            for(int j=1;j<50;j++) {
                if(i%2==1 && j%2==1 && b) ans[i][j] = 'B', --b;
                else ans[i][j] = 'D';
            }
        }
    
        --c;
        --d;
        for(int i=25;i<=36;i++) {
            for(int j=1;j<50;j++) {
                if(i%2==1 && j%2==1 && c) ans[i][j] = 'C', --c;
                else ans[i][j] = 'D';
            }
        }
    
        for(int j=1;j<50;j++) {
            ans[37][j] = 'C';
        }
    
        for(int i=38;i<50;i++) {
            for(int j=1;j<50;j++) {
                if(i%2==1 && j%2==1 && d) ans[i][j] = 'D', --d;
                else ans[i][j] = 'C';
            }
        }
    
    
    }
    int main() {
        cin>>a>>b>>c>>d;
        solve();
        printf("49 49\n");
        for(int i=1;i<50;i++) {
            for(int j=1;j<50;j++)
                printf("%c", ans[i][j]);
            printf("\n");
        }
        
        return 0;
    }

E - [Igor In the Museum][]

**DFS**到墙的边界 对每块编号！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    int n, m, k;
    char mp[1010][1010];
    int v[1010][1010], id;  // v[i][j]: mp[i][j]的分类编号   id: 当前编号
    int res[1010*1010];        // res[id]: 第id块的答案
    
    const int dx[] = {
         0, 0, 1, -1};
    const int dy[] = {
         1, -1, 0, 0};
    
    int ans;
    void dfs(int x, int y) {
        if(mp[x][y]=='*') {
            ans++;
            return;
        }
        v[x][y] = id;
        for(int i=0;i<4;i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(nx>=0 && nx<m && ny>=0 && ny<n && !v[nx][ny]) {
                dfs(nx, ny);
            }
        }
    }
    int main() {
        scanf("%d %d %d", &m, &n, &k);
        getchar();
        for(int i=0;i<m;i++) {
            scanf("%s", mp[i]);
        }
    
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(mp[i][j]=='.' && !v[i][j]) {
                    ++id;
                    ans = 0;
                    dfs(i, j);
                    res[id] = ans;
                } 
            }
        }
    
        while(k--) {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", res[v[x-1][y-1]]);
        }
    
        return 0;
    }

F - [The Cild and Toy][] （补）

**贪心**！由于每去掉一个点，等价于去掉了所有与它相连的边，就是问去掉全部边的最小代价。答案当然就是每条边两个节点权值小的那头的总和。都不用建图！！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 1010;
    int n, m;
    int w[maxn];
    
    int main() {
        cin>>n>>m;
        for(int i=1;i<=n;i++) {
            scanf("%d", &w[i]);
        }
        int u, v, ans = 0;
        for(int i=0;i<m;i++) {
            scanf("%d %d", &u, &v);
            ans += min(w[u], w[v]);
        }
        printf("%d\n", ans);
        
        return 0;
    }

G - [New Year Permutation][]

对连通部分排序就完事了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int n, num[310], id;
    int mp[310][310];
    bool vis[310];
    
    int ans[310];
    struct list {
        vector<int> num;
        vector<int> id;
    }L[310];
    
    void dfs(int x, int id) {
        vis[x] = 1;
    
        L[id].num.push_back(num[x]);
        L[id].id.push_back(x);
    
        for(int i=1;i<=n;i++) {
            if(mp[x][i]) {
                if(!vis[i])
                    dfs(i, id);
            }
        }
    }
    
    int main() {
        cin>>n;
        for(int i=1;i<=n;i++) {
            scanf("%d", &num[i]);
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                scanf("%1d", &mp[i][j]);
            }
        }
    
        for(int i=1;i<=n;i++) {
            if(!vis[i])
                dfs(i, ++id);
        }
    
        for(int i=1;i<=id;i++) {
            // for(int j=0;j<L[i].num.size();j++) {
            //     printf("%d:%d ", L[i].num[j], L[i].id[j]);
            // }
            // cout<<endl;
            
            sort(L[i].num.begin(), L[i].num.end());
            sort(L[i].id.begin(), L[i].id.end());
    
    
            for(int j=0;j<L[i].num.size();j++) {
                ans[L[i].id[j]] = L[i].num[j];
            }
        }
        for(int i=1;i<=n;i++) {
            printf("%d%c", ans[i], i!=n?' ':'\n');
        }
        return 0;
    }

H - [Alyona and the Tree][] （补）

从根开始**dfs**就好，每个节点为max(0LL, now+w\[i\])

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    const int maxn = 100010;
    typedef long long ll;
    
    struct Edge {
        int to;
        ll w;
        Edge(int v, ll ww):to(v), w(ww) {}
    };
    vector<Edge> G[maxn];
    int n, vw[maxn];
    int ans;
    void dfs(int u, int fa, ll now) {
        for(int i=0;i<G[u].size();i++) {
            int v = G[u][i].to;
            if(v!=fa) {
                if(vw[v]>=now+G[u][i].w) {
                    --ans;
                    // printf("%d->%d\n", u, v);
                    dfs(v, u, max(now+G[u][i].w, 0LL));
                }
            }
        }
    
    }
    
    int main() {
        cin>>n; ans = n;
        for(int i=1;i<=n;i++) {
            scanf("%d", &vw[i]);
        }
        int u, w;
        for(int i=2;i<=n;i++) {
            scanf("%d %d", &u, &w);
            G[i].push_back(Edge(u, w));
            G[u].push_back(Edge(i, w));
        }
    
        dfs(1, -1, 0);
        printf("%d\n", ans-1);
        return 0;
    }

L - [Love Triangle][]

假的三元环？？

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    using namespace std;
    const int maxn = 5010;
    int n, tot;
    int love[maxn], low[maxn];
    bool vis[maxn];
    bool ans;
    void dfs(int u) {
        if(ans) return;
    
        vis[u] = true;
        low[u] = ++tot;
        int v = love[u];
        if(v && !vis[v]) {
            dfs(v);
            if(love[v] && low[love[v]]==low[u]+2 && love[love[v]]==u) {
                ans = true;
                return;
            }
        }
    }
    
    int main() {
        cin>>n;
        for(int i=1;i<=n;i++) {
            scanf("%d", &love[i]);
        }
        ans = false;
        for(int i=1;i<=n;i++) {
            if(!vis[i] && !ans)
                dfs(i);
        }
        printf("%s\n", ans?"YES":"NO");
        return 0;
    }

N - [News Distribution][]

**并查集**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int maxn = 500100;
    int n, m;
    int fa[maxn];
    int g[maxn], cnt[maxn];
    
    int Find(int x) {
        return fa[x]==x?x:(fa[x]=Find(fa[x]));
    }
    
    void Union(int x, int y) {
        int a = Find(x);
        int b = Find(y);
        if(a==b) return;
        fa[a] = b;
    }
    
    int main() {
        cin>>n>>m;
        for(int i=1;i<=n;i++) fa[i] = i;
        while(m--) {
            int k;
            scanf("%d", &k);
            for(int i=0;i<k;i++) {
                scanf("%d", &g[i]);
            }
            for(int i=1;i<k;i++) {
                Union(g[0], g[i]);
            }
        }
        for(int i=1;i<=n;i++) {
            cnt[Find(i)]++;
        }
        for(int i=1;i<=n;i++) {
            printf("%d%c", cnt[Find(i)], i!=n?' ':'\n');
        }
        return 0;
    }

O - [NP-Hard Problem][] （补）

**二分图**裸题。。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn = 100010;
    int n, m;
    vector<int> G[maxn];
    int deg[maxn];
    int id[maxn];
    vector<int> ans[2];
    bool dfs(int u) {
        for(int i=0;i<G[u].size();i++) {
            int v = G[u][i];
            if(!id[v]) {
                id[v] = 3 - id[u];
                if(id[v]==1)
                    ans[0].push_back(v);
                else
                    ans[1].push_back(v);
                if(!dfs(v)) return false;
            } else if(id[v]==id[u]) return false;
        }
        return true;
    }
    
    int main() {
        cin>>n>>m;
        int u, v;
        for(int i=0;i<m;i++) {
            scanf("%d %d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
            ++deg[u];
        }
        for(int i=1;i<=n;i++) {
            if(!deg[i]) continue;
    
            if(!id[i]) {
                id[i] = 1;
                ans[0].push_back(i);
                if(!dfs(i)) 
                    return 0 * printf("-1\n");
            }
    
    
        }
        
        for(int k=0;k<=1;k++) {
            printf("%d\n", ans[k].size());
            for(int i=0;i<ans[k].size();i++) {
                printf("%d%c", ans[k][i], i==ans[k].size()-1?'\n':' ');
            }
        }
    
        return 0;
    }

## [Day2][] ##

第二天的主题是简单数论，下午挂的是CF上的一场区域赛：[2015 ACM National Contest Romania][]

注意文件读入要求！！！（第一题让我WA了4次样例。。。尝试两种方法写）

A - [Por Costel and Azerah][]

子序列里和为偶数的个数，简单**dp**（或组合数计算）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const ll mod = 1e9+7;
    const int maxn = 1000100;
    int arr[maxn], n;
    ll a[maxn], b[maxn];
    
    int main() {
        
        freopen("azerah.in", "r", stdin);
        freopen("azerah.out", "w", stdout);
            int t; cin>>t;
        while(t--) {
            scanf("%d", &n);
            for(int i=1;i<=n;i++) {
                scanf("%lld", &arr[i]);
            }
            a[1] = b[1] = 0;
            if(arr[1]%2==0) b[1] = 1;
            else a[1] = 1;
            for(int i=2;i<=n;i++) {
                if(arr[i]%2==0) {
                    b[i] = (b[i-1]*2+1) % mod;
                    a[i] = (a[i-1]*2)% mod;
                }else {
                    b[i] = (a[i-1] + b[i-1]) %mod;
                    a[i] = (a[i-1] + b[i-1] + 1) %mod;
                }
            //    cout<<b[i]<<endl;
            }
            cout<<b[n]<<endl;
        }
        return 0;
    }
    
    /*
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const ll mod = 1e9+7;
    const int maxn = 1000100;
    int arr[maxn], n;
    
    ll pow(ll a, ll n) {
        ll res = 1;
        while(n) {
            if(n%2) {
                res = res * a %mod;
            }
            a = a*a % mod;
            n >>= 1;
        }
        return res;
    }
    int main() {
        freopen("azerah.in", "r", stdin);
        freopen("azerah.out", "w", stdout);
        
        int t; cin>>t;
        while(t--) {
            ll odd = 0, even = 0;
            scanf("%d", &n);
            for(int i=1;i<=n;i++) {
                scanf("%lld", &arr[i]);
                if(arr[i]%2==0) even++;
                else odd++;
            }
            if(odd==0)
                cout<<(pow(2, even)-1+mod)%mod<<endl;
            else
                cout<<(pow(2, odd-1)*pow(2, even)%mod-1+mod)%mod<<endl;
        }
        return 0;
    }
    
     */

B - [Por Costel and the Algorithm][] （补）

给了一段Bellman-Ford代码，调整边的顺序让它最多执行两次。

记录**最短路**上的边即可，dfs输出边的顺序。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn = 100100;
    
    int n, m;
    struct Edge{
        int to;
        int id;
        ll w;
        Edge(int v, int i, ll _w):to(v), id(i), w(_w) {}
        bool operator<(const Edge& e)const {
            return w > e.w;
        }
    };
    vector<Edge> G[maxn];
    
    ll d[maxn];
    int e[maxn];  // e[v]: 连向v的边的编号
    bool path[2*maxn];
    
    void Dijkstra() {
        memset(d, 0x3f, sizeof(d));
        d[1] = 0;
    
        priority_queue<Edge> q;
        q.push(Edge(1, 0, 0));
        while(!q.empty()) {
            Edge tmp = q.top(); q.pop();
            int u = tmp.to;
            for(int i=0;i<G[u].size();i++) {
                int v = G[u][i].to;
                if(d[v]>d[u]+G[u][i].w) {
                    d[v] = d[u] + G[u][i].w;
    
                    path[e[v]] = 0;
                    path[G[u][i].id] = 1;
                    e[v] = G[u][i].id;
    
                    q.push(Edge(v, 0, d[v]));
                }
            }
        }
    }
    
    
    void dfs(int u) {
        for(int i=0;i<G[u].size();i++) {
            int m = G[u][i].id, v = G[u][i].to;
            //printf("%d->%d %d", u, v, m);
            if(path[m]) {
                printf("%d ", m);
                dfs(v);
            }
        }
    }
    
    int main() {
        freopen("algoritm.in", "r", stdin);
        freopen("algoritm.out", "w", stdout);
        int t; cin>>t;
        while(t--) {
            memset(e, 0, sizeof(e));
            memset(path, 0, sizeof(path));
            for(int i=0;i<maxn;i++) G[i].clear();
    
            scanf("%d %d", &n, &m);
            for(int i=1;i<=m;i++) {
                int u, v; ll w;
                scanf("%d %d %lld", &u, &v, &w);
                G[u].push_back(Edge(v, i, w));
            }
            Dijkstra();
    
            dfs(1);
            for(int i=1;i<=m;i++) {
                if(!path[i])
                    printf("%d ", i);
            }
            printf("\n");
        }
        return 0;
    }

C - [Por Costel and Bujor][]

D - [Por Costel and the Censorship Committee][]

E - [Por Costel and the Cipher][]

F - [Por Costel and the Alien Invasion][]

G - [Por Costel and the Orchard][]

H - [Por Costel and the Match][]

**并查集**裸题（可以用带权并查集做？）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 100010;
    int n, m;
    int fa[maxn*2];
    int Find(int x) {
        return fa[x]==x?x:(fa[x]=Find(fa[x]));
    }
     
    void Union(int x, int y) {
        int a = Find(x), b= Find(y);
        if(a!=b) 
            fa[a] = b;
    }
     
    int main() {
        freopen("meciul.in", "r", stdin);
        freopen("meciul.out", "w", stdout);
        int t; cin>>t;
        while(t--) {
            scanf("%d %d", &n, &m);
            for(int i=1;i<=2*n;i++) fa[i] = i;
            int x, y;
            while(m--) {
                scanf("%d %d", &x, &y);
                if(Find(x)!=Find(y) && Find(x+n)!=Find(y+n)) {
                    printf("YES\n");
                    Union(x, y+n);
                    Union(x+n, y);
                } else {
                    printf("NO\n");
                }
            }
        }
        return 0;
    }

I - [Por Costel and the Match][]

求\[n/i\]，**分块**（也可以只计算k=sqrt(n)的结果，ans\*2 - k\*k就是最终答案）

> ll ans = 0;  
> for(int i=1;i<=n;) \{  
>     ans += n/i \* (n/(n/i) - i +1);  
>     i = n/(n/i) + 1;  
> \}

J - [Por Costel and Pinball][]

K - [Por Costel and the Firecracker][] （补）

没有内存限制的话就是水题，可是完全没有优化空间。。。

百度之，学会了**分块打表**

把第一次查询看成了x1，debug了半天。。。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const int maxn = 10000010;
    const int mod = 10000003;
    ll n, a, b, x1, q, q1;
    ll ans[maxn/100+10];
    void pre() {
        ans[0] = x1;
        ll last = x1;
        for(ll i=1;i<maxn;i++) {
            last = (last*i % n + a) % n;
            if(i%100==0) {
                ans[i/100] = last;
            }
        //    cout<<i<<' '<<ans[i]<<endl;
        }
    
    }
    
    ll cal(ll k) {
        if(k%100==0) return ans[k/100];
        
        ll last = ans[k/100];
        for(ll i=k/100*100+1;i<=k;i++) {
            last = (last*i % n + a) % n;
        }
        return last;
    }
    
    int main() {
        freopen("pocnitoare.in", "r", stdin);
        freopen("pocnitoare.out", "w", stdout);
    
        cin>>n>>a>>b>>x1>>q>>q1;
    
        pre();
        printf("%lld\n", x1=cal(q1-1));  // 第一次查询是q1-1而不是x1-1!!!
        for(int i=1;i<q;i++) {
            q1 = (i*x1 % mod + b) % mod + 1;
            printf("%lld\n", x1=cal(q1-1));
    
        }
        return 0;
    }

L - [Por Costel and the Semipalindromes][]

WA了半天，原来是1左移出现了溢出，ll范围一定要写成 **(1LL<<k)**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    char res[1010];
    int tmp[1010];
    int main() {
        freopen("semipal.in", "r", stdin);
        freopen("semipal.out", "w", stdout);
        int t; cin>>t;
        while(t--) {
            int n; ll k;
            scanf("%d %lld", &n, &k);
            
            res[1] = res[n] = 'a';
    
            if(k>(1LL<<(n-2))) {
                k -= (1LL<<(n-2));
                res[1] = res[n] = 'b';
            } 
            --k;
            for(int i=0;i<n-2;i++) {
                tmp[n-1-i] = (k>>i)&1;
            }
            for(int j=2;j<n;j++) {
                if(tmp[j]) {
                    res[j] = 'b';
                } else {
                    res[j] = 'a';
                }
            }
    
            for(int i=1;i<=n;i++) {
                putchar(res[i]);
            }
            puts("");
        }
        return 0;
    }

## [Day3][] ##

题目来自于NAIPC 2016北美邀请赛。

E - [K-Inversions][]

给定一个只含有AB的字符串（长度不超过1000000），求间隔为1~n-1的B-A有多少对。

FFT模板题

F - [Mountain Scenes][]

给长度总和为n的木条以及相框的宽度w和高度h，问能组成多少种不同的山峰形状。

大家的签到dp题，我的自闭题。。。 j 没有从0开始样例死都调不出来 噗

也就是dp\[i\]\[0\] = 1

dp\[i\]\[j\] 为宽度 i 用了总长 j 的木条的方案数。 dp\[i+1\]\[j\] = sum( dp\[i\]\[j-k\] ) ( 0<=k<=h, j )

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    typedef long long ll; 
    const int maxn = 10010;
    const int mod = 1e9+7;
    
    int n, w, h;
    ll dp[110][maxn];
    int main() {
        
        cin>>n>>w>>h;
        // for(int i=0;i<=h && i<=w;i++) dp[i][0] = 1;
        dp[0][0] = 1;
        for(int i=1;i<=w;i++) {
             for(int j=0;j<=n;j++) {  // j=0 开始。。。坑死自己了
                for(int k=0;k<=h && k<=j;k++) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % mod;
                }
            }
        }
    
        ll ans = 0;
        for(int i=1;i<=n;i++)
            ans = (ans + dp[w][i])%mod;
    
        cout<<(ans-min(n/w, h))%mod<<endl;
        return 0;
    }

G - [Symmetry][]

平面上有 n 个点（ n<=1000），问至少加入多少点，使全部点与某一个点中心对称，或者全部点关于某条过其中两点的直线对称。

计算几何。

对于要求1，枚举全部点再check剩下点是否中心对称，复杂度O(n^2logn)，可行。

对于要求2，枚举两点所得直线再check剩下点是否关于直线对称，复杂度O(n^3logn)，TLE。

看题解好像是把直线去重才能过。

I - [Tourists][]

求树上所有整除关系的两对节点的最短路之和。

计算所有符合条件的节点复杂度O(nlogn)，树上两点 u, v 的最短路为 dep\[u\] + dep\[v\] - 2\*dep\[lca(u, v)\] + 1。

找了个LCA的[板子][Link 1]就1A了 O.O （第四个板子是改进的**树链剖分**求LCA，复杂度O(n + mlogn)，是其中最快的。）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn = 500010;
    struct Edge {
        int to, next;
    }edges[maxn];
    int head[maxn], tot;
    
    int fa[maxn], siz[maxn], dep[maxn], top[maxn];
    // top[u] == u : u不是重儿子
    // top[u] == fa: fa的重儿子是u
    void add(int u, int v) {
        edges[++tot].to = v;
        edges[tot].next = head[u];
        head[u] = tot;
    }
    
    void dfs(int u) { // 求fa, siz, dep, top
        int maxSon = 0, son = 0;
        top[u] = u;
        siz[u] = 1;
        for(int i=head[u];i;i=edges[i].next) {
            int v = edges[i].to;
            if(v==fa[u]) continue;
    
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
            siz[u] += siz[v];
    
            if(siz[v]>maxSon)
                maxSon = siz[son=v];
        }
        if(son)    // 重儿子
            top[son] = u;
    }
    
    int Find(int u) {
        return u==top[u]?u:top[u]=Find(top[u]);
    }
    
    int LCA(int u, int v) {
        if(Find(u)!=Find(v))
            return dep[top[u]]<dep[top[v]] ? LCA(u, fa[top[v]]):LCA(v, fa[top[u]]);
        else
            return dep[u]<dep[v] ? u:v;
    }
    
    
    int main() {
        int n;
        cin>>n;
        for(int i=0;i<n-1;i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            add(u, v);
            add(v, u);
        }
        memset(fa, -1, sizeof(fa));
        dfs(1);
    
        long long ans = 0;
        for(int i=1;i<=n/2;i++) {
            for(int j=i*2;j<=n;j+=i) {
                ans += dep[i]+dep[j]-2*dep[LCA(i, j)] + 1;
            }
        }
        printf("%lld\n", ans);
        return 0;
    }

## [Day4][] ##

A - [One-dimensional Japanese Crossword][]

简单模拟题。

B - [Passwords][]

简单数学题。

C - [Journey][]

E - [Jamie and Alarm Snooze][]

简单模拟题。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    
    bool check(int h, int m) {
    //    cout<<h<<":"<<m<<endl;
        if(h%10==7 || m%10==7) return true;
        return false;
    }
    int main()
    {
        int x, h, min;
        scanf("%d", &x);
        scanf("%d %d", &h, &min);
    
        int y = 0;
        while(!check(h, min)) {
            if(x==60) {
                if(--h<0) h = 23;
            } else {
                min -= x;
                if(min<0) {
                    min += 60;
                    if(--h<0) h = 23;
                }
            }
            ++y;
        }
    
        printf("%d\n", y);
        return 0;
    }

F - [Jamie and Binary Sequence (changed after round)][Jamie and Binary Sequence _changed after round]

给定 n 和 k，将 n 分解成 k 个二次幂之和，求2的指数最小且字典序最大的一组解，不存在则输出 No。

思维题。

把 n 转成二进制，要保证最高次幂最小，当二进制位1个数小于k时，把最高位2^n拆成 2^(n-1) + 2^(n-1)，这样多了一个1。

当拆分之后1的数量大于k时，要保证字典序最大，再从最低位开始拆分，每次只拆一个1，新的低位加2。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    
    ll n;
    int k, bits[100100], cnt, high, len;
    int tmp[65];
    
    int main()
    {
        cin>>n>>k;
        ll nn = n;
        for(int i=0;nn;i++) {
            tmp[i] = nn&1;
            nn >>= 1; 
            len = i;
            if(tmp[i]) ++cnt;
        }
        for(int i=len;i>=0;i--) {
            bits[len-i] = tmp[i];
        }
        high = len;  // 记录最高位指数
        // for(int i=0;i<=len;i++) cout<<bits[i];
    
        if(cnt>k) return 0 * printf("No\n");
    
        int pos = 0;
        while(cnt<k) {
            if(cnt+bits[pos]<=k) { // 最小化y=max(ai)
                cnt += bits[pos];
                bits[pos+1] += 2*bits[pos];
                bits[pos] = 0;
                ++pos;
                len = max(pos, len);   // 忘记更新，WA66组
            } else {
                pos = len; 
                while(!bits[pos]) --pos;
                while(cnt<k) {
                    ++cnt;
                    bits[pos] -= 1;
                    bits[++pos] += 2;
                    
                }
            }
        }
    
        printf("Yes\n");
        int up = max(pos, len);
        for(int i=0;i<=up;i++) {
            for(int j=0;j<bits[i];j++)
                printf("%d ", high-i);
        }
        return 0;
    }

G - [Jamie and Interesting Graph][]

需要构造出一个n个节点m条边的图，满足最小生成树的权为素数，1到n的最短路为素数。

构造1~n的一条链为最小生成树，权为p = 100019。剩下不停加边，边权为2p。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    using namespace std;
    int p = 100019;
    int main() {
        int n, m;
        cin>>n>>m;
        printf("%d %d\n", p, p);
        printf("1 2 %d\n", p-(n-2));
        for(int i=2;i<n;i++)
            printf("%d %d 1\n", i, i+1);
        m -= n-1;
    
        for(int i=1;i<n && m;i++)
        for(int j=i+2;j<=n && m;j++) {
            printf("%d %d %d\n", i, j, 2*p);
            --m;
            
        }
    
        return  0;
    }

H - [树上染色][Link 2]

很经典的树形dp。

// f\[u\]\[j\]: 以u为根节点，涂了 j 个黑点的子树对答案的最大贡献

对于一条边，左边子树有 x 个黑点，则右边有 k-x 个黑点，左边白点为 size\[v\] - x，右边白点为 n - size\[v\] - (k-x)，按照题意计算这部分贡献 val。

状态转移方程为 f\[u\]\[j\] = max( f\[u\]\[j\], f\[u\]\[j-x\] + f\[v\]\[x\] + val)，j 倒序枚举更新。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #define max(x, y) ((x) > (y) ? (x) : (y))
    #define min(x, y) ((x) < (y) ? (x) : (y))
    using namespace std;
    typedef long long ll;
    const int maxn = 2010;
    struct Edge {
        int u, w;
        Edge(int uu, int ww):u(uu), w(ww) {}
    };
    vector<Edge> G[maxn];
    int siz[maxn], n, kk;
    ll f[maxn][maxn];  // f[u][j]: 节点i含有j个黑点的子树对答案的最大贡献
    
    void dfs(int u, int fa) {
        f[u][0] = f[u][1] = 0;
        siz[u] = 1;
        for(int i=0;i<G[u].size();i++) {
            int v = G[u][i].u;
            if(v==fa) continue;
            
            dfs(v, u);
            siz[u] += siz[v];
     
        }
        for(int i=0;i<G[u].size();i++) {
            int v = G[u][i].u, w = G[u][i].w;
            if(v==fa) continue;
            
            for(int j=min(kk, siz[u]);j>=0;j--) {
                for(int k=0;k<=min(j, siz[v]);k++) {
                    if(f[u][j-k]!=-1) {
                        ll val = (1LL*k*(kk-k)+ 1LL*(siz[v]-k)*(n-kk-(siz[v]-k)))*w;
                        f[u][j] = max(f[u][j], f[u][j-k]+f[v][k]+val);
                    }
                }
            }
        }
    }
    
    
    int main() {
        scanf("%d %d", &n, &kk);
        for(int i=1;i<n;i++) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(Edge(v, w));
            G[v].push_back(Edge(u, w));
    
        }
        memset(f, -1, sizeof(f));
        dfs(1, -1);
        printf("%lld\n", f[1][kk]);
    
        return 0;
    }

## [Day5][] ##

## [Day6][] ##

转载于:https://www.cnblogs.com/izcat/p/11274543.html

[Day1]: https://vjudge.net/contest/312902
[Jzzhu and Cities]: https://vjudge.net/contest/312902#problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/d384a06b82314a84b2602df56654556e.png
[Phillip and Trains]: https://vjudge.net/contest/312902#problem/B
[A Mist of Florescence]: https://vjudge.net/contest/312902#problem/C
[1446954-20190731102702017-1626254094.png]: /images/20211029/1cf3a2d7bb4e4d8385604249b440cc85.png
[Igor In the Museum]: https://vjudge.net/contest/312902#problem/E
[The Cild and Toy]: https://vjudge.net/contest/312902#problem/F
[New Year Permutation]: https://vjudge.net/contest/312902#problem/G
[Alyona and the Tree]: https://vjudge.net/contest/312902#problem/H
[Love Triangle]: https://vjudge.net/contest/312902#problem/L
[News Distribution]: https://vjudge.net/contest/312902#problem/N
[NP-Hard Problem]: https://vjudge.net/contest/312902#problem/O
[Day2]: https://vjudge.net/contest/313217
[2015 ACM National Contest Romania]: https://codeforces.com/gym/100923
[Por Costel and Azerah]: https://codeforces.com/gym/100923/problem/A
[Por Costel and the Algorithm]: https://codeforces.com/gym/100923/problem/B
[Por Costel and Bujor]: https://codeforces.com/gym/100923/problem/C
[Por Costel and the Censorship Committee]: https://codeforces.com/gym/100923/problem/D
[Por Costel and the Cipher]: https://codeforces.com/gym/100923/problem/E
[Por Costel and the Alien Invasion]: https://codeforces.com/gym/100923/problem/F
[Por Costel and the Orchard]: https://codeforces.com/gym/100923/problem/G
[Por Costel and the Match]: https://codeforces.com/gym/100923/problem/H
[Por Costel and Pinball]: https://codeforces.com/gym/100923/problem/J
[Por Costel and the Firecracker]: https://codeforces.com/gym/100923/problem/K
[Por Costel and the Semipalindromes]: https://codeforces.com/gym/100923/problem/L
[Day3]: https://vjudge.net/contest/313584
[K-Inversions]: https://vjudge.net/contest/313584#problem/E
[Mountain Scenes]: https://vjudge.net/problem/Gym-101002F
[Symmetry]: https://vjudge.net/problem/Gym-101002G
[Tourists]: https://vjudge.net/problem/Gym-101002I
[Link 1]: https://blog.csdn.net/Sunshine_cfbsl/article/details/53212825
[Day4]: https://vjudge.net/contest/314412
[One-dimensional Japanese Crossword]: https://vjudge.net/problem/CodeForces-721A
[Passwords]: https://vjudge.net/problem/CodeForces-721B
[Journey]: https://cn.vjudge.net/problem/CodeForces-721C
[Jamie and Alarm Snooze]: https://cn.vjudge.net/problem/CodeForces-916A
[Jamie and Binary Sequence _changed after round]: https://vjudge.net/contest/314412#problem/F
[Jamie and Interesting Graph]: https://vjudge.net/problem/CodeForces-916C
[Link 2]: https://vjudge.net/problem/HYSBZ-4033
[Day5]: https://vjudge.net/contest/314730
[Day6]: https://vjudge.net/contest/314974