A - Arranging tiles
留坑。
B - Buggy ICPC
题意：给出一个字符串，然后有两条规则，如果打出一个辅音字母，直接接在原字符串后面，如果打出一个元音字母，那么接在原来的字符串后面之后再翻转整个字符串，在这两条规则之下，求有多少种打印给定字符串的方法
思路：如果第一个字符是辅音，那么答案为0
如果全是辅音或全是元音，那么答案为1
如果只有一个辅音，答案为len
否则是最中间两个元音中间的辅音字符个数+1
#include <bits/stdc++.h> using namespace std; #define N 100010 char s[N]; bool vis[]; inline void Init()
{
vis['a'] = ;
vis['e'] = ;
vis['i'] = ;
vis['o'] = ;
vis['u'] = ;
} inline int work()
{
int len = strlen(s);
if (len == ) return ;
int cnt = ;
for (int i = ; i < len; ++i) if (vis[s[i]]) cnt++;
if (cnt == || cnt == len) return ;
if (!vis[s[]]) return ;
if (cnt == ) return len;
int l = , r = len - ;
while (vis[s[r]] == ) --r;
int flag = ;
for (; true; flag ^= )
{
cnt = ;
if (flag == )
{
++l;
while (true)
{
if (l == r) return cnt + ;
if (vis[s[l]]) break;
++cnt;++l;
}
}
else
{
--r;
while (true)
{
if (l == r) return cnt + ;
if (vis[s[r]]) break;
++cnt;--r;
}
}
}
} int main()
{
Init();
while (scanf("%s", s) != EOF)
{
printf("%d\n", work());
}
return ;
}
C - Complete Naebbirac's sequence
题意：可以有三种操作， 一种是可以加上一个数，一种是可以减去一个数，一种是可以改变一个数 使得所有数出现次数相同，只能有一个操作，如果不能完成，输出"*"
思路：记录出现次数最大的数以及出现次数最小的次数，加上一个数是在(n + 1) % k == 0的时候，减去一个数是在(n - 1) % k == 0的时候，判断一下即可（水）
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + ;
const int INF = 0x3f3f3f3f; int k, n;
int arr[maxn];
int Max, Min, Mx, Mn; inline bool check()
{
for(int i = ; i <= k; ++i)
{
if(arr[i] != arr[]) return false;
}
return true;
} int main()
{
while(~scanf("%d %d", &k, &n))
{
memset(arr, , sizeof arr);
for(int i = , num; i < n; ++i)
{
scanf("%d", &num);
arr[num]++;
}
Max = -INF, Min = INF;
for(int i = ; i <= k; ++i)
{
if(arr[i] > Max)
{
Max = arr[i];
Mx = i;
}
if(arr[i] < Min)
{
Min = arr[i];
Mn = i;
}
}
if((n - ) % k == )
{
--arr[Mx];
if(check())
{
printf("-%d\n", Mx);
continue;
}
++arr[Mx];
}
if((n + ) % k == )
{
++arr[Mn];
if(check())
{
printf("+%d\n", Mn);
continue;
}
--arr[Mn];
}
++arr[Mn];
--arr[Mx];
if(check())
{
printf("-%d +%d\n", Mx, Mn);
continue;
}
printf("*\n"); }
return ;
}
D - Daunting device
留坑。
E - Enigma
题意：给出两个数，有一个数中某些位是空的，填充空的位，使得左边那个数能够整除右边的数，并且左边那个数最小
思路：记忆化搜索，枚举每一位的每一种状态，从小向大枚举保证自断续最小。记录到每个点的余数，如果访问过就不继续搜索。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 + ; bool flag[maxn][maxn];
int vis[maxn][maxn];
string str;
string ans;
int len;
int m; inline bool DFS(int idx, int res)
{
if(idx >= len)
{
return res == ;
}
if(vis[idx][res] != -) return flag[idx][res];
vis[idx][res] = ;
bool &ret = flag[idx][res];
if(str[idx] == '?')
{
for(int i = !idx; i <= ; ++i)
{
ret |= DFS(idx + , (res * + i) % m);
if(ret) return true;
}
return false;
}
else
{
ret |= DFS(idx + , (res * + (str[idx] - '')) % m);
}
return ret;
} inline void WORK(int idx,int res)
{
if(idx == len) return ;
if(str[idx] == '?')
{
for(int i = !idx; i <= ; ++i)
{
if(DFS(idx + , (res * + i) % m))
{
ans += (char)(i + '');
WORK(idx + , (res * + i) % m);
return ;
}
}
}
else
{
ans += str[idx];
WORK(idx + , (res * + str[idx] - '') % m);
return ;
}
} int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
while(cin >> str >> m)
{
memset(flag, , sizeof flag);
memset(vis, -, sizeof vis);
len = str.length();
if(DFS(, ))
{
ans.clear();
WORK(, );
cout << ans << "\n";
}
else
{
cout << "*\n";
}
}
return ;
}
F - Fundraising
题意：每个人有两个值，以及一个权值，若两个人都能选出来，那么要么两个人的值都相同，或者某个人的两个值分别大于另一个人，求选出一些人使得权值和最大
思路：两个值都相同的先合并，然后按一维排序，另一维做最大上升子序列权值和
#include <bits/stdc++.h> using namespace std; #define N 100010
#define ll long long
typedef pair <int, int> pii; struct node
{
int x, y; ll D;
inline node() {}
inline node(int x, int y, ll D) : x(x), y(y), D(D) {}
inline bool operator < (const node &r) const
{
return x < r.x || x == r.x && y > r.y;
}
}arr[N]; map <pii, int> mp;
int n, m, cnt;
ll brr[N], a[N]; inline int Get(pii x)
{
if (mp.find(x) == mp.end())
{
mp[x] = ++cnt;
brr[cnt] = x.second;
arr[cnt] = node(x.first, x.second, );
}
return mp[x];
} inline void Init()
{
memset(a, , sizeof a);
sort(brr + , brr + + cnt);
m = unique(brr + , brr + + cnt) - brr - ;
} inline int lowbit(int x)
{
return x & (-x);
} inline void update(int x, ll val)
{
for (int i = x; i <= m; i += lowbit(i))
a[i] = max(a[i], val);
} inline ll query(int x)
{
ll res = ;
for (int i = x; i > ; i -= lowbit(i))
res = max(res, a[i]);
return res;
} int main()
{
while (scanf("%d", &n) != EOF)
{
mp.clear(); cnt = ;
int x, y; ll D;
for (int i = ; i <= n; ++i)
{
scanf("%d%d%lld", &x, &y, &D);
int pos = Get(pii(x, y));
arr[pos].D += D;
}
Init();
for (int i = ; i <= cnt; ++i) arr[i].y = lower_bound(brr + , brr + + m, arr[i].y) - brr;
sort(arr + , arr + + cnt);
for (int i = ; i <= cnt; ++i)
{
ll v = query(arr[i].y - );
update(arr[i].y, v + arr[i].D);
}
printf("%lld\n", query(m));
}
return ;
}
G - Gates of uncertainty
留坑。
H - Hard choice
水。
#include <bits/stdc++.h> using namespace std; int a[], b[]; int main()
{
while (scanf("%d%d%d", &a[], &a[], &a[]) != EOF)
{
for (int i = ; i < ; ++i) scanf("%d", b + i);
int ans = ;
for (int i = ; i < ; ++i) ans += max(, b[i] - a[i]);
printf("%d\n", ans);
}
return ;
}
I - Imperial roads
题意：给出一张图，然后询问给出一条边，求有这条边的最小生成树的权值和
思路：先求最小生成树，然后询问的边如果在最小生成树里面那么就是原来的权值和，否则在原来的最小生成树里面的加入一条边，形成个环，然后去掉这个环里面除了加入的边之外的边权最大的边
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + ;
const int DEG = ; typedef long long ll; int n, m; struct node{
int u, v;
ll w;
inline node(){}
inline node(int u, int v, ll w) :u(u), v(v), w(w){}
inline bool operator < (const node &b)const
{
return w < b.w;
}
}; struct Edge{
int to;
int nxt;
ll w;
inline Edge(){}
inline Edge(int to, int nxt, ll w) :to(to), nxt(nxt), w(w){}
}edge[maxn << ]; int dis[maxn][DEG];
bool inMST[maxn << ];
int head[maxn];
int tot;
int father[maxn];
vector<node>G;
int cnt;
map<pair<int,int>, int>mp; inline void addedge(int u,int v, ll w)
{
edge[tot] = Edge(v, head[u], w);
head[u] = tot++;
} inline void Init()
{
G.clear();
cnt = ;
tot = ;
memset(dis, , sizeof dis);
memset(head, -, sizeof head);
for(int i = ; i <= n; ++i)
{
father[i] = i;
}
} inline int find(int x)
{
return x == father[x] ? father[x] : father[x] = find(father[x]);
} inline void mix(int x,int y)
{
x = find(x);
y = find(y);
if(x != y)
{
father[x] = y;
}
} inline bool same(int x,int y)
{
return find(x) == find(y);
} inline ll MST()
{
mp.clear();
ll res = ;
sort(G.begin(), G.end());
memset(inMST, false, sizeof inMST);
for(auto it : G)
{
int u = it.u;
int v = it.v;
mp[make_pair(v, u)] = cnt;
mp[make_pair(u, v)] = cnt++;
}
for(auto it : G)
{
int u = it.u;
int v = it.v;
if(same(u, v)) continue;
mix(u, v);
inMST[mp[make_pair(u, v)]] = true;
addedge(u, v, it.w);
addedge(v, u, it.w);
res += it.w;
}
return res;
} int fa[maxn][DEG];
int deg[maxn]; inline void BFS(int root)
{
queue<int>q;
deg[root] = ;
fa[root][] = root;
q.push(root);
while(!q.empty())
{
int tmp = q.front();
q.pop();
for(int i = ; i < DEG; ++i)
{
dis[tmp][i] = max(dis[tmp][i - ], dis[fa[tmp][i - ]][i - ]);
fa[tmp][i] = fa[fa[tmp][i - ]][i - ];
}
for(int i = head[tmp]; ~i; i = edge[i].nxt)
{
int v = edge[i].to;
if(v == fa[tmp][]) continue;
deg[v] = deg[tmp] + ;
fa[v][] = tmp;
int id = mp[make_pair(tmp, v)];
dis[v][] = G[id].w;
q.push(v);
}
}
} inline int LCA(int u,int v)
{
int res = ;
if(deg[u] > deg[v])
swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for(int det = hv - hu, i = ; det; det >>= , ++i)
{
if(det & )
{
res = max(res, dis[tv][i]);
tv = fa[tv][i];
}
}
if(tu == tv) return res;
for(int i = DEG - ; i >= ; --i)
{
if(fa[tu][i] == fa[tv][i]) continue;
res = max(res, max(dis[tu][i], dis[tv][i]));
tu = fa[tu][i];
tv = fa[tv][i];
}
res = max(res, max(dis[tu][], dis[tv][]));
return res;
} int main()
{
while(~scanf("%d %d", &n , &m))
{
Init();
for(int i = ; i <= m; ++i)
{
int u, v;
ll w;
scanf("%d %d %lld", &u, &v, &w);
G.push_back(node(u, v, w));
}
ll ans = MST();
BFS();
int q;
scanf("%d", &q);
while(q--)
{
int u, v;
scanf("%d %d", &u, &v);
int id = mp[make_pair(u, v)];
ll w = G[id].w;
if(inMST[id])
{
printf("%lld\n", ans);
}
else
{
ll res = LCA(u, v);
printf("%lld\n", ans + w - res);
}
}
}
return ;
}
#include <bits/stdc++.h>
using namespace std; #define N 100010
#define M N * 30
typedef pair <int, int> pii; struct Edge1
{
int u, v, w;
inline Edge1() {}
inline Edge1(int u, int v, int w) : u(u), v(v), w(w) {}
inline bool operator < (const Edge1 &r) const
{
return w < r.w;
}
}; struct Edge2
{
int to, nx, w;
inline Edge2() {}
inline Edge2(int to, int nx, int w) : to(to), nx(nx), w(w) {}
}edge[N << ]; vector <Edge1> vec;
map <pii, bool> mp;
map <pii, int> MP;
int n, m, q;
int pre[N];
int head[N], pos;
int MST;
int rmq[N << ], F[N << ], P[N], cnt;
int T[N], L[M], R[M], C[M], tot; struct ST
{
int mm[N << ];
int dp[N << ][];
inline void init(int n)
{
mm[] = -;
for (int i = ; i <= n; ++i)
{
mm[i] = ((i & (i - )) == ) ? mm[i - ] + : mm[i - ];
dp[i][] = i;
}
for (int j = ; j <= mm[n]; ++j)
{
for (int i = ; i + ( << j) - <= n; ++i)
{
dp[i][j] = rmq[dp[i][j - ]] < rmq[dp[i + ( << (j - ))][j - ]] ? dp[i][j - ] : dp[i + ( << (j - ))][j - ];
}
}
}
inline int query(int a, int b)
{
if (a > b) swap(a, b);
int k = mm[b - a + ];
return rmq[dp[a][k]] <= rmq[dp[b - ( << k) + ][k]] ? dp[a][k] : dp[b - ( << k) + ][k];
}
}st; inline void Init()
{
for (int i = ; i <= n; ++i) pre[i] = i;
memset(head, -, sizeof head);
vec.clear(); mp.clear(); MP.clear();
MST = ; tot = , cnt = , pos = ;
} inline void addedge(int u, int v, int w)
{
edge[++pos] = Edge2(v, head[u], w); head[u] = pos;
} inline int find(int x)
{
if (pre[x] != x)
pre[x] = find(pre[x]);
return pre[x];
} inline void join(int x, int y)
{
int fx = find(x), fy = find(y);
if (fx != fy)
pre[fx] = fy;
} inline void Kruskal()
{
sort(vec.begin(), vec.end());
int cnt = ;
for (auto it : vec)
{
int u = it.u, v = it.v, w = it.w;
if (find(u) == find(v)) continue;
++cnt; join(u, v); MST += w;
mp[pii(u, v)] = mp[pii(v, u)] = ;
addedge(u, v, w); addedge(v, u, w);
if (cnt == n) break;
}
} inline int build(int l, int r)
{
int root = tot++;
C[root] = ;
if (l < r)
{
int mid = (l + r) >> ;
L[root] = build(l, mid);
R[root] = build(mid + , r);
}
return root;
} inline int update(int root, int pos)
{
int newroot = tot++, tmp = newroot;
C[newroot] = C[root] + ;
int l = , r = ;
while (l < r)
{
int mid = (l + r) >> ;
if (pos <= mid)
{
L[newroot] = tot++, R[newroot] = R[root];
newroot = L[newroot], root = L[root];
r = mid;
}
else
{
L[newroot] = L[root], R[newroot] = tot++;
newroot = R[newroot], root = R[root];
l = mid + ;
}
C[newroot] = C[root] + ;
}
return tmp;
} inline int query(int left_root, int right_root)
{
int l = , r = ;
while (l < r)
{
int mid = (l + r) >> ;
int tot = C[R[left_root]] - C[R[right_root]];
if (tot > )
{
left_root = R[left_root];
right_root = R[right_root];
l = mid + ;
}
else
{
left_root = L[left_root];
right_root = L[right_root];
r = mid;
}
}
return l;
} inline void DFS(int u, int pre, int dep)
{
F[++cnt] = u;
rmq[cnt] = dep;
P[u] = cnt;
for (int it = head[u]; ~it; it = edge[it].nx)
{
int v = edge[it].to;
if (v == pre) continue;
int w = edge[it].w;
T[v] = update(T[u], w);
DFS(v, u, dep + );
F[++cnt] = u;
rmq[cnt] = dep;
}
} inline void LCA_init(int root, int node_num)
{
T[] = build(, );
DFS(root, root, );
st.init( * node_num - );
} inline int query_lca(int u, int v)
{
return F[st.query(P[u], P[v])];
} inline void Run()
{
while (scanf("%d%d", &n, &m) != EOF)
{
Init();
for (int i = , u, v, w; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
vec.emplace_back(u, v, w);
MP[pii(u, v)] = MP[pii(v, u)] = w;
}
Kruskal(); LCA_init(, n);
scanf("%d", &q);
for (int i = , u, v; i <= q; ++i)
{
scanf("%d%d", &u, &v);
if (mp[pii(u, v)]) printf("%d\n", MST);
else
{
int lca = query_lca(u, v);
int Max = query(T[u], T[lca]);
Max = max(Max, query(T[v], T[lca]));
//printf("%d %d %d %d\n", u, v, lca, Max);
printf("%d\n", MST + MP[pii(u, v)] - Max);
}
}
}
} int main()
{
#ifdef LOCAL
freopen("Test.in", "r", stdin);
#endif Run();
return ;
}
J - Jumping frog
题意：给出一个字符串，是一个圆圈，'R' 代码岩石 'P' 代表池塘 有一只青蛙，随便从哪一个岩石出发，固定步数k，若能回到原来的位置，那么这个步数就是ok的，求有多少个步数是ok的
思路：如果一个步数k可以完成，那么前提为gcd(n, k)可行（可通过反证法证明）。枚举n的每个因子跑一边即可。
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 +; bool flag[maxn];
char str[maxn]; inline int gcd(int a, int b)
{
return b == ? a : gcd(b, a % b);
} int main()
{
while(~scanf("%s", str))
{
memset(flag, false, sizeof flag);
int n = strlen(str);
for(int i = ; i < n; ++i)
{
if(n % i != ) continue;
for(int j = ; j < i; ++j)
{
bool tmp = true;
for(int k = ; k <= n / i; ++k)
{
if(str[(j + k * i) % n] == 'P')
{
tmp = false;
break;
}
}
if(tmp)
{
flag[i] = true;
break;
}
}
}
int ans = ;
for(int i = ; i < n; ++i)
{
if(flag[gcd(i, n)]) ans++;
}
printf("%d\n", ans);
}
return ;
}
K - Keep it covered
留坑。
L - Linearville
留坑。
M - Marblecoin
留坑。