【比赛】gym-101889
比赛
2017-2018 ACM-ICPC Latin American Regional Programming Contest
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | Y | Y | - | Y | L | L | Y | Z | L | - | - | **Z |
题解
B
规律题。
- 如果含有元音字母，最终串中第一个字母必为元音。
- 演绎翻转操作，维护一个双端队列，若开始向左选择数字，从头部加入，反之从尾部加入。遇到一个元音字母则更改插入的方向。
- 只考虑元音字母，按照数量奇偶分类，选择的方案唯一；在插入辅音字母后，选择的方案至于开始的辅音字母是哪个有关。
- 只有辅音字母是只有一种输入方案。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int inf = 0x7fffffff;
char s[100010];
bool ch(char c){
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
vector <int> v;
int main(){
scanf("%s", s+1);
int m = strlen(s+1);
for(int i = 1; i <= m; i ++){
if(ch(s[i])) v.push_back(i);
}
int md = (v.size() + 1) / 2;
if(v.size() == 0) printf("1\n");
else if(!ch(s[1])) puts("0");
else if(v.size() == 1) printf("%d\n", m);
else printf("%d\n", v[md] - v[md-1]);
return 0;
}
C
签到题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int inf = 0x7fffffff;
int k, n;
int a[10010];
int main(){
cin >> k >> n;
int v = n % k;
if(v != k-1 && v != 0 && v != 1) return puts("*"), 0;
if(v == k-1) v = n / k + 1;
else v = n / k;
for(int i = 1, b; i <= n; i ++){
cin >> b;
a[b] ++;
}
int jian = 0, jia = 0;
for(int i = 1; i <= k; i ++){
if(a[i] <= v + 1 && a[i] >= v - 1){
if(a[i] == v - 1) {
if(jia != 0) return puts("*"), 0;
else jia = i;
}
if(a[i] == v + 1){
if(jian != 0) return puts("*"), 0;
else jian = i;
}
}else return puts("*"), 0;
}
if(jian != 0 && jia != 0){printf("-%d +%d\n", jian, jia);}
else if(jian != 0) printf("-%d\n", jian);
else if(jia != 0) printf("+%d\n", jia);
return 0;
}
E
数位dp。
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示从最高位开始，现在正在操作第
i
i
i位的数字，之前数字余数为
j
j
j时，当前位能放的最小的数字，无解保存
−
2
-2
−2。
记忆化搜索即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int inf = 0x7fffffff;
char s[1010], ss[1010];
int mi[1010], f[1010][1010];
int k;
bool dfs(int p, bool fir, int val){
if(p == 0) return val == 0 ? 1 : 0;
if(f[p][val] != -1) return f[p][val] == -2 ? 0 : 1;
if(ss[p] != '?'){
int v = ss[p] - '0';
if(dfs(p-1, 0, (val + mi[p-1] * v % k) % k)) {
f[p][val] = v;
return true;
}
}else{
for(int i = (fir == 1 ? 1 : 0); i <= 9; i ++){
if(dfs(p-1, 0, (val + mi[p-1] * i % k) % k)){
f[p][val] = i;
return true;
}
}
}
f[p][val] = -2;
return false;
}
int main(){
mi[0] = 1;
scanf("%s%d", s+1, &k);
int m = strlen(s+1);
for(int i = 1; i <= m; i ++) ss[m-i+1] = s[i];
for(int i = 1; i <= m; i ++) mi[i] = mi[i - 1] * 10 % k;
memset(f, -1, sizeof(f));
if(!dfs(m, 1, 0)) return puts("*"), 0;
int val = 0;
for(int i = 1; i <= m; i ++){
s[i] = '0' + f[m-i+1][val];
val = (val + mi[m-i] * f[m-i+1][val] % k) % k;
}
printf("%s\n", s+1);
return 0;
}
F
二维偏序问题。
对于
n
n
n个人的属性，将其中一维排序，对于排序后的数组就可以DP了。
f
[
i
]
f[i]
f[i]表示选择第
i
i
i个人时所能获取的最大价值
所以
f
[
i
]
=
m
a
x
(
f
[
j
]
)
+
d
[
i
]
f[i]=max(f[j])+d[i]
f[i]=max(f[j])+d[i]，转移时要保证第
j
j
j个人的财富和价值均要小于
i
i
i的财富和价值。
为了快速求得
m
a
x
(
f
[
j
]
)
max(f[j])
max(f[j])，我们可以用树状数组 or 线段树维护。
有两个细节需要注意：
- 对于一群财富和颜值均相同的人，他们之间不会起冲突，可以先把这群人合并成一个人；
- 由于是要在财富和价值均要小于第 i i i个人的财富和价值的人中找到那个 j j j，所以对于目前某一维相同的人，计算出dp的值的时候不能马上在数据结构中更新，这个时候需要用栈维护一下。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define LL long long
#define inl inline
#define re register
#define MAXN 101000
using namespace std;
struct per
{
LL b,f,d;
int u;
};
struct node
{
int u;
LL d;
}que[MAXN];
per r[MAXN],kk[MAXN];
int n,ind;
bool cmp1(const per &a,const per &bb){return a.b<bb.b;}
bool cmp2(const per &a,const per &bb){return a.f<bb.f;}
bool cmp3(const per &a,const per &bb)
{
if(a.f==bb.f)return a.b<bb.b;
return a.f<bb.f;
}
LL tree[MAXN];
int low(int i){return i&(-i);}
void add(int i,LL b){for(;i<=n;i+=low(i))tree[i]=max(b,tree[i]);}
LL find (int i)
{
LL ans=0;
for(;i;i-=low(i))ans=max(tree[i],ans);
return ans;
}
LL anss;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&r[i].b,&r[i].f,&r[i].d);
sort(r+1,r+n+1,cmp3);
ind=0;
for(int i=1;i<=n;i++)
{
if(r[i].b==r[i-1].b&&r[i].f==r[i-1].f)kk[ind].d+=r[i].d;
else kk[++ind]=r[i];
}
n=ind;
for(int i=1;i<=n;i++)r[i]=kk[i];
ind=0;
sort(r+1,r+n+1,cmp1);
for(int i=1;i<=n;i++)
{
if(r[i].b!=r[i-1].b)ind++;
r[i].u=ind;
}
sort(r+1,r+n+1,cmp2);
ind=0;
for(int i=1;i<=n;i++)
{
if(r[i].f!=r[i-1].f)
while(ind)add(que[ind].u,que[ind].d),ind--;
LL tmp=find(r[i].u-1)+r[i].d;
anss=max(anss,tmp);
que[++ind].d=tmp;
que[ind].u=r[i].u;
}
cout<<anss<<endl;
return 0;
}
G
设
f
[
i
]
[
0
/
1
]
[
0
/
1
]
f[i][0/1][0/1]
f[i][0/1][0/1]，第一维表示第
i
i
i个节点，第二维表示以
i
i
i为输出端的一组没有损坏的的与非门所能得到的输出，第三维表示对于目前的结构所能得到的输出。
f
[
i
]
[
0
/
1
]
[
0
/
1
]
f[i][0/1][0/1]
f[i][0/1][0/1]表示在目前状态下的方案数。
然后对于每一种类型的节点，直接转移就好了。
答案就是
f
[
1
]
[
1
]
[
0
]
+
f
[
1
]
[
0
]
[
1
]
f[1][1][0]+f[1][0][1]
f[1][1][0]+f[1][0][1]
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define LL long long
#define inl inline
#define re register
#define MAXN 101000
using namespace std;
const LL mod=1000000007;
struct edge
{
int l,r;
int k;
}h[MAXN];
int n;
LL f[MAXN][2][2];
int ind[5][2]={{},{0,1},{1,1},{1,0},{0,0}};
int dfs(int p)
{
LL dpl[2][2],dpr[2][2];
memset(dpl,0,sizeof(dpl));
memset(dpr,0,sizeof(dpr));
if(h[p].l==0)dpl[1][1]=1,dpl[0][0]=1;
else
{
dfs(h[p].l);
dpl[1][1]=f[h[p].l][1][1];
dpl[1][0]=f[h[p].l][1][0];
dpl[0][0]=f[h[p].l][0][0];
dpl[0][1]=f[h[p].l][0][1];
}
if(h[p].r==0)dpr[1][1]=1,dpr[0][0]=1;
else
{
dfs(h[p].r);
dpr[1][1]=f[h[p].r][1][1];
dpr[1][0]=f[h[p].r][1][0];
dpr[0][0]=f[h[p].r][0][0];
dpr[0][1]=f[h[p].r][0][1];
}
for(int i=1;i<=4;i++)
{
int a=ind[i][0],b=ind[i][1];
for(int j=1;j<=4;j++)
{
int c=ind[j][0],d=ind[j][1];
int t1=!(a&c),t2=!(b&d);
if(h[p].k==1)f[p][t1][1]=(f[p][t1][1]+dpl[a][b]*dpr[c][d])%mod;
if(h[p].k==-1)f[p][t1][t2]=(f[p][t1][t2]+dpl[a][b]*dpr[c][d])%mod;
if(h[p].k==0)f[p][t1][0]=(f[p][t1][0]+dpl[a][b]*dpr[c][d])%mod;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&h[i].l,&h[i].r,&h[i].k);
dfs(1);
LL ans=f[1][1][0]+f[1][0][1];
ans=(ans%mod+mod)%mod;
cout<<ans;
return 0;
}
H
签到题。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const int inf = 0x7fffffff;
int main(){
int a[10], b[10], res = 0;
for(int i = 1; i <= 3; i ++) cin >> a[i];
for(int i = 1; i <= 3; i ++) cin >> b[i];
for(int i = 1; i <= 3; i ++) res += max(0, b[i] - a[i]);
cout << res;
return 0;
}
I
题意：每次询问给一条已有的边，求包含这条边在内的最小生成树
就按照次小生成树就可以了，用倍增LCA维护路径最大值，需要注意的是询问时需要判断给定的边是不是在最小生成树里面，代码长但不难写。
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 200010;
struct edge{
int u, v, w, nxt;
}e[N], r[N];
int n, m, te, tot;
map<long long, int>mp;
int fa[N], head[N], dep[N], flag[N], lf[N][20], mf[N][20], BIT[20];
inline void add(int u, int v, int w){
e[++te] = (edge){u, v, w, head[u]};
head[u] = te;
}
inline long long ys(edge a){return 1ll * a.u * 100000 + a.v;}
inline long long ys1(edge a){return 1ll * a.v * 100000 + a.u;}
inline long long ys(int a, int b){return 1ll * a * 100000 + b;}
inline int getf(int x){return fa[x] == x ? x : fa[x] = getf(fa[x]);}
inline int cmp (const edge &a, const edge &b){return a.w < b.w;}
inline void kruskal(){
sort(r + 1, r + m + 1, cmp);
for (int i = 1; i <= m; ++i) mp[ys(r[i])] = mp[ys1(r[i])] = i;
int cnt = 0;
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int i = 1; i <= m; ++i){
int fx = getf(r[i].u), fy = getf(r[i].v);
if (fx != fy){
cnt++, tot += r[i].w;
fa[fx] = fy, flag[i] = 1;
add(r[i].u, r[i].v, r[i].w);
add(r[i].v, r[i].u, r[i].w);
if (cnt == n - 1) break;
}
}
}
inline void dfs(int x){
for (int i = 1; i <= 18; ++i){
lf[x][i] = lf[lf[x][i-1]][i-1];
mf[x][i] = max(mf[x][i-1], mf[lf[x][i-1]][i-1]);
}
for (int i = head[x]; i; i = e[i].nxt){
int v = e[i].v;
if (!lf[v][0]){
dep[v] = dep[x] + 1;
lf[v][0] = x;
mf[v][0] = e[i].w;
dfs(v);
}
}
}
inline int lca(int u, int v){
int mx = 0;
if (dep[v] < dep[u]) swap(u, v);
int tmp = dep[v] - dep[u];
for (int i = 0; i <= 18; ++i)
if (tmp & BIT[i]){
mx = max(mx, mf[v][i]);
v = lf[v][i];
}
for (int i = 18; i >= 0; --i){
if (lf[u][i] != lf[v][i]){
mx = max(mx, max(mf[u][i], mf[v][i]));
u = lf[u][i], v = lf[v][i];
}
}
if (u == v) return mx;
else return max(mx, max(mf[u][0], mf[v][0]));
}
inline int solve(int u, int v){
int tmp = mp[ys(u, v)];
if (flag[tmp]) return tot;
else return tot + r[tmp].w - lca(u, v);
}
int main(){
BIT[0] = 1;
for (int i = 1; i <= 18; ++i) BIT[i] = BIT[i-1] << 1;
dep[1] = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)scanf("%d%d%d", &r[i].u, &r[i].v, &r[i].w);
kruskal();
dfs(1);
int q, u, v;
scanf("%d", &q);
for (int i = 1; i <= q; ++i){
scanf("%d%d", &u, &v);
printf("%d\n", solve(u, v));
}
}
J
i
i
i表示起点，
k
k
k表示跳跃长度，
b
b
b表示跳跃次数，如果不考虑池塘，那么
k
k
k可行当且仅当下式有解
(
i
+
b
k
)
%
n
=
i
(i+bk)\%n=i
(i+bk)%n=i，即
b
k
%
n
=
0
bk\%n=0
bk%n=0有解。
所有有可能成为答案的数是与
n
n
n不互素的数。
-
对于一个数 d d d满足 d ∣ n d|n d∣n，此时 i i i可能的取值为 [ 0 , d ) [0,d) [0,d)，当 i i i取其他值时青蛙走过的位置，所组成的集合，必然与 i m o d d i\ mod\ d i mod d重复。所以对于每一个取值直接暴力验证即可。 n n n的因数有 n \sqrt{n} n个，对于每一个因数 d d d枚举 d d d个位置，暴力判断每一次复杂度 n / d n/d n/d；
-
对于其他可能的 d d d，假如 t = g c d ( n , d ) t=gcd(n,d) t=gcd(n,d)，那么 当 k = d 当k=d 当k=d时所走过的位置的集合一定是 k k k取 t t t的因数时走过的位置的集合的子集。所以如果当 k k k取 t t t的某一个因数时可行，那么 k = d k=d k=d时可行。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define LL long long
#define inl inline
#define re register
#define MAXN 101000
using namespace std;
char r[MAXN];
int n,g[MAXN],ind,ans;
bool vis[MAXN],key;
bool check(int i,int k)
{
int j=i;
if(r[i]=='R')
{
for(i=(i+k)%n;i!=j;i=(i+k)%n)
if(r[i]=='P')return 0;
}
else return 0;
return 1;
}
int main()
{
scanf("%s",r);n=strlen(r);
for(int i=0;i<n;i++)if(r[i]=='P')key=1;
if(!key)
{
cout<<n-1<<endl;
return 0;
}
for(int i=1;i<n;i++)if(__gcd(n,i)!=1)g[++ind]=i;
for(int i=1;i<=ind;i++)
{
if(n%g[i]==0)
{
for(int j=0;j<g[i];j++)
if(check(j,g[i])){vis[g[i]]=1;break;}
}
else
{
int t=__gcd(g[i],n);
for(int j=1;j*j<=t;j++)
if(vis[j]&&t%j==0){vis[g[i]]=1;break;}
if(vis[t])vis[g[i]]=1;
}
}
for(int i=1;i<=n;i++)if(vis[i])ans++;
cout<<ans;
return 0;
}
M
题意：给n个栈，每个栈中有不等数量的玻璃珠，玻璃珠的有权值并且和取的顺序有关，确定取玻璃珠的顺序使得总权值和最小。
因为V的范围在300以内，所以贪心是正确的，但是当有两个相通的权值是需要判断后面的权值大小，暴力最坏复杂度可以到O(n^2)，所以用后缀数组事先求一下顺序就可以了。
具体做法是把所有栈的元素连接起来，两个栈之间用301连接，跑一边后缀数组就可以了，代码长但不难写。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
const int N = 500010;
const int SN = 100010;
const int P = 1e9+7;
struct node{
long long x;
int id, rk;
int operator < (const node &t) const {
return rk > t.rk;
}
};
priority_queue <node> q;
long long mi[400010];
int ct, tot;
int sa[N], x[N], y[N], c[N], s[N], rk[N];
inline void SA(){
int n = tot;
for (int i = 1; i <= n; ++i) x[i] = s[i];
int m = 301;
for (int i = 0; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) c[x[i]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i-1];
for (int i = n; i; i--) sa[c[x[i]]--] = i;
for (int k = 1, p; k <= n; k <<= 1){
p = 0;
for (int i = n; i > n - k; i--) y[++p] = i;
for (int i = 1; i <= n; ++i)
if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 0; i <= m; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) c[x[i]]++;
for (int i = 1; i <= m; ++i) c[i] += c[i-1];
for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i];
p = y[sa[1]] = 1;
for (int i = 2, a, b; i <= n; ++i){
a = sa[i] + k > n? -1 : x[sa[i] + k];
b = sa[i-1] + k > n? -1 : x[sa[i-1] + k];
y[sa[i]] = (x[sa[i]] == x[sa[i-1]] && (a==b)? p : ++p);
}
swap(x, y);
m = p;
if (p == n)break;
}
for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
}
struct stone{
int val, pos;
}marble[N];
int st[N], ed[N];
int main(){
int n;
mi[0] = 1;
scanf("%d", &n);
for(int i = 1, k; i <= n; i ++){
st[i] = ct + 1, scanf("%d", &k);
for(int j = 1, a; j <= k; j ++){
scanf("%d", &a);
marble[++ct].val = a, s[++tot] = a;
marble[ct].pos = tot;
}
ed[i] = ct;
s[++tot] = 301;
}
SA();
for(int i = 1; i <= ct; i ++) mi[i] = mi[i-1] * 365 % P;
for(int i = 1; i <= n; i ++) {
if(st[i] <= ed[i])
q.push((node){marble[st[i]].val, i, rk[marble[st[i]++].pos]});
}
long long res = 0;
while(!q.empty()){
node xx = q.top();
q.pop();
int i = xx.id;
res = (res + xx.x * mi[ct--] % P) % P;
if(st[i] <= ed[i]) {
q.push((node){marble[st[i]].val, i, rk[marble[st[i]].pos]});
st[i]++;
}
}
printf("%lld\n", res);
return 0;
}