ACM-ICPC Asia Beijing Regional Contest 2018 Reproduction hihocoder1870~1879

A

签到，dfs 或者 floyd 都行。

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

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
const int SZ = 1e5 + 10;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const LD eps = 1e-8;

LL read() {
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

string S1[22],S2[22];
int n;
int f[111][111];

void work() {
    map<string,int> mp;
    int tot = 0;
    for(int i = 1;i <= n;i ++) {
        string s1 = S1[i],s2 = S2[i];
        if(!mp[s1]) mp[s1] = ++ tot;
        if(!mp[s2]) mp[s2] = ++ tot;
    }

    for(int i = 1;i <= tot;i ++) {
        for(int j = 1; j <= tot;j ++) {
            f[i][j] = 0;
        }
    }

    for(int i = 1;i <= n;i ++) {
        string s1 = S1[i],s2 = S2[i];
        int x = mp[s1],y = mp[s2];
        if(f[y][x]) {
            cout << s1 << " " << s2 << endl;
            return ;
        }
        f[x][y] = 1;
        for(int k = 1;k <= tot;k ++) {
            for(int u = 1;u <= tot;u ++) {
                for(int v = 1;v <= tot;v ++) {
                    if(f[u][k] && f[k][v]) {
                        f[u][v] = 1;
                    }
                }
            }
        }
        for(int u = 1;u <= tot;u ++) {
            for(int v = 1;v <= tot;v ++) {
                if(f[u][v]) {
                    if(u == v || f[v][u]) {
                        cout << s1 << " " << s2 << endl;
                        return ;
                    }
                }
            }
        }
       /* for(int u = 1;u <= tot;u ++,puts(""))
            for(int v = 1;v <= tot;v ++)
                printf("%d ",f[u][v]);
        puts("");*/
    }
    puts("0");
    return ;
}

int main() {
    while(~scanf("%d",&n)) {
        for(int i = 1;i <= n;i ++) {
            string s1,s2;
            cin >> s1 >> s2;
            S1[i] = s1;
            S2[i] = s2;
        }
        work();
    }
}

B

阅读题，模拟，坑点多，WA了好多发，换了个写法就过了，不知道为什么

C

题意：定义 (a,b,c) 为一组勾股数，c 是斜边长度，且 (a,b,c) 与 (b,a,c) 看做一组。问 c<=n 的三元组有多少对。 \(n \le 10^9\)

key：推公式

我真的是惊了，为什么要出这种带了板子就会的题。

首先你要知道勾股数的构造才能做这个题，即 \(a=m^2-n^2,b=2mn,c=m^2+n^2\) 。所有勾股数不好算，所以我们对本原勾股数计数，乘上个倍数即可。在上式中， \((a,b,c)\) 为一组本原勾股数当且仅当 \(\gcd(m,n)=1 \text{且 $m,n$为一奇一偶}\) 。

设 \(f(n)\) 为以 n 为斜边的三元组对数， \(g(n)\) 为以 n 为斜边的本原勾股数个数，\(F,G\) 为对应的前缀和，那么有：
\[ f = g \times 1 \to F=\sum_{1 \le i\le n}G(n/i) \\ G(n) = \sum_{1\le x\le N} \sum_{1 \le y \le N} [x^2+y^2 \le N][\gcd(x,y)=1][\text{x is odd, y is even}] \]
然后就对 G 随便推一波就行了。形式是一个调和级数。

不预处理的话复杂度是 \(O(Tn^{3/4}\ln n)\)，预处理前根号下三分之二次方的复杂度就变成 \(O(Tn^{2/3}\ln n)\) 。预处理就直接用上面给出的这个 G ，随便积分一下算出来预处理前 B 项的复杂度是 \(O(B \ln B)\) 。实测了一下大概取 \(10^7\) 比较优，十组 \(10^9\) 只跑 0.6s 左右。

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

typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
const int SZ = 1e7 + 10;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const LD eps = 1e-8;

LL read() {
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

int preG[SZ];
const int MAXN = 1e7;
int mu[100100];
bool vis[100100];
int pri[100100];

void preWork(int n) {
    for(int x = 1;x * x <= n;x += 2) {
        for(int y = 2;x * x + y * y <= n;y += 2) {
            if(__gcd(x,y) == 1)
                preG[x*x+y*y] ++;
        }
    }
    for(int i = 1;i <= n;i ++) preG[i] += preG[i-1];

    n = 100000;
    mu[1] = 1;
    for(int i = 2;i <= n;i ++) {
        if(!vis[i]) pri[++ pri[0]] = i,mu[i] = -1;
        for(int j = 1,m;j <= pri[0] && (m=i*pri[j]) <= n;j ++) {
            vis[m] = 1;
            if(i%pri[j] == 0) {
                mu[m] = 0;
            }
            else {
                mu[m] = -mu[i];
            }
        }
    }
}

LL G(int n) {
    if(n <= MAXN) return preG[n];
    LL ans = 0;
    for(int d = 1;d * d * 2 <= n;d ++) {
        int tmp = 0;
        int d2 = d*d,m = n/d2;
        for(int x = 1,lim = sqrt(n-d*d)/d;x*x <= m;x ++) {
            while(lim*lim+x*x > m) lim --;
            if((d*x)&1) tmp += lim / 2;
            else tmp += lim;
        }
        ans += mu[d] * tmp;
    }
    return ans / 2;
}

int main() {
   // freopen("C.in","r",stdin);
    preWork(MAXN);
    int T = read();
    while(T --) {
        int n = read();
        LL ans = 0;
        for(int i = 1,r;i <= n;i = r + 1) {
            r = n / (n / i);
            ans += G(n / i) * (r-i+1);
        }
        printf("%lld\n",ans);
    }
}
/**
3080075432
*/

D

题意：你要从 0 跳到 200，第 i 个位置能跳到第 i+1 和 i+2 上。你可以设置若干个传送门，一个位置只有一个入口，出口任意。跳到入口处就立马被传送到出口，如果构成环则永远出不去。求使得走到 200 的方案数恰好为 M 的一组传送门设置方案。 \(M < 2^{32}\)

key：构造

如果你想 ban 掉一个位置，那么一定是原地传送最优。考虑 ban 掉第 i 个位置，那么设第 i-1 个位置的方案数是 x，那么从第 i-1 开始的方案数是 \(x,0,x,x,2x\) 。这样就容易想到二进制。

如果想凑出 \(2^i\) ，那么应该设置为 \(2^i,X,2^i,2^i,2^{i+1},Y\) 。如果不想，那么应该是 \(2^i,2^i,2^{i+1},Y\) 。其中 X 是传到终点，Y 是原地传送。

#include<bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
using namespace std;
ll m;
ll f[304];
vector<pa>ans;
int w33ha(){
    ans.clear();
    memset(f,0,sizeof(f));
    f[0]=1;
    f[1]=1;
    //int a=0;
    int B = 0;
    for(ll i=0;i<=32;i++){
        if((m&(1LL<<i))){
            ans.push_back({B+1,199});
            ans.push_back({B+5,B+5});
            B += 6;
        }
        else{
            ans.push_back({B+3,B+3});
            B += 4;
        }
    }
    ans.push_back({197,197});
    ans.push_back({198,198});
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();i++){
        printf("%d %d\n",ans[i].first,ans[i].second);
    }
    return 0;
}

int main(){
    while(scanf("%lld",&m)!=EOF)w33ha();
    return 0;
}

E

咕

F

题意：给一个有向图，定义 (u,v) 合法当且仅当 u 能走到 v，权值为 u^v。Q 次询问每次问第 k 大的权值。 \(n \le 5*10^4,m \le 2*10^5 , Q \le 10,T \le 3, k \le 10^9\)

key：bitset

容易想到二分答案，问题在于 check 。如果我们处理出来点 x 能走到哪些点，设这个集合是 S，那么就要找有多少个 \(y \in S\) ，使得 x^y>mid。这个是在 trie 上做的。所以就不用二分答案了，直接在 trie 上贪心。

考虑从 trie 上走的过程：贪心选 0，如果不行，那么走 1。判断是否不行是用子树和，这就是值域上的区间和，所以现在问题变成查询标号小于等于一个数的个数。

所以有一个 bitset 的做法。用 tarjan+拓扑排序 预处理 bitset 的复杂度是 \(O((n+m)n/W)\)，模拟 trie 上的复杂度是 \(O(n^2/W\log n)\) ，后者应该是不行的。

所以手写 bitset ，对 n/W 位建一个前缀和。后者的复杂度为 \(O(n \log n)\) ，需要用到 __builtin_popcountll 。

所以这个题的总复杂度为 \(O(T((n+m)n/W+Qn\log n))\) ，空间复杂度为 \(O(n^2/W)\)

（这里手写了 bitset ，由于差分的性质所以改成前缀和，由于 __builtin_popcountll 而优化了查询的复杂度。如果不是二进制 1 的个数那么查询的复杂度要再乘一个 W，如果不满足差分性质可以在 bitset 上分块）

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

typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
const int SZ = 5e4 + 10;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const LD eps = 1e-8;

LL read() {
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

struct Bitset {
    #define W (64)

    int n;
    ULL bits[SZ / W + 10];
    int num[SZ / W + 10];

    void preWork() {
        for(int i = 0;i <= n/W;i ++) num[i] = __builtin_popcountll(bits[i]);
        for(int i = n/W-1;i >= 0;i --) num[i] += num[i+1];
     //  for(int i = 0;i < m;i ++) printf("%d ",sum[i]); puts("");
      //  for(int i = 0;i <= n/W;i ++) printf("%llu ",bits[i]); puts("");
    }

    int ask(int x) {
        if(x > n) return 0;
        int blockid = x / W;
        int ans = __builtin_popcountll(bits[blockid]>>(x%W));
        blockid ++;
        if(blockid <= n/W) ans += num[blockid];
        return ans;
    }

    int ask(int l,int r) {
        return ask(l) - ask(r+1);
    }

    void Or(const Bitset &t) {
        for(int i = 0;i <= n / W;i ++) bits[i] |= t.bits[i];
    }

    void Copy(const Bitset &t) {
        n = t.n;
        for(int i = 0;i <= n / W;i ++) bits[i] = t.bits[i];
    }

    void Set(int x) {
        bits[x/W] |= 1llu << (x%W);
    }

    void init(int nn) {
        n = nn; //n ++;
        for(int i = 0;i <= n / W;i ++) bits[i] = 0;
    }

    void print() {
        for(int i = 0;i < n;i ++) {
            if(bits[i/W] >> (i%W) & 1)
                printf("%d ",i);
        }
        puts("");
    }

    #undef W
}bs[SZ];

struct Tarjan {

    int n;
    int dfn[SZ],low[SZ],dfs_clock,scccnt,sccnum[SZ];
    vector<int> g[SZ],sccnodes[SZ];
    stack<int> S;

    void dfs(int u) {
        dfn[u] = low[u]= ++ dfs_clock;
        S.push(u);
        for(int v : g[u]) {
            if(!dfn[v]) {
                dfs(v);
                low[u] = min(low[u],low[v]);
            }
            else if(!sccnum[v])
                low[u] = min(low[u],dfn[v]);
        }
        if(low[u] == dfn[u]) {
            scccnt ++;
            while(1) {
                int x = S.top(); S.pop();
                sccnum[x] = scccnt;
                sccnodes[scccnt].push_back(x);
                if(x == u) break;
            }
        }
    }

    vector<int> g2[SZ];
    int cd[SZ];

    void work(Bitset bs[]) {
        for(int i = 1;i <= n;i ++)
            if(!dfn[i])
                dfs(i);
      //  for(int u = 1;u <= n;u ++) printf("%d ",sccnum[u]); puts("");
        for(int u = 1;u <= n;u ++)
            for(int v : g[u])
                if(sccnum[u] != sccnum[v]) {
                    g2[sccnum[v]].push_back(sccnum[u]);
                    cd[sccnum[u]] ++;
                }
        static Bitset tmp[SZ];
        for(int i = 1;i <= scccnt;i ++) {
            tmp[i].init(n); //tmp[i].print();
            for(int x : sccnodes[i])
                tmp[i].Set(x);
        }
        queue<int> q;
        for(int i = 1;i <= scccnt;i ++)
            if(cd[i] == 0) {
                q.push(i);
            }
        while(q.size()) {
            int v = q.front(); q.pop();
           // printf("%d: ",v); tmp[v].print();
            for(int x : sccnodes[v]) bs[x].Copy(tmp[v]);
            for(int u : g2[v]) {
                tmp[u].Or(tmp[v]);
                cd[u] --;
                if(cd[u] == 0) {
                    q.push(u);
                }
            }
        }
    }

    void addEdge(int x,int y) {
        g[x].push_back(y);
    }

    void init(int nn) {
        n = nn;
        for(int i = 1;i <= scccnt;i ++) {
            g2[i].clear();
            sccnodes[i].clear();
            cd[i] = 0;
        }
        for(int i = 1;i <= n;i ++) {
            g[i].clear();
            dfn[i] = low[i] = sccnum[i] = 0;
        }
        scccnt = 0;
        dfs_clock = 0;
    }

}tarjan;

int now[SZ];

void work(int n,int &mid,int id,int &k) {
    LL ans = 0;
    for(int i = 1;i <= n;i ++) {
        int t,l,r;
        if(i>>id&1)
            t = bs[i].ask(l=now[i],r=now[i]+(1<<id)-1);
        else
            t = bs[i].ask(l=now[i]+(1<<id),r=now[i]+(2<<id)-1);
        ans += t;
     //   printf("%d: [%d,%d] %d\n",i,l,r,t);
    }
    //cout << id << " " << ans << " " << k << endl;
    if(k <= ans) {
        for(int i = 1;i <= n;i ++) {
            if((i>>id&1) == 0) {
                now[i] |= 1 << id;
            }
        }
        mid |= 1 << id;
    }
    else {
        k -= ans;
        for(int i = 1;i <= n;i ++) {
            if(i>>id&1) {
                now[i] |= 1 << id;
            }
         }
    }
    //cout << k << endl;
   // for(int i = 1;i <= n;i ++) printf("%d ",now[i]); puts("");
}

int main() {
   // freopen("F.in","r",stdin); freopen("my.out","w",stdout);
    int T = read();
    while(T --) {
        int n = read(),m = read(),Q = read();
        tarjan.init(n);
        for(int i = 1;i <= m;i ++) {
            int x = read(),y = read();
            tarjan.addEdge(x,y);
        }
        tarjan.work(bs);
//        for(int i = 1;i <= n;i ++) bs[i].print();
        for(int i = 1;i <= n;i ++){
            bs[i].preWork();
        }
        while(Q --) {
            int k = read();
            int ans = 0;
            for(int i = 1;i <= n;i ++) now[i] = 0;
            for(int i = 16;i >= 0;i --) {
                work(n,ans,i,k);
            }
            printf("%d\n",ans);
        }
    }
}

G

题意：给一个 n 次多项式 F，求一个 n 阶多项式 G，使得 G 的每一个根（不一定实根）为 F 的对应根的 m 次幂。 \(n+m \le 10,|a_i| \le 120\)，保证 G 的系数 \(< 10^{12}\)

H

题意：定义字符串 A 几乎匹配 B 当且仅当 B 存在一个子串，与 A 长度相同且至多一个字符不同。给出 A，求有多少个长度为 m 的 B。字符集是 {0,1}。 \(|A|,m\le 40\)

key：dp

主要怕算重，这个只需要找到第一次匹配的位置即可。\(f_{i,j}\) 表示 A 第一次出现位置在 \([i-|A|+1,i]\) 且第 j 位不同的方案数，有：
\[ f_{i,j} = 2^{i-|A|}-\sum_{k\le i-|A|,l}f_{k,l}\times 2^{i-|A|-k}-\sum_{i-|A|< k< i}f_{k,l}\times w(i,j,k,l) \]
即前面随便填的，减去出现过的。第一项是出现位置与当前串不相交的个数，第二项是相交的个数。注意这里相交可能不合法，所以需要一个 \(w(i,j,k,l)\) 来 check，合法时返回 1，否则返回 0。这个可以预处理一下。总复杂度是 \(O(m^2|A|^2)\)

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

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,int> pli;
const int SZ = 1e5 + 10;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const LD eps = 1e-8;

LL read() {
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

char s[55];
int n,m;
LL f[55][55];
LL g[55][55][55];

bool isequ(int len,int p1,int p2) {
    string s1,s2;
    for(int i = 1;i <= len;i ++) {
        if(i==p1) {
            if(s[i] == '0') s1 += '1';
            else s1 += '0';
        }
        else s1 += s[i];
    }
    for(int i = n-len+1;i <= n;i ++) {
        if(i==p2) {
            if(s[i] == '0') s2 += '1';
            else s2 += '0';
        }
        else s2 += s[i];
    }
    return s1 == s2;
}

int main() {
    int T = read();
    while(T --) {
        n = read(),m = read();
        scanf("%s",s+1);
        for(int j = 0;j <= n;j ++) {
            for(int k = 1;k < n;k ++) {
                for(int l = 0;l <= n;l ++) {
                    if(isequ(k,j,l)) {
                        g[j][k][l] = 1;
                    }
                    else {
                        g[j][k][l] = 0;
                    }
                }
            }
        }
        for(int i = 1;i <= m;i ++) {
            for(int j = 0;j <= n;j ++) {
                if(i-n < 0) {
                    f[i][j] = 0;
                    continue;
                }
                LL ans = 1ll<<(i-n);
                for(int k = 1;k < i;k ++) {
                    for(int l = 0;l <= n;l ++) {
                        if(k <= i-n) {
                            ans -= f[k][l] * (1ll<<(i-n-k));
                        }
                        else {
                            ans -= f[k][l] * g[j][k-i+n][l];
                        }
                    }
                }
                f[i][j] = ans;
            }
        }
        LL ans = 0;
        for(int i = 1;i <= m;i ++) {
            for(int j = 0;j <= n;j ++) {
                ans += f[i][j] * (1ll<<(m-i));
            }
        }
        printf("%lld\n",ans);
    }
}

I

打表找规律

J

题意：二维平面上给出 n 个点，求所有锐角三角形面积之和。 \(n \le 2000\)

key：扫描线

总面积减去直角三角形面积减去钝角三角形面积。这三个都能在极角排序的序列上用双指针定位。算面积用前缀和就行。