The 2018 ACM-ICPC Asia Nanjing Regional Programming Contest

A. Adrien and Austin

大意: $n$个石子, 编号$1$到$n$, 两人轮流操作, 每次删除$1$到$k$个编号连续的石子, 不能操作则输, 求最后胜负情况.

删除一段后变成两堆, 可以用$sg$函数打表找规律

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

    int n,k;

    cin>>n>>k;

    if (!n) return puts("Austin"),;

    if (k!=) return puts("Adrien"),;

    return puts(n&?"Adrien":"Austin");

}

D. Country Meow

大意: 给定空间$n$个点, 求构造一个点到$n$个点距离和最小.

等价于求一个最小的球覆盖所有的点, 可以三分套三分

E. Eva and Euro coins

大意: 给定$01$串$s$和$t$, 每次操作在$s$中选择一段连续相同的长为$k$的区间翻转, 求$s$是否能变为$t$

观察$1$: 操作可逆. 观察$2$: 长度为$k$的连续相同区间可以任意移动.

注意特判$k=1$

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n,k;

char s[N],t[N];

pii a[N];

void trans(char s[], int n) {

    int top = ;

    REP(i,,n) {

        if (!top||a[top].x!=s[i]) a[++top]=pii(s[i],);

        else if (++a[top].y==k) --top;

    }

    int cnt = ;

    REP(i,,top) while (a[i].y--) s[++cnt] = a[i].x;

    REP(i,cnt+,n) s[i] = '';

}

int main() {

    scanf("%d%d%s%s",&n,&k,s+,t+);

    if (k==) return puts("Yes"),;

    trans(s,n),trans(t,n);

    puts(strcmp(s+,t+)?"No":"Yes");

}

G. Pyramid

大意: 求$n$层等边三角形中等边三角形的个数.

打表然后插值求系数, 答案为$\frac{n}{4}+\frac{11n^2}{24}+\frac{n^3}{4}+\frac{n^4}{24}$

#include <iostream>

#include <set>

#include <queue>

#define x first

#define y second

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

using namespace std;

typedef pair<int,int> pii;

int n;

set<pii> s;

void dfs(int d, int x, int y) {

    if (d>n) return;

    if (s.count(pii(x,y))) return;

    s.insert(pii(x,y));

    dfs(d+,x-,y+);

    dfs(d+,x+,y+);

}

int dis(pii u, pii v) {

    return (u.x-v.x)*(u.x-v.x)+*(u.y-v.y)*(u.y-v.y);

}

int main() {

    cin>>n;

    dfs(,,);

    vector<pii> v(s.begin(),s.end());

    int sz = v.size(), ans = ;

    REP(i,,sz-) REP(j,i+,sz-) REP(k,j+,sz-) {

        int q=dis(v[i],v[j]),w=dis(v[i],v[k]),e=dis(v[j],v[k]);

        if (q==w&&w==e) ++ans;

    }

    printf("%d\n",ans);

}

暴力代码

H. Huge Discount

大意: 给定一个长$n$的串$s$, 只含数字'0','1','2', 有$n$个商品, 第$i$个商品价格为s[i...n]. 对于一个商品, 每次操作选两个连续且不相同的数删除, 可以进行任意次操作. 求$n$个商品最小价格和.

I. Magic Potion

大意: $n$个英雄, $m$个怪物, 给定每个英雄能杀死的怪物集合, 每个英雄只能从中选一个杀死. 可以选出$k$个英雄多杀一次, 求最大能杀怪物数.

最大流水题, 开个虚拟结点, 源点向虚拟结点连$k$即可.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

const int N = 1e6+;

const int SS = N-, S = N-, T = N-, INF = 0x3f3f3f3f;

int n, m, k;

struct edge {

    int to,w,next;

    edge(int to=,int w=,int next=):to(to),w(w),next(next){}

} e[N];

int head[N], dep[N], vis[N], cur[N], cnt=;

queue<int> Q;

int bfs() {

    REP(i,,n+m) dep[i]=INF,vis[i]=,cur[i]=head[i];

    REP(i,SS,T) dep[i]=INF,vis[i]=,cur[i]=head[i];

    dep[S]=,Q.push(S);

    while (Q.size()) {

        int u = Q.front(); Q.pop();

        for (int i=head[u]; i; i=e[i].next) {

            if (dep[e[i].to]>dep[u]+&&e[i].w) {

                dep[e[i].to]=dep[u]+;

                Q.push(e[i].to);

            }

        }

    }

    return dep[T]!=INF;

}

