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"),0; if (k!=1) return puts("Adrien"),0; return puts(n&1?"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+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;} inline int rd() {int x=0;char p=getchar();while(p<‘0‘||p>‘9‘)p=getchar();while(p>=‘0‘&&p<=‘9‘)x=x*10+p-‘0‘,p=getchar();return x;} //head const int N = 1e6+50; int n,k; char s[N],t[N]; pii a[N]; void trans(char s[], int n) { int top = 0; REP(i,1,n) { if (!top||a[top].x!=s[i]) a[++top]=pii(s[i],1); else if (++a[top].y==k) --top; } int cnt = 0; REP(i,1,top) while (a[i].y--) s[++cnt] = a[i].x; REP(i,cnt+1,n) s[i] = ‘0‘; } int main() { scanf("%d%d%s%s",&n,&k,s+1,t+1); if (k==1) return puts("Yes"),0; trans(s,n),trans(t,n); puts(strcmp(s+1,t+1)?"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+1,x-1,y+1); dfs(d+1,x+1,y+1); } int dis(pii u, pii v) { return (u.x-v.x)*(u.x-v.x)+3*(u.y-v.y)*(u.y-v.y); } int main() { cin>>n; dfs(0,0,0); vector<pii> v(s.begin(),s.end()); int sz = v.size(), ans = 0; REP(i,0,sz-1) REP(j,i+1,sz-1) REP(k,j+1,sz-1) { 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+10; const int SS = N-3, S = N-2, T = N-1, INF = 0x3f3f3f3f; int n, m, k; struct edge { int to,w,next; edge(int to=0,int w=0,int next=0):to(to),w(w),next(next){} } e[N]; int head[N], dep[N], vis[N], cur[N], cnt=1; queue<int> Q; int bfs() { REP(i,1,n+m) dep[i]=INF,vis[i]=0,cur[i]=head[i]; REP(i,SS,T) dep[i]=INF,vis[i]=0,cur[i]=head[i]; dep[S]=0,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]+1&&e[i].w) { dep[e[i].to]=dep[u]+1; Q.push(e[i].to); } } } return dep[T]!=INF; } int dfs(int x, int w) { if (x==T) return w; int used = 0; for (int i=cur[x]; i; i=e[i].next) { cur[x] = i; if (dep[e[i].to]==dep[x]+1&&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^1].w+=f; if (used==w) break; } } return used; } int dinic() { int ans = 0; 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,0,head[v]); head[v] = cnt; } int main() { scanf("%d%d%d",&n,&m,&k); add(S,SS,k); REP(i,1,n) { add(S,i,1); add(SS,i,1); int t; scanf("%d",&t); while (t--) { int x; scanf("%d",&x); add(i,n+x,1); } } REP(i,1,m) add(n+i,T,1); 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+7, P2 = 998244353, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;} inline int rd() {int x=0;char p=getchar();while(p<‘0‘||p>‘9‘)p=getchar();while(p>=‘0‘&&p<=‘9‘)x=x*10+p-‘0‘,p=getchar();return x;} //head const int N = 1e6+10; int n, mi[N], a[N]; vector<int> g[N]; int main() { REP(i,1,N-1) mi[i]=i; REP(i,2,N-1) if (mi[i]==i) { for (int j=i;j<N;j+=i) mi[j]=min(mi[j],i); } scanf("%d", &n); REP(i,1,n) { scanf("%d", a+i); while (a[i]!=1) g[mi[a[i]]].pb(i),a[i]/=mi[a[i]]; } ll ans = 0; REP(i,2,N-1) if (g[i].size()) { ll t = (ll)n*(n+1)/2; int now = 1; g[i].pb(n+1); for (int j:g[i]) { t -= (ll)(j-now)*(j-now+1)/2; now = j+1; } 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+7, INF = 0x3f3f3f3f; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;} ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;} inline int rd() {int x=0;char p=getchar();while(p<‘0‘||p>‘9‘)p=getchar();while(p>=‘0‘&&p<=‘9‘)x=x*10+p-‘0‘,p=getchar();return x;} //head const int N = 4e6+50; void init(char *s, int *z, int n) { int mx=0,l=0; REP(i,1,n-1) { z[i] = i<mx?min(mx-i,z[i-l]):0; 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][26], num[N]; ll sum[N]; char ss[N]; int getfail(int x) { while (ss[cnt-len[x]-1]!=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]+2; fail[tot]=ch[getfail(fail[p])][c]; ch[p][c]=tot; num[tot]=num[fail[tot]]+1; } last = ch[p][c]; return num[last]; } void clear() { REP(i,0,tot) { memset(ch[i],0,sizeof ch[0]); num[i]=len[i]=fail[i]=0; } ss[0]=‘#‘,fail[0]=1,last=0; len[0]=0,len[1]=-1,tot=1,cnt=0; } 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,0,n-1) c[i]=insert(s[i]); reverse(s,s+n); t[m] = ‘?‘; strcat(t,s); init(t,z,n+m+1); ll ans = 0; REP(i,m+1,n+m) ans += (ll)z[i]*c[n+1-i+m]; printf("%lld\n", ans); }
The 2018 ACM-ICPC Asia Nanjing Regional Programming Contest
原文：https://www.cnblogs.com/uid001/p/11546149.html