int dfs(int x, int w) {

    if (x==T) return w;

    int used = ;

    for (int i=cur[x]; i; i=e[i].next) {

        cur[x] = i;

        if (dep[e[i].to]==dep[x]+&&e[i].w) {

            int f = dfs(e[i].to,min(w-used,e[i].w));

            if (f) used+=f,e[i].w-=f,e[i^].w+=f;

            if (used==w) break;

        }

    }

    return used;

}

int dinic() {

    int ans = ;

    while (bfs()) ans+=dfs(S,INF);

    return ans;

}

void add(int u, int v, int w) {

    e[++cnt] = edge(v,w,head[u]);

    head[u] = cnt;

    e[++cnt] = edge(u,,head[v]);

    head[v] = cnt;

} 

int main() {

    scanf("%d%d%d",&n,&m,&k);

    add(S,SS,k);

    REP(i,,n) {

        add(S,i,);

        add(SS,i,);

        int t;

        scanf("%d",&t);

        while (t--) {

            int x;

            scanf("%d",&x);

            add(i,n+x,);

        }

    }

    REP(i,,m) add(n+i,T,);

    printf("%d\n",dinic());

}

J. Prime Game

大意: 给定序列$a$, 设$fac(l,r)$为$[l,r]$区间积的素因子个数, 求$\sum\limits_{i=1}^n\sum\limits_{j=i}^n fac(i,j)$

计算出每种素因子所在的区间即可

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, P2 = , INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 1e6+;

int n, mi[N], a[N];

vector<int> g[N];

int main() {

    REP(i,,N-) mi[i]=i;

    REP(i,,N-) if (mi[i]==i) {

        for (int j=i;j<N;j+=i) mi[j]=min(mi[j],i);

    }

    scanf("%d", &n);

    REP(i,,n) {

        scanf("%d", a+i);

        while (a[i]!=) g[mi[a[i]]].pb(i),a[i]/=mi[a[i]];

    }

    ll ans = ;

    REP(i,,N-) if (g[i].size()) {

        ll t = (ll)n*(n+)/;

        int now = ;

        g[i].pb(n+);

        for (int j:g[i]) {

            t -= (ll)(j-now)*(j-now+)/;

            now = j+;

        }

        ans += t;

    }

    printf("%lld\n", ans);

}

M. Mediocre String Problem

大意: 给定串$s,t$, 求三元组$(i,j,k)$的个数, 满足$j-i+1>k$且$s[i,j]+t[1,k]$为回文串

合法方案一定是$s$中与$t$的一段前缀对称, 然后中间再连上一段回文串.

exkmp求出最长匹配前缀, pam求出每个位置开头的回文串数

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <cstring>

#include <bitset>

#include <functional>

#include <random>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<',';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=%P;for (a%=P;n;a=a*a%P,n>>=)if(n&)r=r*a%P;return r;}

ll inv(ll x){return x<=?:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=;char p=getchar();while(p<''||p>'')p=getchar();while(p>=''&&p<='')x=x*+p-'',p=getchar();return x;}

//head

const int N = 4e6+;

void init(char *s, int *z, int n) {

    int mx=,l=;

    REP(i,,n-) {

        z[i] = i<mx?min(mx-i,z[i-l]):;

        while (s[z[i]]==s[i+z[i]]) ++z[i];

        if (i+z[i]>mx) mx=i+z[i],l=i;

    }

}

int n, m, tot, cnt, last, fac[N];

int fail[N], len[N], ch[N][], num[N];

ll sum[N];

char ss[N];

int getfail(int x) {

    while (ss[cnt-len[x]-]!=ss[cnt]) x=fail[x];

    return x;

}

int insert(int c) {

    ss[++cnt] = c;

    int p = getfail(last);

    if (!ch[p][c]) {

        len[++tot] = len[p]+;

        fail[tot]=ch[getfail(fail[p])][c];

        ch[p][c]=tot;

        num[tot]=num[fail[tot]]+;

    }

    last = ch[p][c];

    return num[last];

}

void clear() {

    REP(i,,tot) {

        memset(ch[i],,sizeof ch[]);

        num[i]=len[i]=fail[i]=;

    }

    ss[]='#',fail[]=,last=;

    len[]=,len[]=-,tot=,cnt=;

}

char s[N], t[N];

int c[N],z[N];

int main() {

    scanf("%s%s",s,t);

    n = strlen(s);

    m = strlen(t);

    clear();

    PER(i,,n-) c[i]=insert(s[i]);

    reverse(s,s+n);

    t[m] = '?';

    strcat(t,s);

    init(t,z,n+m+);

    ll ans = ;

    REP(i,m+,n+m) ans += (ll)z[i]*c[n+-i+m];

    printf("%lld\n", ans);

}

巴特西

The 2018 ACM-ICPC Asia Nanjing Regional Programming Contest

最新文章

热门文章